# Principle of Mathematical Induction/One-Based/Proof 2

Jump to navigation
Jump to search

## Theorem

Let $\map P n$ be a propositional function depending on $n \in \N_{>0}$.

Suppose that:

- $(1): \quad \map P 1$ is true

- $(2): \quad \forall k \in \N_{>0}: k \ge 1 : \map P k \implies \map P {k + 1}$

Then:

- $\map P n$ is true for all $n \in \N_{>0}$.

## Proof

Let $M$ be the set of all $n \in \N_{>0}$ for which $\map P n$ holds.

By $(1)$ we have that $1 \in M$.

By $(2)$ we have that if $k \in M$ then $k + 1 \in M$.

From the Axiomatization of $1$-Based Natural Numbers, Axiom $(F)$, it follows that $M = \N_{>0}$.

$\blacksquare$

## Sources

- 1964: W.E. Deskins:
*Abstract Algebra*... (previous) ... (next): $\S 2.1$: Theorem $2.1$

- 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$