良序性，数学归纳法，强归纳法，结构归纳法

正整数集合上的公理（Axioms for Positive Integers）

数1是正整数
如果n是正整数那么n+1(n的后继也是正整数)
每个大于1的正整数都是一个正整数的后继
良序性(The Well-Ordering Property):正整数集合的每个非空子集都有一个最小元

介绍(introduction)

良序性公理–>数学归纳法–>强归纳法–>结构归纳法

数学归纳法

####描述

很多命题都断言，某个性质对所有有正整数来说都为真。数学归纳法是证明这类命题的一个有效证明方法。首先证明命题对于正整数1成立。然后证明这个命题如果对于一个正整数成立，那么对于下一个正整数也必然成立。这证明方法基于下面这个推理规则。
$$
∀n∈Z^,\ \ \ \ (P(1)∧(∀k∈Z^,P(k)→P(k+1)) → ∀nP(n)
$$
也就是说对于任意正整数n 如果$P(1)$且$∀k∈Z^*,P(k)→P(k+1)$,那么∀nP(n)也成立。

可以使用使用数学归纳法证明的命题

对于一个无限长的多米诺骨牌，每张多米诺骨牌都直立着，如果第一个多米诺骨牌倒了，并且如果一张多米诺骨牌倒了，下一张多米诺骨牌也会倒，那么所有的多米诺骨牌都会倒。
前n个正整数之和为$\frac{n(n-1)}{2}$
前n个正奇数之和为$n^2$
含有n个元素的有限集的子集个数为$2^n$，n为非负整数(nonpositive integer)
假设我们一组讲座，每个讲座都有开始时间和结束时间。假如讲座一旦开始就会持续到结束，两个讲座不能同时进行，一个讲座结束后另一个讲座就开始，演讲厅只有一个，目的是尽可能安排更多的讲座。数学归纳法可以证明每一次选择与已选讲座相容的讲座中，结束时间最早的讲座。就能安排更多的讲座。
只要n是一个正整数，则$f(x)=x^n$ 的导数就等于 $nx^{n-1}$，注意命题是微积分中求导法则 $f(x)=x^n$ 的导数为$nx^{n-1}$

的论域不同，具体看一下高等数学书就知道了

扩展

在逻辑学中，通过推理规则从前提导出结论的叫演绎推理，寻找结论来支持证据的叫归纳推理，数学证明包括使用了数学归纳法的证明都是演绎推理。这个是术语的冲突。

数学归纳法的基础步骤不一定要从1开始，有时候需要证明对于任意的$n>=b,P(n)$为真,其中n，b是整数，b可以是正数负数或0

有时候数学归纳法不能直接证明一个结论，但是可以证明一个更广的结论，从而得到需要证明的结论，这个方法叫归纳载入

强归纳法

描述

强归纳法可以使用在直接使用数学归纳法不容易证明的命题上。他的基础步骤和数学归纳法相同，首先证明$P(1)$为真，归纳步骤不同，归纳步骤需要证明对于任意不大于k的正整数 j ,$P(j)$为真，那么$P(k+1)$也为真。表示为逻辑语句就是
$$
∀n∈Z^,\ \ \ \ (P(1)∧(∀k∈Z^,P(1)∧P(2)∧..∧P(k-1)∧P(k)→P(k+1)) → ∀nP(n)
$$

强归纳法可以证明的一些命题

每个正整数都可以写成素数的乘积
具有n条边的简单多边形能够被三角形化为n-2分三角形，n是大于等于3的整数
$\sqrt2$是无理数(第一个被发现的无理数就是$\sqrt2$,希帕索斯也因此被丢进了爱琴海)
任意正整数n都可以写成2的不同次幂的和

结构归纳法

##应用

##正确性证明

###良序性(The Well-Ordering Property) –> 数学归纳法

先看良序性公理的陈述，正整数集合的每个非空子集都有一个最小元。需要证明的是
对于任意正整数n 如果$P(1)$且$∀k∈Z^*,P(k)→P(k+1)$ 能够推出∀nP(n)。

Proof 1:

首先先注意到有两个前提，第一个是P(1) ≡ T ,

第二个是$∀k∈Z^*,P(k)→P(k+1)$ ≡ T

假设S是使得P(n)为假的值的集合。要证数学归纳法为真$∀n∈Z^,\ \ \ \ (P(1)∧(∀k∈Z^,P(k)→P(k+1)) → ∀nP(n)$

可以证明S = ∅ 或者证明 S 非空为假。这里我们证明 S 非空为假。

假设数学归纳法结论为假,也就是说结论的否定为真，即$¬∀nP(n) ≡ T$

$¬∀nP(n)$ ≡ ∃n,¬P(n) 也就是说集合S非空。S是正整数集合的子集且非空，那么根据良序性公理，S必定存在最小元，假设该最小元为m，那么m-1 不属于集合S。

因此P(m-1) 为真。

又因为$∀k∈Z^*,P(k)→P(k+1)$为真，则$P(m-1)→P(m)$ ，$P(m) ≡ T$，这与$P(m) ≡ F$ 矛盾，所以$∀nP(n)$

对于Proof 1 的分析

首先我们希望在对于任意正整数n 如果$P(1)$和$∀k∈Z^*,P(k)→P(k+1)$都为真的前提下，证明$∀nP(n)$也为真.这是直接证明的一个例子。

随后我们发现$∀nP(n)$ 等价于S为空,这一步将证明$∀nP(n)$ 转换为证明 S 为空集。为了证明这一点，我们假设S非空，并通过他来得到一个矛盾式(即永远为假的命题)。即P(m)为真并且P(m)为假的矛盾，这是归谬证明法的一个例子。

后面得到了S非空为假，即S为空为真，因为S为空→$∀nP(n)$，S为空，于是$∀nP(n)$ 为真，这个是假言推理的一个例子。