Set Properties

Given sets A, B, and C, and a universal set U, the following properties hold:

A  B = B  A A  B = B  A	Commutative property
A  (B  C) = (A  B)  C A  (B  C) = (A  B)  C)	Associative property
A  (B  C) = (A  B)  (A  C) A  (B  C) = (A  B)  (A  C)	Distributive properties
A = A   = A U  A = A  U = A	Identity properties
A  Ac = U A  Ac  =	Union and Intersection with Complement
A  U = U A  U = A	Union and Intersection with U
(Ac)c = A	Double Complement Law
A  A  = A A  A  = A	Idempotent Laws
A  (A  B) = A A  (A  B) = A	Absorption properties
A - B = A  Bc	Alternate Set Difference Representation
A  A  B B  A  B	Inclusion in Union
A  B  A A  B  B	Inclusion in Intersection
if A  B, and B  C, then  A  C	Transitive Property of Subsets

Set Definitions

Given a universal set U, let A and B be subsets of U, and x and y be elements of U. Then,

• x  A  B  x  A or x  B
  
  
• x  A  B  x  A and x  B
  
  
• x  A - B  x  A and x  B
  
  
• x  A^c x  A
  
  
• (x, y)  A x B (the cross product) x  A and y  B

Practice Exercises

Set Equality

Given sets X and Y, the two sets are equal (X = Y) iff every element of X is in Y, and every element of Y is in X.  

Drawing from the earlier definition of subsets, set equality can be represented symbolically as follows:

The Empty Set

Earlier, we touched on the concept of an "empty set", a set with no elements.  Just as it is possible and even necessary to use '0' in mathematics, or to speak of 'nothing' or 'nobody' in daily conversation, so is the concept of an empty set necessary to set theory.

The following theorem and corollary deal with properties of the empty set.

Theorem:  The Empty Set is a subset of every other set.

Let A be any set, and let   be the set with no elements.  Then     A.

Proof (by contradiction):

Suppose that there exists a set A, and a set with no elements, ,  and further suppose that   A.   By our earlier definition of  'not a subset of ',  this means there must be an element of  that is not an element of A. This is a contradiction, since  has no elements.  Therefore, the theorem is true.

Corollary:  There is only one empty set. (The empty set is unique.)

Proof:

Let ₁ and ₂ be sets with no elements. Then, by the above theorem, ₁ is a subset of ₂, and ₂ is a subset of ₁.  So, by the earlier definition of set equality, ₁ and ₂ are equal.

Set Partitions and Power Sets

Disjoint Sets

Two sets which have no elements in common are called disjoint, defined symbolically as follows:

Mutually Disjoint Sets

Let A = {1, 2, 3, 4, 5, 6, 7, 8, 9}.  Suppose that A is divided into the following:

A₁ = {1, 2, 3},

A₂ = {4, 5, 6}, and

A₃ = {7, 8, 9}.

The collection of these subsets, {A₁, A₂, A₃}, is a partition of set A, and A is a union of mutually disjoint subsets.  The sets A₁, A₂, A₃, . . ., A_n are said to be mutually disjoint iff, for all i, j = 1, 2, 3, ..., n,

Power Sets

Let X = {a, b, c}. The power set of X, denoted P(X), is the set consisting of all subsets of X. For this example, P(X) = {, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.

Power sets have the following 2 properties:

For all sets X and Y, if XY, then P(X) P(Y).

If a set X has n elements, then P(X) has 2ⁿ elements.

Practice Exercises

Boolean Algebras

Boolean algebra is a particular algebraic method used to determine the truth or falsity of statements. It uses 2 operators, generally denoted as + (addition) and x (multiplication), and given a set S with elements a and b, both a + b and a x b are in S. The operations performed by   and  upon statement forms, and the set theory operations performed by  and   are specialized forms of Boolean algebras. The similarities can be seen in the following table.

Boolean Algebra	Statement Algebra	Set Theory	English Equivalent
+			"or"
x			"and"
0	F		"false"
1	T		"true"
a'	~a	ac	"not a"

 

Likewise, similarities can be seen in the properties of statement algebra, set theory properties and Boolean algebra.  Given a set S, with elements a, b and c, the following axioms are true: