2.1 The Peano Axioms

Axiom 2.1. \(0\) is a natural number.

Axiom 2.2. If \(n\) is a natural number, then \(n++\) is also a natural number.

　i.e., \(0++\) is also a natural number, \((0++)++\) is also a natural number.

Definition 2.1.3 We define \(1\) to be the number \(0++\), \(2\) to be the number \((0++)++\)， \(3\) to be the number \(((0++)++)++\), etc. (In other words, \(1:=0++\), \(2:=1++\), \(3:=2++\), etc. In this text I use "\(x:=y\)" to denote the statement that \(x\) is defined to equal \(y\).)

Proposition 2.1.4 \(3\) is a natural number.

\(Proof.\) By Axiom 2.1, \(0\) is a natural number. By Axiom 2.2, \(0++=1\) is a natural number. By Axiom 2.2 again, \(1++=2\) is a natural nuber. By Axiom 2.2 again, \(2++=3\) is a natural number.

Axiom 2.3. \(0\) is not the successor of any natural number; i.e., we have \(n++ \neq 0\) for every natural number \(n\).

Proposition 2.1.6 \(4\) is not equal to \(0\).

\(Proof.\) By definition, \(4=3++\). By Axioms 2.1 and 2.2, \(3\) is a natural number. Thus by Axiom 2.3, \(3++ \neq 0\), i.e., \(4\neq0\).

Axiom 2.4. Different natural numbers must have different successors; i.e., if \(n,m\) are natural numbers and \(n \neq m\), then \(n++ \neq m++\). Equivalently, if \(n++ = m++\), then we must have \(n=m\).

　This is an example of reformulating an implication using its contrapositive; see Section A.2 for more details. In the converse diretion, if \(n=m\), then \(n++=m++\); this is the axiom of substitution (see Section A.7) applied to the operation ++.

Proposition 2.1.8 \(6\) is not equal to \(2\).

\(Proof.\) Suppose for sake of contradiction that \(6=2\). Then \(5++=1++\), so by Axiom 2.4 we have \(5=1\), so that \(4++=0++\). By Axiom 2.4 again we then have \(4=0\), which contradicts our previous proposition.

Axiom 2.5. (Principle of mathematical induction). Let \(P(n)\) be any property pertaining to a naural number n. Suppose that \(P(0)\) is true and supose that whenwver \(P(n)\) is true, \(P(n++)\) is also true. Then \(P(n)\) is true for every natural nummber \(n\).

Assumption 2.6. (Informal) There exists a number system \(\mathbb{N}\), whose elements we will call natural numbers, for which Axioms 2.1-2.5 are true.

　We will make this assumption a bit more precise once we have laid down our notation for sets and functions in the next chapter.

　One consquence of the axioms is that we can now define sequences \(recursivly\). Suppose we want to build a sequence \(a_0,a_1,a_2,...\) of numbers by first defining \(a_0\) to be some base value, e.g., \(a_0:=c\) for some number c, and then bu lettimg \(a_1\) be some fnunction of \(a_0\), \(a_1:=f_0(a_0)\), \(a_2\) be some fnunction of \(a_1\), \(a_2:=f_1(a_1)\), and so forth. In geneal, we set \(a_{n++}:=f_n(a_n)\) for some function \(f_n\) from \(N\) to \(N\). By using all the axionms together we will now conclude that this procedure will give a single value to the sequence element \(a_n\) for each ntural number \(n\).

(Strictly speaking, this proposition requires one to define the notion of a \(function\), which we shall do in the next chapter. However, this will not be circular, as the concept of a function does not require the Peano axioms. Proposition 2.1.6 can be formalized more rigorously in the language of set theory; se Exercise 3.5.12.)

Proposition 2.1.6 (Recursive definitions). Suppose for each natural number n, we have some function \(f_n:N \rightarrow N\) from the natural numbers to the natural numbers. Let c be a natural number. Then we can assign a unique natural number \(a_n\) to each number n, such that \(a_0=c\) and \(a_{n++}=f_n(a_n)\) for each natural number n.

\(Proof.\)(Informal) We use induction. we first observe that this procedure gives a single value to \(a_0\), namelt c. (None of the other definitions \(a_{n++}=f_n(a_n)\) will redefine the value of \(a_0\), because of Axiom 2.3.)
Now suppose inductively that the procedure gives a single value to \(a_n\). Then it gives a single value to \(a_{n++}\), namely \(a_{n++}=f_n(a_n)\). (None of the other definitions \(a_{m++}=f_m(a_m)\) will redefine the value of \(a_{n++}\), because of Axiom 2.4.). This completes the induction, and so \(a_n\) is defined for each natural number n, with a single value assigned to each \(a_n\).

　Recursive definitions are very powerful; for instance, we can use them to define addition and multiplication, to which we now urn.

2.2 Addition

　So we give a recursive definition for addition as follows.

Definition 2.2.1 (Addition of natural numbers) Let m be a natural　number. To add zero to m, we define \(0 + m := m\). Now suppose　inductively　that we have defined how to add n to m. Then we can add　\(n++\) to m by defining \((n++) + m := (n + m)++\).

　Thus \(0 + m\) is \(m\), 1+ \(m = (0++) + m\) is \(m++\); \(2 + m = (1++) + m = (m++)++\); and so forth; for instance we have \(2 + 3 = (3++)++ = 4++ = 5\).

　Notice that we can prove easily, using Axioms 2.1, 2.2, and induction (Axiom 2.5), that the sum of two natural numbers is again a natural number (why?).

Lemma 2.2.2. For any natural number \(n\), \(n +0= n\).

　Note that we cannot deduce this immediately from \(0 + m = m\) because we do not know yet that \(a + b = b + a\).

\(Proof.\) We use induction. The base case \(0 + 0 = 0\) follows since we know that \(0 + m = m\) for every natural number \(m\), and \(0\) is a natural number. Now suppose inductively that \(n +0 = n\). We wish to show that \((n++)+ 0 = n++\). But by definition of addition, \((n++)+ 0\) is equal to \((n + 0)++\), which is equal to \(n++\) since \(n+0= n\). This closes the induction.

Lemma 2.2.3. For any natural numbers \(n\) and \(m\), \(n + (m++) = (n +m)++\).

　Again, we cannot deduce this yet from \((n++) + m = (n + m)++\) because we do not know yet that \(a + b = b + a\).

\(Proof.\) We induct on \(n\) (keeping \(m\) fixed). We first consider the base case \(n = 0\). In this case we have to prove \(0 + (m++) = (0 + m)++\). But by definition of addition, \(0 + (m++) = m++\) and \(0 + m = m\), so both sides are equal to \(m++\) and are thus equal to each other. Now we assume inductively that \(n + (m++) = (n + m)++\); we now have to show that \((n++)+ (m++) = ((n++)+m)++\). The left-hand side is \((n+(m++))++\) by definition of addition, which is equal to \(((n + m)++)++\) by the inductive hypothesis. Similarly, we have \((n++)+m = (n+m)++\) by the definition of addition, and so the right-hand side is also equal to \(((n + m)++)++\). Thus both sides are equal to each other, and we have closed the induction.

From a logical point of view, there is no difference between a lemma, proposition, theorem, or corollary - they are all claims waiting to be proved. However, we use these terms to suggest different levels of importance and difficulty. A lemma is an easily proved claim which is helpful for proving other propositions and theorems, but is usually not particularly interesting in its own right. A proposition is a statement which is interesting in its own right, while a theorem is a more important statement than a proposition which says something definitive on the subject, and often takes more effort to prove than a proposition or lemma. A corollary is a quick consequence of a proposition or theorem that was proven recently.

　As a particular corollary of Lemma 2.2.2 and Lemma 2.2.3 we see that \(n++ = n + 1\) (why?).

　As promised earlier, we can now prove that \(a + b = b + a\).

Proposition 2.2.4 (Addition is commutative). For any natural numbers \(n\) and \(m\), \(n + m = m + n\).

\(Proof.\) We shall use induction on \(n\) (keeping \(m\) fixed). First we do the base case \(n = 0\), i.e., we show \(0 + m = m + 0\). By the definition of addition, \(0 + m = m\), while by Lemma 2.2.2, \(m +0 = m\). Thus the base case is done. Now suppose inductively that \(n + m = m + n\), now we have to prove that \((n++) + m = m + (n++)\) to close the induction. By the definition of addition, \((n++) + m = (n + m)++\). By Lemma 2.2.3, \(m + (n++) = (m + n)++\), but this is equal to \((n + m)++\) by the inductive hypothesis \(n + m = m + n\). Thus \((n++) + m = m + (n++)\) and we have closed the induction.

Proposition 2.2.5 (Addition is associative). For any natural numbers \(a\), \(b\), \(c\), we have \((a + b) + c = a + (b + c)\).

\(Proof.\)

Proposition 2.2.6 (Cancellation law). Let \(a\), \(b\), \(c\) be natural numbers such that \(a + b = a + c\). Then we have \(b = c\).

　Note that we cannot use subtraction or negative numbers yet to prove this proposition, because we have not developed these concepts yet. In fact, this cancellation law is crucial in letting us define subtraction (and the integers) later on in this text, because it allows for a sort of “virtual subtraction” even before subtraction is officially defined.

\(Proof.\) We prove this by induction on \(a\). First consider the base case \(a = 0\). Then we have \(0 + b = 0+ c\), which by definition of addition implies that \(b = c\) as desired. Now suppose inductively that we have the cancellation law for \(a\) (so that \(a + b = a + c\) implies \(b = c\)); we now have to prove the cancellation law for \(a++\). In other words, we assume that \((a++) + b = (a++) + c\) and need to show that \(b = c\). By the definition of addition, \((a++) + b = (a + b)++ and (a++) + c = (a + c)++\) and so we have \((a + b)++ = (a + c)++\). By Axiom 2.4, we have \(a + b = a + c\). Since we already have the cancellation law for \(a\), we thus have \(b = c\) as desired. This closes the induction.

　We now discuss how addition interacts with positivity. 这里没有 Fixed, 是因为 \(b=c\) 是性质与值无关。

Definition 2.2.7 (Positive natural numbers). A natural number \(n\) is said to be positive iff it is not equal to \(0\). (“iff” is shorthand for “if and only if” - see Section A.1).

Proposition 2.2.8. If \(a\) is a positive number and b is a natural number, then \(a+b\) is positive (and hence \(b + a\) is also, by Proposition 2.2.4).

\(Proof.\) We use induction on \(b\). If \(b = 0\), then \(a + b = a +0= a\), which is positive, so this proves the base case. Now suppose inductively that \(a + b\) is positive. Then \(a + (b++) = (a + b)++\), which cannot be zero by Axiom 2.3, and is hence positive. This closes the induction.

Corollary 2.2.9. If \(a\) and \(b\) are natural numbers such that \(a + b = 0\), then \(a = 0\) and \(b = 0\).

\(Proof.\) Suppose for sake of contradiction that \(a \neq 0\) or \(b \neq 0\). If \(a \neq 0\) then \(a\) is positive, and hence \(a+b = 0\) is positive by Proposition 2.2.8, a contradiction. Similarly if \(b \neq 0\) then b is positive, and again \(a+b = 0\) is positive by Proposition 2.2.8, a contradiction. Thus \(a\) and \(b\) must both be zero.

Lemma 2.2.10. Let \(a\) be a positive number. Then there exists exactly one natural number \(b\) such that \(b++ = a\).

\(Proof.\)

　Once we have a notion of addition, we can begin defining a notion of order.

Definition 2.2.11 (Ordering of the natural numbers). Let \(n\) and \(m\) be natural numbers. We say that \(n\) is greater than or equal to \(m\), and write \(n \geq m\) or \(m \leq n\), iff we have \(n=m+a\) for some natural number \(a\). We say that \(n\) is strictly greater than \(m\), and write \(n>m\) or \(m<n\), iff \(n \geq m\) and \(n \neq m\) .

　Thus for instance \(8 > 5\), because \(8 = 5+ 3\) and \(8 \neq 5\). Also note that \(n++ > n\) for any \(n\); thus there is no largest natural number \(n\), because the next number \(n++\) is always larger still.

Proposition 2.2.12 (Basic properties of order for natural numbers). Let \(a\), \(b\), \(c\) be natural numbers. Then

　(a) (Order is reflexive) \(a ≥ a\).
　(b) (Order is transitive) If \(a ≥ b\) and \(b ≥ c\), then \(a ≥ c\).
　(c) (Order is anti-symmetric) If \(a ≥ b\) and \(b ≥ a\), then \(a = b\).
　(d) (Addition preserves order ) \(a ≥ b\) if and only if \(a + c ≥ b + c\).
　(e) \(a<b\) if and only if \(a++ ≤ b\).
　(f) \(a < b\) if and only if \(b = a + d\) for some positive number \(d\).

\(Proof.\)

Proposition 2.2.13 (Trichotomy of order for natural numbers). Let \(a\) and \(b\) be natural numbers. Then exactly one of the following statements is true: \(a<b\), \(a = b\), or \(a>b\).

\(Proof.\) This is only a sketch of the proof; the gaps will be filled in Exercise 2.2.4.　First we show that we cannot have more than one of the statements \(a<b\), \(a = b\), \(a>b\) holding at the same time. If \(a<b\) then \(a \neq b\) by　definition, and if \(a>b\) then \(a \neq b\) by definition. If \(a>b\) and \(a<b\) then by Proposition 2.2.12 we have \(a = b\), a contradiction. Thus no more than one of the statements is true.
Now we show that at least one of the statements is true. We keep \(b\) fixed and induct on \(a\). When \(a = 0\) we have \(0 ≤ b\) for all \(b\) (why?), so we have either \(0 = b\) or \(0 < b\), which proves the base case. Now suppose we have proven the proposition for \(a\), and now we prove the proposition for \(a++\). From the trichotomy for \(a\), there are three cases: \(a<b\), \(a = b\), and \(a>b\). If \(a>b\), then \(a++ > b\) (why?). If \(a = b\), then \(a++ > b\) (why?). Now suppose that \(a<b\). Then by Proposition 2.2.12, we have \(a++ ≤ b\). Thus either \(a++ = b or a++ < b\), and in either case we are done. This closes the induction.

\(Proof.\)

　The properties of order allow one to obtain a stronger version of the principle of induction:

Proposition 2.2.14 (Strong principle of induction). Let \(m_0\) be a natural number, and let \(P(m)\) be a property pertaining to an arbitrary natural number m. Suppose that for each \(m ≥ m_0\), we have the following implication: if \(P(m)\) is true for all natural numbers \(m_0 ≤ m < m\), then \(P(m)\) is also true. (In particular, this means that \(P(m_0)\) is true, since in this case the hypothesis is vacuous.) Then we can conclude that \(P(m)\) is true for all natural numbers \(m ≥ m_0\).

— Exercises 2.2 —

\(Why\; 2.2.x.1\) The sum of two natural numbers is again a natural number. (Hint: using Axioms 2.1, 2.2, and induction (Axiom 2.5))

\(Proof.\) Let \(n, m\) are two natural numbers, \(n + m\) is also a natural number.
We use induction on \(n\) (keeping fixed \(m\)).
The base case \(n=0\), \(0+m=m\) by definition of Addition. \(m\) is a natural number.
Now suppose inductively \(n+m\) is a natural number. We wish to show that \((n++)+m\) is also a natural number. By definition of Addition \((n++)+m =(n+m)++\), \(n+m\) is a natural number by inductive hypothesis. Since \(n+m\) is a natural number, \((n+m)++\) is also a natural number by Axiom 2.2. We have closed the induction.

\(Why\;2.2.x.2\) Let \(n\) be a natural number, \(n++ = n + 1\). (Hint: As a particular corollary of Lemma 2.2.2 and Lemma 2.2.3)

\(Proof.\) \(n++ = (n+0)++\) by lemma 2.2.2. \((n+0)++ = n+(0++)\) by lemma 2.2.3, \(n+(0++) = n + 1\) by definition 2.1.3.

\(Exercise\; 2.2.1.\) Prove Proposition 2.2.5. (Hint: fix two of the variables and induct on the third.)(Priority calculations are indicated in parentheses.)

Proposition 2.2.5 (Addition is associative). For any natural numbers \(a, b, c\), we have \((a + b) + c = a + (b + c)\).

\(Proof.\) We use induction on \(c\)(keeping \(a, b\) fixed). We first consider the base case \(c=0\), i.e. \((a+b)+0=a+(b+0)\). By lemma 2.2.2, \((a+b)+0=a+b\). By lemma 2.2.2, \(b+0 = b\), so \(a+(b+0)= a+b\). Thus the base case is done.
Now suppose inductively that \((a+b)+c = a+(b+c)\), we now have to prove that \((a+b)+(c++)=a+(b+(c++))\). The left-hand side is \((a+b)+(c++)=((a+b)+c)++\) by lemma 2.2.3. The right-hand side is \(a+(b+(c++)) = a +((b+c)++) = (a+(b+c))++\) by lemma 2.2.3. Thus this is equal to \(((a+b)+c)++\) by the inductive hypothesis \((a + b) + c = a + (b + c)\), and Axiom 2.3. We have closed the induction.

\(Exercise\;2.2.2.\) Prove Lemma 2.2.10. (Hint: use induction.)

Proposition 2.2.m.0. Every natural number \(n\) is exactly one.

\(Proof.\) Base case \(n = 0\), \(0\) is exactly one by Axiom 2.3.
Now suppose every natural number \(n\) is exactly one, we have to prove \(n++\) is exactly one. By Axiom 2.2 \(n++\) is also a natural number. Since no one natural number can be equal to n expect by itself, so no one natural number can be equal to \(n++\) expect by itself. Thus \(n++\) is exactly one by the inductive hypothesis and Axiom 2.4. We have closed the induction.

Lemma 2.2.10. Let \(a\) be a positive number. Then there exists exactly one natural number \(b\) such that \(b++ = a\).

　注意这里的条件，Let \(a\) be a positive number是对于所有的 \(a\). 当 \(a = 0\) 时，显然是vacuosly true(总是显然的)，但是毫无意义，它不能打倒 \(a = 1\)，我们就得证一下 \(a = 1\)，这个空真和真的支点的分界. 然后用这个真的支点去归纳。同时注意等于号的神奇之处(=是可替换的)。

\(Proof.\) We use induction on \(a\). The base case \(a=0\), vacuously true. Then when \(a=1\), by definition 2.1.3, \(0++=1=a\), by Axiom 2.3 \(0\) is exactly one.
Now suppose inductively that \(a\) be a positive number there exists exactly one natural number \(b\) such that \(b++ = a\). We now have to prove there exists exactly one natural number \(b++\) such that \((b++)++=a++\). We see that there have at least one natural number \(b++\). Suppose that there have some natural number \(c++\), which \((c++)++=a++\). So \((c++)++=(b++)++\), \(c++ = b++\) by Axiom 2.4. So there exists one natural number \(b++\) such that \((b++)++=a++\). We have closed induction.

\(Exercise\;2.2.3.\) Prove Proposition 2.2.12. (Hint: you will need many of the preceding propositions, corollaries, and lemmas.)

Proposition 2.2.12 (Basic properties of order for natural numbers). Let \(a\), \(b\), \(c\) be natural numbers. Then

\(Proof.\)
　(a) By lemma 2.2.2 \(a+0=a\), \(a ≥ a\) by definition of Ordering.

　(b) By definition of Ordering \(a ≥ b\) and \(b ≥ c\) euqal to \(a = b + m\) and \(b = c + n\), \(m, n\) are some natural numbers. So, \(a = c + m + n\), by why 2.2.x.1 \(m +n\) is also a natural number. By definition of Ordering again, \(a ≥ c\).

　(c) By the definition of Ordering, \(a = b + m\), \(b = a + n\). m, n are some natural numbers. So \(a = a + n + m\), by Proposition 2.2.5 \(a = a + (n+m)\), by lemma 2.2.2 \(n + m = 0\), by Corollary 2.2.9 \(m=0\), \(n=0\). Thus \(a = b + 0\), \(a=b\) by lemma 2.2.2.

Proposition 2.2.m.1. If \(a,b\) are some natural numbers and \(a=b\), then \(a + c= b + c\);
\(Proof.\) The left-hand side is \(a+c=b+c\) by the hypothesis, The right-hand side is \(b+c\), so the both side are equal. Done.

　(d) First, if \(a + c ≥ b + c\), then \(a ≥ b\). By definition of Ordering, \(a + c=b + c + n\), \(n\) is a natural number. By Proposition 2.2.4, \(a + c=b + n + c\). By Proposition 2.2.6, \(a = b + n\). By definition of Ordering, \(a ≥ b\).
　　 Second, if \(a ≥ b\), then \(a + c ≥ b + c\). By definition of Ordering, \(a = b + n\), \(n\) is a natural number. By Proposition 2.2.m.1, \(a + c = b + n + c\). By Proposition 2.2.4, \(a + c = b + c +n\). By definition of Ordering, \(a + c ≥ b + c\).

Proposition 2.2.m.2. If \(a=b+m\), \(m \neq 0\) iff \(a\neq b\);

\(Proof.\) First if \(m \neq 0\) then \(a\neq b\). Suppose for the sake of contradiction that \(a=b\), \(b = b+0\) by lemma 2.2.2, so \(a = b + 0\). By hypothesis \(a = b + m\), so \(b + 0 = b + m\). By Proposition 2.2.6 \(m=0\), which contradicts our hypothesis \(m \neq 0\).
Second if \(a\neq b\) then \(m \neq 0\). Suppose for the sake of contradiction that \(m = 0\). Since \(a = b + 0\), \(a = b\) by lemma 2.2.2. A contradiction. Done.

　(e) First, if a<b then \(a++ ≤ b\). By definition of Ordering, \(b = a+m\), \(b \neq a\), \(m\) is a naturnal number. By proposition 2.2.m.2, \(m \neq 0\). By lemma 2.2.10, there exists exactly one natural number \(n\) such that \(n++ = m\), so \(b = a + (n++)\). By lemma 2.2.3, \(b = (a+n)++\). By definition of Addition, \(b = (a++) + n\). By definition of Ordering, \(a++ ≤ b\).
　　 Second, if \(a++ ≤ b\) then \(a<b\). By definition of Ordering, \((a++) + m = b\), \(m\) is a naturnal number. By definition of Addition, \((a + m)++ = b\). By lemma 2.2.3, \(a + (n++)= b\). By Axiom 2.3, \(n++ \neq 0\). By Proposition 2.2.m.2., \(a \neq b\). Thus \(a<b\) by definition of Ordering.

　(f) First, if \(a < b\) then \(b = a + d\) for some positive number \(d\). By definition of Ordering, \(b = a+d\), \(b \neq a\), \(d\) is a naturnal number. By proposition 2.2.m.2, \(d \neq 0\).
　　 Second, if \(b = a + d\) for some positive number \(d\) then \(a < b\). Because of \(b = a + d\) and \(d \neq 0\), \(b \neq a\) by Proposition 2.2.m.2. Thus \(a<b\) by definition of Ordering.

\(Exercise\;2.2.4.\) Justify the three statements marked (why?) in the proof of Proposition 2.2.13.

Proposition 2.2.13 (Trichotomy of order for natural numbers). Let \(a\) and \(b\) be natural numbers. Then exactly one of the following statements is true: \(a<b\), \(a = b\), or \(a>b\).

\(Proof.\) Why_1. When \(a = 0\) we have \(0 ≤ b\) for all \(b\). By lemma 2.2.2, \(b = b + 0\). \(0\) is a natural number by Axiom 2.1. By definition of Ordering, \(b \geq 0\).

Lemma 2.2.m.3. Let \(a, b\) are natural numbers and \(a=b\), then \(a++=b++\). (Axiom of substitution (see Section A.7))

\(Proof.\) The left-hand side is \(a++=b++\) by the hypothesis \(a=b\), The right-hand side is \(b++\), so the both side are equal. Done.

\(Proof.\) Why_2. If \(a>b\), then \(a++ > b\). By definition of Ordering, \(a = b + m\), \(a \neq b\), \(m\) is a natural number. So \(a++ = (b+m)++\), \(a++ = b + (m++)\) by lemma 2.2.3. By Axiom 2.3 \(m++ \neq 0\). By Proposition 2.2.m.2, \(a++ \neq b\). Thus \(a++ > b\) by definition of Ordering.

\(Proof.\) Why_3. If \(a = b\), then \(a++ > b\). By lemma 2.2.2 \(b = b+0\). Thus \(a++ = b++ = (b+0)++\). By lemma 2.2.3, \(a++ = b + (0++)\). By Axiom 2.3 \(0++ \neq 0\). By Proposition 2.2.m.2, \(a++ \neq b\). Thus \(a++ > b\) by definition of Ordering.

\(Exercise\;2.2.5.\) Prove Proposition 2.2.14. (Hint: define \(Q(n)\) to be the property that \(P(m)\) is true for all \(m_0 ≤ m<n\); note that \(Q(n)\) is vacuously true when \(n<m_0\).)

For clarity transcribing Proposition 2.2.14 in logic symbol it takes the form.
\(\left(\forall m\geq m_0 \left[(\forall m_0\leq m' < m\; P(m')) \Rightarrow P(m)\right]\right) \Rightarrow \forall m\geq m_0\;P(m)\)

Which can be rewritten in terms of our definition of \(Q(n)\) as

\(\left(\forall m\geq m_0 \left[(\forall m_0\leq m' < m\; P(m')) \Rightarrow P(m)\right]\right) \Rightarrow \forall m\geq m_0\;Q(m)\)

\(\left(\forall m\geq m_0 \left[(Q(m) \Rightarrow P(m)\right]\right) \Rightarrow \forall m\geq m_0\; Q(m)\)

Above transfromations are writen by Gabríel Snær Völuson from stackexchange.com.

　之前我们也多次用到了直接证明，但是都是假设一个条件condition是真的，再推导conclusion。下面是假设一个蕴含implies是真的。这两个其实是一个东西，初次接触可能会混乱。无意义的真是显而易见的。无意义的真不可以做归纳的Base Case。

Define \(Q(n)\) to be the property that \(P(m)\) is true for all \(m_0 ≤ m<n\);

\(Proof.\) We use the direct proof. First we assume the hypothesis is true that "for each \(m ≥ m_0\), we have the following implication: if \(P(m)\) is true for all natural numbers \(m_0 ≤ m < m\), then \(P(m)\) is also true." is true.

We use induction on \(n\).

When \(n \leq m_0\), \(Q(n)\) is vacuosly true. There have no one \(m\) this time.
And when \(n = m_0\), \(Q(n)\) is vacuosly true. So \(P(m_0)\) is true by the hypothesis.

When \(n = m_0 +1\), because of \(P(m_0)\) is true, thus we have \(Q(n)\) is real true.(Real fulcrum! The real Base Case!)

Now suppose inductively that \(Q(n)\) is true when \(n > m_0\). We need to prove \(Q(n++)\) is true. Equal to "\(P(m)\) is true for all \(m_0 ≤ m < n++\)" is true. Since \(m_0 ≤ m < n++\) can be rewritten in terms of \(m_0 ≤ m ∧ m< n++\). By Proposition 2.2.12(e), \(m< n++\) equal to \(m++ \leq n++\). By Proposition 2.2.12(d), \(m \leq n\). Now we need to prove "\(P(m)\) is true for all \(m_0 ≤ m \leq n\)" is true. We know that \(Q(n)\) is true by the inductive hypothesis. Since \(n > m_0\), we can use implication hypothesis to deduce that \(P(n)\) is true. Finally \(Q(n)\) and \(P(n)\) are both true, thus the \(Q(n++)\) is true. We have closed the induction.

\(Q(n)\) is true for each natural number n. For any natural number \(m\), \(m \geq m_0\), we have \(Q(m)\) is ture. Thus \(P(m)\) is ture. \(P(n)\) is true for all natural number \(m\), \(m \geq m_0\).

Done!

\(Exercise\;2.2.6.\) Let \(n\) be a natural number, and let \(P(m)\) be a property pertaining to the natural numbers such that whenever \(P(m++)\) is true, then \(P(m)\) is true. Suppose that \(P(n)\) is also true. Prove that \(P(m)\) is true for all natural numbers \(m ≤ n\); this is known as the principle of backwards induction. (Hint: apply induction to the variable \(n\).)

\((\forall n \in \mathbb{N}\; P(n) \; and \;(\forall m \in \mathbb{N}\; P(m++) \Rightarrow P(m))\Rightarrow \forall m\leq n\;P(m)\)

\(Proof.\) We use the induction on \(n\). We consider teh base case \(n=0\). In this case we need to prove "\(P(m)\) is ture for all \(m \leq 0\)". By the definition of Ordering, \(0=m+a\), \(a\) is a natural number. By the corollary 2.2.9, \(m=0\) and \(a=0\). Thus there have just one case of \(m\) that \(m=0\). \(P(0)\) is true by the hypothesis \(P(n)\) is true. So \(P(m)\) is ture for all \(m \leq 0\).
Now we suppose inductively that \(P(m)\) is true for all \(m \leq n\). We need to prove that \(P(m)\) is true for all \(m \leq n++\). When \(m=n++\), this time \(P(n++)\) is ture by the hypothesis. \(P(n++)\) is true then \(P(n)\) is also true by the hypothesis implication. \(P(n)\) is ture then \(P(m)\) is true for all \(m \leq n\) by the inductive hypothesis. Thus \(P(m)\) is true for all \(m \leq n++\). We have closed the induction.

2.3 Multiplication

In the previous section we have proven all the basic facts that we know to be true about addition and order. To save space and to avoid belaboring the obvious, we will now allow ourselves to use all the rules of algebra concerning addition and order that we are familiar with, without further comment. Thus for instance we may write things like a + b + c = c + b + a without supplying any further justification. Now we introduce multiplication. Just as addition is the iterated increment operation, multiplication is iterated addition.

Definition 2.3.1 (Multiplication of natural numbers). Let \(m\) be a natural number. To multiply zero to \(m\), we define \(0×m := 0\). Now suppose inductively that we have defined how to multiply \(n\) to \(m\). Then we can multiply \(n++\) to \(m\) by defining \((n++) × m := (n × m) + m\).

　Thus for instance \(0 × m = 0, 1 × m =0+ m, 2 × m =0+ m + m\), etc. By induction one can easily verify that the product of two natural numbers is a natural number.

Lemma 2.3.2 (Multiplication is commutative). Let \(n, m\) be natural numbers. Then \(n × m = m × n\).

Proof. See Exercise 2.3.1

Lemma 2.3.3 (Positive natural numbers have no zero divisors). Let \(n, m\) be natural numbers. Then \(n × m = 0\) if and only if at least one of \(n, m\) is equal to zero. In particular, if \(n\) and \(m\) are both positive, then \(nm\) is also positive.

Proof. See Exercise 2.3.2.

Proposition 2.3.4 (Distributive law). For any natural numbers \(a, b, c\), we have \(a(b + c) = ab + ac\) and \((b + c)a = ba + ca\).

Proof. Since multiplication is commutative we only need to show the first identity \(a(b + c) = ab + ac\). We keep \(a\) and \(b\) fixed, and use induction on \(c\). Let’s prove the base case \(c = 0\), i.e., \(a(b + 0) = ab + a0\). The left-hand side is \(ab\), while the right-hand side is \(ab +0= ab\), so we are done with the base case. Now let us suppose inductively that \(a(b + c) = ab + ac\), and let us prove that \(a(b + (c++)) = ab + a(c++)\). The left-hand side is \(a((b + c)++) = a(b + c) + a\), while the right-hand side is \(ab + ac + a = a(b + c) + a\) by the induction hypothesis, and so we can close the induction.

Proposition 2.3.5 (Multiplication is associative). For any natural numbers \(a, b, c\), we have \((a × b) × c = a × (b × c)\).

Proof. See Exercise 2.3.3

Proposition 2.3.6 (Multiplication preserves order). If a, b are natural numbers such that \(a<b\), and \(c\) is positive, then \(ac < bc\).

Proof. Since \(a<b\), we have \(b = a + d\) for some positive \(d\). Multiplying by \(c\) and using the distributive law we obtain \(bc = ac + dc\). Since d is positive, and \(c\) is positive, \(dc\) is positive, and hence \(ac < bc\) as desired.

Corollary 2.3.7 (Cancellation law). Let \(a, b, c\) be natural numbers such that \(ac = bc\) and \(c\) is non-zero. Then \(a = b\).

Remark 2.3.8. Just as Proposition 2.2.6 will allow for a “virtual subtraction” which will eventually let us define genuine subtraction, this corollary provides a “virtual division” which will be needed to define genuine division later on.

Proof. By the trichotomy of order (Proposition 2.2.13), we have three cases: \(a<b\), \(a = b\), \(a>b\). Suppose first that \(a<b\), then by Proposition 2.3.6 we have \(ac < bc\), a contradiction. We can obtain a similar contradiction when \(a>b\). Thus the only possibility is that \(a = b\), as desired.

Proposition 2.3.9 (Euclidean algorithm). Let \(n\) be a natural number, and let \(q\) be a positive number. Then there exist natural numbers \(m, r\) such that \(0 ≤ r<q\) and \(n = mq + r\).

Remark 2.3.10. In other words, we can divide a natural number \(n\) by a positive number \(q\) to obtain a quotient \(m\) (which is another natural number) and a remainder \(r\) (which is less than \(q\)). This algorithm marks the beginning of number theory, which is a beautiful and important subject but one which is beyond the scope of this text.

Proof. See Exercise 2.3.5

Definition 2.3.11 (Exponentiation for natural numbers). Let \(m\) be a natural number. To raise \(m\) to the power 0, we define \(m^0 := 1\); in particular, we define \(0^0 := 1\). Now suppose recursively that mn has been defined for some natural number \(n\), then we define \(m^{n++} := m^n × m\).

Examples 2.3.12. Thus for instance \(x^1 = x^0 \times x = 1 \times x = x\); \(x^2 = x^1 \times x = x \times x\); \(x^3 = x^2 \times x = x \times x \times x\); and so forth. By induction we see that this recursive definition defines \(x^n\) for all natural numbers \(n\).

— Exercises 2.3 —

Exercise 2.3.1. Prove Lemma 2.3.2. (Hint: modify the proofs of Lemmas 2.2.2, 2.2.3 and Proposition 2.2.4.)

Lemma 2.2.2.m.3 For any natural number \(n\), \(n \times 0=0\).

\(Proof.\) We use induction on \(n\). The base case \(0 \times 0\) follows since we know that \(0xm=0\) for every natural number \(m\), and \(0\) is a natural number. Now suppose inductively that \(n \times 0=0\). We wish to show that \((n++) \times 0=0\). But by the definition of Multiplication \((n++)\times m=(n\times m)+m\), \((n++)\times 0\) is equal to \((n\times0)+0\), which is equal to \(0\) since \(n\times 0=0\). This close the induction.

Lemma 2.2.3.m.3 For any natural numbers \(n\) and \(m\), \(n\times (m++)=(n\times m)+n\).

\(Proof.\) We use induction on \(n\)(keeping \(m\) fixed). We first consider the base case \(n=0\). In this case we have to prove \(0\times (m++)=(0\times m)+0\). By the definition of Multiplication \(0\times (m++)=0\) and \(0\times m+0=0\). So both sides are equal to \(0\). Now we assume inductively that \(n\times (m++)=(n\times m)+n\). We now have to show that \((n++)\times (m++)=((n++)\times m)+n++\). The left-hand side is \((n\times (m++))+ (m++)\) by definition of Multiplication which is equal to \((n\times m)+n+(m++)\) by the inductive hypothesis. Similarly, we have \((n\times m)+m+(n++)\) by definition of Multiplication. Thus the both side are equal to \((n\times m)+((n+m)++)\) by the lemma 2.2.3 and Proposition 2.2.4. We have closed the induction.

Lemma 2.3.2 (Multiplication is commutative). Let \(n, m\) be natural numbers. Then \(n \times m = m \times n\).

\(Proof.\) We shall use induction on \(n\) (keeping \(m\) fixed). First we do the base case \(n=0\), i.e., we show \(0\times m=m\times 0\). By the definition of Multiplication, \(0\times m=0\), while by lemma 2.2.2.m.3, \(mx0=0\). Thus the base case is dowm.
Now suppose inductively that \(n\times m=m\times n\), now we have to prove that \((n++)\times m=m\times (n++)\) to close the induction. By definition of Multiplication, \((n++)\times m=(n\times m)+m\). By lemma 2.2.3.m.3 \(m\times (n++)=m\times n +m\), but this is equal to \((n\times m)+m\) by the inductive hypothesis \(n\times m=m\times n\). Thus \((n++)\times m=m\times (n++)\) and we have closed the induction.

Exercise 2.3.2. Prove Lemma 2.3.3. (Hint: prove the second statement first.)

Lemma 2.3.3 (Positive natural numbers have no zero divisors). Let \(n, m\) be natural numbers. Then \(n \times m = 0\) if and only if at least one of \(n, m\) is equal to zero. In particular, if \(n\) and \(m\) are both positive, then \(nm\) is also positive.

\(Proof.\)
　First. Let m, n be natural numbers. If \(mn=0\), then at least one of \(n,m\) be equal to zero. The statement equal to “Let \(m, n\) be natural numbers. If \(n\) and \(m\) both positive, then \(nm\) is also positive.”. By lemma 2.2.10, \(n = b++\), \(b\) is a natural number. \(m=c++\), \(c\) is a naturnal number. \(nm=(b++) \times (c++)= b \times (c++) + (c++) = bc + b + (c++)= bc + (b+c)++\). Since \((b+c)++\) is positive. By proposition 2.2.8 \(nm\) is positive.
　Second. If at least one of \(m,n\) is equal to zero, then \(mn=0\). The first case: \(m=0\), \(n \neq 0\), \(mn=0 \times n = 0\) by Definition of Multiplication. The second case: \(m \neq 0\), \(n=0\), \(mn=m \times 0=0\) by lemma 2.2.2.m.3. The third case: \(n=0, m=0\), \(mn= 0 \times 0 =0\) by Definition of Multiplication.

Exercise 2.3.3. Prove Proposition 2.3.5. (Hint: modify the proof of Proposition 2.2.5 and use the distributive law.)

Proposition 2.3.5 (Multiplication is associative). For any natural numbers \(a, b, c\), we have \((a × b) × c = a × (b × c)\).

\(Proof.\) We use induction on \(c\) (keeping \(a\) and \(b\) fixed). Let's prove the base case \(c=0\), i.e., \((a × b) × 0 = a × (b × 0)\). The left-hand side is \(0\), while the right-hand side is \(a \times 0=0\). So we are done the base case. Now suppose inductively that \((a × b) × c = a × (b × c)\), and we need to prove that \((a × b) × (c++)= a × (b × (c++))\). The left-hand side is \((a \times b) \times c + a \times b\). The right-hand side is \(a \times ((b \times c)+b)\). By the Distributive law, \(a \times (b \times c) + a \times b\). And this is equal to \((a \times b) \times c + a \times b\) by the inductive hyothesis that \((a × b) × c = a × (b × c)\). We have closed the induction.

Exercise 2.3.4. Prove the identity \((a + b)^2 = a^2 + 2ab + b^2\) for all natural numbers \(a, b\).
By the Definition 2.3.11, \((a + b)(a + b) = a^2 + 2ab + b^2\). The left-hand side is \(a(a+b)+b(a+b)=aa+ab+ab+bb= a^2 +2ab + b^2\) by the Distributive law and Definition 2.3.11. So both side are equal.

Exercise 2.3.5. Prove Proposition 2.3.9. (Hint: fix q and induct on n.)

Method of Proofs.

https://www.thoughtco.com/converse-contrapositive-and-inverse-3126458

https://condor.depaul.edu/ichu/csc383/notes/notes1/Proof.htm

https://www.whitman.edu/mathematics/higher_math_online/section01.01.html

Conclution

数学归纳法：首先我们需要证明 P(0) 是对的。但这只是一个个例的正确。但有了这个个例，我们就可以归纳假设 P(n) 是对的(假设任意一个是对的，此时就与 P(0)有了联系)，同时希望P(n++)是对的。这个过程就是找到任意前一项正确和任意后一项正确的内在联系。有了这种联系，同时还有一个支点P(0)，就可以利用内在联系，推出P(1)是对的。利用内在联系P(2)是对的，...。P(0) 是最关键的，没有P(0)我们就不能归纳假设P(n)。

数学归纳法证明的时候，遇到多个变量我们可以用的方法是。只对一个变量来进行归纳，对于其他变量我们采用的方法是(Keep them fixed.) 这个东西老师没有细说，但在我的理解是，其他变量是变量，可以有任意值，如果我们不固定住他们的话，P(0)：0+m=m 是对的，i.e. 0+1=1。但是到了假设 P(n) 的时候, P(n):n+m=n+m 这个时候m可以为不为1, i.e. 0+2=2, 这就与我们的支点脱节了。我们固定他们，P(n):n+m=n+1，这就保证了证明前后的一致性。最重要的，数学归纳法只能归纳一个变量 i.e. n+0=n, 不固定的话就成了多个变量了，这就得使用多变量的数学归纳法了。

Principle of Double Induction:
If \(P(m, n)\) is a doubly indexed family of statements, one for each m ≥ a and n ≥ b such that
　\((i)\) \(P(a, b)\) is true
　\((ii)\) For all \(m ≥ a\), if \(P(m, b)\) is true, then \(P(m + 1, b)\) is true
　\((iii)\) For all \(n ≥ b\), if \(P(m, n)\) is true for all \(m ≥ a\), then \(P(m, n + 1)\) is true for all \(m ≥ a\), then \(P(m, n)\) is true for all \(m ≥ a\) and \(n ≥ b\).

某个证明卡住，原因一，有前提证明没有完成。原因二，对于问题的描述理解不足(最好化成标准的PQ，数学语言)。

数学归纳法使用的时候就已经非常抽像了。证后，一定要拿着内在联系和支点推几个例子出来。同时，vacuously true到真正true的时候，要仔细分析。

感想：

刚开始打算学数学分析的时候，是因为机器学习中遇到许多数学问题，知道微积分的力量无处不在。于是乎打算学数学分析(这是数学专业大一一整个学年的课程)。找到了陶哲轩教授的实分析中文版，开篇就讲了 Why do analysis?. 这才发现高等数学等同于没学。这更坚定了我的想法。拿什么教材学呢？

看了刘思齐老师B站上推荐的

《PRINCIPLES OF MATHEMATICAL ANALYSIS》《REAL COMPLEX ANALYSIS》 BY WALTER RUDIN.
- 实数定义：Dedekind 分割。
- 微积分基本定理：标准版
- 隐函数基本定理：不动点法
- 重积分换元法：最简微分同胚法(标准) 看到这里就行了，写的最好。
- 高级内容：
  1. 度量空间
  2. 微分形式的Stokes公式
  3. Lebesgue积分(不好)
- 特点：简明，导致看不懂。习题多，难。美国。
卓里奇《数学分析》
- 实数定义：公理法
- 微积分基本定理：有限例外点
- 隐函数基本定理：消元法+不动点法
- 重积分换元法：最简微分同胚法(标准)
- 高级内容：
  1. 度量空间的拓扑学
  2. 赋范空间的微分学
  3. 一般流形上的积分学
- 特点：传统。重视物理应用。物理学不好，某些数学做不了。俄国。
AMANN-ESCHER：ANALYSIS I II III．
- 实数定义：Dedekind 分割 + Cantor基本列(非常漂亮)
- 微积分基本定理：极简版 + Lebesgue积分
- 隐函数基本定理：不动点法(极度现代)
- 重积分换元法：Schwartz法(Lebesgue积分)
- 高级内容：所有能想到的都讲到了。实分析复分析泛函分析。
- 特点：德国，现代。
  1. 完全的现代观点，对传统内容交代不足。还是要看传统的观点，因为那是历史。我们也要看数学的历史。
  2. 内容过于丰富，不要奢望完全掌握
  3. 适合自学。
GODEMENT:ANALYSIS I II III IV 喜欢话痨老头子
- 实数定义：Dedekind 分割 +公理法
- 微积分基本定理：标准版 + 可数例外点
- 隐函数基本定理：不动点法(极度现代)
- 重积分换元法：Schwartz法(调和分析味儿的)
- 高级内容：甚至可以学到模形式
- 特点：法国，老头子，讲的细致，有老头子的想法的叙述。基本现代
  1. 非常话痨，经常跑题，注重传统。甚至有7-8页的二战后国际形式，苏美冷战，朝鲜战争，费马大定理...
  2. 内容过于丰富，不要奢望完全掌握
  3. 法式章节顺序。电子版找东西。