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

Result R800 on D1095: Ordered set of natural numbers
Subresult of R796: Principle of weak mathematical induction

Proof by principle of weak mathematical induction

Formulation 1

Let $P = (\mathbb{Z}, {\leq})$ be the D1098: Ordered set of integers such that

(i)	$f : \mathbb{Z} \to \{ 0, 1 \}$ is a D218: Boolean function on $\mathbb{Z}$
(ii)	$a \in \mathbb{Z}$ is an D995: Integer
(iii)	\begin{equation} [a, \infty) : = \{ n \in \mathbb{Z} : n \geq a \} \end{equation}
(iv)	\begin{equation} X : = \{ n \in \mathbb{Z} : f(n) = 1 \} \end{equation}
(v)	\begin{equation} a \in X \subseteq [a, \infty) \end{equation}
(vi)	\begin{equation} \forall \, n \in \mathbb{Z} \left( n \in X \quad \implies \quad n + 1 \in X \right) \end{equation}

Then \begin{equation} X = [a, \infty) \end{equation}

Remarks

▶

Remark 0

In a proof by weak induction, we interpret $f$ to be a predicate statement depending on an integer $n \in \mathbb{Z}$ which we want to show to be true for all integers on some ray $[a, \infty) : = \{ n \in \mathbb{Z} : n \geq a \}$ 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{Z} : f(n) = 1\} = [a, \infty)$.

Proofs

Proof 0

Let $P = (\mathbb{Z}, {\leq})$ be the D1098: Ordered set of integers such that

(i)	$f : \mathbb{Z} \to \{ 0, 1 \}$ is a D218: Boolean function on $\mathbb{Z}$
(ii)	$a \in \mathbb{Z}$ is an D995: Integer
(iii)	\begin{equation} [a, \infty) : = \{ n \in \mathbb{Z} : n \geq a \} \end{equation}
(iv)	\begin{equation} X : = \{ n \in \mathbb{Z} : f(n) = 1 \} \end{equation}
(v)	\begin{equation} a \in X \subseteq [a, \infty) \end{equation}
(vi)	\begin{equation} \forall \, n \in \mathbb{Z} \left( n \in X \quad \implies \quad n + 1 \in X \right) \end{equation}

This result is a particular case of R796: Principle of weak mathematical induction. $\square$