Can induction be logically derived?

Question

I already know how induction works but logically it's often stated:

$$\forall P, (P(0) \land (\forall k, P(k) \implies P(k+1)) \implies \forall n, P(n))$$

Is this logical relationship something you can show or prove or is it something we just accept as true from our intuition / taken as true via axiom of induction?

Answer 1

Induction is one of the forms of argument we allow ourselves 'in the $\textit{metatheory.}$' I.e. most of our theorems and arguments are based on a very strictly and concretely defined "theory" with a very strictly and concretely defined notion of what is a correctly formed 'phrase' and what is a correctly formed 'argument'. All of this is made $\textit{syntactically}$, and these arguments are what we call $\textit{formal proofs}$. (A theorem is never presented as a formal proof, and you only actually read or write them in a basic logic course; henceforth a correct argument is one that you $could$ transcribe into a formal proof if dared to.)

But the construction and definition of this "theory," and our arguments to conclude that this theory $\textit{works}$, can't, of course, be based on any rigorous system; it is the $\textit{first}$ and $\textit{basic}$ rigorous system. The reasoning we permit outselves to make outside of our rigorous systems is often referred to as "the metatheory" and we are extremely careful of what we allow us to state as true, here in the metatheory, outside of our rigorous system. These statements are made in natural language, i.e. what we're using right now, and although sometimes written as mathematical symbols, these symbols are just for clearness and there's nothing $\textit{formal}$ about them. And, in this unrigorous, natural, and informal reasoning, we allow ourselves induction. (Of length $\omega$ anyway.)

The definition of a well formed sentence, for example, is done inductively, and $\textit{metatheorems}$ about it are proved by $\textit{metatheoretical induction}$ (also sometimes called $\textit{external induction}$), i.e. what you may call intuitive, unfundamented induction. You can probably find more info on this if you search around using these terms.

Answer 2

There is nothing mysterious or counter-intuitive about induction. It can hold even on finite sets, e.g. $N = \{0\}$ with $S(0)=0$ where $S$ is the "successor function" on $N$. It is then trivial to prove that induction holds on $N$, i.e. $\forall P\subset N:[0\in P \land \forall x\in P: [S(x)\in P] \implies P=N]$.

Similarly for $N=\{0, 1\}$, $0\neq 1$, $S(0)=1$ and $S(1)=0$.

In general, for any set $X$ (finite or otherwise), $x_0\in X$, and $S: X\to X$, it can be shown that there exists $N =\{x_0, S(x_0), S(S(x_0)), \cdots \}$ such that induction holds on N, i.e. $\forall P\subset N:[x_0\in P \land \forall x\in P: [S(x)\in P] \implies P=N]$.

Answer 3

We can prove Principle of Mathematical Induction by using Contrapositive Method

WELL ORDERED SET : A set $\mathcal{S}$ is "Well-Ordered" if EVERY non-empty subsets of $\mathcal{S}$ has a Least Element.
Example : $\mathbb{N}$

• $\mathbb{Z}$ is NOT well-ordered, $\{x\in\mathbb{Z} : x<0\}$ has no least element
• $\mathbb{R}$ is NOT well-ordered, $\{x\in\mathbb{R} : x>1\}$ has no least element

We will exploit this property of $\mathbb{N}$.

Statement of PMI for $\mathbb{N}$ $$( P(n_{o}) \wedge [\forall k {P(k) \rightarrow P(k+1)}] ) \rightarrow \forall n P(n)$$

Let $n_o=1$.

To validate Implication Statement: In order to prove the statement “if $p$ then $q$” we need to show that any one of the following case is true.

• Case 1 : By assuming that $p$ is $\color{green}{True}$, prove that $q$ must be $\color{green}{True}$. (Direct Method)
• Case 2 : By assuming that $q$ is $\color{red}{False}$, prove that $p$ must be $\color{red}{False}$. (Contrapositive Method)

[Page $20$ of this PDF]

We will use Case 2 but with a twist, we will assume that $q$ is $\color{red}{False}$ [and $p$ is $\color{green}{True}$] and later arrive at conclusion that $p \color{red}{\text{ cannot be True}}$.

Let us Assume that even after proving SUFFICIENT CONDITION (Antecedent/LHS of Arrow), still RHS (Consequence) is $\color{red}{Not}$ fulfilled.

Assuming there is atleast one positive integer $n$ for which $P(n)$ is $\color{red}{\text{False}}$.
Let $\mathcal{X}$ be the Set of positive integers for which $P(n)$ is $\color{red}{\text{False}}$.

Mathematically, $$\mathcal{X} = \{ n : \neg P(n) \}$$ Because of our assumption, $\mathcal{X}$ is non-empty.

Since, $\mathcal{X} \subset \mathbb{N}$ and $\mathbb{N}$ is Well-Ordered. Therefore, by well-ordering property, $\mathcal{X}$ has a least element. [Definition of Well-Ordered Set!].
Let it be $m$

Now, $m \neq 1$ since $P(1)$ holds! [We have proved Sufficient Condition]
Therefore, $m>1$

Since $m$ is Positive, and $m>1$. Thus, $(m-1)$ must be a positive integer. Now, $$m-1 < m$$ but still $(m-1)$ is not least element.
Thus, $(m-1) \notin \mathcal{X}$

This implies $P(m-1)$ must be $\color{green}{\text{True}}$. [Otherwise, it would have been in $\mathcal{X}$]

Since, $P(k) \rightarrow P(k+1)$ [We have proved Sufficient Condition]
Therefore, $P(m)$ must be $\color{green}{True}$.

This CONTRADICTS $P(m)$ being $\color{red}{False}$.

Hence, our assumption was Wrong. If LHS of Arrow (Antecedent) Holds, then RHS (Consequence) will definitely hold!

Thus, Principle of Mathematical Induction is backed by Logic!