Skip to content
September 29, 2010 / cdsmith

Insights on Infinite Sets and the Peano Axioms

It’s possible I’m the only person that didn’t already notice this; but it’s just occurred to me that two mathematics concepts which are often taught independently are, actually, intimately related.  These are the Peano Axioms (the basic properties observed by the natural numbers), and a common definition of an infinite set.

First, the Peano Axioms.  Here they are, according to Krantz in Real Analysis and Foundations (2nd Ed.).  I’ve changed notation a bit to fit into the blog better (less mathematical typesetting)

  1. 1 is a natural number.
  2. If x is a natural number, then there is a natural number called the successor of x.
  3. The number 1 is not the successor of any natural number.
  4. If the successors of two natural numbers are the same, then they are the same.  (Put otherwise, no two distinct natural numbers have the same successor.)
  5. (I’m rephrasing this one to avoid the need to worry about what a “property” is.)  If some set Q of natural numbers contains 1, and it also contains the successor of everything in it, then Q is the entire set of natural numbers.

These properties make sense, but I’ll spend a second talking about what they mean in a little more detail.

Axiom #1: 1 is a natural number.

Remember what Juliet Capulet said: “A rose by any other name would smell as sweet.”  This doesn’t refer to whatever concept you have in your head about the number 1: the name is, in fact, arbitrary.  I can call anything 1 if I feel like it.

The first axiom isn’t completely meaningless on its own, though.  It does two things.  (a) it excludes the possibility that there are no natural numbers, i.e. that the set of natural numbers is the empty set; and (b) is establishes terminology for later; this element 1 will come up again.

Axiom #2: Every natural number has a successor.

Again, you have no license to use your own notions about successors here.  This axiom serves only the purpose of establishing notation for later; it doesn’t exclude any possibility at all with regard to how the natural numbers look.  After all, one can define a function from any set to itself.  But now we’ve fixed such a function.

Axiom #3: 1 isn’t the successor of anything.

Now things start to get interesting.  We’ve fixed a specific function (the successor function), and a specific element of the set (namely, 1).  We’re now saying that 1 is not in the image of the successor function.

In other words, all that is required by axioms 1 and 3 together is that the successor function is not surjective.  (If you prefer other terminology, the successor function is not onto.)

Axiom #4: No two naturals have the same successor.

So it’s fairly clear by now where this is going, and indeed axiom #4 is quite clearly just stating that the successor function is injective.  (Again, if you prefer different terminology, it’s one-to-one.)

A brief recap before continuing…

So to recap, from axioms 1 through 4, we get that the natural numbers is some set, which has an injective but not surjective map to itself.  Put otherwise, there is a bijection from the set to a proper subset of itself.

Wait a second!  This isn’t new at all.  This is, in fact, a commonly used definition of an infinite set, known as being Dedekind-infinite.  So Peano axioms 1 through 4 can be summarized as follows: “The natural numbers are a Dedekind-infinite set.”  This is something that no one had ever presented to me in that way before.

Axiom #5: The inductive property

Finally, axiom #5 comes in.  This is the one that confuses a lot of undergraduate mathematics students, and often seems a bit arbitrary.  It says that if you take a subset of the naturals, and it contains 1, and it also contains the successor of everything in it, that set must actually be all of the natural numbers.

This is often phrased as a proof technique for inductive proofs, rather than as a statement about sets.  Here, though, we’ll understand it to say this: not only are the natural numbers an infinite set, but in fact they are in a specific sense the smallest infinite set.  That is, every Dedekind-infinite set (witnessed by some injective but not surjective function f) must have some element not in the image of f, and then must contain the image of f on everything in it.  This last axiom simply says that the natural numbers don’t contain anything else; so they are as few as they can be.

As with all intuitions about smallness or largeness of infinite sets, one must be careful here.  Of course one could throw out plenty of elements (even infinitely many) and still end up with an infinite set.  But the statement can be made into a precise one about cardinality: given any (Dedekind-)infinite set, one has an injective function from the set to itself whose image misses some element a.  Then there is an obvious injection from the natural numbers to that set, obtained by mapping 1 to a, 2 to f(a), and so on.  So certainly, the natural numbers have minimum cardinality among infinite sets.

So that’s it.  The Peano axioms can be summarized in a nutshell as follows: the natural numbers are the smallest infinite set.  In the comments, please let me know if you’ve ever seen them taught this way.

About these ads

3 Comments

Leave a Comment
  1. zygoloid / Sep 29 2010 10:40 am

    You need to be rather careful if you go down this route. It’s very common these days for mathematicians to use first-order Peano arithmetic, rather than the full power of the second-order Peano axioms which you describe above. By upwards Lowenheim-Skolem, Peano arithmetic (being a first-order theory with an infinite model) has uncountable models and as such does /not/ require the natural numbers to be the smallest infinite set.

  2. Dan Doel / Sep 29 2010 1:39 pm

    I suppose this is somewhat similar to the way natural numbers objects are defined in category theory.

    http://ncatlab.org/nlab/show/natural+numbers+object

    Some of the parts may be hard to tease out. But, being “least” or “smallest” (without over-quotienting) typically corresponds to some kind of initiality in category theory, and that’s exactly how the natural numbers are defined.

    Definitions of inductive types in type theory are typically couched in this language, too. The natural numbers are the ‘least type closed under z and s.’ Equality is the ‘least reflexive relation’ (data Eq A x y where refl : (x : A) -> Eq A x x). Et cetera. And they of course have semantics in initial algebras.

  3. L Spice / Sep 30 2010 2:36 pm

    I think that a danger of this point of view is that, if one abstracts out (1)–(4) as ‘the set of natural numbers is infinite’, then one loses any way to refer to the specific injection that witnesses this infinitude; and that it is then basically impossible to state the (crucial) principle of induction.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 62 other followers

%d bloggers like this: