Set Theory

Set Theory Definitions

~#{Sets} and ~#{elements} will remain primitive undefined notions. Sets #~{contain} elements, write _ ~x &in. ~A _ for '~x is an element of ~A'. _ We write _ ~A = \{ ~x \} _ for _ '~A is the set of its elements'.

For completeness define &empty. the #~{empty set}, i.e. the set that has no elements.

Subsets

A set ~Y is said to be a #~{subset} of a set ~X: _ _ ~Y &subset. ~X _ if _ ~x &in. ~Y => ~x &in. ~X.
Obviously if _ ~X &subset. ~Y _ and ~Y &subset. ~X _ then ~X = ~Y.

Write _ @P(~X) _ for the #~{power set} of ~X, the set of all subsets of ~X;
We have: _ &empty. &in. @P(~X) , _ ~X &in. @P(~X)

• #~{intersection} _ _ ~X &intersect. ~Y _ = _ \{ ~x | ~x &in. ~X _ and _ ~x &in. ~Y \}
• #~{union} _ _ ~X &union. ~Y _ = _ \{ ~x | ~x &in. ~X _ or _ ~x &in. ~Y \}
• #~{difference} _ _ ~X &diff. ~Y _ = _ \{ ~x | ~x &in. ~X _ but _ ~x &nin. ~Y \}
• #~{symmetric difference} _ _ ~X &triangle. ~Y _ = _ ( ~X &union. ~Y ) &diff. ( ~X &intersect. ~Y )

Clearly _ _ ~X &intersect. ~Y _ = _ ~Y &intersect. ~X , _ _ ~X &union. ~Y _ = _ ~Y &union. ~X , _ and _ _ ~X &triangle. ~Y _ = _ ~Y &triangle. ~X , _ but in general _ _ ~X &diff. ~Y _ != _ ~Y &diff. ~X

Elementary Set Theory

These results follow directly from the definitions:

1. ~X &union. ~X _ = _ ~X , _ _ ~X &intersect. ~X _ = _ ~X
2. ~X &union. &empty. _ = _ ~X , _ _ ~X &intersect. &empty. _ = _ &empty.
3. ~X &diff. ~X _ = _ &empty.
   _
4. ~X &union. ( ~Y &union. ~Z ) _ = _ ( ~X &union. ~Y ) &union. ~Z
5. ~X &intersect. ( ~Y &intersect. ~Z ) _ = _ ( ~X &intersect. ~Y ) &intersect. ~Z
   _
6. ~X &intersect. ( ~Y &union. ~Z ) _ = _ ( ~X &intersect. ~Y ) &union. ( ~X &intersect. ~Z )
7. ~X &union. ( ~Y &intersect. ~Z ) _ = _ ( ~X &union. ~Y ) &intersect. ( ~X &union. ~Z )

If _ ~X &subset. ~Y _ then the following results hold:

8. ~X &intersect. ~Z &subset. ~Y &intersect. ~Z , _ _ ~X &union. ~Z &subset. ~Y &union. ~Z
9. ~X &diff. ~Z &subset. ~Y &diff. ~Z , _ _ ~X &triangle. ~Z &subset. ~Y &triangle. ~Z

Absorption Rules

10. ~X &subset. ~X &union. ~Y , _ _ ~Y &subset. ~X &union. ~Y
11. ~X &intersect. ~Y &subset. ~X , _ _ ~X &intersect. ~Y &subset. ~Y
12. ~X &diff. ~Y &subset. ~X
13. ~Y &intersect. ( ~X &diff. ~Y ) = &empty.
14. ~Y &union. ( ~X &diff. ~Y ) = ~X &union. ~Y
15. ~Y &intersect. ( ~X &diff. ~Y ) = ~X &intersect. ~Y

Subsets: Equivalent Definitions

The following are equivalent

1. ~X &subset. ~Y
2. ~X &intersect. ~Y _ = _ ~X
3. ~X &union. ~Y _ = _ ~Y
4. ~X &diff. ~Y _ = _ &empty.

a => b : _ _ ~X &intersect. ~Y &subset. ~X _ (xi) _ ~X &subset. ~Y _ => _ ~X &intersect. ~X &subset. ~Y &intersect. ~X _ (viii) _ => _ ~X &subset. ~Y &intersect. ~X , _ so _ ~X = ~X &intersect. ~Y

b => c : _ _ ~X &union. ~Y _ = _ ( ~X &intersect. ~Y ) &union. ~Y _ = _ ( ~X &union. ~Y ) &intersect. ( ~Y &union. ~Y ) _ (vii) _ = _ ( ~X &union. ~Y ) &intersect. ~Y _ (i) _ = _ ~Y
[ since ~Y &subset. ( ~X &union. ~Y ) and result follows from a => b ]

c => d : _ _ ~Y _ = _ ~X &union. ~Y _ = _ ~Y &union. ( ~X &diff. ~Y ) _ (xiv) _ => _ ( ~X &diff. ~Y ) _ = _ &empty.

d => a : _ _ ~X &diff. ~Y _ = _ &empty. _ => _ there does not exist ~x such that _ ~x &in. ~X _ but _ ~x &nin. ~Y . _ I.e. _ ~x &in. ~X _ => _ ~x &in. ~Y _ => _ ~X &subset. ~Y

Cartesian Product

The #~{cartesian product} of two sets ~X and ~Y is the set of all ordered pairs of elements from ~X and ~Y respectively:

~X # ~Y _ = _ \{ ( ~x , ~y ) | ~x &in. ~X _ and ~y &in. ~Y \}

Given a family _ \{ ~X_~i \}_{~i = 1 ... ~n} _ of sets, define their cartesian product:

prod{~X_~i, ~i = 1, ~n} _ = _ \{ ( ~x_1, ... , ~x_~n ) | ~x_~i &in. ~X_~i \}

Note: _ _ ~X # ~Y _ != _ ~Y # ~X _ _ unless _ ~X = ~Y.

Identify ( ~X # ~Y ) # ~Z _ with _ ~X # ~Y # ~Z , _ _ i.e. ( ( ~x , ~y ) , ~z ) _ = _ ( ~x , ~y , ~z ) , _ ~x &in. ~X , _ ~y &in. ~Y , _ ~z &in. ~Z ,

Complement

Given a collection ~A_~i of sets (where _ ~i &in. ~I _ - some index set), then the #~{universal set} ~U is the set such that ~A_~i &subset. _ ~U _ &forall. ~i &in. ~I.

The #~{complement} of ~A ( in ~U ), _ ~A^c _ = _ ~U &diff. ~A _ = _ \{ ~x | ~x &nin. ~A \}.

Duality Results

• ~U ^c _ = _ &empty.
• &empty.^c _ = _ ~U
• ( ~A^c )^c _ = _ ~A
• ( ~A &union. ~B )^c _ = _ ~A^c &intersect. ~B^c
• ( ~A &intersect. ~B )^c _ = _ ~A^c &union. ~B^c

Partition

A collection \{ ~X_~i \} of subsets of a set ~A is a #~{partition} of ~A if _ ~A = &union._~i ~X_~i , _ and the ~X_~i are mutually exclusive, _ ~X_~i &intersect. ~X_~j = &empty. , _ ~i != ~j.

---