2
$\begingroup$

What is a theorem about the positive integers that cannot (or is not known to) be proved without induction over the positive integers?

  • 0
    Almost everything, and more.2011-10-18

3 Answers 3

2

The following is a rather technical answer. First we need to decide what we mean by induction over the positive integers. We take an interpretation that could be argued to be somewhat narrow. By induction we mean ordinary induction, except that the induction is only used with formulas in the usual first-order language for arithmetic.

Then apart from some trivialities, the sentence $\varphi$ is provable using induction precisely if $\varphi$ is a theorem of PA, first-order Peano Arithmetic, and $\phi$ is refutable using induction precisely if the negation $\lnot\varphi$ of $\varphi$ is a theorem of PA.

Then your question is fully settled by the Gödel Incompleteness Theorem. If PA is consistent (which it surely is), then there are sentences $\varphi$ in the language of PA that are neither provable nor refutable in PA.

The construction of such sentences is highly indirect, and the sentences produced by the construction are not mathematically very natural. So there has for a long time been an interest in finding more natural sentences of arithmetic that are neither provable nor refutable in PA.

The search has been successful! One famous such result is Goodstein's Theorem. Another is a Ramsey-like theorem first described by Paris and Harrington. Both results are relatively natural. We omit the statements of these results, since the above links do a perfectly good job of that.

Goodstein's Theorem and the Ramsey-like theorem of Paris-Harrington can be each be stated as a sentence in the language of PA. It has been proved that (if PA is consistent), then neither theorem is provable in PA. This means that induction arguments using sentences of PA are not strong enough to prove either theorem.

Each of these results can be proved, for example, in ZFC (Zermelo-Fraenkel Set Theory plus the Axiom of Choice). ZFC is the ordinary background formal set theory within which, in principle at least, one ordinarily proves theorems in mathematics.

8

If we assume our "ground floor" are the Peano Axioms:

  1. $1\in\mathbb{N}$.
  2. If $n\in\mathbb{N}$, then $s(n)\in\mathbb{N}$.
  3. If $s(n)=s(m)$, then $n=m$.
  4. For all $n\in\mathbb{N}$, $s(n)\neq 1$.
  5. If $S\subseteq \mathbb{N}$ is such that $1\in S$ and for all $k\in\mathbb{N}$, $k\in S\Rightarrow s(k)\in S$, then $S=\mathbb{N}$.

then you cannot prove that:

For every $n\in\mathbb{N}$, either $n=1$ or else there exists $k\in\mathbb{N}$ such that $n=s(k)$.

without appealing to induction in some way.

To see this, take $\mathbb{N}$ to mean two copies of the natural numbers: a copy that contains "blue naturals" and a copy of "red naturals". Let "1" correspond to the "blue 1"; define $s$ as follows: if $n$ is blue, then $s(n)$ is the blue successor of $n$ in the usual way. If $n$ is red, then $s(n)$ is the red successor of $n$ in the usual way.

Then this model satisfies Axioms 1 through 4, but not Axiom 5 (the set of "blue naturals" contains $1$, and whenever it contains a blue or red natural number it contains it successor, but the set of blue naturals is not the whole set we are calling $\mathbb{N}$. In this model, the highlighted statement is false; but it's true for any model that satisfies 1-5. So it cannot be proven without induction (i.e., without appealing in some way to Axiom 5).

Added. It's also worth noting that the statement in question is not equivalent to induction; indeed, there is a model of Axioms 1 through 4 in which the theorem is true, but induction false. That is, the theorem is independent of (Axioms 1-4)+(negation of Axiom 5). Take as your set $\mathbb{N}$ a copy of the natural numbers, colored blue, and then put a copy of the integers, colored red, after it. "1" refers to the blue natural number $1$; $s$ is the function that sends a blue natural $n$ to the blue $s(n)$; and sends a red integer $m$ to $m+1$. In this model, every red integer and every blue natural except for 1 are the succesor of someone, so the quoted result is true, as are Axioms 1-4, but Axiom 5 is false (the set of blue naturals satisfies the hypothesis of Peano's fifth, but not its conclusion).

5

It really depends on what you use as your starting axioms. If you start with Peano's axioms, for example, you need induction to even prove addition is commutative, multiplication is commutative, and the distributive law.

In general, given a set of axioms, and a theorem proved from those axioms, you show that the theorem requires one axiom by creating a "model" which satisfies the other axioms but not your target axiom, and then show that the theorem is not true in that model.