next up previous
Next: Friday, April 7, 2000 Up: Lecture Notes Previous: April 4, 2000

April 5, 2000

I will not be here on Friday, April 14.  I'm not sure how the class will
be covered yet.

Points to be covered:

The ``negative results'',  theorems 8-10 in the previous notes, were
proved and discussed.

In the proof of theorem 8, I explicitly proved the following

Lemma:  {x : Set(x) & ~(x E x)} is not a set.

Proof:  Suppose for the sake of a contradiction that {x : Set(x) & ~(x E x)},
which we abbreviate R, is a set.  Then either R E R or ~R E R.  In case
R E R we have (by definition of R) Set(R) & ~(R E R).  This is a contradiction,
since we have deduced ~R E R from R E R.  In case ~(R E R) we have
(by definition of R) ~(Set(R) & ~(R E R)), thus either ~Set(R) or R E R.
We have supposed that Set(R), so we can conclude R E R, which is again
a contradiction.  Since both cases lead to contradiction, we conclude
that our assumption Set(R) was false.

There was an interesting discussion of the following question.  Theorem 3
allows us to construct the union A U B of any two sets A and B.  A student
asked why this does not allow us to construct the union of all sets,
that is, the class V, as a set.

I gave the following example.  Notice that if A and B are finite sets,
A U B is a finite set.  It does not follow from this that the union
of _all_ finite sets is a finite set!

Theorem 6 gives us an even stronger ability to construct unions: if we
have any set (possibly an infinite set) of sets, we can take the union
of all of them and get a set.  (This shows that no set of sets can
``cover'' the entire universe V; it is very large in some sense).

There was also an interesting discussion of whether sets can be elements
of themselves.  For example, can there be a set x = {x} which is its own
singleton?  A student pointed out that it shouldn't be a set because we
have no way to ``construct'' it.

I exhibited the

Axiom of Foundation:  For any class C, there is an element D of C such 
that D ^ C = {} (D and C share no elements).

This axiom can be adjoined to our system (and is much better motivated
than it appears to be at first glance).  It would rule out x = {x};
such a set x (which would be a class as well!) would have only the element
x, which is not disjoint from x.  But it is also true that the existence
of a set x = {x} is consistent with our axioms.

Here is a possible motivation for Foundation.  We suppose that our
sets are ``constructed'' in some order, and that our classes are things
we might possibly construct (so although we may not actually have constructed
C (it may not be a set) it must be possible to imagine constructing C).
Among the elements of C, there must be some class D which was constructed
first (or possibly a group of classes all constructed at the same tim,
from which we choose D).  Any element of D must have been constructed
before D, and so before any element of C was constructed, and so D
shares no elements with C:  any class C has an element D such that
D ^ C is empty.  The construction picture makes it easy to see why
x = {x} is unreasonable:  in order to construct {x}, we already need
to have x in hand!

I repeated the definition of the set N of natural numbers, with an additional

Definition:  0 is defined as the empty set {}

Definition:  for any set x, x' is defined as the set x U {x}.

If we interpret the notions of zero and successor in the usual way,
this means that we are defining 0 as {}, 1 as {0}, 2 as {0,1}, 3 as
{0,1,2} and so forth.

This is just a convention.  We do not claim that {0,1,2,3} is _really_
what the number 4 is (we are not sure what a claim like this means).

Definition:  A class c is said to be ``inductive'' iff 0 E c and
(Ay, y E c -> y' E c).

Notice that inductive classes are exactly those classes which we
expect to be able to prove to contain every natural number by
mathematical induction.

Definition:  N is the class {x : x belongs to every inductive class}

We showed (Theorem 7 above) that N exists and is in fact a set.  A
crucial part of this proof was the observation that the non-set class
V is inductive (this allows us to show that N satisfies condition
3 for the application of axiom 5).

We are obligated to show that our set N satisfies the axioms of our formal
number theory.  We don't address the question of + and * here because we
cannot yet define them, but we do discuss the axioms which mention only
zero and successor.

The axioms to be covered are

1.  induction:  this is the easiest!  We defined N so that induction would

2.  x' =/= 0: this is obvious.  x U {x} has an element and {} does not
so they are distinct.

3.  x' = y' -> x = y (the other implication in ax. 2 of arithmetic follows
by properties of equality).

This is harder to prove.  There is a short proof using the Axiom of Foundation
which I gave above.

First we give a 

Useful Observation:  x E y' iff either x E y or x = y.  This follows
from the definitions of singleton set and union of two sets.

A Syntactical Observation:  I notice that I have been writing sentences
like x = y = z and x E y = z in the following, so I formally stipulate
that if R and S are infix predicate symbols that x R y S z means
(x R y) & (y S z).

   Let x and y be arbitrary.

   Suppose x' = y', that is x U {x} = y U {y}, and assume x =/= y for
   the sake of a contradiction.  Notice that we would have x E (x U {x}) 
   = (y U {y}), so either x E y or x = y.  Since x =/= y, we have
   x E y.  By an exactly symmetrical argument, we have y E x.  We
   would then be able to observe that {x,y} has no element disjoint
   from itself, because x shares the common element y with {x,y} and y
   shares the common element x from {x,y}, which is impossible by
   Foundation and therefore completes the proof.

   Since we do not have Foundation in our system, we need to prove
   that x E y & y E x is impossible for natural numbers x and y.  
   We prove this by induction.

Lemma 1:  (Axy E N.~(x E y & y E x))

   We prove this by induction on x.

   Basis:  0 E y & y E 0 is impossible, because y E 0 is impossible
   (0 is defined as the empty set!)

   Induction Step:  Suppose that (Ay E N.~(n E y & y E n)).

   We assume for the sake of a contradiction that n' E y & y E n'.
   y E n' = n U {n} breaks down into two cases, y E n and y = n.

   Case 1:  y = n.  We then have n' E n & n E n', which is impossible
   by inductive hypothesis.

   Case 2:  y E n.  We have n' E y and y E n and y E n'.  We would
   be done if we could show n' E y -> n E y, and we proceed to prove
   this as a lemma.

Lemma 2:  (Axy E N.(x' E y -> x E y))

   Basis:  x' E 0 -> x E 0 is vacuously true because x' E 0 is false.

   Induction Step:  Suppose (Ax E N.(x' E n -> x E n)).

   Our goal is to show that for all x E N, x' E n' -> x E n'.

   Suppose that x' E n' = n U {n}.  There are two cases:  either x' E n
   or x' = n.  If x' E n then x E n by inductive hypothesis.  If
   x' = n, then we have n = x U {x}, from which we have x E n, from
   which we have x E n' = n U {n}.

We return to the proof of case 2 of Lemma 1.

   n' E y implies n E y by Lemma 2, so we have n E y and y E n, contrary
   to ind hyp.  From this it follows that our assumption n' E y & y E n'
   was false, which is what is needed to complete the proof by induction
   of Lemma 1.

This completes the proof of the interpreted version of axiom 2 of our
system of formal arithmetic.

The definition of the natural numbers is the first step in a program
of implementation of all of mathematics in set theory.  It is now generally
accepted that all mathematical objects can be viewed as sets.

We remind ourselves that we can define all finite sets by listing:

Definition:  {x,y} = {x} U {y}; {x,y,z} = {x,y} U {z}, and so forth.

{x,y} is an unordered pair of x and y; {x,y} = {y,x}.
We need an ordered pair:

Definition:  (x,y) = {{x},{x,y}}

This definition is another ``implementation''.  We will prove two
basic properties of this pair, and after that the internal details of
the definition will be entirely irrelevant.

We use the following

Lemma:  {x} = {x,y} iff x = y.

   The proof of this Lemma will be an example of the ``style'' of
   a proof that A = B (where A and B are classes).  Formally,
   we need to prove (Au. u E A <-> u E B)

   This suggests the following structure:

      Let u be arbitrary.

      Assume u E A and prove that under this assumption u E B.

      This establishes u E A -> u E B.

      Assume u E B and prove that under this assumption u E A.

      This establishes u E B -> u E A.

      The two implications establish the biconditional u E A <-> u E B,
      from which we get (Au. u E A <-> u E B) because u was arbitrarily
      chosen, from which we get A = B by extensionality.

  We exemplify this in the proof of the Lemma:

  Our first goal is to prove x = y -> {x} = {x,y}.

  Suppose x = y.  Our goal is to prove {x} = {x,y}.

  Let u be arbitrary.  Suppose that u E {x}.  Equivalently, u = x.
  Then u E {x,y} because x E {x,y} = {u : u = x | u = y}.  Suppose
  that u E {x,y}.  Then either u = x or u = y.  In the first case,
  u = x, so u E {x}.  In the second case, u = y = x (by hypothesis)
  so u E {x}.  So we have concluded that u E {x} <-> u E {x,y} for
  arbitrary u, from which it follows that {x} = {x,y},
  and so x = y -> {x} = {x,y}.

  Our second goal is to prove {x} = {x,y} -> x = y.

  Suppose {x} = {x,y}.  We know that y E {x,y}, so it follows that
  y E {x}, and so x = y as desired.

  We have completed the proof of the biconditional x = y <-> {x} = {x,y}.

Theorem:  (x,y) = (z,w) -> x = z and y = w

Case 1:  x=y

In this case {x} = {x,y} by the Lemma.  Thus {{x},{x,y}} = {{x}} by
another application of the Lemma.

Now suppose that (x,y) = {{x}} = (z,w) = {{z},{z,w}}.  We certainly
have {z} E {{z},{z,w}}, from which we have {z} E {{x}}, from which we
have {z} = {x}, from which we have z = x.  Similarly, {z,w} E {{z},{z,w}},
from which {z,w} E {{x}}, from which {z,w} = {{x}} = {z}, from which z = w
by the Lemma, from which we have y = x = z = w, so y = w.

Case 2.  x =/= y.

Assume {{x},{x,y}} = {{z},{z,w}}.  Note that since x =/= y,
we have {x} =/= {x,y} (by the contrapositive of the Lemma).

We must have {x} E {{z},{z,w}} so {x} = {z} or {x} = {z,w}.  In
either case, z E {x} so x = z.

We must have {x,y} E {{z},{z,w}}, so we must have {x,y} = {z}
or {x,y} = {z,w}.  We cannot have {x,y} = {z} = {x}, as we have
already seen, so we must have {x,y} = {z,w}.  We have y E {z,w},
so y = z or y = w.  We cannot have y = z = x by hypothesis, so we
must have y = w.  This completes the proof of Case 2 and the entire

Proof of the existence of Cartesian products is part of the essential
work to make sure this pair definition satisfies the specification!
Axiom 5 could be used directly to establish the existence of A x B,
but we can also use theorems 1-7.

Notation {(x,y) : Pxy} defined as {z : (Exy. (z = (x,y) & Pxy))}

A x B = {z : (Exy. z=(x,y) & x E A & y E B)} = {(x,y) : x E A & y E B}

If A and B are sets, A x B is a set by ax. 5:  its definition does
not mention Set and mentions as free variables or constants only the
sets A and B.  A z which satisfies the condition is an ordered pair
(x,y), where x is an element of a set A and so a set, and y is an
element of a set B and so a set.  (x,y) is obviously a set (ths. 2,3)
if x and y are sets.  So A x B is a set by ax. 5.

This can also be proved from theorems 1-7, as follows.

If x E A and y E B, x and y both belong to A U B (a set by th. 3), {x}
and {x,y} both belong to P(A U B) and {{x},{x,y}} belongs to P(P(A U B)) 
(a set by Th. 5).  So we can define A x B as {z E P(P(A U B)) :
(Exy. z=(x,y) & x E A & y E B)} which is a set by th. 4.

Once we have proved these two theorems about ordered pairs, it will
quite literally never again be necessary to look at the definition of the
ordered pair unless one is doing technical set theory.

In class on April 5, we got as far as stating the definition of the ordered
pair and the theorems it needs to satisfy, but we did not give the proofs.

Randall Holmes