God and Mathematics 2: The Inconsistency of the Principle of Mathematical Induction By Dr John Jensen
The principle of mathematical induction, which is actually a deductive principle, is used extensively in number theory, and it would seriously wreck mathematics if there were sound objections to it. Here, I argue that there are, as part of my Christian humbling programme for the sciences. Human hubris and intellectual pride needs to be put in its place so that the grace of God can once more rule the hearts of men. But, to business.
The principle of mathematical induction is a proof method for proving that a proposition P(n) holds for all natural numbers 0, 1, 2, 3, … . It is like a series of dominoes knocking the next over. And, it is said to work because the axiom of induction is one of the Peano axioms for arithmetic:
If φ is a unary predicate such that:
• φ(0) is true, and
• for every natural number n, φ(n) being true implies that φ(S(n)) is true,
then, φ(n) is true for every natural number n.
To conduct a proof, first prove the base step, P(0), that the property holds for the number 0, or 1. The second step is the inductive step where one makes the assumption that P(k), is true for some k. Then one considers P(k+1), and shows that P(k) implies P(k+1), thus concluding that the proposition is true by the principle of mathematical induction.
Fine, but is the principle correct? We know from “Wang’s paradox,” that the principle fails for vague predicates like “small”:
0 is a small number; if P(k), is assumed to be small, then P(k+1) is also small (as there is no radical jump in numbers from small to big), so all numbers are small! Philosophers and logicians find this interesting, but mathematicians usually tell you to go away if you want to talk about this, and may even flex their 8-inch biceps to show that they mean business. It is a terrifying sight. Anyway, there are some technical issues raising doubt about the principle of mathematical induction. Princeton University mathematician Edward Nelson (1932-2014), who once thought that he had a proof of the inconsistency of arithmetic:
But was wrong on a technicality, in his book, Predicative Arithmetic, (Princeton University Press, Princeton, 1986), expressed doubt about the principle of mathematical induction, saying:
“That the reason for mistrusting the induction principle is that it involves an impredicative concept of number. It is not correct to argue that induction only involves the numbers from 0 to n; the property of n being established may be a formula with bound variables that are thought of as ranging over all numbers. That is, the induction principle assumes that the natural number system is given. A number is conceived to be an object satisfying every inductive formula; for a particular inductive formula, therefore, the bound variables are conceived to range over objects satisfying every inductive formula, including the one in question.”
Thus, the principle of mathematical induction is up to its neck in metaphysical assumptions about infinity. Another problem with so-called proofs by the principle of mathematical induction is that all such proofs assume that arithmetic is not ω-inconsistent, where for some formula A(x), each formula of the infinite sequence A(0),…,A(n),…, and the formula ¬∀xA(x) are provable, where 0 is a constant of the formal system signifying the number 0, while the constants n are defined recursively in terms of (x)′, denoting the number following directly after x: n+1=(n)′. Thus, if arithmetic is ω-consistent it may be provable that A(0), A(1), … A(n), … but still there may be some natural number for which the proposition fails. By Gödel’s First Incompleteness Theorem, the ω-consistency of arithmetic cannot be proved, so there is an existential doubt naturally holding over every proof by the principle of mathematical induction:
However, here is my attack on the principle of mathematical induction. The basic idea is to give a simple proof of a proposition which parallels standard inductive proofs, but which runs into conflict with “big man theorems” of more advanced mathematics, in particular, Gödel’s Second Incompleteness Theorem, that the consistency of Peano arithmetic cannot be proved in the system itself. Since there can be no choice between the principles from different areas of mathematics, the principle of mathematical induction has to be held as being inconsistent.
Proof: consider proposition P(n) such that a natural number n is not equal to 0 for n > 0, i.e. ~ (n=0, unless n=0), where “~” means “not.” For P(1), this says that 1 is not equal to 0, as 1 > 0. Now using the standard reasoning mathematicians use, that is true by inspection, or if one likes, by the Peano axioms for arithmetic, as 1 is the successor of 0. P(k) is then assumed to be true, that is, that for all k, ~(k=0), for k > 0. Then consider proposition P(k+1), that proposition k+1, is not equal to 0. Yet this follows from P(k), as if it is not the case that k = 0, then from P(1), P(k+1) is not equal to 0 either. Hence, the proposition is true by the principle of mathematical induction. It follows then that ~ (1 = 0). Yet, the proof is logically circular, as many such proofs are. Worse, the conclusion alleges the absolute consistency of arithmetic, ~ (1 = 0), which is in direct conflict with the big daddy theorem of Gödel, that the consistency of arithmetic is not provable in arithmetic. Hence, a contradiction. In part 3 of this series I will turn to the question of infinity in arithmetic, and attempt to refute some standard theorems. I hope that readers are enjoying this series as much as I am writing it.