陶哲轩Analysis I习题的参考解答及思考（第4章）

第4章

版本

Analysis I（第3版）。

章节4.1

练习4.1.1

题目：

Verify that the definition of equality on the integers is both reflexive and symmetric.

证明自反性：

\( \forall a — b \in \mathbf{Z} \)，有\( a + b = a + b \)，再根据相等性的定义有：\( a — b = a — b \)。

证毕。

证明对称性：

\( \forall a — b, c — d \in \mathbf{Z} \)，如果\( a — b = c — d \)，即\( a + d = c + b \)，则有\( c + b = a + d \)，再根据相等性的定义有：\( c — d = a — b \)。

证毕。

练习4.1.2

题目：

Show that the definition of negation on the integers is well-defined in the sense that if \( (a — b) = (a' — b') \), then \( -(a — b) = -(a' — b') \) (so equal integers have equal negations).

证明：

如果\( a — b = a' — b' \)，则有\( a + b' = a' + b \)，进而有\( b + a' = b' + a \)，此时可得\( b — a = b' — a' \)，即\( -(a — b) = -(a' — b') \)。

证毕。

练习4.1.3

题目：

Show that \( (-1) \times a = -a \) for every integer \( a \).

证明：

因为\( a \)为整数，故存在自然数\( c, d \)，使得\( a = c — d \)，此时，\( (-1) \times a = (0 — 1) \times (c — d) = d — c = -a \)。

证毕。

练习4.1.4

题目：

Prove the remaining identities in Proposition 4.1.6. (Hint: one can save some work by using some identities to prove others. For instance, once you know that \( xy = yx \), you get for free that \( x1 = 1x \), and once you also prove \( x(y + z) = xy + xz \), you automatically get \( (y + z)x = yx + zx \) for free.)

Proposition 4.1.6的内容：

1. x + y = y + x
2. (x + y) + z = x + (y + z)
3. x + 0 = 0 + x = x
4. x + (-x) = (-x) + x = 0
5. xy = yx
6. (xy)z = x(yz)
7. x1 = 1x = x
8. x(y + z) = xy + xz
9. (y + z)x = yx + zx

其中，第6个命题在书中已经证明过了，这里仍然再证一遍。

因为\( x, y, z \in \mathbf{Z} \)，故存在自然数\( a, b, c, d, e, f \)，使得 \( x = a — b, y = c — d, z = e — f \)。

证明\( x + y = y + x \)：

\( x + y = (a — b) + (c — d) = (a + c) — (b + d) = (c + a) — (d + b) \)， \( y + x = (c — d) + (a — b) = (c + a) — (d + b) = x + y \)。

证毕。

证明\( (x + y) + z = x + (y + z) \)：

\( (x + y) + z = ((a — b) + (c — d)) + (e — f) = ((a + c) — (b + d)) + (e — f) = ((a + c) + e) — ((b + d) + f) = (a + (c + e)) — (b + (d + f)) \)， \( x + (y + z) = (a — b) + ((c — d) + (e — f)) = (a — b) + ((c + e) — (d + f)) = (a + (c + e)) — (b + (d + f)) = (x + y) + z \)。

证毕。

证明\( x + 0 = 0 + x = x \)：

\( x + 0 = (a — b) + (0 — 0) = (a + 0) — (b + 0) = a — b = x \)，

由命题1，可得\( 0 + x = x + 0 = x \)。

证毕。

证明\( x + (-x) = (-x) + x = 0 \)

\( x + (-x) = (a — b) + (b — a) = (a + b) — (a + b) \)，又\( (a + b) + 0 = 0 + (a + b) \)，得\( (a + b) — (a + b) = 0 — 0 = 0 \)，即\( x + (-x) = 0 \)。

由命题1，可得\( (-x) + x = x + (-x) = 0 \)。

证毕。

证明\( xy = yx \)：

\( xy = (a — b) \times (c — d) = (ac + bd) — (ad + bc) = (ca + db) — (cb + da) \)， \( yx = (c — d) \times (a — b) = (ca + db) — (cb + da) = xy \)。

证毕。

证明\( (xy)z = x(yz) \)：

\( (xy)z = ((a — b) \times (c — d)) \times (e — f) = ((ac + bd) — (ad + bc)) \times (e — f) = ((ac + bd)e + (ad + bc)f) — ((ac + bd)f + (ad + bc)e) = (ace + bde + adf + bcf) — (acf + bdf + ade + bce) = (ace + adf + bcf + bde) — (acf + ade + bce + bdf) \)， \( x(yz) = (a — b) \times ((c — d)) \times (e — f)) = (a — b) \times ((ce + df) — (cf + de)) = (a(ce + df) + b(cf + de)) — (a(cf + de) + b(ce + df)) = (ace + adf + bcf + bde) — (acf + ade + bce + bdf) = (xy)z \)。

证毕。

证明\( x1 = 1x = x \)：

\( x1 = (a — b) \times (1 — 0) = (a1 + b0) — (a0 + b1) = a — b = x \)。

由命题5，得\( 1x = x1 = x \)。

证毕。

证明\( x(y + z) = xy + xz \)：

\( x(y + z) = (a — b) \times ((c — d) + (e — f)) = (a — b) \times ((c + e) — (d + f)) = (a(c + e) + b(d + f)) — (a(d + f) + b(c + e)) = (ac + ae + bd + bf) — (ad + af + bc + be) = (ac + bd + ae + bf) — (ad + bc + af + be) \)， \( xy + xz = (a – b) \times (c — d) + (a — b) \times (e — f) = ((ac + bd) — (ad + bc)) + ((ae + bf) — (af + be)) = (ac + bd + ae + bf) — (ad + bc + af + be) = x(y + z) \)。

证毕。

证明\( (y + z)x = yx + zx \)：

由命题5和命题8，得\( (y + z)x = x(y + z) = xy + xz = yx + zx \)。

证毕。

练习4.1.5

题目：

Prove Proposition 4.1.8. (Hint: while this proposition is not quite the same as Lemma 2.3.3, it is certainly legitimate to use Lemma 2.3.3 in the course of proving Proposition 4.1.8.)

Proposition 4.1.8的内容：

(Integers have no zero divisors). Let \( a \) and \( b \) be integers such that \( ab = 0 \). Then either \( a = 0 \) or \( b = 0 \) (or both).

证明：

如果\( a, b \)都是自然数，则根据引理2.3.3，有：如果\( ab = 0 \)，则\( a = 0 \)或\( b = 0 \)。

如果\( a, b \)中有且仅有一个不是自然数，不妨设\( a \)不是自然数，则\( \exists n > 0 \in \mathbf{N}, -n = a \)，此时如果\( ab = 0 \)，则有\( -nb = 0 \)，两边同乘\( -1 \)，可得\( nb = 0 \)，此时根据引理2.3.3，有\( n = 0 \)或\( b = 0 \)，如果是\( n = 0 \)，则也有\( a = 0 \)，综合可得\( a = 0 \)或\( b = 0 \)。

如果\( a, b \)两个都不是自然数，则\( \exists n > 0, m > 0 \in \mathbf{N}, -n = a, -m = b \)，此时如果\( ab = 0 \)，则有\( (-n)(-m) = 0 \)，即\( nm = 0 \)，此时根据引理2.3.3，有\( n = 0 \)或\( m = 0 \)，进而有\( a = 0 \)或\( b = 0 \)。

综上，有：如果\( ab = 0 \)，则\( a = 0 \)或\( b = 0 \)。

证毕。

练习4.1.6

题目：

Prove Corollary 4.1.9. (Hint: there are two ways to do this. One is to use Proposition 4.1.8 to conclude that \( a - b \) must be zero. Another way is to combine Corollary 2.3.7 with Lemma 4.1.5.)

Corollary 4.1.9的内容：

(Integers have no zero divisors). If \( a, b, c \) are integers such that \( ac = bc \) and \( c \) is non-zero, then \( a = b \).

证明（使用定理4.1.8）：

\( ac = bc \)，得\( c(a - b) = 0 \)，根据定理4.1.8，有\( c = 0 \)或\( a - b = 0 \)，又\( c \neq 0 \)，故只能\( a - b = 0 \)，此时有\( a = b \)。

证毕。

注：使用推论2.3.7以及引理4.1.5的证明就不写了，估计和练习4.1.5是一样的证明方法，即分成三种情况：两者都是自然数，有且仅有一个是自然数，两者都是非自然数。

练习4.1.7

题目：

Prove Lemma 4.1.11. (Hint: use the first part of this lemma to prove all the others.)

Lemma 4.1.11的内容：

(Properties of order). Let \( a, b, c \) be integers.

1. \( a > b \) if and only if \( a - b \) is a positive natural number.
2. (Addition preserves order) If \( a > b \), then \( a + c > b + c \).
3. (Positive multiplication preserves order) If \( a > b \) and \( c \) is positive, then \( ac > bc \).
4. (Negation reverses order) If \( a > b \), then \( -a < -b \).
5. (Order is transitive) If \( a > b \) and \( b > c \), then \( a > c \).
6. (Order trichotomy) Exactly one of the statements \( a > b \), \( a < b \), or \( a = b \) is true.

证明命题1：

必要性：

如果\( a > b \)，则\( \exists d \in \mathbf{N} \)，使得\( a = b + d \)，且\( a \neq b \)，假设\( d = 0 \)，则\( a = b + 0 = b \)，矛盾，故\( d \neq 0 \)，即\( d \)为正自然数。

充分性：

如果\( a - b \)为正自然数，则\( a = b + (a - b) = a \)，即\( \exists (d = a - b) \in \mathbf{N} \)，使得\( a = b + d \)。

证毕。

证明命题2：

如果\( a > b \)，则根据命题1，有\( a - b \)为正自然数，进而有\( (a + c) - (b + c) = a - b \)为正自然数，此时根据命题1，有\( a + c > b + c \)。

证毕。

证明命题3：

如果\( a > b \)，则有\( a - b \)为正自然数，又c为正自然数，此时有\( (a - b)c = ac - bc \)为正自然数，进而有\( ac > bc \)。

证毕。

证明命题4：

如果\( a > b \)，则有\( a - b \)为正自然数，进而有\( (-b) - (-a) = -b + a = a - b \)也为正自然数，可得\( -b > -a \)，也就是\( -a < -b \)。

证毕。

证明命题5：

如果\( a > b \)且\( b > c \)，则有\( a - b \)和\( b - c \)均为正自然数，于是\( (a - b) + (b - c) = a - c \)也是正自然数，这意味着\( a > c \)。

证毕。

证明命题6：

首先证明三者中至少有一个是成立的：

\( a - b \)为整数，故根据引理4.1.5，有三种情况有且仅有一种成立：

1. \( a - b \)为自然数。
2. \( a - b = 0 \)。
3. 存在正自然数\( n \)，使得\( -n = a - b \)。

如果是情况1，则因为\( a = b + (a - b) \)，可得\( a > b \)。如果是情况2，则\( a = b \)。如果是情况3，则\( b = a + (b - a) = a + n \)，可得\( b > a \)。

综上，三者中至少有一个是成立的，下面证明至多有一个命题是成立的：

\( a > b \)和\( a = b \)是矛盾的，故不可能同时成立。

\( a < b \)和\( a = b \)也是矛盾的，故不可能同时成立。

假设\( a > b \)和\( a < b \)同时成立，则存在两个正自然数\( d_0, d_1 \)，使得\( a = b + d_0, b = a + d_1 \)，进一步可得\( a = a + d_1 + d_0 \)，从而有\( d_0 + d_1 = 0 \)为正自然数，矛盾，故\( a > b \)和\( a < b \) 也不可能同时成立。

三者中两两不能同时成立，故也不可能三个同时成立，则至多只能有一个同时成立了，再加上至少有一个成立，可得：三者中有且仅有一种情况是成立的。

证毕。

练习4.1.8

题目：

Show that the principle of induction (Axiom 2.5) does not apply directly to the integers. More precisely, give an example of a property \( P(n) \) pertaining to an integer n such that \( P(0) \) is true, and that \( P(n) \) implies \( P(n+\!+) \) for all integers n, but that \( P(n) \) is not true for all integers \( n \). Thus induction is not as useful a tool for dealing with the integers as it is with the natural numbers. (The situation becomes even worse with the rational and real numbers, which we shall define shortly.)

例子：

\( P(n): n \)为自然数。

\( n = 0 \)自然数。

归纳假设当\( n = k \)时成立，当\( n = k+\!+ \)时，根据公理2.2，有\( k+\!+ \)也为自然数。

综上，\( P(n) \)符合公理2.5的模板，但是此时\( -1 \in \mathbf{Z} \)却不满足\( P(n) \)。

所以数学归纳法不能用在\( \mathbf{Z} \)吗？可以，分成两种情况，即自然数和非自然数进行数学归纳就行，针对\( n \)是自然数的情况，正常按公理2.5进行数学归纳就行。针对\( n \)是非自然数的情况，我们把归纳的命题写成类似： \( \forall n >= 1 \in \mathbf{N} \)，有\( P(-n) \)为真。最后利用引理\( 4.1.5 \)，得到：一个整数\( z \)要么是正自然数，要么是0，要么是某个正自然数的取反，如果是前两者，根据我们对\( z \)是自然数情况下的数学归纳，可得\( P(z) \)为真，如果是最后一种情况，可得存在正自然数\( n \)，使得\( -n = z \)，此时根据我们对\( z \)是非自然数情况下的数学归纳，可得\( P(-n) = P(z) \)为真。整个过程比较麻烦，不过是可行的。

章节4.2

练习4.2.1

题目：

Show that the definition of equality for the rational numbers is reflexive, symmetric, and transitive. (Hint: for transitivity, use Corollary 4.1.9.)

\( \forall x, y, z \in \mathbf{Q} \)，有\( \exists a, b, c, d, e, f \in \mathbf{Z} \)，使得\( x = a // b, y = c // d, z = e // f \)。

证明自反性：

因为\( ab = ab \)，故\( a // b = a // b \)，即\( x = x \)。

证毕。

证明对称性：

如果\( x = y \)，则有\( ad = cb \)，进而有\( cb = ad \)，即\( y = x \)。

证毕。

证明传递性：

如果\( x = y \)且\( y = z \)，则：因为\( x = y \)，有\( ad = cb \)。因为\( y = z \)，有\( cf = ed \)。综上，有\( adcf = cbed \)，消去\( c, d \)，得：\( af = be = eb \)，即\( x = z \)。

证毕。

练习4.2.2

题目：

Prove the remaining components of Lemma 4.2.3.

Lemma 4.2.3的内容：

The sum, product, and negation operations on rational numbers are well-defined, in the sense that if one replaces \( a // b \) with another rational number \( a' // b' \) which is equal to \( a // b \), then the output of the above operations remains unchanged, and similarly for \( c // d \).

注：文中已经证明了加法了，这里仅证明乘法和取反。

验证乘法满足代入公理：

\( (a // b) \times (c // d) = ac // bd \)。

首先验证\( a', b' \)代入\( a, b \)的情况：

\( (a' // b') \times (c // d) = a’c // b’d \)，因为\( a // b = a' // b' \)，故\( ab' = a’b \)，两边同乘\( cd \)，再整理下，可得\( acb’d // a’cbd \)，故\( ac // bd = a' = b’d \)，即\( (a // b) \times (c // d) = (a' // b') \times (c // d) \)。

接着验证\( c', d' \)代入\( c, d \)的情况：

\( (a // b) \times (c' // d') = ac' // bd' \)，因为\( c // d = c' // d' \)，故\( cd' = c’d \)，两边同乘\( ab \)，再整理下，可得\( acbd' = ac’bd \)，故\( ac // bd = ac' // bd' \)。

验证完毕。

验证取反满足代入公理：

\( -(a // b) = -a // b \)， \( -(a' // b') = -a' // b' \)，因为\( a // b = a' // b' \)，故\( ab' = a’b \)，两边同乘以\( -1 \)，可得\( -ab' = -a’b \)，即\( -a // b = -a' // b' \)。

验证完毕。

练习4.2.3

题目：

Prove the remaining components of Proposition 4.2.4. (Hint: as with Proposition 4.1.6, you can save some work by using some identities to prove others.)

Proposition 4.2.4的内容：

(Laws of algebra for rationals). Let \( x, y, z \) be rationals. Then the following laws of algebra hold:

1. x + y = y + x
2. (x + y) + z = x + (y + z)
3. x + 0 = 0 + x = x
4. x + (-x) = (-x) + x = 0
5. xy = yx
6. (xy)z = x(yz)
7. x1 = 1x = x
8. x(y + z) = xy + xz
9. (y + z)x = yx + zx

其中，第2个命题在书中已经证明过了，这里仍然再证一遍。

因为\( x, y, z \in \mathbf{Q} \)，故\( \exists a, b, c, d, e, f \in \mathbf{Z} \)，使得 \( x = a // b, y = c // d, z = e // f \)。

证明\( x + y = y + x \)：

\( x + y = (a // b) + (c // d) = (ad + bc) // bd \)， \( y + x = (c // d) + (a // b) = (cb + da) // db \)，而\( (ad + bc)db = addb + bcdb = cbbd + dabd = (cb + da)bd \)，故\( (ad + bc) // bd = (cb + da) // db \)，即\( x + y = y + x \)。

证毕。

证明\( (x + y) + z = x + (y + z) \)：

\( (x + y) + z = ((a // b) + (c // d)) + (e // f) = ((ad + bc) // bd) + (e // f) = ((ad + bc)f + bde) // bdf = (adf + bcf + bde) // bdf \)。

\( x + (y + z) = (a // b) + ((c // d) + (e // f)) = (a // b) + ((cf + de) // df) = (adf + b(cf + de)) // bdf = (adf + bcf + bde) // bdf = (x + y) + z \)。

证毕。

证明\( x + 0 = 0 + x = x \)：

\( x + 0 = (a // b) + (0 // 1) = (a + 0) // b = a // b = x \)。

根据命题1，有\( 0 + x = x + 0 = x \)。

证毕。

证明\( x + (-x) = (-x) + x = 0 \)：

\( x + (-x) = (a // b) + ((-a) // b) = (ab - ba) // bb = 0 // bb = 0 \)。

根据命题1，有\( (-x) + x = x + (-x) = 0 \)。

证毕。

证明\( xy = yx \)：

\( xy = a // b \times c // d = ac // bd = ca // db = (c // d) \times (a // b) = yx \)。

证毕。

证明\( (xy)z = x(yz) \)：

\( (xy)z = ((a // b) \times (c // d)) \times (e // f) = (ac // bd) \times (e // f) = ace // bdf \)。

\( x(yz) = (a // b) \times ((c // d) \times (e // f)) = (a // b) \times (ce // df) = ace // bdf = (xy)z \)。

证毕。

证明\( x1 = 1x = x \)：

\( x1 = (a // b) \times (1 // 1) = a // b = x \)。

根据命题1，有\( 1x = x1 = x \)。

证毕。

证明\( x(y + z) = xy + xz \)：

\( x(y + z) = (a // b) \times ((c // d) + (e // f)) = (a // b) \times ((cf + de) // df) = (acf + ade) // bdf \)。

\( xy + xz = ((a // b) \times (c // d)) + ((a // b) \times (e // f)) = (ac // bd) + (ae // bf) = (acbf + bdae) // bdbf = (acf + ade) // bdf = x(y + z) \) 。

证毕。

证明\( (y + z)x = yx + zx \)：

根据命题1，\( (y + z)x = x(y + z) = xy + xz = yx + zx \)。

证毕。

练习4.2.4

题目：

Prove Lemma 4.2.7. (Note that, as in Proposition 2.2.13, you have to prove two different things: firstly, that at least one of (a), (b), (c) is true; and secondly, that at most one of (a), (b), (c) is true.)

Lemma 4.2.7的内容：

(Trichotomy of rationals). Let \( x \) be a rational number. Then exactly one of the following three statements is true: (a) \( x \) is equal to 0. (b) \( x \) is a positive rational number. (c) \( x \) is a negative rational number.

证明：

首先证明三者中至少有一个是成立的：

因为\( x \)为有理数，故存在整数\( a, b \)，使得\( x = a // b \)，针对整数\( a \)，三种情况有且仅有一种成立：\( a \)为正自然数，\( a = 0 \)， \( \exists n_0 > 0 \in \mathbf{Z}, a = -n_0 \)，同理\( b \)也有三种情况，且有且仅有一种成立： \( b \)为正自然数，\( b = 0 \)，\( \exists n_1 > 0 \in \mathbf{Z}, b = -n_1 \)。

如果\( a = 0 \)，则\( x = 0 \)。如果\( a, b \)均为正自然数，则根据定义，\( x \)为正有理数。如果\( \exists n_0 > 0, n_1 > 0 \in \mathbf{Z}, a = -n_0, b = -n_1 \)，则\( x = a // b = (-n_0) // (-n_1) = n_0 // n_1 \)，此时根据定义，\( x \)为正有理数。如果（\( \exists n_0 > 0 \in \mathbf{Z}, a = -n_0 \)且\( b \)为正自然数）或者（\( a \)为正自然数且\( \exists n_1 > 0 \in \mathbf{Z}, b = -n_1 \)），则均有\( x = (-a) // b \)，此时根据定义，\( x \)为负有理数。

综上，不论什么情况下，均至少有一种情况成立。

现在，证明三者中至多有一个是成立的：

如果\( x \)为正有理数且\( x = 0 \)，则\( \exists a > 0, b > 0 \in \mathbf{Z}, x = a // b = 0 // 1 \)，从而有\( a = 0 \)，这个和\( a > 0 \)矛盾，该种情况不可能。

如果\( x \)为负有理数且\( x = 0 \)，则\( \exists a > 0, b > 0 \in \mathbf{Z}, x = (-a) // b = 0 // 1 \)，从而有\( -a = 0 \)，即\( a = 0 \)，这个和\( a > 0 \)矛盾，该种情况不可能。

如果\( x \)同时为正有理数以及负有理数，则\( \exists a > 0, b > 0, a' > 0, b' > 0 \in \mathbf{Z}, x = a // b = (-a') // b \)，可得\( ab = -a’b \)，然而正整数\( ab \)是不可能等于负整数\( -a’b \)的，产生矛盾，故该种情况不可能。

综上，有三者中两两不能同时成立，故也不可能三个同时成立，即至多有一个是成立的，再加上至少有一个成立，可得三者中有且仅有一个是成立的。

练习4.2.5

题目：

Prove Proposition 4.2.9.

Proposition 4.2.9的内容：

(Basic properties of order on the rationals). Let \( x, y, z \) be rational numbers. Then the following properties hold.

1. (Order trichotomy) Exactly one of the three statements \( x = y \), \( x < y \), or \( x > y \) is true.
2. (Order is anti-symmetric) One has \( x < y \) if and only if \( y > x \).
3. (Order is transitive) If \( x < y \) and \( y < z \), then \( x < z \).
4. (Addition preserves order) If \( x < y \), then \( x + z < y + z \).
5. (Positive multiplication preserves order) If \( x < y \) and \( z \) is positive, then \( xz < yz \).

注：证明中用到了两个正有理数相乘为正有理数，这个很容易证明，这里直接假设证过了。

证明命题1：

首先证明三者中至少有一个是成立的：

根据引理4.2.7，\( x - y \)有三种情况，且有且仅有一种成立：

1. \( x - y = 0 \)
2. \( x - y \)为正有理数
3. \( x - y \)为负有理数

如果\( x - y = 0 \)，则\( x = y \)。如果\( x - y \)为正有理数，则根据定义，有\( x > y \)。如果\( x - y \)为负有理数，则根据定义，有\( x < y \)。

综上，不论什么情况下，均至少有一种情况成立。

现在，证明三者中至多有一个是成立的：

如果\( x > y \)且\( x = y \)，则\( x - y \)为正有理数且\( x - y = 0 \)，根据引理4.2.7，这两个不可能同时成立。

如果\( x < y \)且\( x = y \)，则\( x - y \)为负有理数且\( x - y = 0 \)，根据引理4.2.7，这两个不可能同时成立。

如果\( x > y \)且\( x < y \)，则\( x - y \)同时为正有理数以及负有理数，根据引理4.2.7，这两个不可能同时成立。

综上，有三者中两两不能同时成立，故也不可能三个同时成立，即至多有一个是成立的，再加上至少有一个成立，可得三者中有且仅有一个是成立的。

证毕。

证明命题2：

必要性：

如果\( x < y \)，则\( x - y \)为负有理数，此时\( -(x - y) = y - x \)为正有理数，可得\( y > x \)。

充分性：

如果\( y > x \)，则\( y - x \)为正有理数，此时\( -(y - x) = x - y \)为负有理数，可得\( x < y \)。

证毕。

证明命题3：

因为\( x < y \)且\( y < z \)，有\( x - y \)和\( y - z \)均为负有理数，故\( (x - y) + (y - z) = x - z \)也为负有理数（注：如果\( x - z \)为正有理数，则\( -(x - y) + (-(y - z)) = z - x \)为负有理数，即两个正有理数相加为负有理数，矛盾），即\( x < z \)。

证毕。

证明命题4：

如果\( x < y \)，则\( x - y \)为负有理数，故\( (x + z) - (y + z) = x - y \)为负有理数，即\( x + z < y + z \)。

证毕。

证明命题5：

如果\( x < y \)，则\( x - y \)为负有理数，从而有\( y - x \)为正有理数，又\( z \)为正有理数，故\( z(y - x) = zy - zx = -xz + yz \)也是正有理数，进一步有\( -(-xz + yz) = xz - yz \)为负有理数，即\( xz < yz \)。

证毕。

练习4.2.6

题目：

Show that if \( x, y, z \) are rational numbers such that \( x < y \) and \( z \) is negative, then \( xz > yz \).

证明：

如果\( x < y \)，则\( x - y \)为负有理数，从而\( y - x \)为正有理数，又\( z \)为负有理数，故\( -z \)为正有理数，从而有\( (-z)(y - x) = -zy + zx = xz - yz \)为正有理数，即\( xz > yz \)。

章节4.3

练习4.3.1

题目：

Prove Proposition 4.3.3. (Hint: while all of these claims can be proven by dividing into cases, such as when x is positive, negative, or zero, several parts of the proposition can be proven without such a tedious division into cases. For instance one can use earlier parts of the proposition to prove later ones.)

Proposition 4.3.3的内容：

(Basic properties of absolute value and distance). Let\( x, y, z \) be rational numbers.

1. (Non-degeneracy of absolute value) We have \( |x| \geq 0 \). Also, \( |x| = 0 \) if and only if x is \( 0 \).
2. (Triangle inequality for absolute value) We have \( |x + y| \leq |x| + |y| \).
3. We have the inequalities \( -y \leq x \leq y \) if and only if \( y \geq |x| \). In particular, we have \( -|x| \leq x \leq |x| \).
4. (Multiplicativity of absolute value) We have \( |xy| = |x||y| \). In particular, \( |-x| = |x| \).
5. (Non-degeneracy of distance) We have \( d(x, y) \geq 0 \). Also, \( d(x, y) = 0 \) if and only if \( x = y \).
6. (Symmetry of distance) \( d(x, y) = d(y, x) \).
7. (Triangle inequality for distance) \( d(x, z) \leq d(x, y) + d(y, z) \).

证明命题1：

证明\( |x| \geq 0 \)：

如果\( x > 0 \)，则\( |x| = x \geq 0 \)，如果\( x = 0 \)，则\( |x| = 0 \geq 0 \)，如果\( x < 0 \)，则\( |x| = -x \geq 0 \)，综上，不管什么情况，都有\( |x| \geq 0 \)。

证明\( |x| = 0 \equiv x = 0 \)：

必要性：

如果\( |x| = 0 \)，此时假设\( x > 0 \)或\( x < 0 \)，如果\( x > 0 \)，则\( |x| = x > 0 \)，这和\( |x| = 0 \)矛盾，如果\( x < 0 \)，则\( |x| = -x > 0 \)，这也和\( |x| = 0 \)矛盾，综上，假设不成立，有\( |x| = 0 \)。

充分性：

如果\( x = 0 \)，则根据绝对值的定义，有\( |x| = 0 \)。

证毕。

证明命题3：

先证明命题3，可以简化命题2的证明。

必要性：

如果\( -y \leq x \leq y \)，此时分多种情况讨论：

1. 如果\( x \geq 0 \)，则\( |x| = x \leq y \)。
2. 如果\( x < 0 \)，此时可能有：
   1. \( -y \leq x \leq y < 0 \)，但是这意味着\( -y > 0 > y \)，矛盾，故该种情况不可能。
   2. \( -y \leq x < 0 \leq y \)，则此时\( -y \leq x \)，两边同乘\( -1 \)，得：\( y \geq -x \)，而\( |x| = -x \)，故\( |x| \leq y \)。

综上，不论什么情况下，都有\( |x| < y \)。

充分性：

如果\( |x| < y \)，此时分多种情况讨论：

1. 如果\( x \geq 0 \)，则\( 0 \leq |x| = x \leq y \)，可得\( -y \leq 0 \)，进一步可得\( -y \leq x \leq y \)。
2. 如果\( x < 0 \)，则\( |x| = -x \leq y \)，\( -x \leq y \)两边同乘\( -1 \)，得\( x \geq -y \)，现在有\( -x \leq y \)且\( x \geq -y \)，即\( -y \leq x \leq y \)。

证毕。

最后，因为\( |x| \leq |x| \)，故\( -|x| \leq x \leq |x| \)。

证明命题2：

因为\( |x| \leq |x|, |y| \leq |y| \)，由命题2，得：\( -|x| \leq x \leq |x|, -|y| \leq y \leq |y| \)，两式相加得：\( -(|x| + |y|) \leq x + y \leq |x| + |y| \)，最后再根据命题2，有\( |x + y| \leq |x| + |y| \)。

证毕。

证明命题4：

如果\( x \geq 0, y \geq 0 \)，则\( xy \geq 0, |xy| = xy = |x||y| \)。如果\( x \leq 0, y \leq 0 \)，则\( xy \geq 0, |xy| = xy, |x||y| = (-x)(-y) = xy = |xy| \)。如果\( x, y \)两者中有且仅有一个\( \leq 0 \)，另外一个则\( \geq 0 \)，不妨设\( x \leq 0 \)，则\( xy \leq 0, |xy| = -xy, |x||y| = (-x)y = |xy| \)。

综上，有\( |xy| = |x||y| \)。

证毕。

最后，我们有\( |-x| = |-1||x| = |x| \)。

证明命题5：

因为\( d(x, y) = |x - y| \)，故根据命题1，有\( d(x, y) \geq 0 \)。

如果\( d(x, y) = |x - y| = 0 \)，则根据命题1，有\( x - y = 0 \)，即\( x = y \)。

证毕。

证明命题6：

\( d(x, y) = |x - y|, d(y, x) = |y - x| = |-(x - y)| = |-1||x - y| = |x - y| = d(x, y) \)。

证毕。

证明命题7：

根据命题2，\( d(x, z) = |x - z| = |x - y + y - z| = |(x - y) + (y - z)| \leq |x - y| + |y - z| = d(x, y) + d(y, z) \)。

证毕。

练习4.3.2

题目：

Prove the remaining claims in Proposition 4.3.7.

Proposition 4.3.7的内容：

1. If \( x = y \), then \( x \) is \( \epsilon \)-close to \( y \) for every \( \epsilon > 0 \). Conversely, if \( x \) is \( \epsilon \)-close to \( y \) for every \( \epsilon > 0 \), then we have \( x = y \).
2. Let \( \epsilon > 0 \). If \( x \) is \( \epsilon \)-close to \( y \), then \( y \) is \( \epsilon \)-close to \( x \).
3. Let \( \epsilon > 0 \). If \( x \) is \( \epsilon \)-close to \( y \), and y is \( \delta \)-close to z, then \( x \) and \( z \) is \( \epsilon + \delta \)-close.
4. Let \( \epsilon, \delta > 0 \). If \( x \) and \( y \) are \( \epsilon \)-close, and \( z \) and \( w \) are \( \delta \)-close, then \( x + z \) and \( y + w \) are (\( \epsilon + \delta \))-close, and \( x - z \) and \( y - w \) are also (\( \epsilon + \delta \))-close.
5. Let \( \epsilon > 0 \). If \( x \) and \( y \) are \( \epsilon \)-close, they are also \( \epsilon' \)-close for every \( \epsilon' > \epsilon \).
6. Let \( \epsilon > 0 \). If \( y \) and \( z \) are both \( \epsilon \)-close to \( x \), and \( w \) is between \( y \) and \( z \) (i.e., \( y ≤ w ≤ z \) or \( z ≤ w ≤ y \)), then \( w \) is also \( \epsilon \)-close to \( x \).
7. Let \( \epsilon > 0 \). If \( x \) and \( y \) are \( \epsilon \)-close, and \( z \) is non-zero, then \( xz \) and \( yz \) are \( \epsilon|z| \)-close.
8. Let \( \epsilon, \delta > 0 \). If \( x \) and \( y \) are \( \epsilon \)-close, and \( z \) and \( w \) are \( \delta \)-close, then \( xz \) and \( yw \) are (\( \epsilon|z| + \delta|x| + \epsilon\delta \))-close.

注：命题8文中已经证明了，这里不再证明。

证明命题1：

必要性：

如果\( x = y \)，则\( \forall \epsilon > 0, d(x, y) = 0 < \epsilon \)。

充分性：

如果\( \forall \epsilon > 0 \)，有\( x \) \( \epsilon \)-接近 \( y \)，此时假设\( x \neq y \)，则令\( \epsilon_1 = |x - y| / 2 > 0 \)，可得\( d(x, y) = |x - y| > \epsilon_1 \)，即\( x \)不\( \epsilon_1 \)-接近\( y \)，矛盾，故假设不成立，有\( x = y \)。

证毕。

证明命题2：

如果\( x \) \( \epsilon \)-接近 \( y \)，则\( d(x, y) \leq \epsilon \)，从而有\( d(y, x) = d(x, y) \leq \epsilon \)，即\( y \) \( \epsilon \)-接近\( x \)。

证毕。

（注：之后我们可以直接说\( x, y \) \( \epsilon \)-接近了，而不一定要说\( x \) \( \epsilon \)-接近\( y \)了，这是因为根据该命题，\( \epsilon \)接近具有对称性，所以谁接近谁无所谓。）

证明命题3：

如果\( x, y \) \( \epsilon \)-接近，\( y, z \) \( \delta \)-接近，则\( d(x, y) \leq \epsilon, d(y, z) \leq \delta \)，根据定理4.3.3的命题7，有\( d(x, z) \leq d(x, y) + d(y, z) \leq \epsilon + \delta \) 即\( x, z \) \( \epsilon + \delta \)-接近。

证毕。

证明命题4：

如果\( x, y \) \( \epsilon \)-接近，\( z, w \) \( \delta \)-接近，则\( d(x, y) \leq \epsilon, d(z, w) \leq \delta \)，从而有：

1. \( d(x + z, y + w) = |(x + z) - (y + w)| = |(x - y) + (z - w)| \leq |x - y| + |z - w| \leq \epsilon + \delta \)
2. \( d(x - z, y - w) = |(x - z) - (y - w)| = |(x - y) + (- (z - w))| \leq |x - y| + |(- (z - w))| = |x - y| + |-1||z - w| = |x - y| + |z - w| \leq \epsilon + \delta \)

由1得\( x + z, y + w \) \( (\epsilon + \delta) \)-接近，由2得\( x - z, y - w \)也\( (\epsilon + \delta) \)-接近。

证毕。

证明命题5：

如果\( x, y \) \( \epsilon \)-接近，则\( d(x, y) \leq \epsilon \)，此时\( \forall \epsilon' > \epsilon \)，有\( d(x, y) \leq \epsilon \leq \epsilon' \)，即\( x, y \) \( \epsilon' \)-接近。

证毕。

证明命题6：

如果\( y, z \)都\( \epsilon \)-接近\( x \)，则\( d(y, x) = |y - x| \leq \epsilon, d(z, x) = |z - x| \leq \epsilon \)，此时根据定理4.3.3的命题3，有\( -\epsilon \leq y - x \leq \epsilon, -\epsilon \leq z - x \leq \epsilon \)。又因为\( w \)在\( y \)和\( z \)之间，故\( y \leq w \leq z \)或\( z \leq w \leq y \)。如果\( y \leq w \leq z \)，则同加\( -x \)，得\( -\epsilon \leq y - x \leq w - x \leq y - x \leq \epsilon \)，即\( -\epsilon \leq w - x \leq \epsilon \)，进而得\( |w - x| \leq \epsilon \)，也就是\( w, x \) \( \epsilon \)-接近。如果\( z \leq w \leq y \)，则同理可得\( w, x \) \( \epsilon \)-接近。

证毕。

证明命题7：

因为\( z \)非0，故\( |z| > 0 \)（注：\( \epsilon \)-接近，要求\( \epsilon > 0 \)）。

如果\( x, y \) \( \epsilon \)-接近，则\( d(x, y) = |x - y| \leq \epsilon \)，不等式两边同乘\( |z| > 0 \)，得\( |z||x - y| = |z(x - y)| = |xz - yz| \leq |z|\epsilon \)，即\( xz, yz \) \( |z|\epsilon \)-接近。

证毕。

练习4.3.3

题目：

Prove Proposition 4.3.10. (Hint: use induction.)

Proposition 4.3.10的内容：

(Properties of exponentiation, I). Let \( x, y \) be rational numbers, and let \( n, m \) be natural numbers.

1. We have \( x^nx^m = x^{n + m} \), \( (x^n)^m = x^{nm} \), and \( (xy)^n = x^ny^n \).
2. Suppose \( n > 0 \). Then we have \( x^n = 0 \) if and only if \( x = 0 \).
3. If \( x \geq y \geq 0 \), then \( x^n \geq y^n \geq 0 \). If \( x > y \geq 0 \) and \( n > 0 \), then \( x^n > y^n \geq 0 \).
4. We have \( |x^n| = |x|^n \).

证明命题1：

证明\( x^nx^m = x^{n + m} \)：

对\( n \)进行数学归纳。

当\( n = 0 \)时，左边 = \( x^nx^m = x^0x^m = x^m \)，右边 = \( x^{0 + m} = x^m \)，左边 = 右边，成立。

归纳假设当\( n = k \)时成立，当\( n = k+\!+ \)时，\( x^{k+\!+}x^m = (x^kx)x^m = (x^kx^m)x = x^{k + m}x = x^{k + 1 + m} \)，即\( n = k+\!+ \)时成立。

证毕。

证明\( (xy)^n = x^ny^n \)：

对\( n \)进行数学归纳。

当\( n = 0 \)时，左边 = \( (xy)^n = (xy)^0 = 1 \) ，右边 = \( x^ny^n = x^0y^0 = 1 \)，左边 = 右边，成立。

归纳假设当\( n = k \)时成立，当\( n = k+\!+ \)时，\( (xy)^{k+\!+} = (xy)^k(xy) = (x^ky^k)(xy) = (x^kx)(y^ky) = x^{k+\!+}y^{k+\!+} \)，即\( n = k+\!+ \)时成立。

证毕。

证明\( (x^n)^m = x^{nm} \)：

对\( n \)进行数学归纳。

当\( n = 0 \)时，左边 = \( (x^n)^m = (x^0)^m = 1^m = 1 \)，右边 = \( x^{0m} = x^0 = 1 \)，左边 = 右边，成立。

归纳假设当\( n = k \)时成立，当\( n = k+\!+ \)时，\( (x^{k+\!+})^m = (x^kx)^m = (xx^k)^m = (x^m(x^k)^m) = x^mx^{km} = x^{m + km} = x^{(k + 1)m} \)，即\( n = k+\!+ \)时成立。

证毕。

证明命题2：

必要性：

首先证明一个引理：如果\( x \neq 0 \)，则\( \forall n \in \mathbf{N}, x^n \neq 0 \)。

对\( n \)进行数学归纳。

当\( n = 0 \)时，\( x^0 = 1 \neq 0 \)，成立。

归纳假设当\( n = k \)时成立，当\( n = k+\!+ \)时，\( x^{k+\!+} = x^kx \)，根据归纳假设，有\( x^k \neq 0 \)，此时假设\( x^kx = 0 \)，则有\( x^k = 0 \)或\( x = 0 \)，矛盾，故\( x^kx \neq 0 \)，归纳完毕。

现在，继续回去证明必要性。

如果\( n > 0 \)且\( x^n = 0 \)，此时假设\( x \neq 0 \)，则\( x^n \neq 0 \)，矛盾，故假设不成立，有\( x = 0 \)。

充分性：

如果\( x = 0 \)，令\( m = n - 1 \)，则充分性的证明等价于证明\( x^{m + 1} = 0 \)，对\( m \)进行数学归纳。

当\( m = 0 \)时，\( x^{m + 1} = x^1 = x = 0 \)，成立。

归纳假设当\( m = k \)时成立，当\( m = k+\!+ \)时，\( x^{(k+\!+) + 1} = x^{k+\!+}x \)，根据归纳假设，有\( x^{k + 1} = x^{k+\!+} = 0 \)，从而有\( x^{k+\!+}x = 0 \)，

综上，\( m = k+\!+ \)时成立，归纳完毕。

证毕。

证明命题3：

对\( n \)进行数学归纳。

当\( n = 0 \)时：

如果\( x \geq y \geq 0 \)，则\( x^1 \geq y^1 \geq 0 \)。

如果\( x > y \geq 0 \)，则\( x^1 > y^1 \geq 0 \)。

归纳假设当\( n = k \)时成立，当\( n = k+\!+ \)时：

如果\( x \geq y \geq 0 \)，则根据归纳假设，有\( x^k \geq y^k \geq 0 \)，同乘\( x \)，得\( x^{k+\!+} \geq xy^k \geq 0 \ \)，又\( x \geq y \geq 0 \)，故\( xy^k \geq yy^k = y^{k+\!+} \geq 0 \)，综合可得\( x^{k+\!+} \geq xy^k \geq y^{k+\!+} \geq 0 \)。

如果\( x > y \geq 0 \)，则根据归纳假设，有\( x^k > y^k \geq 0 \)，同乘\( x \)，得\( x^{k+\!+} > xy^k \geq 0 \)，又\( x > y \geq 0 \)，故\( xy^k \geq yy^k = y^{k+\!+} \geq 0 \) （注：因为\( y^k \geq 0 \)，即\( y^k \)有可能是0，故这里只能得到\( xy^k \geq y^{k+\!+} \)而不能得到\( xy^k > y^{k+\!+} \)，不过已经足够了），综合可得\( x^{k+\!+} > xy^k \geq y^{k+\!+} \geq 0 \)，即\( x^{k+\!+} > y^{k+\!+} \geq 0 \)。

综上，有\( n = k+\!+ \)时成立，归纳完毕。

证毕。

证明命题4：

对\( n \)进行数学归纳。

当\( n = 0 \)时，左边 = \( |x^n| = |x^0| = |1| = 1 \)，右边 = \( |x|^n = |x|^0 = 1 \)，左边 = 右边，成立。

归纳假设当\( n = k \)时成立，当\( n = k+\!+ \)时，\( |x|^{k+\!+} = |x|^k|x| = |x|^k|x| = |x|^{k+\!+} \)，即\( n = k+\!+ \)时是成立的。

证毕。

练习4.3.4

题目：

Prove Proposition 4.3.12. (Hint: induction is not suitable here. Instead, use Proposition 4.3.10.)

Proposition 4.3.12的内容：

(Properties of exponentiation, II). Let \( x, y \) be non-zero rational numbers, and let \( n, m \) be integers.

1. We have \( x^nx^m = x^{n + m} \), \( (x^n)^m = x^{nm} \), and \( (xy)^n = x^ny^n \).
2. If \( x \geq y > 0 \), then \( x^n \geq y^n > 0 \) if \( n \) is positive, and \( 0 < x^n \leq y^n \) if \( n \) is negative（注：额外的，我们会证明，如果\( x > y > 0 \)，则\( \geq \)和\( \leq \)可以分别提升成\( > \)和\( < \)）.
3. If \( x, y > 0, n \neq 0 \), and \( x^n = y^n \), then \( x = y \).
4. We have \( |x^n| = |x|^n \).

注：证明中用到了\( \forall n \in \mathbf{N}, x \in \mathbf{Q}, (1 / x)^n = 1^n / x^n = 1 / x^n \)，这个通过数学归纳法很容易证明，这里直接假设证过了。

证明命题1：

证明\( x^nx^m = x^{n + m} \)：

如果\( n, m \)都是自然数，则根据定理4.3.10的命题1，命题成立。

如果\( n, m \)都是负数，则左边 = \( x^nx^m = = (1 / x^{-n})(1 / x^{-m}) = 1 / (x^{-n}x^{-m}) = 1 / (x^{-n - m}) \)，右边 = \( x^{n + m} = 1 / (x^{-n - m}) \)，左边 = 右边，命题成立。

如果两者中一个是自然数，一个是负数，不妨设\( n \)是自然数，\( m \)是负数（注：因为\( m, n \)在等式中的角色是对称的，所以这样设没问题），此时分两种情况来讨论：

1. 如果\( n + m \geq 0 \)，根据4.3.10的命题1，有\( x^{n + m}x^{-m} = x^n \)，则此时\( x^nx^m = (x^{n + m}x^{-m})x^m = x^{n + m}(x^{-m}x^m) = x^{n + m}((1 / x^m)x^m) = x^{n + m} \)。
2. 如果\( n + m < 0 \)，根据4.3.10的命题1，有 \( x^{-n}x^{n + m} = (1 / x^{n})(1 / x^{-n - m}) = 1 / (x^{n}x^{-n - m}) = 1 / x^{-m} = x^m \)，则此时\( x^nx^m = x^n(x^{-n}x^{n + m}) = (x^nx^{-n})x^{n + m} = (x^n(1 / x^n))x^{n + m} = x^{n + m} \)。

综上，命题成立。

证毕。

证明\( (x^n)^m = x^{nm} \)：

如果\( n, m \)都是自然数，则根据定理4.3.10的命题1，命题成立。

如果\( n, m \)都是负数，则\( (x^n)^m = (1 / x^{-n})^{-m} = 1 / (1 / x^n)^m = 1 / (1 / (x^n)^m) = 1 / (1 / x^{nm}) = x^{nm} \) ，命题成立。

如果\( n \)为负数，\( m \)为自然数，则\( (x^n)^m = (1 / x^{-n})^m = 1 / (x^{-n})^m = 1 / x^{-nm} = x^{nm} \)，命题成立。

证毕。

证明\( (xy)^n = x^ny^n \)：

如果\( n \)是自然数，则根据定理4.3.10的命题1，命题成立。

如果\( n \)是负数，则\( (xy)^n = 1 / (xy)^{-n} = 1 / (x^{-n}y^{-n}) = (1 / x^{-n})(1 / y^{-n}) = x^ny^n \)。

证毕。

证明命题2：

先证明如果\( n \)是自然数，则\( y^n > 0 \)：因为\( y > 0 \geq 0 \)，根据定理4.3.10的命题3，可得\( y^n > 0^n \geq 0 \)，即\( y^n > 0 \)。

如果\( n \)为正整数，则根据定理4.3.10的命题3，可得\( x^n \geq y^n \geq 0 \)，又\( y^n > 0 \)，可得\( x^n \geq y^n > 0 \)，命题成立。

如果\( n \)为负数，则根据定理4.3.10的命题3，有\( x^{-n} \geq y^{-n} \geq 0 \)，又\( y^{-n} > 0 \)，可得\( x^{-n} \geq y^{-n} > 0 \)，即\( (1 / x^{n}) \geq (1 / y^{n}) > 0 \)，同乘\( x^{n}y^{n} > 0 \)，得\( y^{n} \geq x^{n} > 0 \)，即\( 0 < x^{n} \leq y^{n} \)，命题成立。

额外的，我们证明，如果\( x > y > 0 \)，则\( \geq \)和\( \leq \)可以分别提升成\( > \)和\( < \)：

如果\( n \)为正整数，则根据定理4.3.10的命题3，可得\( x^n > y^n \geq 0 \)，又\( y^n > 0 \)，可得\( x^n > y^n > 0 \)，命题成立。

如果\( n \)为负数，则根据定理4.3.10的命题3，有\( x^{-n} > y^{-n} \geq 0 \)，又\( y^{-n} > 0 \)，可得\( x^{-n} > y^{-n} > 0 \)，即\( (1 / x^{n}) > (1 / y^{n}) > 0 \)，同乘\( x^{n}y^{n} > 0 \)，得\( y^{n} > x^{n} > 0 \)，即\( 0 < x^{n} < y^{n} \)，命题成立。

证毕。

证明命题3：

假设\( x > y > 0 \)，则根据命题2中我们额外的证明的定理，有\( x^n > y^n > 0 \)，这和\( x^n = y^n \)矛盾，故不可能。

假设\( x < y < 0 \)，则根据命题2中我们额外的证明的定理，有\( 0 < x^n < y^n \)，这和\( x^n = y^n \)矛盾，故不可能。

故仅剩\( x = y \)这种可能了，由序的三元论（Trichotomy），得至少得有一个成立，于是有\( x = y \)成立。

证毕。

证明命题4：

如果\( n \)为自然数，则根据定理4.3.10的命题4，命题成立。

如果\( n \)为负数，则\( |x^n| = |1 / x^{-n}| = 1 / |x^{-n}| = 1 / |x|^{-n} = |x|^n \)，命题成立。

证毕。

练习4.3.5

题目：

Prove that \( 2^N \geq N \) for all positive integers \( N \). (Hint: use induction.)

注：实际上，当\( N \)为0时也成立，不一定要正整数，但这里还是按题目来。

证明：

首先，先证明一个引理：\( \forall M \in \mathbf{N}, 2(M + 1) \geq M + 2 \)：

当\( M = 0 \)时，\( 2(M + 1) = 2(0 + 1) = 2 \geq ((M + 2) = 0 + 2 = 2) \)，成立。

归纳假设当\( M = K \)时成立，当\( M = K+\!+ \)时， \( 2((K+\!+) + 1) = 2(K+\!+) + 2 \)，根据归纳假设，有\( 2(K+\!+) = 2(K + 1) \geq K + 2 \)，进一步可得\( 2((K+\!+) + 1) = 2(K+\!+) + 2 \geq K + 4 > (K+\!+) + 2 \)，即\( M = K+\!+ \)时成立，归纳完毕。

证明完引理，现在回去证明题目：

令\( M = N - 1 \)，证明题目等价于证明\( 2^{M + 1} \geq M + 1 \)。

当\( M = 0 \)时，\( 2^{M + 1} = 2 \geq (1 = M + 1) \)，成立。

归纳假设当\( M = K \)时成立，当\( M = K+\!+ \)时， \( 2^{(K+\!+) + 1} = 2^{K+\!+} \times 2 = 2^{K + 1} \times 2 \geq ((K + 1) \times 2 = (K+\!+) + K + 1) \geq (K+\!+) + 1 \)，即\( M = K+\!+ \)时成立，归纳完毕。

证毕。

章节4.4

练习4.4.1

题目：

Prove Proposition 4.4.1. (Hint: use Proposition 2.3.9.)

Proposition 4.4.1的内容：

(Interspersing of integers by rationals). Let \( x \) be a rational number. Then there exists an integer \( n \) such that \( n \leq x < n + 1 \). In fact, this integer is unique (i.e., for each \( x \) there is only one \( n \) for which \( n \leq x < n + 1 \)). In particular, there exists a natural number \( N \) such that \( N > x \) (i.e., there is no such thing as a rational number which is larger than all the natural numbers).

证明：

如果\( x \geq 0 \)，则\( \exists p, q \in \mathbf{N}, q \neq 0, x = p / q \)，此时根据定理2.3.9，\( \exists m, r \in \mathbf{N}, 0 \leq r < q, p = mq + r \)，进而有\( m = mq / q \leq ((mq + r) / q = p / q) \)以及 \( m + 1 = (mq + q) / q > ((mq + r) / q = p / q) \)，即\( m \leq x < m + 1 \)，这里\( m \)就是我们要找的\( n \)。

如果\( x < 0 \)，则\( \exists p, q \in \mathbf{N}, q \neq 0, x = -p / q \)，因为\( p / q > 0 \)，根据定理2.3.9，有 \( \exists m, r \in \mathbf{N}, 0 \leq r < q, p = mq + r \)，进而有\( -m - 1 = -(m + 1)q / q \leq (-(mq + r) / q = -p / q ) \) 以及\( -m = -mq / q > (-(mq + r) / q = -p / q) \)，即\( -m - 1 \leq x < -m \)，这里\( -m - 1 \)就是我们要找的\( n \)。

下面证明\( n \)的唯一性，如果存在\( n \neq n' \in \mathbf{Z} \)，使得\( n \leq x < n + 1, n' \leq x < n' + 1 \)，假设\( n > n' \)，则\( n - n' \geq 1 \)，进而有\( n \geq n' + 1 \)，可得\( n' \leq x < n' + 1 \leq n \)，这和\( n \leq x \)矛盾，故不可能。假设\( n < n' \)，则\( n' - n \geq 1 \)，进而有\( n' \geq n + 1 \) ，可得\( n \leq x < n + 1 \leq n' \)，这和\( n' \leq x \)矛盾，故不可能。综上，仅剩\( n = n' \)这个可能，又因至少有一个得成立，有\( n = n' \)。

证毕。

练习4.4.2

题目：

A definition: a sequence \( a_0 , a_1 , a_2 , \dots \) of numbers (natural numbers, integers, rationals, or reals) is said to be in infinite descent if we have \( a_n > a_{n + 1} \) for all natural numbers \( n \) (i.e., \( a_0 > a_1 > a_2 > \dots \)).

1. Prove the principle of infinite descent: that it is not possible to have a sequence of natural numbers which is in infinite descent. (Hint: assume for sake of contradiction that you can find a sequence of natural numbers which is in infinite descent. Since all the a \( n \) are natural numbers, you know that \( a_n \geq 0 \) for all \( n \). Now use induction to show in fact that \( a_n \geq k \) for all \( k \in N \) and all \( n \in N \), and obtain a contradiction.)
2. Does the principle of infinite descent work if the sequence \( a_1 , a_2 , a_3 , \dots \) is allowed to take integer values instead of natural number values? What about if it is allowed to take positive rational values instead of natural numbers? Explain.

注：这里实际上还没有定义序列的概念，序列的定义请参考章节5.1。

证明题目1：

首先证明一个引理：\( \forall k \in \mathbf{N}, a_n - a_{n + k} \geq k \)：

当\( k = 0 \)时，\( a_n - a_{n + k} = a_n - a_n = 0 \geq (k = 0) \)，成立。

归纳假设当\( k = c \)时成立，当\( k = c+\!+ \)时，\( a_n - a_{n + (k+\!+)} = (a_n - a_{n + k}) + (a_{n + k} - a_{n + (k+\!+)}) \)，根据归纳假设，有\( a_n - a_{n + k} \geq k \)，而根据序列的性质\( a_n > a_{n + 1} \)，有\( a_{n + k} - a_{n + (k+\!+)} \geq 1 \)，综合可得\( a_n - a_{n + (k+\!+)} = (a_n - a_{n + k}) + (a_{n + k} - a_{n + (k+\!+)}) \geq k + 1 \)，即\( n = k+\!+ \)时，成立，归纳完毕。

接着，\( \forall k \in \mathbf{N} \)，我们证明\( \forall n \in \mathbf{N} \)，有\( a_n \geq k \)。

用反证法来证明，假设\( \exists n_0 \in \mathbf{N} \)，有\( a_{n_0} < k \)，此时，因为\( a_{n_0} - a_{n_0 + k} \geq k \)，可得\( a_{n_0 + k} \leq a_{n_0} - k \)，又\( a_{n_0} < k \)，故\( a_{n_0 + k} \leq a_{n_0} - k < 0 \)，即\( a_{n_0 + k} < 0 \)，然而\( a_{n_0 + k} \)是自然数，故有\( a_{n_0 + k} \geq 0 \)，矛盾，故假设不成立，有\( \forall n \in \mathbf{N}, a_n \geq k \)。

到这里，我们得到\( \forall k \in \mathbf{N} \)，\( \forall n \in \mathbf{N} \)，有\( a_n \geq k \)的结论，但是明显的又有\( a_n < a_n + 1 \)，矛盾，故不存在无限递减的自然数序列。

证毕。

解释题目2：

1. 如果序列的元素的取值范围变成整数，则无限递减序列是存在的，比如序列：\( a_0 = 100, a_{n + 1} = a_n - 1 \)，这个序列大概长这样：\( 100, 99, 98, \dots, 0, -1, -2, \dots \)，易证明\( \forall n \in \mathbf{N}, a_n > a_{n + 1} \)，且每个元素都是整数，不会出现像题目1中，有元素不是自然数，不符合要求的情况。
2. 如果序列的元素的取值范围变成正有理数，则无限递减序列也是存在的，比如序列：\( a_0 = 1, a_{n + 1} = a_n / 2 \)，这个序列大概长这样：\( 1, 1/2, 1/4, 1/8, \dots \)，易证明\( \forall n \in \mathbf{N}, a_n > a_{n + 1} \)，且每个元素都是正有理数，不会出现像题目1中，有元素不是自然数，不符合要求的情况。

练习4.4.3

题目：

Fill in the gaps marked (why?) in the proof of Proposition 4.4.4.

Proposition 4.4.4的内容：

There does not exist any rational number \( x \) for which \( x^2 = 2 \).

第1个why?的内容：

Every natural number is either even or odd, but not both (why?).

证明第1个why?：

假设存在一个自然数\( n \)，既是奇数，又是偶数，即\( \exists k_0, k_1 \in \mathbf{N}, n = 2k_0 = 2k_1 + 1 \)，则此时可得\( 2(k_0 - k_1) = 1 \)，解得\( k_0 - k_1 = 1 / 2 \)，但这和\( k_0 - k_1 \)是整数矛盾，故假设不成立，不存在一个既是奇数，又是偶数的自然数。

证毕。

第2个why?的内容：

If \( p \) is odd, then \( p^2 \) is also odd (why?).

证明第2个why?：

如果\( p \)是奇数，则\( \exists k \in \mathbf{N}, p = 2_k + 1 \)，此时\( p^2 = (2_k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1 \)，即\( \exists 2k^2 + 2k \in \mathbf{N}, p^2 = 2(2k^2 + 2k) + 1 \)，也就是说\( p^2 \)是奇数。

证毕。

第3个why?的内容：

Since \( p^2 = 2q^2 \), we have \( q < p \) (why?).

证明第3个why?：

假设\( p \leq q \)，如果同乘\( q \)，可得\( pq \leq q^2 \)，如果同乘\( p \)，可得\( p^2 \leq pq \)，综合可得\( p^2 \leq q^2 \)，又\( p^2 = 2q^2 \)，可得\( 2q^2 = q^2 + q^2 \leq q^2 \)，同减\( q^2 \)，可得\( q^2 \leq 0 \)，然而定理4.4.4的证明中，\( q > 0 \)，故\( q^2 > 0 \)，这和\( q^2 \leq 0 \)矛盾，故假设不成立，有\( q < p \)。

证毕。