18
$\begingroup$

More precisely, when we define the set of natural numbers $\mathbb{N}$ using the Peano axioms, we assume the following:

  1. $0\in\mathbb{N}$
  2. $\forall n\in\mathbb{N} (S(n)\in\mathbb{N})$
  3. $\forall n\in\mathbb{N}(0\neq S(n))$
  4. $\forall m,n (m\neq n\to S(m)\neq S(n))$
  5. If $P(n)$ denotes the fact that $n$ has property $P$, then $\Big(P(0)\wedge \forall n\in\mathbb{N}\big(P(n)\to P(S(n))\big)\Big)\implies \forall n\in \mathbb{N} (P(n))$

I understand that using these axioms we can derive everything about the natural numbers, but I also think it's helpful to know why the axioms were chosen the way they are. So my question is why we choose to accept the axiom of induction ((5.) above), which in a way makes this more of a metamathematical question.

For example in Tao's Analysis I, it says that the axiom of induction keeps unwanted elements (such as half-integers) from entering the set.

Wikipedia says:

"Axioms [1], [2], [3] and [4] imply that the set of natural numbers is infinite, because it contains at least the infinite subset $\{ 0, S(0), S(S(0)), \ldots \}$, each element of which differs from the rest. To show that every natural number is included in this set requires an additional axiom, which is sometimes called the axiom of induction. This axiom provides a method for reasoning about the set of all natural numbers."

But I find this tautological: $\mathbb{N}$ is defined as the set of natural numbers so "$n$ is a natural number" means "$n\in\mathbb{N}$", right? So isn't every natural number included in $\mathbb{N}$ by definition?

Suppose we want to show $\mathbb{N}=\{0,1,2,3,\ldots\}$ using all five of the Peano axioms.

If we let $P(n)$ denote $n\in\{0,1,2,3,\ldots\}$, then $P(0)$ is true. Suppose $n$ is in $\{0,1,2,3,\ldots\}$. Then (informally) the dots indicate that $S(n)$ is in $\{0,1,2,3,\ldots\}$. So $\mathbb{N}\subseteq\{0,1,2,3,\ldots\}$, i.e., our defined set contains no "extra" elements (as in Tao's Analysis I).

Yet I still do not see how to show $\{0,1,2,3,\ldots\}\subseteq\mathbb{N}$ (in order to complete the "proof" that $\mathbb{N}=\{0,1,2,3,\ldots\}$) without just assuming it. (I think this is what the Wikipedia article was doing(?))

Thanks in advance for any help and I apologize if this kind of question is unsuitable for this site.

$\endgroup$
1
  • 3
    $\begingroup$ (a) You can't deduce "everything" about the natural numbers using the axioms you stated. (b) Without the axiom of induction, you cannot preclude the existence of "numbers" such as $\omega$, where $\omega \ne 0$, $\omega \ne 1$, \omega \ne 2$, etc. $\endgroup$
    – Zhen Lin
    Commented Apr 17, 2012 at 11:30

6 Answers 6

Reset to default
7
$\begingroup$

You are trying to deduce something about the importance of 5th axiom only from the axioms itself, which is impossible. The axioms by itself do not carry any significance. What is important is that the set defined by the axioms is (a) unique and (b) isomorphic to some real-world object (real-world natural numbers, as in "two apples" and "three oranges").

Giving away the fifth axiom means that:

a) Peano axioms no longer define a set of natural numbers, as there could be two non-isomorphic (and even not of the same cardinality) sets, both compatible with Peano axioms; rather they define a class of sets, each containing a subset, isomorphic to $\{0, 1, 2, 3, \ldots\}$. For example, let us consider the set $\mathbb N$ in its usual sense, and the set $\mathbb C \setminus {\mathbb N}^+$. Both sets fulfill the Peano axioms (except for the fifth one), but they are quite different in itself.

b) Of course, the second set from the previous paragraph has nothing in common with a real=world object called "the natural numbers".

$\endgroup$
7
  • 2
    $\begingroup$ Peano arithmetic (including the induction axiom) certainly has non-isomorphic models. See e.g. Godel's incompleteness theorem. Any (1st order) theory admitting an infinite model has models of arbitrarily large cardinalities (Lowenheim-Skolem). (The axioms stated in the question are a bit vague; one should be at least carefull about what "property" means. The usual formal axioms of Peano arithmetic look somewhat different.) $\endgroup$
    – user8268
    Commented Apr 17, 2012 at 9:07
  • 1
    $\begingroup$ @user8268 I can construct such an isomorphism easily: given some model M with a starting element Z and successor function S, let $f(Z) = 0$ and $f(S(n)) = f(n)+1$. This, by the axiom of induction, gives us a function from M to $\mathbb N$ (defined for Z => defined everywhere on M). From $f(X) = 0$ it follows that there is no $Y$ such that $S(Y)=X$, which means $X = Z$. From $f(X) = n$ it follows $f(S^{-n}(X)) = 0$ and $X = S^n(Z)$. So f is an injection. By the axiom of induction, it is a bijection as well. Obviously such a bijection is a isomorphism as well. Where am I wrong? $\endgroup$
    – penartur
    Commented Apr 17, 2012 at 9:36
  • 3
    $\begingroup$ @penartur: There is no axiom stating that every nonzero element is of the form $S(n)$ for some $n$, hence, your definition of $f$ need not have domain all of $M$, but only a portion of $M$. And indeed, every nonstandard model of Peano arithmetic has a standard model inside of it, as your proof shows. $\endgroup$
    – Jason DeVito - on hiatus
    Commented Apr 17, 2012 at 12:19
  • 4
    $\begingroup$ @penartur: The Peano axioms as described in the post are imprecise. The problem is that "property" is not defined. If "property" is defined narrowly as expressible by a formula of the (first-order) language that has the usual symbols, we have the first-order version of the Peano axioms, many models, of many cardinalities. Furthermore, the theory is incomplete. If we formalize "property" using (first-order) set theory, then most of the same problems, but any model of set theory has a unique up to isomorphism set of naturals, a proof like yours works. $\endgroup$
    – André Nicolas
    Commented Apr 17, 2012 at 14:27
  • 1
    $\begingroup$ There's confusion here between the second-order Peano axioms (which are categorical) with the first-order Peano axioms, in which induction is a scheme - one axiom per formula. The first-order version, which is what people usually mean when they say "PA," is not categorical. However, what the OP described is ambiguous, and could be second-order PA, usually denoted as "PA$_2$" (or similarly). $\endgroup$
    – Noah Schweber
    Commented Oct 7, 2015 at 23:12
2
$\begingroup$

As was noted in the question, the set $\mathbb{N}$ which we are trying to specify is infinite because we know $T \subseteq \mathbb{N}$ for the infinite set $T=\{ 0, S(0), S(S(0)), \ldots \}.$ I will rephrase your question as

How do we show that in fact $\mathbb{N}=\{ 0, S(0), S(S(0)), \ldots \}?$

Well we have to say that, it doesn't follow from the first four axioms because we could use $\mathbb{Q}$ in place of $\mathbb{N}$ and let $S(q)=q+1$ and everything so far works fine.

So we might say that " once you have $0,S(0),S(S(0)),S(S(S(0))),$ etc. that is everything!" That is pretty much what axiom 5 says.

There are some technical details but they are not directly relevant to why we want axiom 5. One detail is, how exactly do we specify what we mean by the etc.? The technical form of axiom 5 handles that, We say any set $A$ with $0 \in A$ and $S(n) \in A$ whenever $n \in A$ has all of $\mathbb{N} \subseteq A.$ This means $\mathbb{N} \subseteq T.$

Another detail is that we want to prove things about $\mathbb{N}$ and axiom 5 gives us proof by induction.

$\endgroup$
1
$\begingroup$

Note: I'm still learning about the Peano Axioms, so if any part of my answer is inaccurate, please let me know.

First, consider why we even bother thinking about the natural numbers. Of course, it's because they obey unique properties; namely, the natural numbers are "natural" in the sense that they represent how we count real-life objects. Clearly, the set of natural numbers is no ordinary set, so we might say that $\mathbb{N}$ is a "set with structure," where the "structure" encapsulates all the unique properties that make the natural numbers special.

Think of the Peano Axioms as a means of formulating this "structure." Any set obeying this "structure" should either be the natural numbers, or a set isomorphic to the natural numbers. Therefore, it doesn't make much sense to try and prove that $\{0, 1, 2, 3, \dots\} \subseteq \mathbb{N}$ (as you do in your answer); instead, you should be trying to prove that the set $\mathbb{N} = \{0, 1, 2, 3, \dots \}$ paired with the canonical successor function obeys the Peano Axioms, and thus represents the natural numbers.

If you view the axioms in this way, your question can be reframed as, "Why are the first four Peano Axioms insufficient in defining the 'structure' of $\mathbb{N}$?" A simple counterexample suffices to answer this, which Tao's half-integers does beautifully. Tao defines the half-integers to be

$$\mathbb{N} := \{0, 0.5, 1, 1.5, 2, 2.5, 3, 3.5, \dots\}.$$

and its successor function $S$ to be

$$ S : \mathbb{N} \to \mathbb{N} \\ S(n) = n + 1 $$

where $+$ is the standard real addition operator. It isn't difficult to check that this obeys the first four Peano Axioms. But this set is not the natural numbers, nor is it isomorphic to them! Therefore, we add a fifth axiom, which (in plain English) states that, "All natural numbers are some eventual successor of $0$."

$\endgroup$
1
  • $\begingroup$ "Why are the first four Peano Axioms insufficient in defining the 'structure' of N?". I think the Q is more why is adding the axiom of induction sufficient for that? Further, why can't we just say "all x in N, x = 0 or exist y in N S(y) = x" instead? $\endgroup$
    – spinkus
    Commented Dec 29, 2023 at 6:40
1
$\begingroup$

Some of the answers seem to be referencing Tao's Analysis in saying the axiom of induction is needed to keep N free from "rogue" elements like, half-integers, real numbers, cats, and planets:

There is however still one more problem: while the axioms (particularly Axioms 2.1 and 2.2) allow us to confirm that 0, 1, 2, 3, . . . are distinct elements of N, there is the problem that there may be other “rogue” elements in our number system which are not of this form [such as half-integers].

Hard to argue with a professor of Mathematics, but going out on a limb and saying I actually don't think that's why the axiom is included. I don't think we need to explicitly exclude half-integers, cats, and dogs etc from the set N (and if we wanted to do that, seems like there are simpler ways of doing that?). It's actually a way of saying axioms #1, #2 allow us to conclude the set N contains all natural numbers (or at least a set of objects isomorphic to the set of natural numbers) - i.e. there are no natural numbers that aren't in N. The Peano axioms Wikipedia page (currently) says as much. It says the axiom of induction can be interpreted (in the context of Peano Axioms) as:

If K is a set such that:

    1. 0 is in K, and
    2. for every natural number n, n being in K implies that S(n) is in K,

then K contains every natural number.

Together other axiom #1, #2 you listed ($0 \in N$, $n \in N -> S(n) \in N$) we can conclude N contains every natural number.

Does feel very tautological, but many axioms are like that.

$\endgroup$
0
$\begingroup$

Informally, $\{0,1,2,3,\ldots\}\subseteq\mathbb{N}$ comes from the first and second axioms.

Of course you would need to define what $\{0,1,2,3,\ldots\}$ is. Perhaps writing it $\{0,S(0),S(S(0)),S(S(S(0))),\ldots\}$ makes it clearer. Then you can take a particular member of this set and use the first and second axioms to show it is in $\mathbb{N}$.

$\endgroup$
2
  • $\begingroup$ If $\{0,1,2,3,\ldots\}\subseteq\mathbb{N}$ follows from the first and second axioms (informally) then why does the Wikipedia article say that induction is needed to show that every natural number is in $\mathbb{N}$? $\endgroup$
    – russell11
    Commented Apr 17, 2012 at 8:32
  • $\begingroup$ @russell11: because "$\ldots$" does not mean anything formal. I meant that you can use the first and second axiom to show for example $42 \in \mathbb{N}$ and similarly with any other particular identified member of the set of successors of $0$. $\endgroup$
    – Henry
    Commented Apr 17, 2012 at 16:45
-1
$\begingroup$

Way of proving some theories by indcution is very importand technique without it mathematics would not be the same so it was added to formalize our intuition. From what I know suprise was that this axiom was not consequence of rest of the axioms but is needed to be stated explicite.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .