How do you prove mathematical induction without the notion of a set?

Question

EDIT - Peano's axioms for N can't be used to answer this question, because they assume induction. So what axioms can be used? I am thinking the following:

P1. x ∈ N iff x=1 ∨ ∃y (x=y' ∧ y ∈ N)

P2. 0'=1 ∧ 0 ∉ N

P3. If x'=y' then x=y

---

In most books on mathematics, they state the principle of weak mathematical induction without proof. I have a book on logic, which proves weak and strong induction using the notion of infinity, and I have a book on Axiomatic Set Theory that derived weak induction using the notion of sets. My question is, how do you prove the principle of mathematical induction, without the notions of set, and infinity?

Principle of Mathematical Induction

Let n denote an arbitrary natural number. Let N denote the set of natural numbers.

P(1) and if P(n) then P(n+1); therefore

∀m ∈ N[P(m)]

Proof.

The principle is straightforward to prove if you have the notion of infinity.

From if P(n) then P(n+1), you get an infinite sequence of true propositions:

If P(1) then P(2), if P(2) then P(3),...

Then by an infinite number of modus ponens arguments you get the following sequence of true propositions:

P(1), P(2), P(3),...

Then by repeated conjunction arguments you get the following true proposition:

P(1) and P(2) and P(3) and...

Which means ∀m ∈ N[P(m)].

The proof of the principle using the notion of set in my book on Axiomatic Set Theory, is quite unintuitive. So I'm looking for a proof/derivation that uses first order logic, but doesn't use the notions of set and infinity.

Answer 1

Your "proof" is bogus. Anytime you see "...", it cannot be a rigorous proof. Worse still, the fatal flaw in your proof is hidden inside that "...". If you wish to try to figure out the flaw yourself, try to write down a proof that does not have "...". If you fail, you will understand the flaw in your ideas better.

Secondly, there is no non-circular proof of induction (without using something at least as strong as induction).

Answer 2

Within Peano Arithmetic, the axiom schema of induction is, as the name suggests, an axiom, which is not provable from the other axioms. In stronger axiomatic systems such as Zermelo-Fraenkel set theory, one can prove induction or more precisely define N ("the" natural numbers) as the least inductive set.

Answer 3

Complete Induction is part of the definition of the set of natural numbers. (Note that some people include 0 in the natural numbers and some don’t).

The axiom is: If P(1) is true, and if for every natural number k, P(k) implies P(succ(k)), then P(n) is true for every natural number n.

Now take the statement P(k): k is a natural number. And take the set M = { 1, 1.5, 2, 2.5, 3, 3.5 … }. The conditions of complete induction are met, but P(n) is not true for all elements of M. For example, 1.5 is not a natural number. Or take M’ = { -1, 0, 1, 2, 3, 4, … }. Again P(-1) and P(0) are not true. But that’s ok because M and M’ are not N.

The important thing is: You are mixing up what you think the natural numbers are with how they are defined. Peano stated “this is an axiom. A set that is meeting all the axioms is called “natural numbers”.” You on the other hand seem to think that there is a set of natural numbers for no reason other than that you think they should exist.

You didn’t prove anything about natural numbers. You compared your preconceptions with the axioms and they matched. But without peano’s axioms you have nothing.

Answer 4

Suppose your Axiomatic system for N consists of only the following three postulates:

P1. x ∈ N iff x=1 ∨ ∃y (x=y' ∧ y ∈ N)

P2. 0'=1 ∧ 0 ∉ N

P3. If x'=y' then x=y

Can you prove induction?

Theorem 1: 1 ∈ N

1. 1 ∈ N iff 1=1 ∨ ∃y (1=y' ∧ y ∈ N) [P1]
2. 1=1 [reflexivity of equality]
3. 1=1 ∨ ∃y (1=y' ∧ y ∈ N) [2; addition]
4. 1 ∈ N [3,1; MP2]

Q.E.D.

Theorem 1 is one of Peano's 5 axioms.

Theorem 2: ~∃y∈N[y'=1]

1. ∃y∈N[y'=1] [OSC1]
2. Z'=1 ∧ z ∈N [1; EI]
3. 0'=1 ∧ 0 ∉ N [P2]
4. Z'=0' [2,3; transitivity of equality]
5. If z'=0' then z=0 [P3]
6. Z=0 [4,5; MP]
7. 0 ∈ N [2,6; substitution]
8. 0 ∈ N ∧ 0 ∉ N [7,3; conjunction]
9. If ∃y∈N[y'=1] then contradiction [1-8; CSC1]
10. ~∃y∈N[y'=1] [9; RAA]

Q E.D.

Theorem 2 is one of Peano's 5 axioms.

Theorem 3: ∀m[If m ∈N then m' ∈N]

1. n ∈N [OSC1]
2. n' ∈ N iff n'=1 ∨ ∃y (n'=y' ∧ y ∈ N)
3. n=x ∧ x ∈N [1; substitution]
4. n'=x' [3; successors are unique]
5. n'=x' ∧ x ∈N [4,3; conjunction]
6. ∃y (n'=y' ∧ y ∈ N) [5; EG]
7. n'=1 ∨ ∃y (n'=y' ∧ y ∈ N) [6; addition]
8. n' ∈N [7,2; MP2]
9. If n ∈N then n' ∈N [1-8;CSC1]
10. ∀m[If m ∈N then m' ∈N] [9; UG]

Q.E.D.

Theorem 3 is one of Peano's 5 axioms.

P3 is one of Peano's 5 axioms. It states that a predecessor of a number is unique.

And, if x=y then x'=y' follows purely by the properties of equality. It states that the successor of a number is unique.

So if 1' is a successor of 1, then 1' is the successor of 1.

By recursive uses of P1, we generate a sequence of true propositions.

1 ∈N, 1' ∈N, 1'' ∈N,...

---

Notice that

0'=1

0''=2

0'''=3

etc.

Thus, if you count the number of successor symbols, that is equivalent to the Arabic numeral.

Df. n = 0⁽ⁿ⁾

The existential part of P1 requires that y be instantiated by a specific natural number. P1 only explicitly names 1 as denoting a specific natural number. By recursion, the only other specific natural numbers, according to P1, are denoted by terms of the sequence: 0'',0''',...,0⁽ⁿ⁾,...

Therefore,

n denotes an arbitrary natural number iff n = 0⁽ⁿ⁾

Theorem 4: Let P(m) be an arbitrary propositional function of m. If P(1) ∧ ∀m∈N[P(m) → P(m')] then ∀m∈N[P(m)]

1. P(1) ∧ ∀m∈N[P(m) → P(m')] [OSC1]
2. ~∀m∈N[P(m)] [OSC2]
3. ∃m∈N[~P(m)] [2; QN]
4. n ∈N ∧ ~P(n) [3; EI]
5. ~P(n) [4; simplification 2]
6. n = 0⁽ⁿ⁾ [Df]
7. ~P(0⁽ⁿ⁾) [5,6; substitution]
8. P(0') [1; simplification 1]
9. If P(0') then P(0'') [1; UI]
10. P(0'') [8,9; MP X 1]
11. If P(0'') then P(0''') [1; UI]
12. P(0''') [10,11; MP X 2] ...
13. P(0⁽ⁿ⁾) [MP X n-1]
14. P(0⁽ⁿ⁾) ∧ ~P(0⁽ⁿ⁾) [13,7; conjunction]
15. If~∀m∈N[P(m)] then contradiction [2-14; CSC2]
16. ∀m∈N[P(m)] [15; RAA]
17. If P(1) ∧ ∀m∈N[P(m) → P(m')] then ∀m∈N[P(m)] [1-16; CSC1]

Q.E.D.

Theorem 4 is weak mathematical induction. Thus, mathematical induction is provable in this Axiomatic system for the natural numbers.

Thus, you can prove mathematical induction without the notion of set, using first order predicate logic. Everywhere I used ∈ N, replace that with the predicate "denotes a natural number".

A system equivalent to Peano's system less induction is:

A1. If x=1 ∨ ∃y (x=y' ∧ y ∈ N) then x ∈N

A2. 0'=1 ∧ 0 ∉ N

A3. If x'=y' then x=y

IF you add to this the converse of A1, namely

A4. If x ∈N then x=1 ∨ ∃y (x=y' ∧ y ∈ N)

THEN you can prove induction.

A1 states "x=1 ∨ ∃y (x=y' ∧ y ∈ N)" is a sufficient condition for x to denote a natural number.

A4 states that condition is necessary for x to denote a natural number.