User:IssaRice/An induction proof that does not use the induction hypothesis

this comes from https://taoanalysis.wordpress.com/2020/03/16/exercise-2-2-2/

the actual exercise is to show that if a is a positive number, then there exists exactly one natural number b such that b++ = a. the uniqueness part is actually not the tricky part; all of the tricky induction stuff is going on in showing existence. so let's just simply things by talking about the statement "if a is a positive number, then there exists some natural number b such that b++ = a" instead.

NOTE: as in tao's book, "n is positive" is defined as "n is not equal to 0".

Let's name the statement in question, "if a is a positive number, then there exists some natural number b such that b++ = a", as "every positive number is a successor".

there's a bunch of things we can ask about this. let's tackle these in turn.

does this exercise require induction?

you might wonder, since we aren't even using the IH, whether induction is even required. shouldn't there be an induction-free proof?

we can actually show that induction is required. the trick is to produce a mathematical structure that's similar to the natural numbers, but which only follows peano axioms 1-4 (not 5, induction), and for which the statement in question ("if a is a positive number, then there exists some natural number b such that b++ = a") is also false. this shows that, if we don't accept induction as an axiom (i.e. we don't try to make use of it) then we can't prove the statement in question, since the statement isn't even true in a concrete structure we behold!

now, what kind of structure could work? a simple example is $\mathbf {N} \cup \{n+0.5:n\in \mathbf {N} \}=\mathbf {N} \cup \{0.5,1.5,2.5,3.5,\ldots \}$ . to work with the rest of the peano axioms, we have to explain how the successor operation works. for any number in this set, we define n++ to be n+1. (this isn't circular because we're assuming we already know what N is and what the integers are.) "n is positive" is still defined to be "n is not equal to 0".

you can verify that this structure obeys all of the peano axioms 1-4. 0 is in the set. if n is in the set, then n++ is in the set (prove by cases based on whether it's a natural number or a half-integer). 0 is not a successor (a natural number can't have 0 as a successor due to the ordinary peano axiom 3; and a half integer can't have 0 as a successor since a successor of a half integer is also a half integer). if n++ = m++, then n=m (just use algebra!).

but now, the induction axiom does not hold for this structure. to show this, we give a counterexample of a predicate. let P(n) = "n is a half integer". P(0) is true. and if P(n) is true, then P(n++) is also true. but P(0.5) is clearly false! so induction doesn't work.

if the exercise could be done using only peano axioms 1-4 without induction, then in this structure, we should also be able to "do the exercise" by proving the statement. but now, observe that the statement is false. 0.5 is positive (i.e. not equal to 0) but there is no n in the structure such that n++ = 0.5. This shows that we must use induction if we want to solve this exercise; induction isn't some cheap trick to easily prove the result but rather a necessity.

why is the induction hypothesis not used?

are there any other induction proofs where the induction hypothesis is not used?

the proof of Proposition 2.2.8 in the book is another example.

i'm not aware of any other examples besides these two.

does this exercise require induction?

why is the induction hypothesis not used?

are there any other induction proofs where the induction hypothesis is not used?

See also