# Axiomless proof of induction and well ordering principle

It is said that "Well-ordering Principle, Induction and Strong Induction" - each two can be proved from the other. However none can be proved independently.

Now, can't we say (without holding any axioms true) that a finite step process must end? (I have seen mathematics texts use this assumption in various proofs.) In that case:

Induction: We have: $P(0)$ holds and $P(k) => P(k+1)$. Now, let there exist an element $m∈N$ for which $P(m)$ is false. Now $P(0) \implies P(1)$ and now $P(1) \implies P(2)$ and now...(The process goes on.) Thus conducting $m-1$ steps, we ultimately achieve that $P(m)$ is true, since $P(1)$ is true in the first place. This is achievable since $m$ must be finite, and so should be $m-1$. This contradicts that $P(m)$ is false. Hence there must be no such $m$.

Well-Ordering: Let $S \subset \mathbb N, S\neq \varnothing$ . Now we choose an arbitrary element $k_0$ in it. Set $k = k_0$ Now:

Step 1: If $k$ is the least element in $S$, go to step 3. Else go to step 2.

Step 2: Since $k$ is not the least element, there must exist $x \in S : x < k$. Set $x = k$. Now go back to step 1.

Step 3: End

This is a finite step process(at most $k_0 - 1$ times looped back to step 1). Hence we will ultimately have a least element.

What's wrong here?

• How do you know that the process ends? Answer: you used induction to assert that every $k_0 \in \mathbb{N}$ is finite. – Patrick Stevens Feb 3 '18 at 18:09
• I guess u are right.. Actually how do we define "finite"? – Rabeeb Ibrat Feb 3 '18 at 18:12
• I equivocated there between "member of $\mathbb{N}$" and "object such that, if you subtract $1$ from it as many times as you can, you will get $0$ eventually". – Patrick Stevens Feb 3 '18 at 18:26
• I simply meant that if n = (1+1+...1(n times)), then n-(1+1+...1(n times)) must be 0. (It's all in the number system!) And nowhere did I see anyone mention anything about finitism having to do anything with induction. Because then, how will you define finitism of real numbers? – Rabeeb Ibrat Feb 5 '18 at 20:43
• Consider a nonstandard model of the naturals. Pick an arbitrary nonstandard element $k$ of that model. Now keep on subtracting one from it. Come back to me when you hit $0$; I'll wait. (To make it completely clear that your procedure isn't going to terminate in any finite time, take the nonstandard model to be uncountable and take $k$ to be uncountably far in.) – Patrick Stevens Feb 5 '18 at 21:08