ZF

My current commuting lecture series is about life in the Medieval Ages and like a Connecticut Yankee in King Author's Court I thought about how I would explain my job (computer programming) to someone Medieval. Instead of describing computers I decided I would call myself a philosopher of algorithms, or meta-thinking about how we think and prove things. This was the core of my university graduate training which then led me to realize how much I've forgotten.

It turns out in mathematics that foundations are really important and the simple concepts we take for granted are not so simple after all. Consider this story, There is a town where the barber shaves every man who does not shave himself. The barber is male. Who shaves the barber?  Think about it....

Mathematically this is equivalent to the set Z which includes all sets that don't include themselves.  Is Z in Z?
Suppose yes. Then by definition Z is not is Z.  Suppose no. Then by definition Z is in Z. Either way you get a contradiction so Z is impossible.

Suppose you argue that it's silly for a set to include itself and ban all such sets. This does not prevent Z described above, the set of all "legal" sets which don't contain themselves. Logicians realized that the problem was with the definition of "set". Just what is a set?

In 1908 Ernst Zermelo proposed a set of rules for defining legal sets. It was revised in 1922 by Abraham Fraenkel. Today we call this the Zermelo-Fraenkel axiomatic set theory or ZF for short.

0 Axiom of Existence. The empty collection is a set.
Optional. Some like this rule, some feel it is not necessary or assumed.

1. Axiom of Extensionality.  Two sets are equal if they have the same elements
Well, duh!

2. Axiom of Regularity or Foundation. For every non-empty set X, there is a member y such that X and y have NO elements in common.
This one sounds weird but it prevents sets from containing themselves. Let A be set. Consider {A} the set containing A. Since A is non-empty and only has one element, by rule 2 {A} and A must be "disjoint" meaning no elements in common. Since A is in {A}, disjoint means A is not in A.

3. Axiom of Regularity  If B is a set and f is a property on elements of B then the collection of elements x of B such that f(x) is true is a set.
Note that this new set is equal to or a subset of B and the role of B as a boundary is vital. The collection of all x such that f(x) is true with no boundary on x need not be a set like Z defined above.

4. Axiom of Pairing  if X and Y are sets then there exists a set containing X and Y
In other words, if X, Y are sets, then so is {X,Y}

5. Axiom of Union.  Let F be a set containing sets. Then there exists a set A that contains all the elements from each set of F.   If F is {B,C} then A = B  U  C with U as the Union symbol

6. Axiom of schema replacement. Given set B and f a function on B. Let Y equal all y such that y = f(x) where x in B. Then Y is a set.
Basically this says a set is not dependent on the symbols or values used. If we map symbols in set B to unique symbols in Y then Y is as set.

7. Axiom of Infinity. Define S(X) =  X U {X} for sets X.  Then there exists a set N such that the empty set is in N and for all Y in N, S(Y) is also in N.
What this means is that the collection of integers is a set. Take the empty set to be zero and define X+1 as S(X). Then N represents the integers 0, 1, 2, ....

8. Axiom of the Power Set. For any set X there is a set Y which contains ALL the subsets of X.
This is an important rule for making bigger sets. If  X = {1,2,3} then the power set of X, the set of all subsets = { {},  {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3} }

Clear as mud? No wonder I did not remember all this from college.