归纳公理
大前提：
1 ° S ⊆ N 1°\ \ S \subseteq N 1° S⊆N
小前提：
1 ° 1 ∈ S 1°\ \ 1\in S 1° 1∈S
2 ° n ∈ S → n + 1 ∈ S 2°\ \ n\in S \rightarrow n+1\in S 2° n∈S→n+1∈S
结论：
S = N S = N S=N
定理1 数学归纳法
归纳公理推出
大前提：
1 ° n ∈ N 1°\ \ n\in N 1° n∈N
2 ° P ( n ) 是 关 于 n 的 命 题 2°\ \ P(n)是关于n的命题 2° P(n)是关于n的命题
小前提：
1 ° n = 1 → P ( 1 ) 1°\ \ n = 1\rightarrow P(1) 1° n=1→P(1)成立
2 ° P ( n ) 2°\ \ P(n) 2° P(n)成立 → P ( n + 1 ) \rightarrow P(n+1) →P(n+1)成立
结论：
P ( n ) P(n) P(n)对所有n成立
证明：
设使 P ( n ) P(n) P(n)成立的所有自然数 n n n组成的集合是 S ( S ⊆ N ) S(S\subseteq N) S(S⊆N).
1 ° 1 ∈ S 1°\ \ 1\in S 1° 1∈S
2 ° n ∈ S → n + 1 ∈ S 2°\ \ n\in S\rightarrow n+1\in S 2° n∈S→n+1∈S
归纳公理得： S = N S = N S=N
定理2 最小自然数原理
数学归纳法推出
1 ° T ≠ ∅ 1°\ \ T\neq \varnothing 1° T=∅
2 ° T ⊆ N 2°\ \ T\subseteq N 2° T⊆N
t 0 ∈ T → ∀ t ∈ T , t 0 ≤ t t_0\in T\rightarrow \forall t\in T,t_0\leq t t0∈T→∀t∈T,t0≤t
证明：
令 S = { s ∣ s ∈ N , s ≤ t ( ∀ t ∈ T ) } S = \{s|s\in N,s\leq t (\forall t\in T)\} S={ s∣s∈N,s≤t(∀t∈T)}
1 ° S ≠ ∅ ( 1 ∈ S ) 1°\ \ S\neq\varnothing(1\in S) 1° S=∅(1∈S)
2 ° ∀ t 1 ∈ S → t 1 + 1 ∉ S 2°\ \ \forall t_1\in S\rightarrow t_1 + 1 \notin S 2° ∀t1∈S→t1+1∈/S
∃ s 0 ∈ S → s 0 + 1 ∉ S \exists s_0\in S \rightarrow s_0+1\notin S ∃s0∈S→s0+1∈/S
否则：
$1\in S\ \ $
s 0 ∈ S → s 0 + 1 ∈ S s_0\in S \rightarrow s_0+1\in S s0∈S→s0+1∈S
数学归纳法得： S = N S=N S=N
由 2 ° 2° 2°可知 S ≠ N S\neq N S=N
故矛盾.
因此：
3 ° ∃ s 0 ∈ S → s 0 + 1 ∉ S 3°\ \ \exists s_0\in S \rightarrow s_0+1\notin S 3° ∃s0∈S→s0+1∈/S
此时证明： t 0 = s 0 t_0 = s_0 t0=s0，即证： s 0 ∈ T s_0\in T s0∈T
反证：若 s 0 ∉ T s_0\notin T s0∈/T，即 ∀ t ∈ T , s 0 < t → s 0 + 1 ≤ t → s 0 + 1 ∈ S \forall t\in T,s_0<t\rightarrow s_0+1\leq t \rightarrow s_0+1\in S ∀t∈T,s0<t→s0+1≤t→s0+1∈S
故与 3 ° 3° 3°矛盾.
最终证毕.
定理3 最大自然数原理
最小自然数原理推出
1 ° M ≠ ∅ 1°\ \ M\neq\varnothing 1° M=∅
2 ° M ⊆ N 2°\ \ M\subseteq N 2° M⊆N
3 ° ∃ a ∈ N , ∀ m ∈ M , m ≤ a 3°\ \ \exists a\in N,\forall m\in M,m\leq a 3° ∃a∈N,∀m∈M,m≤a
m 0 ∈ M → ∀ m ∈ M , m ≤ m 0 m_0\in M\rightarrow \forall m\in M,m\leq m_0 m0∈M→∀m∈M,m≤m0
证明：
令 T = { t ∣ t ∈ N , ∀ m ∈ M , t ≥ m } T=\{t|t\in N,\forall m\in M,t\geq m\} T={ t∣t∈N,∀m∈M,t≥m}
1 ° T ≠ ∅ ( a ∈ T ) 1°\ \ T\neq\varnothing(a\in T) 1° T=∅(a∈T)
由定理2 最小自然数原理可知：
2 ° ∃ t 0 ∈ T , ∀ t ∈ T , t 0 ≤ t 2°\ \ \exists t_0\in T,\forall t\in T,t_0 \leq t 2° ∃t0∈T,∀t∈T,t0≤t
此时证明： t 0 = m 0 t_0 = m_0 t0=m0，即证： t 0 ∈ M t_0\in M t0∈M
反证：若 t 0 ∉ M t_0\notin M t0∈/M，即 ∀ m ∈ M , m < t 0 → m ≤ t 0 − 1 → t 0 − 1 ∈ T \forall m\in M,m<t_0\rightarrow m\leq t_0-1\rightarrow t_0-1\in T ∀m∈M,m<t0→m≤t0−1→t0−1∈T
故与 t 0 t_0 t0是最小自然数矛盾.
最终证毕.
定理4 第二种数学归纳法
最小自然数原理推出
大前提：
1 ° n ∈ N 1°\ \ n\in N 1° n∈N
2 ° P ( n ) 是 关 于 n 的 命 题 2°\ \ P(n)是关于n的命题 2° P(n)是关于n的命题
小前提：
1 ° n = 1 → P ( 1 ) 1°\ \ n=1\rightarrow P(1) 1° n=1→P(1)成立
2 ° n > 1 , m ∈ N , n ∈ N , m < n , P ( m ) 2°\ \ n>1,m\in N,n\in N,m<n,P(m) 2° n>1,m∈N,n∈N,m<n,P(m)成立 → P ( n ) \rightarrow P(n) →P(n)成立
结论：
P ( n ) P(n) P(n)对所有n成立
证明：
反证法：若定理不成立. 令 T = { t ∣ t ∈ N , P ( t ) 不 成 立 } T=\{t|t\in N,P(t)不成立\} T={ t∣t∈N,P(t)不成立}
由 T ≠ ∅ T\neq\varnothing T=∅ T ⊆ N T\subseteq N T⊆N可使用最小自然数原理：
1 ° ∃ t 0 ∈ T , ∀ t ∈ T , t 0 ≤ t 1°\ \ \exists t_0\in T,\forall t\in T,t_0\leq t 1° ∃t0∈T,∀t∈T,t0≤t
由小前提 1 ° 1° 1°：
2 ° t 0 > 1 ( 1 ∉ T ) 2°\ \ t_0>1(1\notin T) 2° t0>1(1∈/T)
3 ° m = 1 , 2 , . . . , t 0 − 1 有 P ( m ) 成 立 3°\ \ m = 1,2,...,t_0-1有P(m)成立 3° m=1,2,...,t0−1有P(m)成立
由小前提 2 ° 2° 2°：
3 ° → P ( t 0 ) 也 成 立 → t 0 ∉ T 3°\rightarrow P(t_0)也成立\rightarrow t_0\notin T 3°→P(t0)也成立→t0∈/T
与 t 0 ∈ T t_0\in T t0∈T矛盾.
最终证毕.
定理4 盒子原理（鸽笼原理）
设n是一个自然数. 现有n个盒子和n+1个物体. 无论怎样把这n+1个物体放入这n个盒子，一定有一个盒子中被放入两个或两个以上的物体.
证明：
反证法：假设结论不成立，即每个盒子至多有一个物体，那么，这n个盒子总共有的物体个数 ≤ n \leq n ≤n，这和有n+1个物体放到了n个盒子中相矛盾.
最终证毕.
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/bian-cheng-ji-chu/108204.html