Proof of induction principle, Proof falsification

Question

I just had a very frustating conversation with one of my Professors. I'm tutoring for a lecture course on Analysis and in the lecture he gave a proof of the induction principle. I was trying to tell him that it is not correct because it is cyclic, but he doesn't see my point. So the argument is as follows:

Theorem. Assume that

1. $\varphi(1)$ is true
2. $\forall n\in\mathbb{N} : (\varphi(n)\rightarrow \varphi(n+1))$

then $\forall n\in\mathbb{N} : \varphi(n)$

Proof. Assume there is $k\in\mathbb{N}$ s.t. $\neg\varphi(k)$. We do know at this point that there is a predecessor-chain of lenght k resulting in $1$, i.e. there are $c_i\in\mathbb{N}$ for $1\leq i\leq k$ s.t. $c_{i+1}=c_i+1, c_1=1$ and $c_k=k$.

Now by assumption we have $\neg\varphi(c_k) \stackrel{2)}{\Rightarrow}\neg\varphi(c_{k-1}) \stackrel{2)}{\Rightarrow}\dots \stackrel{2)}{\Rightarrow}\neg\varphi(c_1)$ contradicting 1).

Now I claim that to formaly proof the "$\dots$" part, we already implicitly use the induction principle, because we use the fact that the property $\neg\varphi$ inherits down along arbitrary long predecessor chains, ie. we need the statement:

For all $n\in\mathbb{N}$: If $c_i\in\mathbb{N}$ for $1\leq i\leq n$ s.t. $c_{i+1}=c_i+1$ and $\neg\varphi(c_n)$ then $\neg\varphi(c_1)$.

And this Statement can only be proved by induction.

He claimed, that we do not need this statement, because we pick a fixed $k$ and $k$ is finite, so we only have to go down a finite number of times.

However I insist that one does need it, since while its clearly true that one only has to go down a finite number of times, this number could be an arbitrary large finite number, since of course $k$ can be arbitrary large, therefore we have to proof the downward transfer for arbitrary long predecessor chains and hence need above statement.

I don't know what more I could say to convince him.

Edit: Definition. $\mathbb{N}$ is a set s.t.

1. $1\in\mathbb{N}$
2. There exists a injective function $\Phi:\mathbb{N}\to\mathbb{N}$ with $\forall n : \Phi(n)\neq 1$
3. If $A\subseteq\mathbb{N}$ and A satisfies 1) and 2) then $A=\mathbb{N}$

For readability I also write $n+1$ for $\Phi(n)$ above.

Answer 1

I wouldn't say that he's necessarily wrong, but it's a questionable approach. There could be a hidden circular reasoning buried in the details, but basically without the proof of the details you cannot say.

The definition of $\mathbb N$ basically already contains the induction principle in the third requirement. Let $A=\{x\in\mathbb N: \phi(x)\}$ one could easily see that this is a subset of $\mathbb N$ that fulfills the first and second requirements and therefor according to the third requirement we have $A=\mathbb N$, therefore $\phi(x)$ holds for all $x\in\mathbb N$. This shows that basically anything provable with the induction principle can be proved using the third requirement instead (so anything you say is proved by using the induction principle could have been proven without it).

It's not just the $\cdots$ part that's problematic in his proof, also the fact that there's a predecessor chain at all, the fact that it would terminate at $1$ need to be proven first too. Any these proofs that are prerequisite of the proof of the induction principle could have used induction principle itself (but could have been shown using the third requirement instead). Even if it's not wrong to do so one would question why one would produce a lot of proofs that begs for the induction principle in order to prove the induction principle when it was readily provable directly instead (it's like a mathematical Rube Goldstein Machine).

Actually you will have to use the third requirement to end up with the induction principle anyway (so you can not use that as an excuse - that you're using a more complicated proof to get rid of one prerequisite). If you drop the last statement you'll end up in a definition from which you can't prove the induction principle. To see this one could for example construct a set that fulfills the Peano's axiom except the induction principle that it doesn't: for example just extend $\mathbb N$ with a new element $\infty = \Phi(\infty)$. We see that the first two requirements are met, but not the third - in this set we can easily see that induction principle doesn't work as we could for example consider $\phi(x): x\in\mathbb N$.

One detail about that formulation of the induction principle is that it's a statement about an arbitrary statement. Formally this isn't allowed and therefore it should be considered what's called a theorem schema. This means that for each statement $\phi$ you can substitute that into the schema and get a valid theorem instance.

A proof of such a schema is not the same as a proof in the formal sense as it's more of a recipe of how to prove any theorem instance. As such the proof schema itself need not be formally verifiable as long as each instantiation of it is. Now if there's a concrete counter example we would have a $\phi$ and $k$ and expanding the proof schema would actually result in a formally valid proof.

Answer 2

The problem lies in his statement "go down a finite number of times". This statement is informal and does not in it self show anything. In order to use this statement and expound on it he would actually have to show that he may do this for $k=1$, $k=2$, $k=3$, etc. or if he do not wish do do an infinite algorithm, he may use induction.

Answer 3

$\dots$ is not a mathematical operator. If your prof thinks his proof is correct, then he should be able to write it without $\dots$ . When $\dots$ is used correctly, it is simply tedious to replace it with symbolic logic. In the above case, it is impossible to replace it with symbolic logic so the professors proof is wrong.

Many attempts at proofs of induction can be disregarded due to a simple transform: instead of considering the natural numbers $\mathbb N$, consider the set of polynomials with natural number coefficients, $\mathbb N [x]$. $\mathbb N [x]$ shares most properties of natural numbers, such as being injective (wrt adding one) and having a zero. It is also totally well ordered. However, it is not an inductive set. So any "proof" of induction that doesn't make an assumption true of $\mathbb N$ but not $\mathbb N[x]$ is wrong.

Answer 4

After a lot of thought and back and forth in the comments, I decided that your professor is probably right.

I'm assuming pre-induction we are allowed to do any number of finite iterations:

So if:

1)True for $n =1$

2)If true for $n$ then true for $n +1$

Then we can conclude:

3) True for $k$ after $k - 1$ iterations.

But that's all. We can't conclude that it is true for all $n$ simply because we can show it is true for arbitrary $n$. arbitrary $\not \implies$ every....yet.

If, however, we assume 2) and 1) and that it is not true for a finite $k$ then we can show it is not true for $k - 1$.

We can re-iterate this $k -1$ times and conclude it is not true for $n = 1$ which is a contradiction. So there is no $k$ that this is not true for. Hence it is true for all $n$.

The subtle but crucial difference between these two methods, is that $k$ was not an arbitrary number, and the number of iterations to get to $n = 1$ was finite, precise and determined.

And it only takes one counter example to disprove a universal statement, but it takes an infinite multitude to prove it directly. (Unless we can prove arbitrary $\implies$ every which I think we can... maybe.)