Set theory has many applications in Computer Science and Mathematics. Amazingly Set Theory, Boolean Algebra (a type of algebra where all values are 0 or 1), Symbolic Logic and Elementary Circuit Design are all very closely related. In fact, in many respects, they are equivalent.

There are three basic methods of proving set theory theorems in this class.

1. Proofs using basic set lemmas, definitions and equivalences.
2. Proofs using set builder notation and symbolic logic and
3. "Element chasing" proofs.

The above are not mutually exclusive. A proof in any one category may borrow elements from the other two. You may find that the third, dubbed "element chasing" will often be the easiest to employ.

A fourth method of proof is called Membership Tables.

Venn Diagrams are quite useful for understanding relationships between sets and discovering whether certain statements are likely to be true or false. They are also useful in discovering counterexamples. However, their use does not constitute proof of a statement.

The following basic and important concepts are covered in the text.

1. Equality of 2 sets, A and B

A = B if and only if x Î A Û x Î B

 

2. A is a subset of B

A Í B if and only if x Î A Þ x Î B

 

3. A is a proper subset of B (A Ì B) if and only if A Í B /\ A ¹ B (page 41)

 

4. The null set, Æ , is the set containing no elements (page 40)

 

5. The universal set, U, consists of all of the objects (elements) under consideration.

 

6. Cardinality

The cardinality of a set S, written |S|, is the number of elements in S.

 

7. The Power Set

The Power Set of a set, S, is the set of all subsets of S. The power set of S is denoted P(S).

Note: |P(S)| = 2^N where N = |S|

 

8. Cartesian Product of two sets.