Chapter 1 Starting at the begining: the natural numbers
1.1 The Peano axioms
Axiom 2.1 \(0\) is a natural number
Axiom 2.2 If \(n\) is natural number, then \(n+\!\!+\) is also a natural number.
Axiom 2.3 \(0\) is not the successor of any natural number; i.e., we have \(n+\!\!+\ne 0\) 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\ne m\), then \(n+\!\!+ \ne m+\!\!+\). Equivalently ??, if \(n+\!\!+ = m+\!\!+\), 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+\!\!+)\) is also true. Then \(P(n)\) is true for every natural number \(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 is true.
Remark 2.1.13 (Informal) One can prove that while each individual natural number is finite, the set of natural numbers is infinite; i.e., \(\mathbb{N}\) is infinite but consists of individually finite elements using Axiom 2.5.
Remark 2.1.14 Our definition of the natural numbers is axiomatic but not constructive.
Proposition 2.1.16 (Recursive definitions) Suppose for each natural number \(n\), we have some function \(f_n:\mathbb{N} \to \mathbb{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 natural number \(n\), such that \(a_0 = c\) and \(a_{n+\!+} = f_n(a_n)\) for each natural number \(n\)
1.2 Addition
Definition 1.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)+\!\!+\).
One can prove the the sum of two natural numbers is again a natural number using Axiom 2.1, 2.2, 2.5.
Lemma 1.1 For any natural number \(n\), \(n+0 = n\)
Lemma 1.2 For any natural number \(n\) and \(m\), \(n+(m+\!\!+) =(n+m)+\!\!+\).
Proposition 1.1 (Addition is commutative) For any natural number \(n\) and \(m\), \(n+m = m+n\).
Proposition 1.2 (Addition is associative) For any natural number \(a,b,c\), \((a+b)+c = a+(b+c)\).
Proposition 1.3 (Cancellation law) Let \(a,b,c\) be natural numbers such that \(a+b=a+c\). Then we have \(b=c\).
We now discuss how addition interacts with positivity.
Definition 1.2 (Positive natural numbers) A natural number \(n\) is said to be positive iff it is not equal to 0.
Proposition 1.4 If \(a\) is positive and \(a\) and \(b\) is a natural number, then \(a+b\) is positive (and hence \(b+a\) is also by Proposition 1.1)
Corollary 1.1 If \(a\) and \(b\) are natural numbers such that \(a+b=0\), then \(a=b=0\)
Lemma 1.3 Let \(a\) be a positive number. Then there exists exactly one natural number \(b\) such that \(b+\!\!+ = a\).
To prove this lemma, we need to define a notion of order.
Definition 1.3 (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 that \(m\), and write \(n>m\) or \(m<n\), iff \(n\geq m\) and \(n \ne m\).
Here is the proof.
Proof. Let \(Q(m)\) be the property “\(P(n_0+m)\) is true”, then we can infer that \(Q(0)\) is true, and suppose that if \(Q(m)\) is true, \(Q(m+\!\!+)\) is also true. According to Axiom 2.5, \(Q(m)\) is true for every natural number \(m\). In the meanwhile, each natural number \(n\) which is greater that \(n_0\) can be written as \(n_0+m_0\) for some natural number \(m_0\).Thus \(P(n)\) is true for every natural number \(n\) which is greater than \(n_0\).
With the proof above, we can prove Lemma 1.3.
Proposition 1.5 (Basic properties of order for natural numbers) Let \(a,b,c\) be natural numbers. Then
- (Order is reflexive) \(a\geq a\).
- (Order is transitive) If \(a\geq b\) and \(b\geq c\), then \(a\geq c\).
- (Order is anti-symmetric) If \(a\geq b\) and \(b \geq a\), then \(a=b\).
- (Addition preserves order) \(a\geq b\iff a+c\geq b+c\).
- \(a<b \iff a+\!\!+ \leq b\).
- \(a<b \iff b = a+d\) for some positive number \(d\).
Proposition 1.6 (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,a>b\).
Proposition 1.7 (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^{\prime})\) is true for all natural numbers \(m_0\leq m^{\prime} < m\), then \(P(m)\) is also true. Then we can conclude that \(P(m)\) is true for all natural numbers \(m \geq m_0\).
In applications we usually use this principle with \(m_0 =0\) or \(m_0 =1\). There is an interesting view of strong principle of induction in this book.
Exercise 1.1 (Principle of backwards induction) 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\leq n\).
1.3 Multiplication
Definition 1.4 (Multiplication of natural number) Let \(m\) be a batural number. To multiply zero to \(m\), we define \(0\times m:=0\).Now suppose inductively that we have defined how to mutiply \(n\) to \(m\) by defining \((n+\!\!+)\times m =(n\times m)+m\).
One can verify that the product of twow natural numbers is a natural numbers.
Lemma 1.4 (Multiplication is commutative) For any natural number \(n\) and \(m\), \(n\times m = m\times n\).
We will now use the usual notational conventions of precedence over addition.
Lemma 1.5 (Positive natural numbers have no zero divisors) Let \(n,m\) be natural numbers. Then \(n\times m= 0\) iff at least one of \(n,m\) is equal to zero. In partiular, if \(n\) and \(m\) are both positive, then \(nm\) is also positive.
Proposition 1.8 (Distributive law) For any natural numbers \(a,b,c\), we have \(a(b+c) = ab+ac\) and \((b+c)a = ba +ca\).
Proposition 1.9 (Multiplication is associative) For any natural number \(a,b,c\), \((a\times b)\times c = a\times(b\times c)\).
Proposition 1.10 (Multiplication preserves order) If \(a,b\) are natural numbers such \(a<b\), and \(c\) is positive, then \(ac<bc\).
Corollary 1.2 (Cancellation law) Let \(a,b,c\) be natural numbers such that \(ac=bc\) and \(c\) is non-zero. Then \(a=b\).
Proposition 1.11 (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\leq r<q\) and \(n=mq+r\).
This algorithm marks the beginning of number theory.
Definition 1.5 (Exponentation for natural numbers) Let \(m\) be a natural number. To raise \(m\) to the power 0, we define \(m^0:=1\). Now suppose recursively that \(m^n\) has been defined for some natural number \(n\), then we difine \(m^{n+\!+}:=m^n\times m\).
Deeper theory of exponentation will be developed after we have defined integers and rational numbers.