62.2加 法21 从而彼此相等.现在我们归纳地假定n+(m++)=(n+m)++,要证明的是 (n++)+(m++)=(n++)+m)++. 根据加法的定义，左边是(n+(m++)++,根据归纳假设它等于(n+m)++)++. 类似地，根据加法的定义，有(n++)+m=(n+m)++.于是右边也等于(n+ m)++)++.于是两边彼此相等，从而我们结束了归纳 ■ 作为引理2.2.2和引理2.2.3的一个特别的推论，我们看到n++=n+1.（为 什么？) 如早先承诺的，现在可以证明a+b=b+a了。 角题2.2.4（加法是交换的）对于任何自然数n和m,n+m=m+n. 证明对n进行归纳（保持m固定）.首先考虑基础情形，即证明0+m=m+0 根据加法的定义，0+m=m,同时根据引理2.2.2，m+0=m.于是基础情形做完 了.现归纳地假定n+m=m+n,我们要证 (n++)+m=m+(n++) 来完成归纳.根据加法定义，(n++)+m=(n+m)++.根据引理2.2.3，m+(n++)= (m+n)++,但根据归纳假定，这等于(n+m)++.于是(n++)+m=m+(n++), 我们完成了归纳， ■ 命题2.2.5（加法是结合的） 对于任何自然数a,b,c,(a+)+c=a+(b+c). 证明见习题2.2.1 ■ 根据这条结合律我们可以把和写成a+b+c这样的形式而无需顾虑这些数是 依怎样的次序加起来的 现在我们建立一个消去律， 命题2.2.6（消去律）设a,b,c是自然数，满足a+b=a+c,那么我们有b=c. 注意，我们尚不可使用减法或负数来证明这个命题，因为我们还不曾建立这些 概念.事实上，这个消去律是此书后面定义减法（以及整数）的决定性依据，因为它 使我们即使在减法被正式定义之前，就能进行一种“虚拟减法”。 证明通过对a进行归纳来证明此命题.先考虑基础情形a=0.那么，0+b= 0+c.根据加法的定义，此式蕴含b=c,此为所欲证者.现归纳地假定消去律对 于a成立（从而a+b=a+c蕴含b=c;现在要证消去律对于a++也成立 换句话说，我们假定(a++)+b=(a十+)+c而要证明b=c.根据加法的定义， (a++)+b=(a+b)++且(a++)+c=(a+c)++,于是有(a+b)++=（a+c)++, 根据公理2.4，有a+b=a+c.由于对于a己有消去律，所以有b=c,它就是所需 要的.这就完成了归纳法
22第2章从头开始：自然数 我们现在来讨论加法如何与正性交互作用 定义2.2.7（正自然数）一个自然数叫作是正的，当且仅当它不等于0. 命题2.2.8若a是正的而b是自然数，则a+b是正的（于是根据命题2.2.4， b+a也是正的). 证明对b施用归纳法.若b=0,则a+b=a十0=a,它是正的，从而证实 了基础情形.现归纳地假定a+b是正的，那么a+(b十+)=(a+b)++,根据公理 2.3它不能是零，从而是正的.这就完成了归纳法， ■ 推论2.2.9如果a和b是自然数，满足a+b=0,那么a=0且b=0. 证明假设不然，则a≠0或b≠0.如果a≠0，那么a是正的，从而根据命 题2.2.8，a+b=0是正的，这是一个矛盾.类似地，如果b卡0，那么b是正的，从 而根据命题2.2.8，a+b=0也是正的，还是矛盾.于是a和b必定都是零.口 引理2.2.10设b是正数.那么恰存在一个自然数b,使得b++=a. 证明见习题2.2.2. 一旦有了加法的概念，我们就可以开始定义序的概念 定义2.2.11（自然数的排序）设n和m是自然数.我们说n大于等于m,记 作n≥m或m≤n,当且仅当对于某自然数a,成立n=m+a.我们说n严格大 于m,记作n>m或m<n,当且仅当n≥m并且n≠m. 于是，譬如8>5，因为8=5+3而8≠5.还有，注意到对于任何n都成立 n++>九，于是不存在最大的自然数几，因为下一个数n++总是更大的 命题2.2.12（自然数的序的基本性质）设a,b,c是自然数.那么 (a)(序是自反的)a≥a. (b)(序是传递的)若a≥b且b≥c,则a≥c. (c)（序是反对称的)若a≥b且b≥a,则a=b. (d)(加法保序)a≥b当且仅当a+c≥b+c. (e)a<b当且仅当a++≤b. (f)a<b当且仅当对于某正数d,b=a+d. 证明见习题2.2.3. ■ 命题2.2.13（自然数的序的三歧性）设a和b是自然数，那么下述三命题中 恰有一个是真的： a<b,a=b,a>b. 证明这里只给出一个证明的框架，其中的缺口将在习题2.2.4中加以弥补， 首先证明三命题a<b,a=b,a>b中不会有多于一个的命题同时成立.若 a<b则根据定义a≠b,而若a>b则根据定义a≠b.若a>b且a<b则根据命 题2.2.12必有a=b,这是矛盾的.于是不会有多于一个的命题成立
$2.3乘法23 现在我们证明至少有一个命题成立.保持b固定而对a进行归纳.若a=0,则 0≤b对于一切b成立（为什么？），于是我们有0=b或0<b,这证明了基础情形 现设我们已对于a证明了命题，而要证命题对a++成立.从对于a的三歧性，有 三种情形：a<b,a=b,以及a>b.若a>b,则a++>b(为什么？).若a=b, 则a++>b(为什么？).现设a<b.那么根据命题2.2.12，有a+十≤b.于是或者 a++=b或者a++<b,而在两种情形中的每种情形下我们都完成了论证.这就 完成了归纳法 ■ 序的性质使我们可以得到归纳法原理的一个更强的形式： 角题2.2.14（强归纳法原理）设mo是一个自然数，而P(m)是一个依赖于任 意自然数m的性质.设对于每个m≥mo都有下述蕴含关系：如果P(m)对于一 切满足mo≤m'<m的自然数m'都成立，那么P(m)也成立（特别地，这意味着 P(mo)成立，因为在m=mo的情况下，假定的条件P(m)是空的)，那么，我们可 以断定P(m)对于一切自然数m≥mo都成立. 注2.2.15 在实用中我们常使用这个原理于mo=0或mo=1. 证明见习题2.2.5 习题 2.2 2.2.1证明命题2.2.5.（提示：固定其中两个变元而对第三个变元进行归纳） 2.2.2 证明引理2.2.10.（提示：使用归纳法.） 2.2.3证明命题2.2.12.（提示：你要用到前面的很多命题、推论和引理.） 2.2.4验证在命题2.2.13的证明中标出“（为什么？）”的三个命题 2.2.5 证明命题2.2.14.（提示：定义Q(n)为性质“P(m)对于一切m0≤m<n成立”，注 意Q(n)当n<mo时是莫须有地成立的) 2.2.6设n是自然数且设P(m)是一个依赖于自然数的性质，它满足条件：只要P(m++) 成立则P(m)也成立.假设P(n)成立，证明对于一切自然数m≤n,P(m)成立.此 即所谓向后归纳原理.（提示：对变元用归纳法） §2.3 乘 法 上一节证明了我们所知的关于加法与序的一切基本事实.为了节省篇幅且避免 唠叨那些明显的事情，现在允许使用我们所熟悉的一切涉及加法与序的代数运算而 不加进一步的评说.于是我们可以不加任何进一步说理地写出如a+b+c=c+b+a 这样的事情.现在我们来引入乘法.就像加法是重复的增长运算一样，乘法是重复 的加法
24第2章从头开始：自然数 定义2.3.1（自然数的乘法）设m是自然数.为把0乘到m上，我们定义 0×m:=0.设已定义了如何把n乘到m上，那么归纳地，我们定义把n++乘到 m上是(n十+)×m:=(n×m)+m. 这样有0×m=0,1×m=0+m,2×m=0+m+m,等等.用归纳法可容 易地验证两个自然数的乘积是自然数： 引理2.3.2（乘法是交换的）设n,m是自然数，那么n×m=m×n. 证明见习题2.3.1. ■ 我们现在将把n×m简写作nm,并且使用通常的先乘后加的约定，于是，作 为例子，ab+c指的是(a×b)+c,而不是a×(b+c).(我们同样也将使用对于以 后定义的其他算术运算的优先性的通常的符号约定，以免总是使用括号) 引理2.3.3（正自然数没有零因子）设n,m是自然数.那么n×m=0当且 仅当中n,m至少有一个等于零.特别地，若n和m都是正的，则nm也是正的. 证明见习题2.3.2. ■ 命题2.3.4（分配律）5 对于任何自然数a,b,c都有a(b+c)=ab+ac以及 (b+c)a ba ca. 证明由于乘法是交换的，我们只需证明第一个等式a(b+c)=ab+ac.保持 a和b固定而对c用归纳法.我们来证明c=0的基础情形，即a(b+0)=ab+a0 左端是ab,同时右端是ab+0=ab,所以我们已搞定基础情形.现在我们归纳地假 定a(b+c)=ab+ac,并且来证明 a(b+(c++)=ab+a(c++). 左端是a(6+c)++)=a(亿+c)+a;而右端是ab+ac+a,并根据归纳假定进而等 于a(b+c）+a.这样我们就完成了归纳法 ■ 命题2.3.5（乘法是结合的）对于任何自然数a,b,c,我们有(a×b)×c= a×(b×c. 证明见习题2.3.3. 0 命题2.3.6（乘法保序）若a,b是自然数，满足a<b,且c是正的，则ac<bc 证明由于a<b,我们知存在某正数d使b=a+d.用c来乘并使用分配 律，得bc=ac+dc.由于d是正的而且c也是正的，所以dc是正的，从而ac<bc 这就是所要证的 ■ 推论2.3.7（消去律）设a,b,c是自然数，满足ac=bc而且c不是零，那么 a=b. 注2.3.8恰如命题2.2.6将能使我们做“虚拟减法”并最终导致定义名副其 实的减法一样，此推论也提供了一个“虚拟除法”，后面定义名副其实的除法时要用 到此“虚拟除法
82.3乘 法25 证明根据序的三歧性（命题2.2.13），有三种情形：a<b,a=b,a>b.先设 a<b,那么根据命题2.3.6有ac≤bc,而这是不对的.当a>b时我们得到类似的 矛盾.于是唯一的可能是a=b,这就是要证的 ■ 用这些命题可以容易地推导出关于加法和乘法的一切熟知的代数算律，参见习 题2.3.4. 既然我们已经有了熟知的加法运算和熟知的乘法运算，更为原始的增长概念就 可靠边站了，此后我们将很少见到它.在任何情况下我们都可以用加法来描述增长， 因为n++=n+1. 命题2.3.9（欧几里得算法）设n是自然数且设q是正数，那么存在自然数 m,r,使得0≤r<q且n=mg+r. 注2.3.10换句话说，我们可以用一个正数g去除一个自然数n而得到商 m(它是另一个自然数)和余数r(它小于q).这个算法标志着数论的开端，数论是一 个优美而重要的课题，但它超出了本书的范围 证明见习题2.3.5. ■ 如同重复地使用增长运算来定义加法和重复地使用加法运算来定义乘法一样， 可以重复地使用乘法运算来定义指数运算： 定义2.3.11（自然数的指数运算）设m是自然数.为把m升到0次幂，我 们定义m°：=1.现递归地假定mn已对自然数n定义好，那么我们定义mn++= m"x m. 例2.3.12那么x2=x0×x=1×x=x;x2=x1×x=x×c;x3=x2×x= x×x×；依次类推.根据归纳法，我们看到，这个递归的定义对于一切自然数都 定义了xn 此处我们不更深入地建立指数运算的理论，而要等到定义了整数和比例数之后 再说；特别参阅命题4.3.10 习 题 2.3 2.3.1证明引理2.3.2.（提示：修正引理2.2.2、引理2.2.3及命题2.2.4的证明.） 2.3.2证明引理2.3.3.（提示：先证第二个命题） 2.3.3 证明命题2.3.5.（提示：修正命题2.2.5的证明并使用分配律.) 2.3.4 证明等式(a+b)2=a2+2ab+b2对于一切自然数a,b成立， 2.3.5证明命题2.3.9.（提示：固定g并对n进行归纳）