Axiom

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

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

• Axiom 2.3. \(0\) is not the sucessor of any natural number; i.e., we have \(n\pp\neq0\) for every natural number \(n\).

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

• Axiom 2.5 (Principle of mathematical induction). Let \(P(n)\) be any property pertaining to a natural number \(n\). Suppose that \(P(0)\) is true, and suppose that whenever \(P(n)\) is true, \(P(n\pp)\) is also true. Then \(P(n)\) is true for every natural number \(n\).

Definitions

• 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\pp\) to \(m\) by defining \((n\pp)+m:=(n+m)\pp\)

• Definition 2.2.7 (Positive natural numbers). A natural number \(n\) is said to be \(positive\) iff it is not equal to \(0\).

• 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\).

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

• 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 \(m^n\) has been defined for some natural number \(n\), then we define \(m^{n\pp}:=m^n\times m\).

Propositions

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

  • Proof by Tao

• Lemma 2.2.3. For any natural number \(n\) and \(m\), \(n+(m\pp)=(n+m)\pp\).

  • Proof by Tao

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

  • Proof by Tao

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

  • \(Proof\). See Exercise 2.2.1

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

  • Proof by Tao

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

  • Proof by Tao

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

  • Proof by Tao

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

  • \(Proof\). See Exercise 2.2.2.

• Propostion 2.2.12 (Basic properties of order for natural numbers) let \(a,b,c\) be natural numbers. Then

  • (a) (Order is reflexive) \(a\geq a\).

  • (b) (Order is transitive) If \(a\geq b\) and \(b\geq c\), then \(a\geq c\).

  • (c) (Order is anti-symmetric) If \(a\geq b\) and \(b\geq a\), then \(a=b\).

  • (d) (Addition preserves order) \(a\geq b\) only and only if \(a+c\geq b+c\).

  • (e) \(a<b\) if and only if \(a\pp\leq b\).

  • (f) \(a<b\) if and only if \(b=a+d\) for some positive number \(a\).

  • \(Proof\). See Exercise 2.2.3.

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

  • Proof by Tao

• 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\geq m_0\), we have the following implication: if \(P(m')\) is true for all natural numbers \(m_0\leq 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 natrual numbers \(m\geq m_0\).

  • \(Proof\). See Exercise 2.2.5

• Lemma 2.3.2 (Multiplication is commutative). Let \(n\) and \(m\) be natural numbers. Then \(n \times m = m \times 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 \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\). See Exercise 2.3.2.

• Propostion 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 by Tao.

• Propostion 2.3.5 (Multiplication is associative). /For any natural numbers \(a,b,c\), we ahve \((a \times b) \times c = a \times (b \times c)\).

  • \(Proof\). See Exercise 2.3.3.

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

  • Proof by Tao.

• 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\).

  • Proof by Tao

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

  • \(Proof\). See Exercise 2.3.5.

Exercises

• Exercise 2.2.1. Prove Proposition 2.2.5

  (Hint: fix two of the variables and induct on the third.)

  Exercise-2.2.1 with solution

• Exercise 2.2.2. Prove Lemma 2.2.10.

  (Hint: use induction. the induction here is somewhat degenerate, in that the induction hypothesis is not actually used, but this does not prevent the argument from remaining valid; cf. the discussion on implication and causality in Appendix A.2.)

  Exercise-2.2.2 with solution

• Exercise 2.2.3. Prove Propostion 2.2.12

  (Hint: you will need many of the preceding propositions, colloraries, and lemmas.)

  Exercise-2.2.3 with solution

• Exercise 2.2.4. Justify the three statments marked (why?) in the proof of Proposition 2.2.13.

• 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\leq m<n\); note that \(Q(n)\) is vacuously ture when \(n\leq m_0\).)

  Exercise-2.2.5 with solution

• 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\pp)\) 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\leq n\); this is known as the \(principle~of~backwards~induction\). (Hint: apply induction to the varable \(n\).)

  Exercise-2.2.6 with solution

• 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)

  Exercise-2.3.1 with solution

• Exercise 2.3.2. Prove Lemma 2.3.3

  (Hint: prove the second statement first.)

  Exercise-2.3.2 with solution

• Exercise 2.3.3. Prove proposition 2.3.5

  (Hint: modify the proof of Proposition 2.2.5 and use the distributive law.)

  Exercise-2.3.3 with solution

• Exercise 2.3.4. Prove the identity \((a + b)^2 = a^2 + 2ab + b^2\) for all natural numbers \(a,b\).

  Exercise-2.3.4 with solution

• Exercise 2.3.5. Prove Proposition proposition 2.3.9

  Exercise-2.3.5 with solution