principle of finite induction proven from the well-ordering principle for natural numbers

We give a proof for the “strong” formulation.

Let $S$ be a set of natural numbers such that $n$ belongs to $S$ whenever all numbers less than $n$ belong to $S$ (i.e., assume $\\forall n(\\forall m<n\\ m\\in S)\\Rightarrow n\\in S$ , where the quantifiers range over all natural numbers). For indirect proof, suppose that $S$ is not the set of natural numbers $\\mathbb{N}$ . That is, the complement $\\mathbb{N}\\setminus S$ is nonempty. The well-ordering principle for natural numbers says that $\\mathbb{N}\\setminus S$ has a smallest element; call it $a$ . By assumption, the statement $(\\forall m<a\\ m\\in S)\\Rightarrow a\\in S$ holds. Equivalently, the contrapositive statement $a\\in\\mathbb{N}\\setminus S\\Rightarrow\\exists m<a\\ m\\in\\mathbb{N}\\setminus S$ holds. This gives a contradition since the element $a$ is an element of $\\mathbb{N}\\setminus S$ and is, moreover, the smallest element of $\\mathbb{N}\\setminus S$ .

单词	PrincipleOfFiniteInductionProvenFromTheWellorderingPrincipleForNaturalNumbers
释义	principle of finite induction proven from the well-ordering principle for natural numbers We give a proof for the “strong” formulation. Let $S$ be a set of natural numbers such that $n$ belongs to $S$ whenever all numbers less than $n$ belong to $S$ (i.e., assume $\\forall n(\\forall m<n\\ m\\in S)\\Rightarrow n\\in S$ , where the quantifiers range over all natural numbers). For indirect proof, suppose that $S$ is not the set of natural numbers $\\mathbb{N}$ . That is, the complement $\\mathbb{N}\\setminus S$ is nonempty. The well-ordering principle for natural numbers says that $\\mathbb{N}\\setminus S$ has a smallest element; call it $a$ . By assumption, the statement $(\\forall m<a\\ m\\in S)\\Rightarrow a\\in S$ holds. Equivalently, the contrapositive statement $a\\in\\mathbb{N}\\setminus S\\Rightarrow\\exists m<a\\ m\\in\\mathbb{N}\\setminus S$ holds. This gives a contradition since the element $a$ is an element of $\\mathbb{N}\\setminus S$ and is, moreover, the smallest element of $\\mathbb{N}\\setminus S$ .
随便看	proof of Fatou’s lemma ProofOfFaulhabersFormula proof of Faulhaber’s formula ProofOfFeketesSubadditiveLemma Proof of Fekete’s subadditive lemma ProofOfFermatsLittleTheoremUsingLagrangesTheorem ProofOfFermatsTheoremstationaryPoints proof of Fermat’s little theorem using Lagrange’s theorem proof of Fermat’s Theorem (stationary points) ProofOfFiniteExtensionsOfDedekindDomainsAreDedekind proof of finite extensions of Dedekind domains are Dedekind ProofOfFiniteInseparableExtensionsOfDedekindDomainsAreDedekind proof of finite inseparable extensions of Dedekind domains are Dedekind ProofOfFinitelyGeneratedTorsionfreeModulesOverPruferDomains proof of finitely generated torsion-free modules over Prüfer domains ProofOfFiniteSeparableExtensionsOfDedekindDomainsAreDedekind proof of finite separable extensions of Dedekind domains are Dedekind ProofOfFirstIsomorphismTheorem proof of first isomorphism theorem ProofOfFixedPointsOfNormalFunctions proof of fixed points of normal functions ProofOfFodorsLemma proof of Fodor’s lemma ProofOfFourthIsomorphismTheorem proof of fourth isomorphism theorem