Last Update: 16 March 2009
Note: or material is highlighted |
What are the natural numbers?
We've listed them in this course as:
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:
What's the difference? Well, clearly, N = Z^{+} ∪ {0}.
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.
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 my Web page on
"Countability",
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:
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.
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:
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:
(i.e.:
next, singleton containing the empty set (i.e., its predecessor) as its only member;
then, 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
(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.
{}, {{}}, { {}, {{}} }, …
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 ∪ 1
3 =_{def} 0 ∪ 1 ∪ 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}
∪_{i∈{0,…,n}}{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 :-)
Rosen, Kenneth H. (2007),
Discrete Mathematics and Its Applications, 6th Edition
(New York: McGraw-Hill)