User:Prime.mover/Proof Structures/Proof by General Induction

Proof by General Induction

The proof proceeds by general induction.

For all $x \in M$, let $\map P x$ be the proposition:

$\text {proposition}_x$

Basis for the Induction

$\map P \O$ is the case:

$\text {proposition}_\O$

Thus $\map P \O$ is seen to hold.

This is the basis for the induction.

Induction Hypothesis

Now it needs to be shown that if $\map P x$ is true, where $x \in M$, then it logically follows that $\map P {\map g x}$ is true.

So this is the induction hypothesis:

$\text {proposition}_x$

from which it is to be shown that:

$\text {proposition}_{\map g x}$

Induction Step

This is the induction step:

\(\ds \)

\(=\)

\(\ds \)

\(\ds \leadsto \ \ \)

\(\ds \)

\(=\)

\(\ds \)

So $\map P x \implies \map P {\map g x}$ and the result follows by the Principle of General Induction.

Therefore:

$\forall x \in M: \text {proposition}_x$