nyuuzyou/wikis huggingface dataset:
Principle of Finite Choice

== Theorem ==
Let $I$ be a non-empty finite indexing set.
Let $\family {S_i}_{i \mathop \in I}$ be an $I$-indexed family of non-empty sets.
Then there exists an $I$-indexed family $\family {x_i}_{i \mathop \in I}$ such that:
:$\forall i \in I: x_i \in S_i$
That is, there exists a mapping:
:$\ds f: I \to \bigcup_{i \mathop \in I} S_i$
such that:
:$\forall i \in I: \map f i \in S_i$
== Proof ==
We use the Principle of Mathematical Induction on the cardinality of $I$.
=== Basis for the Induction ===
Let $\card I = 1$.
Let $j \in I$.
Then $I = \set j$. 
By the definition of a non-empty set, there exists an $x \in S_j$.
Hence, there exists a mapping $f: I \to S_j$ such that $\map f j = x$.
Since $\forall i \in I: i = j$, the result is indeed seen to hold for $\card I = 1$.
This is the basis for the induction
=== Induction Hypothesis ===
Assume that the theorem holds for all $I$ with $\card I = n$.
This is the induction hypothesis.
=== Induction Step ===
Now, suppose that $\card I = n + 1$. 
Let $j \in I$.
Let $J = I \setminus \set j$.
By Cardinality Less One, $\card J = n$.
By the induction hypothesis, there exists a mapping:
:$\ds g: J \to \bigcup_{i \mathop \in J} S_i$
such that:
:$\forall i \in J: \map g i \in S_i$
By the definition of a non-empty set, there exists a $y \in S_j$.
Hence, there exists a mapping:
:$\ds f: I \to \bigcup_{i \mathop \in I} S_i$
such that:
:$\ds \forall i \in I: \map f i = \begin{cases}
\map g i & : i \ne j \\
y & : i = j
\end{cases}$
Then:
:$\forall i \in I: \map f i \in S_i$
as desired.
== Sources ==
* : $\S 15$: The Axiom of Choice
* : $1.$ Introduction: $1.1$ The Axiom of Choice
Category:Choice Functions
Category:Named Theorems
Category:Proofs by Induction
Principle of Finite Induction

== Theorem ==
Let $n_0 \in \Z$ be given.
Let $\Z_{\ge n_0}$ denote the set:
:$\Z_{\ge n_0} = \set {n \in \Z: n \ge n_0}$
Let $S \subseteq \Z_{\ge n_0}$ be a subset of $\Z_{\ge n_0}$.
Suppose that:
:$(1): \quad n_0 \in S$
:$(2): \quad \forall n \ge n_0: n \in S \implies n + 1 \in S$
Then:
:$\forall n \ge n_0: n \in S$
That is:
:$S = \Z_{\ge n_0}$
The principle of finite induction is usually stated and demonstrated for $n_0$ being either $0$ or $1$.
This is often dependent upon whether the analysis of the fundamentals of mathematical logic are zero-based or one-based.
=== Zero-Based ===
=== One-Based ===
== Proof 1 ==
== Proof 2 ==
== Contexts ==
The Principle of Finite Induction can be introduced in a formal development of abstract algebra or mathematical logic in various contexts, and proved from first principles in each.
=== Peano Structure ===
== Terminology ==
== Also known as ==
== Also see ==
* Principle of Mathematical Induction
* Second Principle of Finite Induction
* Second Principle of Mathematical Induction
== Sources ==
* 
* : Appendix $\text{A}$: Set Theory: Induction
* 
* : Chapter $3$: The Natural Numbers: $\S 5$ Applications to natural numbers: Exercise $5.1$
Category:Principle of Finite Induction
Category:Mathematical Induction
Category:Proof Techniques
Principle of Finite Induction/One-Based

== Theorem ==
Let $S \subseteq \N_{>0}$ be a subset of the $1$-based natural numbers.
Suppose that:
:$(1): \quad 1 \in S$
:$(2): \quad \forall n \in \N_{>0} : n \in S \implies n + 1 \in S$
Then:
:$S = \N_{>0}$
== Proof 1 ==
== Proof 2 ==
== Sources ==
* : Chapter $1$: Properties of the Natural Numbers: $\S 20$
* : $\S 1.17$: Finite Induction and Well-Ordering for Positive Integers: $17.1$
* : Chapter $2$: Integers and natural numbers: $\S 2.1$: The integers: $\mathbf{I}$
* : Appendix $\text{A}$: Set Theory: Induction
Category:Principle of Finite Induction
Principle of Finite Induction/One-Based/Proof 1

== Theorem ==
== Proof ==
Consider $\N$ defined as a naturally ordered semigroup.
The result follows directly from Principle of Mathematical Induction for Naturally Ordered Semigroup: General Result.
== Sources ==
* : Chapter $1$: Some Preliminary Considerations: $1.1$ Mathematical Induction: Theorem $1 \text{-} 2$
Category:Principle of Finite Induction
Principle of Finite Induction/One-Based/Proof 2

== Theorem ==
== Proof ==
Let $T$ be the set of all $1$-based natural numbers not in $S$:
:$T = \N_{>0} \setminus S$
 $T$ is non-empty.
From the Well-Ordering Principle, $T$ has a smallest element.
Let this smallest element be denoted $a$.
We have been given that $1 \in S$.
So:
:$a > 1$
and so:
:$0 < a - 1 < a$
As $a$ is the smallest element of $T$, it follows that:
:$a - 1 \notin T$
That means $a - 1 \in S$.
But then by hypothesis:
:$\paren {a - 1} + 1 \in S$
But:
:$\paren {a - 1} + 1 = a$
and so $a \notin T$.
This contradicts our assumption that $a \in T$.
It follows by Proof by Contradiction that $T$ has no such smallest element.
Hence it follows that $T$ can have no elements at all.
That is:
:$\N_{>0} \setminus S = \O$
That is:
:$S = \N_{>0}$
== Sources ==
* : Chapter $1$: Some Preliminary Considerations: $1.1$ Mathematical Induction: Theorem $1 \text{-} 2$
Category:Principle of Finite Induction
Principle of Finite Induction/Peano Structure

== Theorem ==
Let $\struct {P, s, 0}$ be a Peano structure.
Let $S \subseteq P$.
Suppose that:
:$(1): \quad 0 \in S$
:$(2): \quad \forall n: n \in S \implies \map s n \in S$
Then:
:$S = P$
== Proof ==
This is nothing but a reformulation of Axiom $(P5)$ of the Peano Axioms.
Category:Peano's Axioms
Category:Principle of Finite Induction
Principle of Finite Induction/Proof 1

== Theorem ==
== Proof ==
Let $\Z_{\ge n_0} := \set {n \in \Z: n \ge n_0}$.
 $S \ne \Z_{\ge n_0}$.
Let $S' = \Z_{\ge n_0} \setminus S$.
Because $S \ne \Z_{\ge n_0}$ and $S \subseteq \Z_{\ge n_0}$, we have that $S' \ne \O$.
By definition, $\Z_{\ge n_0}$ is bounded below by $n_0$.
From Set of Integers Bounded Below by Integer has Smallest Element, $S'$ has a minimal element.
Let $k$ be this minimal element of $S'$.
By $(1)$ we have that:
:$n_0 \in S$
and so:
:$n_0 \notin S'$
Hence:
:$k \ne n_0$
and so:
:$k > n_0$
It follows that:
:$k - 1 \le n_0$
Because $k$ is the minimal element of $S'$:
:$k - 1 \notin S'$
and so:
:$k - 1 \in S$
But by $(2)$:
:$\paren {k - 1} + 1 = k \in S$
So we have:
:$k \in S$
and:
:$k \notin S$
Hence by Proof by Contradiction $S = \Z_{\ge n_0}$.
== Sources ==
* : Appendix $\text{A}.6$: Mathematical Induction: Theorem $\text{A}.6$
Category:Principle of Finite Induction
Principle of Finite Induction/Zero-Based

== Theorem ==
Let $S \subseteq \N$ be a subset of the natural numbers.
Suppose that:
:$(1): \quad 0 \in S$
:$(2): \quad \forall n \in \N : n \in S \implies n + 1 \in S$
Then:
:$S = \N$
== Proof ==
Consider $\N$ defined as a naturally ordered semigroup.
The result follows directly from Principle of Mathematical Induction for Naturally Ordered Semigroup.
== Sources ==
* : $\S 4$: Number systems $\text{I}$: Peano's Axioms
* : Appendix $\text{A}$: Set Theory: Induction
Category:Principle of Finite Induction
Principle of General Induction

== Theorem ==
Let $M$ be a class.
Let $g: M \to M$ be a mapping on $M$.
Let $M$ be minimally inductive under $g$.
Let $P: M \to \set {\T, \F}$ be a propositional function on $M$.
Suppose that:
Then:
:$\forall x \in M: \map P x = \T$
== Proof ==
We are given that $M$ is a minimally inductive class under $g$.
That is, $M$ is an inductive class under $g$ with the extra property that $M$ has no proper class which is also an inductive class under $g$.
Let $P$ be a propositional function on $M$ which has the properties specified:
:$(1): \quad \map P \O = \T$
:$(2): \quad \forall x \in M: \map P x = \T \implies \map P {\map g x} = \T$
Thus by definition, the class $S$ of all elements of $M$ such that $\map P x = \T$ is an inductive class under $g$.
But because $M$ is minimally inductive under $g$, $S$ contains all elements of $M$.
That is:
:$\forall x \in M: \map P x = \T$
as we were to show.
== Terminology ==
== Also see ==
* Principle of Mathematical Induction
* Principle of Finite Induction
== Sources ==
* : Chapter $3$: The Natural Numbers: $\S 4$ A double induction principle and its applications
Category:Mathematical Induction
Category:Proof Techniques
Category:Principle of General Induction
Principle of General Induction/Minimally Closed Class

== Theorem ==
Let $M$ be a class.
Let $g: M \to M$ be a mapping on $M$.
Let $b \in M$ such that $M$ is minimally closed under $g$ with respect to $b$.
Let $P: M \to \set {\T, \F}$ be a propositional function on $M$.
Suppose that:
:$(1): \quad \map P b = \T$
:$(2): \quad \forall x \in M: \map P x = \T \implies \map P {\map g x} = \T$
Then:
:$\forall x \in M: \map P x = \T$
== Proof ==
We are given that $M$ is minimally closed under $g$ with respect to $b$.
That is, $M$ is closed under $g$ with the extra property that $M$ has no proper class containing $b$ which is also closed under $g$.
Let $P$ be a propositional function on $M$ which has the properties specified:
:$(1): \quad \map P b = \T$
:$(2): \quad \forall x \in M: \map P x = \T \implies \map P {\map g x} = \T$
Let $S \subseteq M$ be the subclass of $M$ defined as:
:$S = \set {x \in M: \map P x}$
We have:
By definition, the class $S$ of all elements of $M$ such that $\map P x = \T$ is closed under $g$.
But because $M$ is minimally closed under $g$ with respect to $b$, if $b \in S$ then $S$ contains all elements of $M$.
That is:
:$S = M$
and so:
:$\forall x \in M: \map P x = \T$
as we were to show.
== Terminology ==
== Also see ==
* Principle of Mathematical Induction
* Principle of Finite Induction
* Principle of General Induction
Category:Mathematical Induction
Category:Proof Techniques
Category:Principle of General Induction
Principle of Induction applied to Interval of Naturally Ordered Semigroup

== Theorem ==
Let $\struct {S, \circ, \preceq}$ be a naturally ordered semigroup.
Let $\closedint p q$ be a closed interval of $\struct {S, \circ, \preceq}$.
Let $T \subseteq \closedint p q$ such that the minimal element of $\closedint p q$ is in $T$.
Let:
:$x \in T: x \prec q \implies x \circ 1 \in T$
Then:
:$T = \closedint p q$
== Proof ==
Let $T' = T \cup \set {x \in S: q \prec x}$.
Then $T'$ satisfies the conditions of the Principle of Mathematical Induction.
Therefore:
:$T' = \set {x \in S: p \preceq x}$
Therefore:
:$T = \closedint p q$
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 16$: The Natural Numbers: Corollary $16.5.2$
Category:Naturally Ordered Semigroup
Principle of Least Action

== Physical Law ==
The Principle of Least Action is a physical law which states the following:
Let $S$ be a dynamical system moving under conservative forces from point $A$ to point $B$.
The motion of $S$ takes place in such a way that the action has a stationary value all other possible trajectories from $A$ to $B$ with the same kinetic plus potential energy.
== Proof ==
== Historical Note ==
== Sources ==
* 
* 
Category:Principle of Least Action
Category:Dynamical Systems
Principle of Least Counterexample

== Theorem ==
Let $\map P n$ be a condition on $n \in \set {x \in \Z: x \ge m \in \Z}$.
Suppose that:
:$\neg \paren {\forall n \ge m: \map P n}$
(That is, not all $n \ge m$ satisfy $\map P n$.)
Then there exists a least counterexample, that is a smallest integral value of $n$ for which $\neg \map P n$.
== Proof ==
Let $S = \set {n \in \Z: n \ge m \in \Z: \neg \map P n}$.
That is, $S$ is the set of all elements of $\Z$ not less than $m$ for which the condition is false.
Since:
:$\neg \paren {\forall n \ge m: \map P n}$
it follows that:
:$S \ne \O$
Also, $S \subseteq \Z$ and is bounded below (by $m$).
Therefore $S$ has a smallest element, which proves the result.
== Also known as ==
Some sources refer to the least counterexample as the least rascal.
== Sources ==
* : $\S 10.3$: The well-ordering principle
Category:Proof Techniques
Principle of Lever

== Physical Law ==
Let $M$ be a lever in a state of equilibrium.
The mechanical advantage $\mathrm {MA}$ of $M$ is given by:
:$\mathrm {MA} = \dfrac b a$
where:
:$L$ is the load applied to the lever at point $A$
:$E$ is the effort applied to the lever at point $B$
:$a$ and $b$ are the distances from the fulcrum to points $A$ and $B$ respectively.
== Proof ==
In equilibrium, the sum of all the moments of all the external forces acting on $M$ is zero.
The moment applied by $L$ about the fulcrum is $L a$.
The moment applied by $E$ about the fulcrum is $-E b$ as it is in the opposite direction to $L$.
The mechanical advantage of $M$ is defined as:
:the ratio of the load on $M$ to the effort applied to $M$.
Hence:
Hence the result.
== Historical Note ==
== Sources ==
* 
* 
Category:Levers
Category:Mechanical Advantage
Category:Mechanics
Category:Physics
Principle of Mathematical Induction

== Theorem ==
Let $\map P n$ be a propositional function depending on $n \in \Z$.
Let $n_0 \in \Z$ be given.
Suppose that:
:$(1): \quad \map P {n_0}$ is true
:$(2): \quad \forall k \in \Z: k \ge n_0 : \map P k \implies \map P {k + 1}$
Then:
:$\map P n$ is true for all $n \in \Z$ such that $n \ge n_0$.
The Principle of Mathematical Induction is usually stated and demonstrated for $n_0$ being either $0$ or $1$.
This is often dependent upon whether the analysis of the fundamentals of mathematical logic are zero-based or one-based.
=== Zero-Based ===
=== One-Based ===
== Proof ==
== Contexts ==
The Principle of Mathematical Induction can be introduced in a formal development of abstract algebra or mathematical logic in various contexts, and proved from first principles in each.
=== Well-Ordered Set ===
=== Well-Ordered Integral Domain ===
=== Naturally Ordered Semigroup ===
=== Peano Structure ===
== Terminology ==
== Informal Analogy ==
== Warning ==
== Also defined as ==
== Also known as ==
== Also see ==
* Principle of Finite Induction
* Second Principle of Finite Induction
* Second Principle of Mathematical Induction
* Equivalence of Well-Ordering Principle and Induction
== Historical Note ==
== Sources ==
* : $\text I$. Algebra: The Method of Induction
* : $\S 0.1$. Arithmetic: Theorem $4$
* : $\S 1.17$: Finite Induction and Well-Ordering for Positive Integers: Exercise $1$
* : Chapter $1$: Preliminaries: $1.3$ Inductive Proofs
* 
* : Chapter $2$: 'And you do addition?': $\S 2.4$: Counting and mathematical induction: Definition $2.4.1$
* 
* 
* 
Category:Principle of Mathematical Induction
Category:Mathematical Induction
Category:Number Theory
Category:Named Theorems
Category:Proof Techniques
Principle of Mathematical Induction/Also defined as

== Principle of Mathematical Induction: Also known as == 
The Principle of Mathematical Induction can often be found stated more informally, inasmuch as the propositional function $P$ is referred to as "a statement about integers".
== Sources ==
* : $\text I$. Algebra: The Method of Induction
* : $\S 0.1$. Arithmetic: Theorem $4$
* : Chapter $1$: Preliminaries: $1.3$ Inductive Proofs
* 
* 
* 
Category:Principle of Mathematical Induction
Principle of Mathematical Induction/Informal Analogy

== Informal Analogy ==
:
The Principle of Mathematical Induction is often likened to a .
A line of dominoes is set up to be balanced on their ends so that if one of the dominoes is knocked over, it knocks over the next one in the line.
When the first domino is knocked over, the entire line topples, one after the other.
It follows that if either:
:$(1) \quad$ no domino is knocked over to start with (that is, the basis for the induction does not hold)
or:
:$(2) \quad$ the gap between two dominoes is too large for one domino to knocked over the next one (that is, the induction step does not hold)
then the does not work and the entire line does not fall (that is, the proposition is not proved for all $\N \ge n_0$).
== Sources ==
* : $\S 3$: Natural Numbers: $\S 3.7$: Principle of induction
* : Chapter $1$: Some Preliminary Considerations: $1.1$ Mathematical Induction
Category:Principle of Mathematical Induction
Principle of Mathematical Induction/Naturally Ordered Semigroup

== Theorem ==
Let $\struct {S, \circ, \preceq}$ be a naturally ordered semigroup.
Let $T \subseteq S$ such that $0 \in T$ and $n \in T \implies n \circ 1 \in T$.
Then $T = S$.
=== General Result ===
== Proof ==
 that $T \subsetneq S$.
That is, $T$ is a proper subset of $S$:
: $T \ne S$
Let $T' = S \setminus T$.
Then by Set Difference with Proper Subset:
:$T' \ne \O$
By , $S$ is well-ordered.
By definition of well-ordered set, it follows that $T'$ has a smallest element $x$.
By definition of $T$:
:$0 \in T$
and so by definition of $T'$:
:$0 \notin T'$
so:
:$0 \prec x$
By Sum with One is Immediate Successor in Naturally Ordered Semigroup:
:$1 \preceq x$
By the definition of a naturally ordered semigroup:
:$\exists y \in S: y \circ 1 = x$
Again by Sum with One is Immediate Successor in Naturally Ordered Semigroup:
:$y \prec x$
We have that $x$ is the smallest element of $T'$ and $y \prec x$.
Therefore:
:$y \notin T'$
and so
:$y \in T$
But from the definition of $T$:
:$y \in T \implies y \circ 1 = x \in T$
But then by the definition of $T'$:
:$x \in T' \implies x \notin T$
From this contradiction, it follows that:
:$T = S$
== Also see ==
* Principle of Mathematical Induction
* Second Principle of Mathematical Induction for Naturally Ordered Semigroup
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 16$: The Natural Numbers: Theorem $16.5$
Category:Naturally Ordered Semigroup
Category:Principle of Mathematical Induction
Principle of Mathematical Induction/Naturally Ordered Semigroup/General Result

== Theorem ==
Let $\struct {S, \circ, \preceq}$ be a naturally ordered semigroup.
Let $p \in S$.
Let $T \subseteq S$ such that:
:$x \in T \implies p \preceq x \land \paren {x \in T \implies x \circ 1 \in T}$
Then:
:$S \setminus S_p \subseteq T$
where:
:$\setminus$ denotes set difference
:$S_p$ denotes the set of all elements of $S$ preceding $p$.
== Proof ==
Let $S_p$ be the set of all elements of $S$ preceding $p$:
:$S_p = \set {x \in S: x \prec p}$
Let $T' = T \cup S_p$.
Then the set $T'$ satisfies the conditions of the Principle of Mathematical Induction for a Naturally Ordered Semigroup.
From that result:
:$T' = S$
By Set Difference with Union is Set Difference:
:$S \setminus S_p = T \setminus S_p$
By Set Difference is Subset:
:$T \setminus S_p \subseteq T$
completing the proof.
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 16$: The Natural Numbers: Corollary $16.5.1$
Category:Naturally Ordered Semigroup
Category:Principle of Mathematical Induction
Principle of Mathematical Induction/One-Based

== 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 1 ==
== Proof 2 ==
== Proof 3 ==
== Also see ==
== Sources ==
* : Chapter $1$: Some Preliminary Considerations: $1.1$ Mathematical Induction
* : Chapter $2$: Integers and natural numbers: $\S 2.1$: The integers: $\mathbf{I}$
* : $\S 1.4.2$: Mathematical induction: Definition $1.29$
* 
Category:Principle of Mathematical Induction
Principle of Mathematical Induction/One-Based/Proof 1

== Theorem ==
== Proof ==
Let $S$ be the set defined as:
:$S := \set {n \in \N_{>0}: \map P n \text { is false} }$
 $S \ne \O$.
From the Well-Ordering Principle it follows that $S$ has a minimal element $m$.
From $(1)$ we have that $\map P 1$ holds.
Hence $1 \notin S$.
Therefore $m \ne 1$.
Therefore $m - 1 \in \N_{>0}$.
But $m$ is the minimal element of $S$.
So $m - 1 \notin S$.
Therefore $\map P {m - 1}$ is true.
Hence by $(2)$ it follows that $\map P m$.
But then $m \notin S$.
This contradicts our supposition that $m \in S$.
Hence there can be no such $m \in S$.
So $S = \O$ and the result follows.
== Sources ==
* : $\S 3$: Natural Numbers: $\S 3.8$: Theorem (principle of induction)
Category:Principle of Mathematical Induction
Principle of Mathematical Induction/One-Based/Proof 2

== Theorem ==
== 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 $(\text F)$, it follows that $M = \N_{>0}$.
== Sources ==
* : $\S 2.1$: Theorem $2.1$
Category:Principle of Mathematical Induction
Principle of Mathematical Induction/One-Based/Proof 3

== Theorem ==
== Proof ==
We have that Natural Numbers are Non-Negative Integers.
Then we have that Integers form Well-Ordered Integral Domain.
The result follows from Induction on Well-Ordered Integral Domain.
== Sources ==
* : Chapter $3$: The Integers: $\S 9$. The Principles of Induction: Theorem $14$
Category:Principle of Mathematical Induction
Principle of Mathematical Induction/Peano Structure

== Theorem ==
Let $\struct {P, s, 0}$ be a Peano structure.
Let $\map Q n$ be a propositional function depending on $n \in P$.
Suppose that:
:$(1): \quad \map Q 0$ is true
:$(2): \quad \forall n \in P: \map Q n \implies \map Q {\map s n}$
Then:
:$\forall n \in P: \map Q n$
=== Principle of Finite Induction ===
== Proof ==
Let $A \subseteq P$ be defined by:
:$A := \set {n \in P: \map Q n}$
From $(1)$, $0 \in A$.
From $(2)$:
:$\forall n \in P: n \in A \implies \map s n \in A$
As this holds for all $n \in P$, it holds a fortiori for all $n \in A$.
Thus the condition:
:$n \in A \implies \map s n \in A$
is satisfied.
So by Axiom $(\text P 5)$ of the Peano Axioms:
:$A = P$
That is:
:$\forall n \in P: \map Q n$
== Also defined as ==
== Also see ==
* Principle of Finite Induction
* Principle of Mathematical Induction
* Second Principle of Mathematical Induction for Peano Structure
== Sources ==
* : Introduction $\S 4$: The natural numbers
* : Chapter $\text {I}$: Number Systems and Algebraic Structures: $2$. The positive integers
* : Chapter $1$: Theory of Sets: $\S 1$: Introduction
* 
Category:Peano's Axioms
Category:Principle of Mathematical Induction
Principle of Mathematical Induction/Proof

== Theorem ==
== Proof ==
Let $\Z_{\ge n_0}$ denote the set:
:$\Z_{\ge n_0} = \set {n \in \Z: n \ge n_0}$
Let $S$ be the set of integers defined as:
:$S = \set {n \in \Z_{\ge n_0}: \map P n}$
That is, the set of all integers for which $n \ge n_0$ and for which $\map P n$ holds.
From Subset of Set with Propositional Function we have that:
:$S \subseteq \Z_{\ge n_0}$
From $(1)$ we have that $\map P {n_0}$.
Hence $n_0 \in S$.
Let $k \in S$.
Then $\map P k$ holds.
But by $(2)$, $\map P {k + 1}$ also holds.
This implies $k + 1 \in S$.
So as:
:$S \subseteq \Z_{\ge n_0}$
and:
:$S$ satisfies $(1)$ and $(2)$
it follows by the Principle of Finite Induction that $S = \Z_{\ge n_0}$.
Hence for all $n \ge n_0$, $\map P n$ holds.
== Sources ==
* : Appendix $\text{A}.6$: Mathematical Induction: Theorem $\text{A}.7$
Category:Principle of Mathematical Induction
Principle of Mathematical Induction/Warning

== Principle of Mathematical Induction: Warning ==
It is a common mistake when setting up a proof by induction to forget to check the base case.
This can cause incorrect reasoning.
=== Example 1 ===
=== Example 2 ===
=== Example 3 ===
== Also see ==
* All Horses are the Same Colour
== Sources ==
* : Chapter $1$: Some Preliminary Considerations: $1.1$ Mathematical Induction
Category:Principle of Mathematical Induction
Principle of Mathematical Induction/Warning/Example 1

== Example of Incorrect Use of Principle of Mathematical Induction ==
Let $L_k$ denote the $k$th Lucas number.
Let $F_k$ denote the $k$th Fibonacci number.
Given that $L_n = F_n$ for $n = 1, 2, \ldots, k$, we see that:
Hence:
:$\forall n \in \Z_{>0}: F_n = L_n$
== Refutation ==
We have made the assumption that $L_n = F_n$ for $n = 1, 2, \ldots, k$.
However, we have that:
:$L_2 = 3$
while:
:$F_2 = 1$
Hence as the base case has been demonstrated to be false, the proof is invalid.
== Sources ==
* : $\text {1-1}$ Principle of Mathematical Induction: Exercise $14$
Category:Principle of Mathematical Induction