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$
  • 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$ – Thomas Andrews Jan 23 '17 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 '17 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$ – Carl Mummert Feb 1 '17 at 14:05
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$
  • 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$ – Q the Platypus Feb 1 '17 at 4:01
  • $\begingroup$ @QthePlatypus I changed my answer to not be misleading. $\endgroup$ – Stella Biderman Feb 1 '17 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$ – Carl Mummert Feb 1 '17 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$ – Carl Mummert Feb 1 '17 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$ – Carl Mummert Feb 1 '17 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$
  • $\begingroup$ -1, both $A$ and $B$ are false $\endgroup$ – Stella Biderman Feb 1 '17 at 13:45
  • 1
    $\begingroup$ @Stella Biderman: could you explain, or give a counterexample? $\endgroup$ – Carl Mummert Feb 1 '17 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$ – Stella Biderman Feb 1 '17 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$ – Carl Mummert Feb 1 '17 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.