1
$\begingroup$

I am deriving the natural numbers with the Peano Axioms and have a question about the Axiom of mathematical induction. I am having trouble grasping the significance of Peanos formulation of this Axiom. For example I cannot see a difference between Peanos Axiom and the formulation:"If n is a natural number it can be reached by repeated incrementation starting from 0".

$\endgroup$
3
  • 5
    $\begingroup$ The latter can't be made formal in any formal language. But it is the essential intuition of the axiom of induction. $\endgroup$ Jan 23, 2017 at 17:03
  • $\begingroup$ By saying that "every natural number has some property P if 0 has property P and for any n: n +1 (or s(n)) has property P if n has property P", the axiom of induction relies or assumes that every natural number can be reached by this repeated incrementation (otherwise the axiom of induction wouldn't make sense) ... but it does not say that. $\endgroup$
    – Bram28
    Jan 23, 2017 at 18:37
  • $\begingroup$ @Thomas Andrews: we could interpret the final statement as saying that there is a sequence of $1$s such that $n$ is the sum of the sequence; this can be expressed in PA. Of course, in this reading the statement becomes a theorem of Peano arithmetic. $\endgroup$ Feb 1, 2017 at 14:05

3 Answers 3

2
$\begingroup$

"If n is a natural number it can be reached by repeated incrementation starting from 0" is meaningfully different from the Peano Axiom of Induction. The Peano Axiom is not just about "is reachable" but is about any property. For example, "$x\geq 0$" is a property that we can use with the axiom of induction.

$\endgroup$
9
  • 2
    $\begingroup$ You can't state that in a formula of first order logic you can exclude those non-standard models in 2nd order logic. $\endgroup$ Feb 1, 2017 at 4:01
  • $\begingroup$ @QthePlatypus I changed my answer to not be misleading. $\endgroup$ Feb 1, 2017 at 13:46
  • 1
    $\begingroup$ Of course, a nonstandard model of PA will still believe every natural number can be reached by adding 1 enough times; it will believe that the primitive recursive function $f(0) = 0$, $f(n+1) = f(n) + 1$ is surjective. The issue is that the number of times will itself be an element of the model.... $\endgroup$ Feb 1, 2017 at 13:50
  • 1
    $\begingroup$ @Stella Biderman: I'm talking about first order Peano arithmetic. You can indeed write down a formula that expresses the statement you just quoted. There are at least two ways. The first is to use the primitive recursive definition of the function $f$ I mentioned. The second is to directly say "There is a $k$ such that a constant sequence of $1$s with length $k$ has sum $n$. " By standard methods, we can quantify over sequences in Peano arithmetic. The last sentence I quoted is a theorem of Peano arithmetic, and directly expresses "every $n$ can be reached by applying successor repeatedly" $\endgroup$ Feb 1, 2017 at 14:15
  • 1
    $\begingroup$ Of course it is not true that a nonstandard element is the sum of a standard number of 1s, but that is not what the quoted statement says: the quantifiers over $n$ and $k$ both range over all elements of whatever model we want to look at. $\endgroup$ Feb 1, 2017 at 14:20
2
$\begingroup$

One issue is that the statement

A: "If n is a natural number it can be reached by repeated incrementation starting from 0"

seems to be trivially true: if $n>0$ is a natural number, then $n$ should be reachable by adding $1$ to itself $n$ times. This does not tell us about whether other properties are maintained as we move upward through the set of naturals.

When we formalize the induction axioms in Peano arithmetic, the statement

B: "If $n>0$ is a natural number it can be reached by adding $1$ to itself $n-1$ times"

is just one consequence of the induction axioms. It is known that the entire set of induction axioms in Peano Arithmetic is not only infinite, but it is not implied by any of its finite subsets. So there are other, more complicated induction axioms that are not implied by $B$ alone; we need to include the entire set of induction axioms to get the full strength of PA.

On the other hand, the intuition that statement A should be true is one of the motivations for the other induction axioms: it helps us see why we might expect them to be true.

Statements $A$ and $B$ have interesting behavior in the context of nonstandard models. Although a nonstandard model of Peano Arithmetic will think that each nonstandard element $n$ can be reached by repeatedly adding $1$ to itself, the number of times that $1$ must be added to itself will also be nonstandard when $n$ is. Somewhat by definition, there is no way to reach a nonstandard number by adding 1 to itself a standard number of times.

$\endgroup$
4
  • $\begingroup$ -1, both $A$ and $B$ are false $\endgroup$ Feb 1, 2017 at 13:45
  • 1
    $\begingroup$ @Stella Biderman: could you explain, or give a counterexample? $\endgroup$ Feb 1, 2017 at 13:47
  • $\begingroup$ How many times do you have to call the successor function to obtain a nonstandard element starting from $0$? en.wikipedia.org/wiki/Non-standard_model_of_arithmetic $\endgroup$ Feb 1, 2017 at 13:55
  • 1
    $\begingroup$ @Stella Biderman: well, in a nonstandard model, a nonstandard element $n$ will be $f(n)$ where $f(0) = 0$ and $f(x+1) = f(x)+1$. So the model believe that you can get to $n$ by adding $1$ exactly $n$ times, that is, adding $1$ to itself $n-1$ times. In particular every nonstandard model will satisfy $A$ and $B$, but more importantly the standard model will, which normally is expressed by saying $A$ and $B$ are true statements about natural numbers. To say that "$A$ is false" would mean it is false in the standard model. $\endgroup$ Feb 1, 2017 at 14:00
0
$\begingroup$

The induction axiom can be formally stated as follows:

$\forall P\subset N: [0\in P \land \forall x\in P:[S(x) \in P] \implies P=N]$

Let $M$ be the subset of $N$ comprised of those and only those elements of $N$ that can be reached by repeated incrementation starting from $0$.

$M=\{0, S(0), S(S(0)), \cdots \}$

In other words, $M$ is smallest subset of $N$ such that $0\in M$ and for all $x\in M$, we also have $S(x)\in M$.

More formally:

$\forall a:[a\in M \iff a\in N \land \forall Q\subset N: [0\in Q \land \forall b\in Q: [S(b)\in Q] \implies a\in Q]]$

From the axioms of set theory, we know that this subset of $N$ will exist.

It is then a simple exercise to prove using the induction axiom that, for all $x\in N$ we also have $x\in M$.


EDIT 1: The converse is also true, so you are correct. They are indeed equivalent. Formal proof to follow.


EDIT 2: See machine-verified, formal proof (136 lines) as promised.

Theorem: Suppose we have a set $n$ (finte or otherwise), a function $s: n \to n$ and $n_0 \in n$. Then induction will hold on set $n$ with successor function $s$ and "first" element $n_0$ if and only if all elements of $n$ are reachable by repeated succession starting at $n_0$, i.e. the set $m = \{n_0, s(n_0), s(s(n_0)), ... \}$ contains every element of $n$.

More formally:

$\forall n,n_0,s:[n_0\in n \land s: n\to n\\\implies[\forall a\subset n:[n_0\in a \land \forall b\in a: [s(b)\in a] \implies n\subset a]\\\iff \exists m:[\forall a: [a\in m \iff a\in n \\\land \forall b\subset n:[n_0\in b \land \forall c\in b:[s(c)\in b]\implies a\in b]]]\\\land n\subset m]]$

$\endgroup$

You must log in to answer this question.

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