From owner-cse191-sp08-list@LISTSERV.BUFFALO.EDU Wed Feb 27 11:28:40 2008 Date: Wed, 27 Feb 2008 11:27:36 -0500 From: "William J. Rapaport" Subject: 191: Using Sets to Define the Natural Numbers To: CSE191-SP08-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: 191: Using Sets to Define the Natural Numbers ------------------------------------------------------------------------ What are the natural numbers? We've listed them in this course as: N = {0,1,2,3,...} And we've discussed Peano's axioms that characterize them (see Rosen, p. A5). You may note that Rosen says that Peano's axioms are axioms for the positive integers, which we have characterized as: Z+ = {1,2,3,...} What's the difference? Well, clearly, N = Z+ U {0} (where I'm typing "U" for the set-union operator). If Peano's axioms characterize both of these very different sets, then what's unique about each of them? How can there be two different sets that satsify the very same axioms? ------------------------------------------------------------------------ In fact, there are an infinite number of sets that satisfy Peano's axioms (or any other axioms, for that matter)! ------------------------------------------------------------------------ First, let me show you how N and Z+ are in some sense the "same", even though they are clearly different sets. Then I'll show you some other sets that satisfy Peano's axioms. 1. Peano's axioms for N can be summarized briefly as follows: We need a "first" member, which has no predecessor. For each member, we need a unique successor (the "next" member). There are other axioms, but these will do for now. Consider N and Z+: Each has a first member: 0 in the case of N, 1 in the case of Z+. Each member, i, has a unique successor: i+1 in both cases. In http://www.cse.buffalo.edu/~rapaport/191/S08/EMAIL/20070114-Countability.txt I tried to convince you that |N| = |Z+|, i.e., that they have the same cardinality. That's because we can count the members in N using the numbers in Z+, which means that N is just Z+ "shifted down", so to speak: N Z+ - -- 0 1 1 2 2 3 3 4 ... ... But what that means is that N could be thought of as Z+ written using a different set of symbols: use "0" instead of "1", "1" instead of "2", etc. Or you could think of Z+ as N written differently: "1" instead of "0", etc. So, that's the sense in which N and Z+ are the "same", even though one is a proper subset of the other. 2. Now, here are some other sets that also satisfy Peano's axioms. Each of them can be considered a "model" of the natural numbers insofar as those numbers are completely "captured" by Peano's axioms: Some of these other sets should be familiar to you; each is a set of **numerals**--i.e., words, or symbols--that satisfy Peano's axioms: I, II, III, IV, V, VI, ... zero, one, two, three, four, ... zero, un, deux, trois, quatre, ... cero, uno, dos, tres, cuatro, ... /, //, ///, ////, ... 0, 1, 10, 11, 100, ... (i.e., base-2 notation) And here are some others that may look weird, but give us a way (actually, lots of different and incompatible ways) to construct N out of sets): A. {}, {{}}, {{{}}}, ... (i.e., the empty set, singleton containing the empty set (i.e., its predecessor) as its only member, singleton containing the singleton containing the empty set (i.e., singleton containing its predecessor), ... I could rewrite that last one slightly more perspicuously as follows: Let 0 =def {} Then 1 =def {0} 2 =def {1} ... n+1 =def {n}, ... B. Here's yet another way to construct/define N out of sets: (Notation: Instead of writing {x | P(x)} to describe the set of all x such that P(x), I'm going to write: {x : P(x)}, so that you won't get confused between the "|" that means "such that" and the cardinality symbol, which is a pair of "|") Let the number n =def {sets S | |S| = n}, i.e.: 0 = {S : |S| = 0} 1 = {S : |S| = 1}, etc. So, each number is identified with the set of all sets that have that cardinality. C. Here's yet another way, starting again from {}: {}, {{}}, { {}, {{}} }, ...} i.e., start with the empty set. Next use the set containing all previous members constructed so far: That's singleton empty set. Next, use the set containing all previous members constructed so far again: Now that contains 2 members: the empty set and singleton empty. Etc. I could write that one a slightly clearer way: 0 =def {} 1 =def {0} 2 =def {0,1} 3 =def {0,1,2} etc. But because these are sets, I could also write it as follows: 0 =def {} 1 =def {{}} 2 =def 0 U 1 3 =def 0 U 1 U 2, etc. Here's a recursive or inductive way of saying that: I'll define 0, and then, given any natural number n, I'll define the successor of n, notated S(n): 0 =def {} S(n) =def Ui{i}, i.e., the union from i=0 to i=n of all sets of the form {i} ------------------------------------------------------------------------ I hope you can imagine that there are actually an infinite number of different models of Peano's axioms; hence, there is no way to say which one of them is "really" the set of natural numbers! Of course, if you don't use 0,1,2,3,..., then people will look at you rather strangely :-)