4.1 Natural Numbers and Integers
As part of the effort to axiomatize (reduce to a system of basic truths or axioms) mathematics in the late 19th and early 20th centuries, individuals such as Richard Dedekind (1831-1916), Georg Cantor (1845-1918), Giuseppe Peano (1858-1932), Alfred Whitehead (1861-1947), David Hilbert (1862-1943), Ernst Zermelo (1871-1953), Bertrand Russell (1872-1970), and Abraham Fraenkel (1891-1965) followed a program to start with the most basic of assumptions (axioms) and build a solid foundation for the field of mathematics. One of the greatest works in this program is the Principia Mathematica by Whitehead and Russell (1910, 1912, 1913) that built such a foundation on logic and set theory that it took until page 86 of the second volume to prove that \(1+1=2\). While we will not go to the full extent of abstraction, we will build up the natural numbers and the integers from the axioms of Zermelo-Fraenkel set theory, together with the axiom of choice (ZFC axioms).
4.1.1 Natural Numbers
We will study the concepts of counting and related ideas of the natural numbers in Chapter 5, but initially we will use John von Neumann’s (1923) definition for the natural numbers which are defined inductively by defining the symbols \[0:=\emptyset, \quad 1:=\{\emptyset\}, \quad 2:=\{\emptyset, \{\emptyset\}\}, \quad 3:=\{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\} \}\},\] and so on. So for any natural number \(n\), the next natural number is defined inductively as \[n+1:=S(n) := n\cup \{n\},\] where you think of \(S(n)\) as the successor of \(n\). We sometimes define to natural number prior to \(n\) as \(n'\), so that \(n=S(n')\).
This definition of the natural numbers is highly dependent upon the axiom of infinity from the ZFC axioms. In the formal language of the ZFC axioms, the axiom of infinity is stated as \[\exists I ( \emptyset\in I \wedge \forall x\in I((x\cup \{x\})\in I),\] where the symbol \(\forall\) can be read as “for all”. Or equivalently, there is a set \(I\) that contains the empty set as an element and that if \(x\in I\), then \(x\cup \{x\}\) is also in \(I\). The set \(I\) is a larger set than \(\mathbb{N}\), but allows for the existence of the natural numbers.
With our definition of the natural numbers, we also have that \(S(n)\neq n\), \[S(n)=S(m) \Leftrightarrow n=m,\] and we can create an order on the set of symbols \(\mathbb{N} = \{0, 1, 2, 3, \ldots \}\) by defining that \[n \leq m \Longleftrightarrow n \subseteq m.\] One can prove that this set of symbols satisfies the well-ordering property (3.4) using the ZFC axioms, which enables us to prove the principle of mathematical induction creating the mathematical machinery necessary for the study of the natural numbers.
Theorem 4.1 (Principle of Mathematical Induction) Suppose that \(S\) is a subset of \(\mathbb{N}\) such that \(0\in S\), and for all \(n\in \mathbb{N}\), \(n\in S\) implies that \(S(n) \in S\).
Then \(S\) must be the set of natural numbers.
We will leave the detailed proof for a text on symbolic logic. However, the application of this theorem is that if we have a mathematical statement that varies along the natural numbers, \(P(n)\). If the statement \(P(0)\) is true, and if \(P(k)\) being true implies that \(P(k+1)\) is true, then \(P(n)\) must be true for all natural numbers.
We inductively define the operation of addition on these symbols so that for any integer \(a\), \[\begin{align*} a+0 &:=a, \\ a+1 := a+S(0) &= S(a+0), \\ a+2:=a+S(1) &= S(a+1), \\ \vdots \\ a+S(b) &:= S(a+b) \end{align*}\] We similarly define multiplication inductively by \[a\times 0 := 0, \quad a\times 1 := (a \times 0)+a = a, \quad \mbox{ and } \quad a\times S(b) := (a\times b)+a.\] With these operations we have the following properties of the natural numbers.
Theorem 4.2 Let \(a\), \(b\), and \(c\) be natural numbers. Then
- \(a+b\) and \(a\times b\) are natural numbers (closure)
- \(a+(b+c)=(a+b)+c\) and \(a\times (b\times c)=(a\times b)\times c\) (associative property)
- \(a+b=b+a\) and \(a\times b=b\times a\) (commutative property)
- \(a+0=a\) and \(a\times 1 =a\) (additive and multiplicative identities)
- \(a \times (b+c)= (a\times b) + (a\times c)\) (distributive property)
- If \(a\times b=0\), then \(a=0\) or \(b=0\) (or both). (no non-zero divisors)
In order to get a flavor for the techniques involved in proving these properties, we will prove the associative property of addition for the natural numbers. The proofs of the remainder of the statements will be left to the reader to work through.
Proof. Let \(a,b \in \mathbb{N}\). Then, for each \(c\in \mathbb{N}\), we let \(P(c)\) be the statement that \[a+(b+c) = (a+b) + c.\]
If \(c=0\), then \(b+c=b\) and \((a+b)+c=a+b\), and so \[a+(b+c)=a+b= (a+b)+c.\] This implies that \(P(0)\) is true.
Assume by that for some value of \(c'\in \mathbb{N}\) that \(P(c')\) is true, i.e. that \(a+(b+c')=(a+b)+c'\) (\(c'=0\) is true and so such a \(c'\) exists). Then for \(c=S(c')\), \[\begin{align*} a+(b+c) &= a+(b+S(c'))=a+S(b+c') \\ &= S(a+(b+c')) = S((a+b)+c') \: \mbox{ (by the induction hypothesis)}\\ &= (a+b)+S(c') = (a+b)+c. \end{align*}\]
Therefore, P(c) is true. and by the principle of mathematical induction we have that \(a+(b+c)=(a+b)+c\) for all values of \(a,b,c\in \mathbb{N}\).
We previously defined the order on the natural numbers using set inclusions. This order can be rewritten using operations by noting that \(m<n\) if, and only if, \(n=m+k\) for some natural number \(k\). We will explore how this order interacts with the operations of addition and multiplication.
Lemma 4.1 Let \(m,n,k\in \mathbb{N}\). Then \[ (1) \: (m=n) \Leftrightarrow (m+k=n+k) \quad \mbox{ and } \quad (2) \: (m<n) \Leftrightarrow (m+k<n+k).\]
Proof. We will prove part \((1)\) using an induction argument on \(k\) using the statement that given \(m,n\in \mathbb{N}\), \(P(k)\) is the statement that \((m=n) \Leftrightarrow (m+k=n+k)\).
Since \(0\) is the additive identity, we know that \(P(0)\) is true.
Using the definition of \(S(n)\), we have that \((m=n) \Leftrightarrow S(n)=S(m)\), showing that \(P(1)\) is true.
If we assume for some \(l\in \mathbb{N}\) that \(P(l)\) is true, then \(m+(l+1) = n+(l+1)\) is equivalent to \((m+l)+1 = (n+l)+1\), and since \(P(1)\) is true this is equivalent to \((m+l)=(n+l)\). So \(P(l)\) being true implies that \(P(l+1)\) is true. Therefore, \(P(k)\) is true for all \(k\in \mathbb{N}\).
In order to prove part \((2)\), we note that \[\begin{align*} (m<n) &\Leftrightarrow (\mbox{There exists } j\in \mathbb{N} \mbox{ such that } (n=m+j)) \\ &\Leftrightarrow (\mbox{There exists } j\in \mathbb{N} \mbox{ such that } ((n+k)=(m+j)+k)) \\ &\Leftrightarrow (\mbox{There exists } j\in \mathbb{N} \mbox{ such that } ((n+k)=(m+k)+j)) \\ &\Leftrightarrow (m+k<n+k). \end{align*}\]
Lemma 4.2 Let \(m,n,k\in \mathbb{N}\). Then \[ (1) \: (m=n) \Leftrightarrow (m\times k=n\times k) \quad \mbox{ and } \quad (2) \: (m<n) \Leftrightarrow (m\times k<n\times k), \mbox{ for } k>0.\]
The proof of this lemma is very similar to the previous lemma and is left as an exercise.
4.1.2 Integers
Now that we have defined the set of the natural numbers (\(\mathbb{N}\)) and the operations on \(\mathbb{N}\) of addition and multiplication, we would like to have additive inverses. However, we do not assume that the set of additive inverses exist, but instead construct the integers from the natural numbers.
Subsection 2.2.3 gives the existence of the set \[\mathbb{N}\times \mathbb{N} = \{ (a,b) \vert a,b \in \mathbb{N}\}.\] On this set of ordered pairs, we will define an equivalence relation that \[(a,b)\sim (c,d) \quad \Leftrightarrow \quad a+d=b+c.\]
Since this is an equivalence relation we can define \(\mathbb{Z}\) to be the set of equivalence classes under this relation. We will denote by \([(a,b)]\) the equivalence class containing \((a,b)\).
We can now define the operations of addition and multiplication on this set of equivalence classes. \[[(a,b)]+[(c,d)]:= [(a+c,b+d)] \quad \mbox{and} \quad [(a,b)]\times [(c,d)] := [(ac+bd,ad+bc)]\]
We need to make sure that these definitions are well-defined in that the operations do not depend on which element of the equivalence class is chosen for the representation. Assume that \((a,b)\) and \((a',b')\) are both elements of \([(a,b)]\) and that \((c,d)\) and \((c',d')\) are both elements of \([(c,d)]\). This is equivalent to the statements that \[a+b'=b+a' \quad \mbox{ and } c+d'=d+c'.\] So, using properties of equivalent equations involving natural numbers we can add the two equations together and see that \[(a+b') + (c+d') = (b+a')+(d+c').\] Using the associative and commutative properties of addition for the natural numbers we see that this equation is equivalent to \[(a+c) + (b'+d') = (b+d) + (a'+c')\] and so \([(a+c,b+d)]\) is equivalent to \([(a'+c',b'+d')]\), proving that addition is well-defined. The proof that multiplication is well-defined is left as an exercise.
We can also put an order on this set by defining that \[[(a,b)] < [(c,d)] \Leftrightarrow a+d<b+c.\]
We can think of the natural numbers, \(\mathbb{N}\), as the subset of \(\mathbb{N}\times \mathbb{N}\) of the form \[\mathbb{N} := \mathbb{N} \times \{0\} = \{ [(a,0)] \vert a\in \mathbb{N}\},\] since \([(a,0)]+[(b,0)] = [(a+b,0)]\) and \([(a,0)] \times [(b,0)] = [(ab,0)]\).
With this identification of the natural numbers with \(\mathbb{N}\times \{0\}\), where \(a=[(a,0)]\), we are able to see that the negative integers can be associated with \(\{0\} \times \mathbb{N}\), since \([(a,0)]+[(0,a)] = [(a,a)] = [(0,0)]\). We then label \([(0,a)]\) as \(- [(a,0)]\), and usually write it as \(-a\). So \(-4\) would be associated to \([(0,4)]\).
We can then identify every element of \(\mathbb{N}\times \mathbb{N}\) with an integer, \[[(a,b)] \leftrightarrow a+(-b).\]
Thus we have constructed a new set \(\mathbb{Z}\) with the operations of addition and multiplication that satisfy the properties for \(a,b,c\in \mathbb{Z}\) in Table 4.1.
| Property | ||
|---|---|---|
| \(a+b\) is an integer | \(a \times b\) is an integer | Closure |
| \(a+(b+c) = (a+b)+c\) | \(a \times (b \times c) = (a \times b) \times c\) | Associative Property |
| \(a+b=b+a\) | \(a\times b = b\times a\) | Commutative Property |
| \(a+0=a\) | \(a \times 1 = a\) | Identities |
| \(a \times (b+c) = (a\times b) + (a \times c)\) | \((a+b) \times c = (a\times c) + (b\times c)\) | Distributive Property |
| \(a + (-a) =0\) | Additive Inverses | |
| If \(a,b>0\), then \(ab>0\). | If \(a,b<0\), then \(ab>0\). | |
| \(ab=0\) if, and only if, \(a=0\), \(b=0\), or both | No zero divisors |
While the integers do not satisfy the Well-Ordering Property (3.4), since the negative numbers are a non-empty set without a least element, it does satisfy the least-upper-bound property that any non-empty set that is bounded above has a least upper bound.
The integers do however, have generalizations of Lemmas 4.1 and 4.2, with the proofs following directly from various properties listed in Table 4.1.
Theorem 4.3 Let \(m,n,k\in \mathbb{Z}\). Then \[(1) \: (m=n) \Leftrightarrow (m+k=n+k), \quad (2) \: (m<n) \Leftrightarrow (m+k<n+k),\] \[ (3) \: (m=n) \Leftrightarrow (m\times k=n\times k), \mbox{ with } k\neq 0 \quad \mbox{ and } \quad (4) \: (m<n) \Leftrightarrow (m\times k<n\times k), \mbox{ with } k> 0 .\]
4.1.3 Properties of Exponents
Let \(a\) be an integer. We define \(a^n\) for each natural number \(n\) using the following recursive definition. \[a^0:=1, \quad a^1 := a, \quad \mbox{ and } \quad a^{n+1}:=a \cdot a^n\, \: \forall n\in \mathbb{N}.\]
Notice that we have defined \(0^0=1\). This is not a universally accepted definition, but is widely accepted in the context of algebraic and combinatoric contexts, while left as indeterminate in a limit context of analysis, since \[\lim_{x\rightarrow 0^+} x^0 = 1 \quad \mbox{ and } \quad \lim_{x\rightarrow 0^+} 0^x = 0.\]
Related Content Standards
- (6.EE.1)] Write and evaluate numerical expressions involving whole-number exponents.
With this definition, we are able to prove many of the properties of exponents of natural numbers with a base of an integer. It is already given that \(a^0=1\) and \(a^1=a\).
Lemma 4.3 Let \(a\) be an integer, and let \(m\) and \(n\) be natural numbers. Then \[a^m\cdot a^n=a^{m+n}.\]
Proof. That we are trying to prove something to be true for all natural numbers points us to a proof by induction argument. In this case, we will fix \(n\in \mathbb{N}\) and let \(P(m)\) be the statement that \(a^m\cdot a^n=a^{m+n}\).
Then \(P(0)\) is the statement that \(a^0\cdot a^n = a^{0+n}\). Since \(a^0=1\) and \(0+n=n\), we have that \(1\cdot a^n = a^n\), which is a true statement.
If we assume that \(P(k)\) is true for some value of \(k\) (we already know that it is true for \(k=0\)), then \(a^k\cdot a^n = a^{k+n}\). This means that \[\begin{align*} a^{(k+1)} \cdot a^n & = (a \cdot a^k) \cdot a^n \mbox{ (by the definition of the exponent)} \\ &= a \cdot (a^k\cdot a^n) \mbox{ (since multiplication is associative for integers)} \\ &= a \cdot a^{k+n} \mbox{ (by the assumption that $P(k)$ is true)} \\ &= a^{(k+n+1)} \mbox{ (by the definition of the exponent)} \\ &= a^{(k+1)+n} \mbox{ (since addition is associative for the natural numbers)}. \end{align*}\] So, \(P(k+1)\) is true.
Therefore, by induction, \(P(m)\) is true for all natural numbers \(m\).
Lemma 4.4 Let \(a\) and \(b\) be any integers, and let \(n\) be any natural number. Then \[(ab)^n=a^n \cdot b^n.\]
Proof. Since we are proving a statement to be true for all natural numbers, we will use a proof by induction with the statement \(P(n)\) being that \((ab)^n=a^n\cdot b^n\).
Since \(P(0)\) is the statement that \((ab)^0=a^0 \cdot b^0\), we have that this is equivalent to the statement that \(1=1\), and so is true.
If we assume that \(P(k)\) is true for some value of \(k\), then we have that \((ab)^k=a^k\cdot b^k\). We can then use properties of addition and multiplication of integers, and the definition of exponents, to see that \[(ab)^{(k+1)}= (ab)^k\cdot (ab) = a\cdot (ab)^k \cdot b = (a\cdot a^k) \cdot (b^k\cdot b) = a^{(k+1)} \cdot b^{(k+1)}\] and so \(P(k+1)\) is true.
Therefore, by induction, \(P(n)\) is true for all \(n\in \mathbb{N}\).
Lemma 4.5 Let \(a\) be an integer and \(n\) and \(m\) be any natural numbers. Then \[(a^m)^n = a^{mn}.\]
The proof of this lemma is similar to the proof of Lemma 4.3 and so will be left as an exercise.
Lemma 4.6 Let \(a\) and \(b\) be integers with \(0<a<b\). Then for each natural number \(n\geq 1\), \(0<a^n<b^n\).
Proof. We will use an induction argument for fixed integers \(a\) and \(b\), with \(a<b\). We let \(P(n)\) be the statement, \(0<a^n<b^n\). Since \(a^1=a\) and \(b^1=b\), we see that \(P(1)\) is true. If for some \(k\in \mathbb{N}\), with \(k\geq 1\), \(P(k)\) is true, then \[a^{(k+1)}=a^k\cdot a^1 < b^k \cdot a^1 < b^k \cdot b^1 = b^{(k+1)}\] using the induction hypothesis and Lemma 4.2. Since the natural numbers are closed under multiplication (the product of two natural numbers is a natural number), and therefore also under exponents, we have that \(P(k+1)\) is true. Therefore, \(P(n)\) is true for all \(n\in \mathbb{N}\), with \(n\geq 1\).
We will summarize these results in the following theorem and extend these properties to other number systems throughout the remainder of the chapter.
Theorem 4.4 Let \(a\) and \(b\) be integers.
\(a^0=1\)
\(a^1=a\)
\(a^m\cdot a^n = a^{m+n}\) for each \(m,n\in \mathbb{N}\)
\((ab)^n=a^n\cdot b^n\) for each \(n\in \mathbb{N}\)
\((a^m)^n = a^{mn}\) for each \(m,n\in \mathbb{N}\)
If \(0<a<b\), \(0<a^n<b^n\) for each \(n\in \mathbb{N}\)
4.1.4 Exercises
After introducing the associative property for addition, a student asks if there is something similar for subtraction so that \[ A-(B-C) = (A-B)-C.\] How would you respond to the student?
Prove that the relation on \(\mathbb{N}\times\mathbb{N}\) defined by \[(a,b)\sim (c,d) \quad \Leftrightarrow \quad a+d=b+c\] is an equivalence relation.
Prove Lemma 4.2.
Prove Lemma 4.5.
Describe the process of proofs by induction in your own words.