2.2 加法
2.2.1
证明命题 2.2.5
命题 2.2.5 (加法是可结合的)对任意三个自然数 a、b、c,有 (a+b)+c=a+(b+c)
成立。
证明:
设 a,c 为定值,对 b 采取归纳法:
当 b=0 时:
左式=(a+0)+c=a+c右式=a+(0+c)=a+c
原式左右两边相等,等式成立。
假设当 b=b 时 (a+b)+c=a+(b+c) 成立,
则当 b=b++ 时:
左式为:(a+b++)+c,根据引理 2.2.3.n+(m++)=(n+m)++ 有:
(a+b++)+c=((a+b)++)+c
根据引理 2.2.4.n+m=m+n 有:
((a+b)++)+c=c+((a+b)++)=(c+(a+b))++=((a+b)+c)++
右式为:
a+(b+++c)=a+((b+c)++)=(a+(b+c))++
又因为当 b=b 时 (a+b)+c=a+(b+c) 成立,
所以 (c+(a+b))++=(a+(b+c))++,即 左式 = 右式,
因此当 b=b++ 时,原式 (a+b++)+c=a+(b+++c) 成立。
即证:对任意三个自然数 a、b、c,有 (a+b)+c=a+(b+c) 成立。
2.2.2
证明引理 2.2.10
引理 2.2.10 令 a 表示一个正自然数,那么恰存在一个自然数 b 使得 b++=a。
证明:
因为 a∈N+,
当 a=1 时,0++=1⇒b=0,此时 b 为自然数。
设当 a=a 时,b++=a,则当 a=a++时,有:
b++=a++
此时 b=a,因为 a∈N+,所以 b∈N+,等式成立。
即证:令 a 表示一个正自然数,那么恰存在一个自然数 b 使得 b++=a。
2.2.3
证明命题 2.2.12
命题 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.11(自然数的序)令 n 和 m 表示任意两个自然数。我们称 n 大于等于 m,
记作 n⩾m 或 m⩽n,当且仅当存在自然数 a 使得 n=m+a。
我们称 n 严格大于 m,并且记作 n>m 或 m<n,当且仅当 n⩾m 且 n≠m。
(a)
因为 a=a+0,0∈N,根据定义 2.2.11 就有 a⩾a。
(b)
根据定义 2.2.11 有:
a⩾b⇒a=b+m,m∈N,
b⩾c⇒b=c+n,n∈N
所以:
a=c+n+m,n+m∈N。
即 a⩾c.
因此:如果 a⩾b 并且 b⩾c,那么 a⩾c。
(c)
根据定义 2.2.11 有:
a⩾b⇒a=b+m,m∈N,
b⩾a⇒b=a+n,n∈N
所以:
a=a+n+m,n+m∈N⇒n+m=0⇒m=0,n=0⇒a=b
即证:如果 a⩾b 并且 b⩾a,那么 a=b。
(d)
由定义 2.2.11 有:
a⩾b⇔a=b+m,m∈N⇔a+c=b+m+c=b+c+m,m∈N⇔a+c⩾b+c
即证:a⩾b,当且仅当 a+c⩾b+c
(e)
a<b⇔((a⩽b)∧(a≠b))⇔((a+m=b,m∈N)∧(a≠b))⇔m≠0⇔∃n∈N,n++=m⇔a+(n++)=b,n∈N⇔(a++)+n=b,n∈N⇔a++⩽b
(f)
a<b⇔((a<b)∧(a≠b))⇔((a+d=b,d∈N)∧(d≠0))⇔a+d=b,d∈N+
2.2.4
证明在命题 2.2.13 证明中标注了(为什么?)的三个命题:
- 当 a=0 时,对所有的 b 均有 0⩽b
- 如果 a>b,那么有 a++>b
- 如果 a=b,那么 a++>b
证明:
(0+b=b,b∈N)⇒(0⩽b,b∈N)
a>b⇒((a=b+m,m∈N)∧(a≠b))⇒a++=(b+m)++=b+(m++),m∈N⇒a++>b
a=b⇒a++=b++=(b+0)++=b+(0++)=b+1⇒a++>b
2.2.5
证明命题 2.2.14(提示:定义 Q(n) 是关于 n 的一个如下性质:P(m)对任意满足 m0⩽m⩽n 的 m 均为真;注意,当 n<m0 时,Q(n)为真,因为此时 m 的
取值范围为空。)
命题 2.2.14(强归纳法原理)令 m0 表示一个自然数,P(m) 表示与任意自然数 m 有关的性质。
假设对任意满足 m⩾m0 的自然数 m,均有如下内容成立:若 P(m′) 对任意满足
m0⩽m′<m 的自然数 m′ 均为真,那么 P(m) 也为真。(特别地,这意味着
P(m0) 为真,因为当 m=m0 时,前提中的 m′ 的取值范围为空。)于是我们能够断定,对于
任意满足 m⩾m0 的自然数 m,P(m) 为真。
证明:
令 Q(n):=P(m)为真,∀m0⩽m<n,当 n<m0 时 Q(n) 为真。
等价于 ∀n⩾m0,Q(n)为真。
当 n=m0 时,因为 m0⩽m<m0 不成立,所以 $Q(m_0) 为真。
设当 n=n 时,Q(n) 为真。
则当 n=n++ 时,因为 Q(n) 为真,所以对 ∀m0⩽k<n 有 P(k)为
真,因此 P(n) 也为真,从而推出 Q(n++) 也为真,即 Q(n++)=P(k)为真,m0⩽k<n++
2.2.6
令 n 表示一个自然数,令 P(m) 是关于自然数的一个性质并且满足:只要 P(m++) 为真,P(m)
就为真。假设 P(n) 也为真,证明:P(m) 对任意满足 m⩽n 的自然数 m 均为真;
这被成为逆向归纳法原理。(提示:对变量 n 使用归纳法)
证明:
令 Q(n):=P(m)为真,∀m⩽n
当 n=0 时,条件成立.
设当 n=k 时, Q(k):=P(m)为真,∀m⩽k,
则当 n=k++ 时,因为 Q(k) 成立,所以 P(k++),所以 Q(k++) 为真,
因此 Q(k++)=P(m)为真,∀m⩽k++。
2.3 乘法
2.3.1
证明引理 2.3.2(提示:修改引理 2.2.2、引理 2.2.3 以及命题 2.2.4 的证明)
引理 2.3.2(乘法交换律)令 n 和 m 表示任意两个自然数,那么有 n×m=m×n 成立。
证明:
a). 对 m×0=0,∀m∈N 成立进行归纳:
当 m=0 时,0×0=0,等式成立,
设 m=m 时成立,则有 m×0=0 成立,
当 m=m++ 时,有 (m++)×0=(m+0)+0=0+0=0 等式依然成立。
b). 对 n×(m++)=(n×m)+n,∀m,n∈N 成立进行归纳:
当 n=0 时,0×(m++)=0=0×m=0,等式成立,
设 n=n 时成立,则有 n×(m++)=(n×m)+n 成立,
当 n=n++ 时,有
(n++)×(m++)=n×(m++)+(m++)=n×m+n+(m++)=n×m+m+(n++)=(n++)×m+(n++)
等式 (n++)×(m++)=(n++)×m+(n++) 成立。
c). 对 n×m=m×n,∀m,n∈N 成立进行归纳:
当 n=0 时,0×m=0=m×0,等式成立,
设 n=n 时成立,则有 n×m=m×n 成立,
当 n=n++ 时,有:
(n++)×m=n×m+n=m×n+m=m×(n++)
即等式 n×m=m×n,∀m,n∈N 成立。
2.3.2
证明引理 2.3.3(提示:首先证明第二个命题)
引理 2.3.3 (正自然数没有零因子)设 n、m 为自然数。那么 n×m=0,当且仅当
n 和 m 中至少有一个为零。特别的,如果 n 和 m 均为正,那么 nm 也是正的。
证明:
有题意有:
(n∈N+)∧(m∈N+)⇒∃c,d∈N,c++=n,d++=m⇒nm=(c++)×(d++)=c×(d++)+(d++)=(c×(d++)+d)++⇒nm∈N+
2.3.3
证明命题 2.3.5(提示:修改命题 2.2.5 的证明并利用分配律)
命题 2.3.5(乘法结合律)对任意自然数 a、b、c ,(a×b)×c=a×(b×c) 均成立.
证明:
对 b 进行归纳:
当 b=0 时,(a×0)×c=0×c=0,a×(0×c)=a×0=0,左边 = 右边,等式成立,
设当 b=b 时成立,则有 (a×b)×c=a×(b×c) 成立,
当 b=b++ 时,有:
(a×(b++))×c=(a×b+a)×c=(a×b)×c+a×ca×((b++)×c)=a×((b×c)+c)=a×(b×c)+a×c=(a×b)×c+a×c⇒(a×(b++))×c=a×((b++)×c)
2.3.4
证明等式 (a+b)2=a2+2ab+b2 对任意自然数 a 和 b 均成立
证明:
(a+b)2=(a+b)(a+b)=a(a+b)+b(a+b)=a2+ab+ba+b2=a2+2ab+b2
2.3.5
证明命题 2.3.9(提示:固定 q 并对 n 进行归纳)
命题 2.3.9(欧几里得算法)设 n 是一个自然数,q 表示一个正自然数,那么存在自然数 m 和
r 使得 0⩽r<q 并且 n=mq+r。
证明:
固定 q,对 n 进行归纳:
当 n=0 时,0=m×q+r,m=0,r=0<q,等式成立,
假设 n=n 时成立,则有 n=mq+r,0⩽r<q 成立,
当 n=n++ 时,有:
n++=(mq+r)++=mq+(r++)r<q⇒(r++)⩽q⇒((r++)<q)∨((r++)=q)
当 r++<q 时,等式成立,
当 r++=q 时,有:
n++=(mq+r)++=mq+(r++)=mq+q=(m++)q+0
等式依然成立,即证。