Third Principle of Mathematical Induction
Jump to navigation
Jump to search
This article needs to be linked to other articles. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{MissingLinks}} from the code. |
Theorem
Let $\map P n$ be a propositional function depending on $n \in \N$.
If:
- $(1): \quad \map P n$ is true for all $n \le d$ for some $d \in \N$
- $(2): \quad \forall m \in \N: \paren {\forall k \in \N, m \le k < m + d: \map P k} \implies \map P {m + d}$
then $\map P n$ is true for all $n \in \N$.
Proof
Let $A = \set {n \in \N: \map P n}$.
We show that $A$ is an inductive set.
By $(1)$:
- $\forall 1 \le i \le d: i \in A$
Let:
- $\forall x \ge d: \set {1, 2, \dotsc, x} \subset A$
Then by definition of $A$:
- $\forall k \in \N: x - \paren {d - 1} \le k < x + 1: \map P k$
Thus $\map P {x + 1} \implies x + 1 \in A$
Thus $A$ is an inductive set.
Thus by the fifth axiom of Peano:
- $\forall n \in \N: A = \N \implies \map P n$
$\blacksquare$
This article needs proofreading. Please check it for mathematical errors. If you believe there are none, please remove {{Proofread}} from the code.To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Proofread}} from the code. |
Sources
- 1964: W.E. Deskins: Abstract Algebra ... (previous) ... (next): Exercise $2.3: \ 5$