1
$\begingroup$

It is a theorem of model theory that any recursively enumerable set of axioms $\Gamma$ for number theory permit non-standard models. That is, if there is one model for $\Gamma$, then there are two models for $\Gamma$ that are not isomorphic to each other.

In the beginning of Kleene's Introduction to Metamathematics, he gives a genetic definition of the natural numbers, and gives a naive explanation for why such a definition uniquely defines the natural numbers. They are as follows.

  1. $0$ is a natrual number.

  2. If $n$ is a natural number, then $n'$ is a natural number.

  3. The only natural numbers are those given by 1 and 2.

He then states two more clauses which insure the distinctness of the operator $(')$:

  1. For any natural numbers $m$ and $n$, $m' = n'$ only if $m = n.$

  2. For any natural number $n$, $n'\neq 0$.

This is very similar to the Peano axioms, with the difference of Clause 3 being replaced with the second order induction axiom. He then gives an intuitive argument for why this uniquely defines the natural numbers.

For, $0$ is a natural number by Clause 1. And $0'$ (defined as 1) is a natural number by Clause 2 and is distinct from 0 by Clause 5. Then we can go on to define $0'' = 2$ using Clause 2 and claim that it is distinct from $0$ by Clause 5 and distinct from $1$ by Clause 4. We can proceed to define inductively using Clause 2 the numbers $0, 1, 2, \dots,k$ for some $k$ and make an argument that each natural number is distinct from the previously defined numbers by Clauses 4 and 5. Lastly, by Clause 3, we can state that any natural number belongs in this inductive tower i.e. there is no natural number that we can't "count" up to in a finite amount of steps.

Note that these 5 clauses are in first order logic. That is we can express the system described in the fives clauses as $(N, 0, ')$ where $0$ is an object and $(')$ is a unary operator by the following axioms.

i. $\forall m[m = 0 \vee \exists n(n' = m)]\,\,\,\,\,\,$ (Clause 3 formalized)

ii. $\forall m\forall n(m' = n' \rightarrow m = n)\,\,\,\,\,\,$ (Clause 4 formalized)

iii. $\forall n(n'\neq 0)\,\,\,\,\,\,$ (Clause 5 formalized).

However, by the theorem referenced in the first paragraph there are non standard models for these axioms. Thus Kleene's intuitive argument that the five clauses uniquely determine the natural numbers are wrong. Furthermore, this equivocation of Clause 3 to the second order induction axioms is also wrong, for the five clauses, with Clause 3 replaced by the second order induction axioms constituted the Peano axioms which are categorical. Why is his intuitive argument wrong? And what would be a correct argument with the second order induction axiom?

$\endgroup$

1 Answer 1

4
$\begingroup$

Clause (3) does not prohibit the existence of non-standard natural numbers, it just says that if $n$ is a non-standard natural number then it is the successor of something (which itself must be a non-standard natural number).

Consider $\mathbb{N} \cup \mathbb{Z}$ (as a disjoint union), and define $n' = n + 1$ on each part of this set. It satisfies all five conditions (as long as we understand that the $0$ mentioned in the conditions is the $0$ from the $\mathbb{N}$ part; just give the $0$ from the $\mathbb{Z}$ part a different name). The intuitive content of (3) is supposed to be something like "if $n$ is a natural number then $n=0$ or $n=0'$ or $n=0''$ or...", which is not first-order.

$\endgroup$
1
  • 1
    $\begingroup$ Of course! So the actual meaning of Clause 3 is fundamentally second order. It is not saying that natural numbers are either $0$ or a successor of a natural number. It is expressing that every natural number is constructed by a finite amount of uses of Clause 1 and 2. But this can be “formalized” by the second order induction axiom which roughly says every number can be counted up to by $0$. $\endgroup$
    – BENG
    Sep 15, 2022 at 23:02

You must log in to answer this question.

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