ThmDex – An index of mathematical definitions, results, and conjectures.

Result R5104 on D1095: Ordered set of natural numbers

Proof by principle of weak mathematical induction on the natural numbers

Formulation 0

Let $P = (\mathbb{N}, {\leq})$ be the D1095: Ordered set of natural numbers such that

(i)	$f : \mathbb{N} \to \{ 0, 1 \}$ is a D218: Boolean function on $\mathbb{N}$
(ii)	\begin{equation} X : = \{ n \in \mathbb{N} : f(n) = 1 \} \end{equation}
(iii)	\begin{equation} 0 \in X \subseteq \mathbb{N} \end{equation}
(iv)	\begin{equation} \forall \, n \in \mathbb{N} \left( n \in X \quad \implies \quad n + 1 \in X \right) \end{equation}

Then \begin{equation} X = \mathbb{N} \end{equation}

Remarks

▶

Remark 0

In a proof by weak induction on the natural numbers, we interpret $f$ to be a predicate statement depending on a natural number $n \in \mathbb{N}$ which we want to show to be true for all natural numbers $\mathbb{N}$ where the statement being true for $n$ is understood to be encoded by $f(n) = 1$. To accomplish this, we must show that $\{ n \in \mathbb{N} : f(n) = 1\} = \mathbb{N}$.

Proofs

Proof 0

Let $P = (\mathbb{N}, {\leq})$ be the D1095: Ordered set of natural numbers such that

(i)	$f : \mathbb{N} \to \{ 0, 1 \}$ is a D218: Boolean function on $\mathbb{N}$
(ii)	\begin{equation} X : = \{ n \in \mathbb{N} : f(n) = 1 \} \end{equation}
(iii)	\begin{equation} 0 \in X \subseteq \mathbb{N} \end{equation}
(iv)	\begin{equation} \forall \, n \in \mathbb{N} \left( n \in X \quad \implies \quad n + 1 \in X \right) \end{equation}

This result is a particular case of R797: Principle of weak mathematical induction on the natural numbers. $\square$