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: 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 work. 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. 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.