Set Algebra: A Quick Reference Guide

[The following set-algebra laws are “borrowed”, in the great tradition of the internet, from Wikipedia.  If you would like more background on why these things work, the article goes into more detail, and of course has the complete lattice of links to accompany it.]

I have a god-awful memory.  So, I’m constantly struggling to find some basic property of sets whenever I’m trying to prove something that I KNOW would be easy, if I could just remember the damned law.  Well, after scouring the net, Wikipedia’s version turned out to be best … but I don’t need all the exposition, just the laws spelled out, easy to see.

Like to here it, here it go:

PROPOSITION 1: For any sets A, B, and C, the following identities hold:

commutative laws:

  • A cup B = B cup A,!
  • A cap B = B cap A,!
associative laws:

  • (A cup B) cup C = A cup (B cup C),!
  • (A cap B) cap C = A cap (B cap C),!
distributive laws:

  • A cup (B cap C) = (A cup B) cap (A cup C),!
  • A cap (B cup C) = (A cap B) cup (A cap C),!

PROPOSITION 2: For any subset A of universal set U, the following identities hold:

identity laws:
  • A cup varnothing = A,!
  • A cap U = A,!
complement laws:

  • A cup A^C = U,!
  • A cap A^C = varnothing,!

PROPOSITION 3: For any subsets A and B of a universal set U, the following identities hold:

idempotent laws:

  • A cup A = A,!
  • A cap A = A,!
domination laws:

  • A cup U = U,!
  • A cap varnothing = varnothing,!
absorption laws:

  • A cup (A cap B) = A,!
  • A cap (A cup B) = A,!

PROPOSITION 4: Let A and B be subsets of a universe U, then:

De Morgan’s laws:

  • (A cup B)^C = A^C cap B^C,!
  • (A cap B)^C = A^C cup B^C,!
double complement or Involution law:

  • A^{CC} = A,!
complement laws for the universal set and the empty set:

  • varnothing^C = U
  • U^C = varnothing

PROPOSITION 5: Let A and B be subsets of a universe U, then:

uniqueness of complements:

  • If A cup B = U,!, and A cap B = varnothing,!, then B = A^C,!

PROPOSITION 6: If A, B and C are sets then the following hold:

reflexivity:

  • A subseteq A,!
antisymmetry:

  • A subseteq B,! and B subseteq A,! if and only if A = B,!
transitivity:

  • If A subseteq B,! and B subseteq C,!, then A subseteq C,!

PROPOSITION 7: If A, B and C are subsets of a set S then the following hold:

existence of a least element and a greatest element:

  • varnothing subseteq A subseteq S,!
existence of joins:

  • A subseteq A cup B,!
  • If A subseteq C,! and B subseteq C,!, then A cup B subseteq C,!
existence of meets:

  • A cap B subseteq A,!
  • If C subseteq A,! and C subseteq B,!, then C subseteq A cap B,!

PROPOSITION 8: For any two sets A and B, the following are equivalent:

  • A subseteq B,!
  • A cap B = A,!
  • A cup B = B,!
  • A setminus B = varnothing
  • B^C subseteq A^C

PROPOSITION 9: For any universe U and subsets A, B, and C of U, the following identities hold:

  • C setminus (A cap B) = (C setminus A) cup (C setminus B),!
  • C setminus (A cup B) = (C setminus A) cap (C setminus B),!
  • C setminus (B setminus A) = (A cap C)cup(C setminus B),!
  • (B setminus A) cap C = (B cap C) setminus A = B cap (C setminus A),!
  • (B setminus A) cup C = (B cup C) setminus (A setminus C),!
  • A setminus A = varnothing,!
  • varnothing setminus A = varnothing,!
  • A setminus varnothing = A,!
  • B setminus A = A^C cap B,!
  • (B setminus A)^C = A cup B^C,!
  • U setminus A = A^C,!
  • A setminus U = varnothing,!
Advertisements

5 Responses

  1. I THANK THIS WEBSITES BECAUSE IT HELP ME THROUGH MY ASSIGMENT IN MATHEMATICS, I WISH IF YOU ALWAYS KEEP THIS SITES UP TO DATE ,LETS SPREAD THE KNOWLEDGE TO THE WHOLE WORLD. FROM TSHILONGAMULENZHE HUMBULANI RONALD SOUTH AFRICA

  2. I think the information and the data is well presented. Very clear understanding logic. Well done

  3. hey~ just wondering… do you think you could explain to me regarding simplifying set algebra? thank you.

  4. Show various ways to prove the theorems/propositions.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: