next up previous
Next: April 5, 2000 Up: Lecture Notes Previous: April 3, 2000

April 4, 2000

I'm going to start by recapitulating the formal content of yesterday's
lecture (which included an intuitive and motivational component which
may have been hard to sort out).  I will also correct an omission in the
statement of axiom 5.

We introduce the notation x E y for ``x is an element of y''.

We define (Ax E y.Px) as (Ax.(x E y -> Px)).  We define (Ex E y.Px) as
(Ex.(x E y & Px)).  In both of these notations, y should not appear free in
Px.

We refer to general elements of our universe as ``classes'' (``sets''
will be reserved for a specific kind of class).  We adopt the 

Axiom of Extensionality:  (Axy.(x = y <-> (Az.z E x <-> z E y)))

In words, ``Classes are equal iff they have the same elements''.  A
consequence of the way that we have phrased this axiom is that everything
in our world is a class.

We define {x : Px} as the class A such that (Ay.(y E A <-> Py)).  If there
is no such class, we say ``{x : Px} does not exist''.

We proved the following theorem:

Russell's Paradox:  {x : ~(x E x)} does not exist.

So it is necessary to restrict what properties can be used to define
sets.  We propose some axioms for this purpose.

First, we introduce a new predicate Set(x), read ``x is a set''.

Axiom 2 (Class Existence):  For any property P, {x : Set(x) & Px} exists.

Less technically, the collection of sets defined by any property exists
(but is not necessarily a set).

We considered the following 

Example: {x : Set(x) & ~(x E x)} exists by Axiom 2.  This is the class
of all sets which are not members of themselves.  Call it R for short.
We see that R E R <-> Set(R) & ~(R E R).  This shows that Set(R) is
impossible; this class is not a set.

Axiom 3 (Elements):  (Set(x) & y E x) -> Set(y)

In words, any element of a set is a set.

Definition:  x c= y is defined as (Az.(z E x -> z E y))

We read x c= y as ``x is a subclass of y'' or as ``x is a subset of y'' when
x is a set.

Axiom 4 (Subsets):  (Set(x) & y c= x) -> Set(y)

In words, any subclass of a set is a set.

Axiom 5 (Set Existence):  {x : Px} exists and is a set if the following
conditions hold:  

1. Px does not mention the Set predicate, and 

2. any free variable or constant other than x mentioned in Px
   represents a set (this was omitted yesterday)

3. (Ax.Px -> Set(x)); i.e., anything with property P is a set.

Notice that this is not an iff:  it is possible for {x : Px} to exist
and be a set for some other conditions Px.

Axiom 5 is rather tricky; the best way to see how it works is to use it.

Positive Results (axioms of standard set theory):

Theorem 1:  {}, the empty class, is a set.

   The formula ``x =/= x'' satisfies conditions 1-3.  The trickiest part
   here is that all elements of the empty class are sets -- this is true
   vacuously.

Theorem 2:  {A}, the singleton of A, is a set if A is a set.

   The formula ``x E A'' satisfies conditions 1-3 as long as the free variable
   A represents a set.

Theorem 3:  A U B, the union of A and B, is a set if A and B are sets.

   The formula ``x E A | x E B'' satisfies conditions 1-2 as long
   as A and B are sets.  We see that ((x E A | x E B) -> Set(x)) by
   axiom 3 (elements of sets are sets).

Corollary:  sets defined by ``listing'' exist.  For example, {A , B, C} =
{A} U {B} U {C} is a set if A, B, and C are sets.

Theorem 4:  {x E A : Px}, the set of x in A such that Px, is a set for
_any_ property P if A is a set.

   We define {x E A : Px} as {x : x E A & Px}.  If x E A, we have Set(x)
   by axiom 3.  Thus {x : x E A & Px} exists by axiom 2 (any class of sets
   exists).  {x : x E A & Px} is a set by axiom 4 (any subclass of the set A
   is a set).  Notice that this does not use axiom 5, and that P can
   be any property at all.

Corollary:  For any sets A and B, the intersection A ^ B and the relative
complement A - B are sets.

   A ^ B = {x E A : x E B} = {x : x E A & x E B}

   A - B = {x E A : ~(x E B)} = {x : x E A & ~(x E B)}

Theorem 5:  P(A), the power set of A, is a set if A is a set.

   P(A) is the set of all subsets of A:  {x : x c= A}.  The formula
   x c= A does not mention Set (one can expand the definition of c=
   to see this, and so satisfies conditions 1-2 as long as A is a set.
   It satisfies condition 3 by axiom 4 (any subclass of the set A is a set)
   so is a set by axiom 5.

   Theorem 5 is a very strong assertion; think about infinite sets A.

Theorem 6:  U(A), the set union of A, is a set if A is a set.

   U(A) is the set of all elements of elements of A: U(A) = 
   {x : (Ey.(x E y & y E A))}.  The formula ``(Ey.(x E y & y E A))''
   satsfies conditions 1-2 and satisfies condition 3 by two applications
   of axiom 3:  an element of an element of a set A will be a set.

   U(A) is a device for taking the union of a possibly infinite collection
   of sets.

Definition:  we define 0 as {} and x' as x U {x} for any set.

   This means that we define 0 as {}, 1 as 0 U {0} = {0}, 2 as
   1 U {1} = {0,1}, 3 as 2 U {2} = {0,1,2}, and so forth.
   No profound philosophical significance is claimed for this definition!

Theorem 7:  N, the set of ``natural numbers'', exists.

   The hardest part of this is coming up with the definition:
   N = {x : (Ac.(c E 0 & (Ay.y E c -> y' E c)) -> x E c)}
   The formula ``(Ac.(c E 0 & (Ay.y E c -> y' E c))->x E c)''
   satisfies conditions 1 and 2, though it is odd that it contains
   a quantifier over all classes!  To see that it satisfies condition
   3, observe that the class of all sets contains 0 (by Theorem 1)
   and contains y' if it contains y (by Theorems 2 and 3), so any
   x that satisfies ``(Ac.(c E 0 & (Ay.y E c -> y' E c))->x E c)''
   will belong to the class of all sets (as a particular choice for c)
   which establishes Theorem 7.

   The secret of the definition is in ``(c E 0 & (Ay.y E c -> y' E c)''; 
   if this formula is true of a class c, we can (informally) prove that all
   natural numbers belong to it by mathematical induction: we call
   such classes c ``inductive classes''.  All such classes c contain N
   (intuitively speaking) and N is itself such a class, so a natural
   number is an object which belongs to all inductive classes.  Then
   the trick of the proof is to notice that the class V of all sets
   (which, as we will see, is not a set) is an inductive class, and so
   all elements of N are sets.

Negative Results:

Definition:  We define V as {x : Set(x)}; V is the class of all sets.

Theorem 8:  V is not a set.

   If V were a set, we would be able to apply Theorem 4 to show
   that {x E V : ~(x E X)} = {x : Set(x) & ~(x E X)} is a set, and
   we already know that this is not a set.

Theorem 9: The complement V - A = {x: Set(x) & ~(x E A)} of a set A is
not a set.

   If the complement of A were a set, then its union with A would be a
   set by Theorem 3, and so V would be a set, which we know is not the
   case.

Theorem 10:  Not all elements of classes are sets.

   In some treatments with both sets and classes, the classes are exactly
   the arbitrary collections of sets (which we cannot safely assume are
   sets) which means that non-sets are not elements of classes (and so
   not elements of anything).  We show that this cannot be true in this
   system.

   Suppose all elements of classes were sets.  Then the class 
   {x : (Ey.x E y)} would exist as a class by axiom 2 (everything
   satisfying the defining property would be a set), and as a set by axiom
   5 ((Ey.yEx) certainly satisfies conditions 1 and 2 and would
   satisfy condition 3 by our hypothesis).  By Theorem 2, every
   set x satisfies (Ey.x E y)} (every set belongs to its singleton)
   so the class {x : (Ey.x E y)} would be the class of all sets V,
   and we know this cannot be a set.

The Story Behind This

Here's a story to explain axioms 1-5.  We build the world of sets by
some process of construction in which we choose collections of things
already constructed and declare them sets.  For ``class'', read
``collection we might construct''; for ``set'' read ``collection we
will actually construct''.

Axiom 2 says that any collection of things we actually will construct
is something we might have constructed (but not necessarily something
we will construct); since we have the power to choose arbitrary
collections of things we have already constructed, we believe this.

Axiom 3 says that any collection we will construct has elements we will
construct (would have constructed already!)

Axiom 4 says that any subclass of a collection we will construct will
also get constructed (this is a strong assertion!)

Axiom 5, as always, is trickiest.  It specifies conditions under which
a property defines a set:

   1.  Any object mentioned in the definition of the property has already
   been constructed. (condition 2 in ax. 5)

   2.  The property of ``actually being constructed'' is not mentioned
   (because we aren't done with the construction process yet -- we
   don't actually know what sets will be constructed).  (condition 1 in
   ax. 5)

   3.  The property is only true of objects we will actually construct. 
	(condition 3 of ax. 5)

Relation to Standard Set Theory

It is known that the system with axioms 1-5 (plus Extensionality and
two technical axioms of Foundation and Choice) is equivalent to the
standard set theory ZFC in everything it says about sets (ZFC does not
have classes).  The theory with axiom 1-5 is called ``Ackermann set
theory'' after the same German mathematician who gave his name to
``Ackermann's function''.

Theorems 1-7 are an axiom set (again, with the exception of
Extensionality, Foundation and Choice) for an important subset of ZFC
called ``Zermelo set theory'', which is enough of a foundation for
most of mathematics.  After this, we will almost always rely on these
statements as if they were axioms, and seldom appeal to our official
axioms.

On April 4, we covered all of this except the ``negative results''.



Randall Holmes
2000-05-05