Suggest edit — principle of induction

Title

Name

Note

---
title: "principle of induction"
type: concept
related: [Natural Numbers, Strong Induction, Principle Of Induction]
source: https://www.jemoka.com/posts/kbhprinciple_of_induction/
confidence: high
status: active
---

The principle of induction is a technique used to prove the relationship between a smaller subset
The following three statements are equivalent.
standard induction Suppose \(S \subset \mathbb{N}\), which is non-empty. If \(S\) is a non-empty subset such that \(0 \in S\), and for all \(n \in \mathbb{N}\), \(n \in S \implies n+1 \in S\). Then, \(S = \mathbb{N}\).
strong induction Suppose \(S \subset \mathbb{N}\), which is non-empty. If \(S\) is a non-empty subset such that \(0 \in S\), and for all \(n \in \mathbb{N}\), \(\{0, \dots, n\} \in S \implies n+1 \in S\). Then, \(S = \mathbb{N}\).
well-ordering principle If \(S \subset \mathbb{N}\) is non empty, then it has a smallest element
PROOF: assume well-ordering principle, prove standard induction Given \(S \in \mathbb{N}\), such that \(0 \in S\), whenever \(n \in S\), then \(n+1\) is also in \(S\). We desire that that \(S\) is the natural numbers.
Assume for the sake of contradiction \(S \neq \mathbb{N}\). Define \(T = \mathbb{N} \setminus S\).
Assume \(T\) is non-empty. The WOP tells us that \(T\) has a smallest element \(t \in T\). We know that \(t \neq 0\), because \(0 \in S\). Therefore, \(t-1 \in \mathbb{N}\). But, \(t-1 &lt; t\), which means that \(t-1 \in S\). But by the statement of the givens, \((t-1) \in S \implies (t-1)+1 = t \in S\). Reaching contradiction. \(\blacksquare\)
assuming strong induction, proof well-ordering principle Assume \(S\) has no smallest element. Create some \(T = \mathbb{N} \setminus S\). Now, \(0 \in T\) because otherwise \(0 \in S\) would be the smallest element. Now, consider \(0, 1, &hellip; n \in T\), we notice that \(n+1\) must be in \(T\) as well. By strong induction, we have that \(T = \mathbb{N}\) and \(S\) is empty.