Principle of Mathematical Induction/Zero-Based
Jump to navigation
Jump to search
Theorem
Let $\map P n$ be a propositional function depending on $n \in \N$.
Suppose that:
- $(1): \quad \map P 0$ is true
- $(2): \quad \forall k \in \N: k \ge 0 : \map P k \implies \map P {k + 1}$
Then:
- $\map P n$ is true for all $n \in \N$.
Proof
Consider $\N$ defined as a Peano structure.
The result follows from Principle of Mathematical Induction for Peano Structure.
$\blacksquare$
Also see
- Results about Proofs by Induction can be found here.
Sources
- 1982: P.M. Cohn: Algebra Volume 1 (2nd ed.) ... (previous) ... (next): Chapter $2$: Integers and natural numbers: $\S 2.1$: The integers
- 1996: H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability ... (previous) ... (next): Appendix $\text{A}.12$: Induction
- 2008: Paul Halmos and Steven Givant: Introduction to Boolean Algebras ... (previous) ... (next): Appendix $\text{A}$: Set Theory: Induction
- 2012: M. Ben-Ari: Mathematical Logic for Computer Science (3rd ed.) ... (previous): Appendix $\text{A}.6$