1.5. Integers#

We provide an axiomatic description of integers and natural numbers. We introduce the set of integers denoted by \(\ZZ\) as a set which is equipped with two functions

  • addition (\(+ : \ZZ \times \ZZ \to \ZZ\))

  • multiplication (\(- : \ZZ \times \ZZ \to \ZZ\))

which satisfy the axioms described below.

1.5.1. Arithmetic Axioms#

1.5.1.1. Closure#

Axiom 1.1 (Closure laws)

If \(a, b \in \ZZ\) then

\[ a + b \in \ZZ \]

and

\[ a \cdot b \in \ZZ. \]

1.5.1.2. Commutativity#

Axiom 1.2 (Commutative laws)

If \(a, b \in \ZZ\) then

\[ a + b = b + a \]

and

\[ a \cdot b = b \cdot a. \]

1.5.1.3. Associativity#

Axiom 1.3 (Associative laws)

If \(a, b, c \in \ZZ\) then

\[ (a + b) + c = a + (b + c) \]

and

\[ (a \cdot b) \cdot c = a \cdot (b \cdot c). \]

1.5.1.4. Distributive Law#

Axiom 1.4 (Distributive law)

If \(a, b, c \in \ZZ\) then

\[ a \cdot (b + c) = a \cdot b + a \cdot c \]

and

\[ (a + b) \cdot c = a \cdot c + b \cdot c. \]

1.5.1.5. Identity#

Axiom 1.5 (Additive identity)

There exists an element \(0 \in \ZZ\) such that

\[ a + 0 = 0 + a = a \]

for every \(a \in \ZZ\).

Axiom 1.6 (Multiplicative identity)

There exists an element \(1 \in \ZZ\) with \(1 \neq 0\) such that

\[ a \cdot 1 = 1 \cdot a = a \]

for every \(a \in \ZZ\).

1.5.1.6. Inverse#

Axiom 1.7 (Additive inverse)

For every \(a \in \ZZ\), there exists an element \(x \in \ZZ\) such that

\[ a + x = x + a = 0. \]

\(x\) is called the additive inverse of \(a\) or the negative of \(a\) and is denoted by \(-a\).

1.5.2. Implications of Integer Axioms#

Theorem 1.5 (Multiplication by zero)

For any \(a \in \ZZ\), we have \(0 \cdot a = a \cdot 0 = 0\).

Proof. Let \(b = - (a \cdot 0)\). Then \( a \cdot 0 + b = 0\). Now

\[\begin{split} & 0 + 0 = 0 & \text{ additive identity} \\ \implies & a \cdot (0 + 0 ) = a \cdot 0 & \text{ multiplication by } a\\ \implies & a \cdot 0 + a \cdot 0 = a \cdot 0 & \text{ distributive law}\\ \implies & (a \cdot 0 + a \cdot 0) + b = a \cdot 0 + b = 0 & \text{ additive inverse} \\ \implies & a \cdot 0 + (a \cdot 0 + b) = 0 & \text{ associative law} \\ \implies & a \cdot 0 + 0 = 0 & \text{ additive inverse} \\ \implies & a \cdot 0 = 0 & \text{ additive identity}. \end{split}\]

By commutativity, we have

\[ 0 \cdot a = a \cdot 0 = 0. \]

Theorem 1.6 (Multiplication by \(-1\))

For any \(a \in \ZZ\), we have \(-a = (-1) \cdot a\).

Proof. We start with

\[\begin{split} 0 &= 0 \cdot a & \text{ multiplication by zero}\\ & = [1 + (-1)] \cdot a & \text{ additive inverse}\\ & = 1 \cdot a + (-1) \cdot a & \text{ distributive law}\\ & = a + (-1) \cdot a & \text{ multiplicative identity}. \end{split}\]

Adding by \(-a\) on both sides, we get:

\[\begin{split} & -a = (-a) + 0 = (-a) + (a + (-1) \cdot a) & \text{ additive identity}\\ \implies & -a = (-a + a) + (-1) \cdot a & \text{ associative law}\\ \implies & -a = 0 + (-1) \cdot a & \text{ additive inverse}\\ \implies & -a = (-1) \cdot a & \text{ additive identity}. \end{split}\]

We can now see that

\[\begin{split} (- a) \cdot b &= ((-1) \cdot a) \cdot b = (-1) \cdot (a \cdot b)\\ &= - (a \cdot b). \end{split}\]

Similarly

\[\begin{split} a \cdot (-b) &= a \cdot ((-1) \cdot b) = a \cdot (b \cdot (-1))\\ &= (a \cdot b) \cdot (-1) = (-1) \cdot (a \cdot b)\\ &= - (a \cdot b). \end{split}\]

Hence

\[ (- a) \cdot b = - (a \cdot b) = a \cdot (-b). \]

Theorem 1.7

\[ (-1) \cdot (-1) = 1. \]

Proof. We have

\[\begin{split} (-1) \cdot (-1) + (-1) &= (-1) \cdot (-1) + (-1) \cdot 1 & \text{ multiplicative identity}\\ &= (-1) \cdot[(-1) + 1] & \text{ distributive law}\\ &= (-1) \cdot 0 & \text{ additive inverse}\\ &= 0 & \text{ multiplication by zero}. \end{split}\]

Adding by \(1\) on both sides, we get:

\[\begin{split} & [(-1) \cdot (-1) + (-1)] + 1 = 0 + 1 = 1 & \text{ additive identity} \\ \implies & (-1) \cdot (-1) + [(-1) + 1] = 1 & \text{ associative law} \\ \implies & (-1) \cdot (-1) + 0 = 1 & \text{ additive inverse} \\ \implies & (-1) \cdot (-1) = 1 & \text{ additive identity}. \end{split}\]

We can now see that

\[\begin{split} (-a) \cdot (- b) &= (-1) \cdot (a \cdot (-b)) = (-1) \cdot ( (-1) \cdot (a \cdot b) ) \\ &= ((-1) \cdot (-1)) \cdot (a \cdot b) = 1 \cdot (a \cdot b)\\ = a \cdot b. \end{split}\]

1.5.2.1. Subtraction#

Definition 1.74 (Subtraction)

For any \(a, b \in \ZZ\), a binary operation \(- : \ZZ \times \ZZ \to \ZZ\) is defined as

\[ a - b = a + (-b). \]

We can see that

\[\begin{split} & a - b = 0\\ & \iff a + (-b) = 0 \\ & \iff (a + (-b)) + b = 0 + b \\ & \iff a + ((-b) + b) = b \\ & \iff a + 0 = b \\ & \iff a = b. \end{split}\]

In short \(a - b = 0 \iff a = b\).

Similarly we can see that

\[\begin{split} a \cdot c - b \cdot c &= a \cdot c + (- (b \cdot c)) \\ &= a \cdot c + ((- b) \cdot c) \\ &= (a + (- b)) \cdot c \\ &= (a - b) \cdot c. \end{split}\]

In short \(a \cdot c - b \cdot c = (a - b) \cdot c\). Similarly, \(a \cdot b - a \cdot c = a \cdot (b - c)\).

1.5.3. Natural Numbers#

We introduce the natural numbers, denoted as \(\Nat\) as a subset of integers that satisfy the following two axioms.

1.5.3.1. Closure#

Axiom 1.8 (Closure axiom of natural numbers)

If \(a, b \in \Nat\), then \(a + b \in \Nat\) and \(a \cdot b \in \Nat\).

1.5.3.2. Trichotomy#

Axiom 1.9 (Law of trichotomy)

For every integer \(a \in \ZZ\), exactly one of the following is true.

\[ a \in \Nat \text{ or } -a \in \Nat \text{ or } a = 0. \]

The law of trichotomy states that \(0\) is not a natural number.

The law of trichotomy also implies that for every nonzero integer, its additive inverse is distinct from it since either \(a \in \Nat\) or \(-a \in \Nat\) but not both.

Axiomatic description of natural numbers doesn’t say whether \(1 \in \Nat\) or \(1 \notin \Nat\). We prove that \(1 \in \Nat\) in the next result.

Theorem 1.8 (One is a natural number)

\(1 \in \Nat\).

Proof. By Axiom 1.9 either \(1 \in \Nat\) or \(-1 \in \Nat\) or \(1 = 0\).

  1. Since \(1 \neq 0\), hence either \(1 \in \Nat\) or \(-1 \in \Nat\).

  2. For contradiction assume that \(-1 \in \Nat\).

  3. Since \(-1 \in \Nat\), hence by Axiom 1.8, \((-1) \cdot (-1) \in \Nat\).

  4. By Theorem 1.7, we have \((-1) \cdot (-1) = 1\).

  5. Hence \(1 \in \Nat\).

  6. But since \(-1 \in \Nat\), hence \(1 \notin \Nat\) due to Axiom 1.9. A contradiction.

  7. Hence \(-1 \notin \Nat\).

  8. Hence we must have \(1 \in \Nat\).

  9. We can see that this is consistent with Axiom 1.8 since \(1 \cdot 1 = 1 \in \Nat\).

1.5.4. Order#

Definition 1.75 (Order on integers)

If \(a, b \in \ZZ\), then we define \(a < b\) if and only if \(b - a \in \Nat\).

If \(a < b\), then we also write \(b > a\).

Theorem 1.9 (One is greater than zero)

\(1 > 0\).

Proof. We have

\[ 1 - 0 = 1 + (-0) = 1 + 0 = 1 \in \Nat. \]

Hence \(1 > 0\).

Theorem 1.10

Let \(a \in \Nat\). Then \(a > 0\).

Proof. Since \(a \in \Nat\) hence

\[ a - 0 = a + (-0) = a + 0 = a \in \Nat. \]

Hence \(a > 0\).

Theorem 1.11

Let \(a, b \in \Nat\). Let \(c = a + b\). Then \(c > a\) and \(c > b\).

Proof. We have

\[ c - a = (a + b) - a = (b + a) + (-a) = b + (a + (-a)) = b + 0 = b. \]

Hence \(c - a = b \in \Nat\). Hence \(c > a\). Similarly \(c > b\).

1.5.5. Construction of Integers#

Observation 1.2 (Construction of integers)

We can see that the above axioms are sufficient to construct the entire set of integers. Let us start with assuming that we know nothing about the set of integers except that they satisfy the axioms described above. In particular, we don’t know that \(1 \in \Nat\) or the integers \(2,3,4,\dots,\) exist.

  1. Axiom 1.5 says that there exists an element in \(\ZZ\) denoted as \(0\).

  2. Axiom 1.6 says that there exists an element in \(\ZZ\) denoted as \(1\) such that \(1 \neq 0\).

  3. Thus, at least two different elements exist in \(\ZZ\) namely \(0\) and \(1\).

  4. Axiom 1.7 says that there exists an additive inverse \(-1\) of \(1\) such that \((-1) + 1 = 1 + (-1) = 0\).

  5. We need to show that \(-1 \notin \{ 0, 1 \}\).

  6. We must have \(0 \neq -1\). Otherwise, we would have

    \[ 1 = 1 + 0 = 1 + (-1) = 0 \]

    a contradiction.

  7. In Theorem 1.8, we showed that \(1 \in \Nat\).

  8. By Axiom 1.9 \(-1 \notin \Nat\).

  9. Hence \(-1 \neq 1\).

  10. Hence \(-1, 0, 1\) are three distinct numbers belonging to \(\ZZ\).

  11. By Axiom 1.1 a number \(b = 1 + 1\) belongs to \(\ZZ\).

  12. We claim that \(b \notin \{ -1, 0, 1\}\).

    1. By Axiom 1.8, \(b = 1 + 1 \in \Nat\).

    2. Since \(0\) and \(-1\) are not in \(\Nat\), hence \(b\) cannot be either one of them.

    3. For contradiction assume that \(b = 1\).

    4. Then

      \[ 0 = 1 + (-1) = b + (-1) = (1 + 1) + (-1) = 1 + (1 + (-1)) = 1 + 0 = 1. \]

    5. But \(0 \neq 1\), a contradiction.

    6. Hence \(b= 1 + 1 \notin \{ -1, 0, 1\}\).

  13. We assign the label \(2\) to the distinct integer \(1+1\). Note that the existence of a number \(2\) distinct from \(-1,0,1\) has been deduced directly from the axioms. \(2\) is just a label assigned to this number for convenience.

  14. Then \(-2 \in \ZZ\) and \(-2 \notin \Nat, -2 \neq 0\) due to Axiom 1.9.

  15. We can also show that \(-2 \neq -1\).

  16. Thus, we have five distinct integers \(-2,-1,0,1,2 \in \ZZ\).

  17. Continuing in this manner, for every \(n \in \Nat\), the integer \(n + 1 \in \Nat\) and \(n+1\) must be distinct from the integers \(1,2,\dots,n\).

  18. In this sequence, every new integer is a successor of the previous integer. This construction is similar to Peano axioms.

  19. Axiom 1.7 leads to the existence of the negative integers.

This construction shows that closure axiom of natural numbers and law of trichotomy are essential for the construction of integers. Without these laws, there are several other sets which can satisfy the axioms Axiom 1.1 through Axiom 1.7 with an appropriate choice of addition and multiplication functions.

1.5.6. Zero Divisor#

Definition 1.76 (Zero divisor)

We say that an integer \(a\) is a zero divisor or divisor of zero if and only if \(a \neq 0\) and there exists an integer \(b \neq 0\) such that \(a \cdot b = 0\).

We now show that \(\ZZ\) doesn’t contain any zero divisors.

Theorem 1.12 (No zero divisors)

If \(a, b \in \ZZ\) and \(a \cdot b = 0\) then either \(a = 0\) or \(b = 0\) or both.

In other words, the set of integers contains no zero divisors.

Proof. Suppose that \(a, b \in \ZZ\) and \(a \cdot b = 0\). For contradiction assume that \(a \neq 0\) and \(b \neq 0\).

  1. By law of trichotomy either \(a \in \Nat\) or \(-a \in \Nat\).

  2. Similarly either \(b \in \Nat\) or \(-b \in \Nat\).

  3. Thus, we have 4 possible cases.

We recall that

\[ a \cdot b = (-a) \cdot (-b) \text{ and} - (a \cdot b) = (-a) \cdot b = a \cdot (-b). \]

We shall consider the four possible cases and arrive at contradiction for each case.

  1. \(a, b \in \Nat\). Then by closure \(0 = a \cdot b \in \Nat\). A contradiction.

  2. \(a \in \Nat\) and \(-b \in \Nat\). Then \(a \cdot (-b) = - (a \cdot b) = - 0 = 0 \in \Nat\). A contradiction.

  3. \(-a \in \Nat\) and \(b \in \Nat\) Then \((-a) \cdot b = - (a \cdot b) = -0 = 0 \in \Nat\). A contradiction.

  4. \(-a \in \Nat\) and \(-b \in \Nat\). Then \((-a) \cdot (-b) = - (a \cdot b) = - 0 = 0 \in \Nat\). A contradiction.

Therefore we must have either \(a = 0\) or \(b = 0\) whenever \(a \cdot b = 0\).

Note

The idea of zero divisors becomes important in the theory of rings. While the set of integers doesn’t contain any zero divisors other rings do contain zero divisors.

1.5.6.1. Cancellation Law#

Theorem 1.13 (Cancellation law)

Let \(a, b, c \in \ZZ\) such that \(c \neq 0\). If \(a \cdot c = b \cdot c\) then \(a = b\).

Proof. We note that

\[\begin{split} & a \cdot c = b \cdot c \\ \iff & a \cdot c + (- b \cdot c) = b \cdot c + (- b \cdot c) = 0\\ \iff & a \cdot c + ((- b) \cdot c) = 0 \\ \iff & (a + (- b)) \cdot c = 0 \\ \iff & (a - b) \cdot c = 0. \end{split}\]

Since \(c \neq 0\) hence by cancellation law \(a - b = 0\). Which means that \(a = b\).

1.5.7. Partial Order#

Recall from Definition 1.38 that a relation, denoted by \(\leq\), on a set \(X\) is said to be a partial order for \(X\) (or that \(X\) is partially ordered by \(\leq\)) if it satisfies the following properties:

  • \(x \leq x\) holds for every \(x \in X\) (reflexivity).

  • If \(x \leq y\) and \(y \leq x\), then \(x = y\) (antisymmetry).

  • If \(x \leq y\) and \(y \leq z\), then \(x \leq z\) (transitivity).

Definition 1.77 (Partial order on the set of integers)

For any \(a, b \in \ZZ\), we say that \(a \leq b\) if and only if \(a < b\) or \(a = b\).

This relation is a partial order on the set of integers.

Proof. Since \(a = a\) for every \(a \in \ZZ\), hence reflexivity holds.

Antisymmetry

  1. Let \(a \leq b\) and \(b \leq a\).

  2. Assume that \(a \neq b\).

  3. Then, \(a < b\) and \(b < a\).

  4. This means \(b -a \in \Nat\) and \(a - b \in \Nat\).

  5. But \(- (b - a) = a - b\).

  6. Hence, they both cannot be in \(\Nat\).

  7. Hence we must have \(a = b\).

Transitivity

  1. Let \(a \leq b\) and \(b \leq c\).

  2. Then \(b -a = 0\) or \(b - a \in \Nat\).

  3. Similarly, \(c - b = 0\) or \(c - b \in \Nat\).

  4. We have \(c -a = (c - b) + (b - a)\).

  5. If \(c -b = 0\) and \(b - a = 0\) then \(c - a = 0\).

  6. In all other cases, we have \(c -a \in \Nat\).

  7. Hence \(c-a =0\) or \(c - a \in \Nat\).

  8. Hence \(c = a\) or \(a < c\).

  9. Hence \(a \leq c\).

Theorem 1.14 (Total order)

The relation \(\leq\) defines a total order on \(\ZZ\). In other words, for every \(a, b \in \ZZ\), we must have either \(a \leq b\) or \(b \leq a\).

Proof. Let \(a, b \in \ZZ\).

  1. If \(a \leq b\) then there is nothing more to say.

  2. Suppose that \(a \not\leq b\).

  3. Then neither \(a = b\) nor \(a < b\).

  4. Hence \(b - a \notin \Nat\) and \(b - a \neq 0\).

  5. Hence \(-(b -a) = a - b \in \Nat\).

  6. Hence \(b < a\).

  7. Hence \(b \leq a\).

  8. Hence \(\leq\) is a total order.

Theorem 1.15 (Implications of order relation)

Let \(a,b,c,d \in \ZZ\). Then

  1. If \(a < b\), then \(a \pm c \leq b \pm c\).

  2. If \(a < b\) and \(c > 0\) then \(a \cdot c < b \cdot c\).

  3. If \(a < b\) and \(c < 0\) then \(a \cdot c > b \cdot c\).

  4. If \(0 < a < b\) and \(0 < c < d\) then \(a \cdot c < b \cdot d\).

  5. If \(a \in \ZZ\) and \(a \neq 0\) then \(a^2 > 0\).

1.5.8. Well Ordering Principle#

There are some issues still left with the construction of integers. We don’t know if there is any integer between \(0\) and \(1\). The nonexistence of any integer between \(0\) and \(1\) cannot be established based on the arithmetic and natural number axioms established so far. Readers can check that the set of rational numbers also satisfy all the axioms stated so far.

This requires another axiom known as the well ordering principle.

Axiom 1.10 (Well ordering principle)

If \(B\) is a nonempty subset of \(\ZZ\) which is bounded below; i.e., there exists an \(n \in \ZZ\) such that \(n \leq b\) for every \(b \in B\), then \(B\) has a smallest element; i.e., there exists \(b_0 \in B\) such that \(b_0 < b\) for every \(b \in B, b \neq b_0\).

As a consequence every nonempty subset of integers that is bounded above has a largest element.

Theorem 1.16 (Well ordering principle for natural numbers)

Every nonempty set of natural numbers has a least element.

Proof. Let \(A \subseteq \Nat\).

  1. Since for every \(a \in A\), we have \(0 < a\), hence \(A\) is bounded below by \(0\).

  2. Hence by well ordering principle, it has a least element.

Theorem 1.17

There is no integer \(n\) satisfying \(0 < n < 1\).

Proof. Let

\[ B = \{ n \ST n \in \ZZ, \text{ and } 0 < n < 1 \}. \]

  1. Assume for contradiction that \(B\) is not empty.

  2. \(B\) is bounded below by \(0\).

  3. By well ordering principle, \(B\) has a least element.

  4. Let \(m\) be the least element of \(B\).

  5. Then we have \(0 < m < 1\).

  6. Since \(m\) is an integer hence \(m^2 = m \cdot m\) is also an integer.

  7. Since \(m < 1\), hence \(m^2 < m\).

  8. Since \(0 < m\), hence \(0 < m^2\).

  9. We have \(0 < m^2 < m < 1\).

  10. Hence \(m^2 \in B\).

  11. But this contradicts the fact that \(m\) is the smallest element in \(B\).

  12. A contradiction. Hence, \(B\) must be empty.

1.5.8.1. Odd and Even Numbers#

Definition 1.78 (Odd and even numbers)

If \(n \in \ZZ\), then we say that \(n\) is even if and only if there exists an integer \(k \in \ZZ\) such that \(n = 2 k\).

We say that \(n\) is odd if and only if there exists \(k \in \ZZ\) such that \(n = 2 k + 1\).

Theorem 1.18

Every integer is either even or odd.

Proof. For contradiction, assume that there is an integer \(m\) that is neither even nor odd.

  1. Define the set

    \[ B = \{n \in \ZZ \ST n \text{ is even or odd and } n \leq m \}. \]

  2. Then \(B \neq \EmptySet\) and \(B\) is bounded above by \(m\).

  3. Hence \(B\) by well ordering principle, \(B\) has a largest element.

  4. Let \(p \in B\) be the largest element of \(B\).

  5. Since \(p\) is either even or odd and \(p \leq m\) hence \(p < m\).

  6. If \(p\) is even then \(p+1\) is odd. Since \(p\) is the largest element of \(B\), we must have \(p < m < p + 1\).

  7. If \(p\) is odd then \(p+1\) is even. Since \(p\) is the largest element of \(B\), we must have \(p < m < p + 1\).

  8. Thus, in both cases, we have

    \[ p < m < p + 1. \]

  9. Subtracting \(p\) from this inequality, we get

    \[ 0 < m - p < 1. \]

  10. Since \(m\) and \(p\) are both integers. Hence \(m - p\) must be an integer too.

  11. But due to Theorem 1.17 there is no integer between \(0\) and \(1\). A contradiction.

  12. Therefore every integer must be either odd or even.

Theorem 1.19 (Distinctness of odd and even integers)

There is no integer which is even or odd.

Proof. Let \(a \in \ZZ\) be an integer which is both even and odd.

  1. Then there exist \(k, l \in \ZZ\) such that \(a = 2 k\) and \(a = 2 l + 1\).

  2. Therefore \(2 k = 2 l + 1\).

  3. Hence \(2 (k - l) = 1\).

  4. Since \(1 > 0\) hence by law of trichotomy, \(k -1 > 0\).

  5. Since \(2 = 1 + 1 > 1 + 0 = 1\), hence

    \[ 1 = 2 ( k - l) > 1 (k - l ) = k - l. \]

  6. Therefore, we have \(0 < k - l < 1\).

  7. But due to Theorem 1.17 there is no integer between \(0\) and \(1\). A contradiction.

  8. Hence \(a\) cannot be odd and even simultaneously.

1.5.8.2. Principle of Mathematical Induction#

Well ordering principle is equivalent to the principle of mathematical induction.

Theorem 1.20 (Principle of mathematical induction)

If a subset \(S\) of \(\Nat\) satisfies the following properties:

  • \(1 \in S\) and

  • \(n \in S \implies n + 1 \in S\),

then \(S = \Nat\).

Proof. We prove this by contradiction.

  1. Assume that \(S \neq \Nat\).

  2. Consider the set \(T = \Nat \setminus S\).

  3. Since \(S \neq \Nat\), hence \(T\) is nonempty.

  4. By definition \(T\) is a subset of natural numbers.

  5. By the well ordering principle Theorem 1.16, \(T\) has a smallest number. Let it be \(t\).

  6. A lower bound on \(\Nat\) is \(1\).

  7. Hence \(1\) is also a lower bound of \(T\).

  8. By hypothesis, \(1 \in S\).

  9. Hence \(1 \notin T\).

  10. Hence \(t\) is of the form \(k+1\) where \(k \in \Nat\).

  11. Since \(t\) is the smallest element of \(T\), hence \(k \notin T\).

  12. Hence \(k \in S\) as by definition \(\Nat = S \cup T\) (a disjoint union).

  13. But by hypothesis \(k \in S\) implies \(t = k+1 \in S\).

  14. We arrive at a contradiction that \(t\) belongs to both \(T\) and \(S\) but the two sets are disjoint.

The principle of mathematical induction is applied as follows.

  1. We consider a set

    \[ S \triangleq \{ n \in \Nat \ST n \text{ satisfies } P \} \]

    where \(P\) is some property that the members of this set satisfy.

  2. We then show that \(1\) satisfies the property \(P\).

  3. Further, we show that if \(n\) satisfies property \(P\), then \(n + 1\) also has to satisfy \(P\).

  4. Then, applying the principle of mathematical induction, we claim that \(S = \Nat\).

  5. In other words, every number \(n \in \Nat\) satisfies the property \(P\).

The following is a different version of the principle of mathematical induction.

Theorem 1.21 (Principle of mathematical induction)

Let \(P(n)\) be an assertion about the integer \(n\). Assume the following:

  1. The assertion \(P(n_0)\) is true for some integer \(n_0\).

  2. For any integer \(k \geq n_0\), if \(P(k)\) is true then \(P(k+1)\) must also be true.

Then \(P(n)\) is true for every integer \(n \geq n_0\).

Proof. Consider the set \(S\) defined as follows.

\[ S = \{n \in \Nat \ST P(n + n_0 -1) \text{ is true } \}. \]

  1. By hypothesis, \(P(n_0)\) is true.

  2. \(P(n_0) = P(1 + n_0 - 1)\).

  3. Hence \(1 \in S\).

  4. Assume that \(n \in S\).

  5. Then \(P(n + n_0 -1)\) is true.

  6. Since \(n \in \Nat\), hence \(k = n + n_0 -1 \geq n_0\).

  7. By hypothesis \(P(k + 1) = P(n + n_0)\) is also true.

  8. Hence \(n + 1 \in S\) also holds.

  9. Hence by Theorem 1.20, \(S = \Nat\).

  10. Now, let \(n\) be some integer with \(n \geq n_0\).

  11. Then \(n - n_0 \geq 0\).

  12. Hence \(n - n_0 + 1 \geq 1\).

  13. Hence \(n - n_0 + 1 \in S = \Nat\).

  14. Hence \(P((n - n_0 + 1) + n_0 - 1) = P(n)\) is true.

We are done.

Definition 1.79 (Proof by mathematical induction)

Let \(P\) be some assertion which is defined for every integer and is either false or true for each integer.

In a proof by mathematical induction:

  1. Some particular integer \(n_0\) for which the assertion \(P(n_0)\) is true is known as the base case.

  2. Proving the statement that \(P(n) \implies P(n + 1)\) for every \(n \geq n_0\) is called the inductive step.

  3. The assumption in the inductive step that \(P(n)\) is true for some arbitrary \(k \geq n_0\) is called the inductive hypothesis.

See Enumerative Combinatorics for a number of applications of the principle of mathematical induction.

Sometimes we need a stronger form of mathematical induction.

Theorem 1.22 (Strong mathematical induction)

Let \(P(n)\) be an assertion about the integer \(n\). Assume the following:

  1. The assertion \(P(n_0)\) is true for some integer \(n_0\).

  2. For any integer \(k \geq n_0\), if \(P(i)\) is true for every \(i \in \{n_0, \dots, k \}\); then \(P(k+1)\) must also be true.

Then \(P(n)\) is true for every integer \(n \geq n_0\).

We can call the induction described in Theorem 1.21 as the weak form of mathematical induction.

Proof. We shall prove this result by forming an equivalent problem for which weak induction applies.

  1. Let \(Q(n)\) be the assertion that for every \(i\) with \(n_0 \leq i \leq n\), \(P(n)\) is true.

  2. By hypothesis, \(Q(n_0)\) is true since \(P(n_0)\) is true.

  3. Assume that for some \(k \geq n_0\), \(Q(k)\) is true.

  4. Then by definition of \(Q\), \(P(i)\) is true for every \(i\) with \(n_0 \leq i \leq k\).

  5. Then by hypothesis \(P(k+1)\) is also true.

  6. But \(Q(k+1)\) is true if \(P(i)\) is true for every \(i\) with \(n_0 \leq i \leq k+1\).

  7. Hence \(Q(k+1)\) is also true.

  8. Thus, for every \(k \geq n_0\), \(Q(k) \implies Q(k+1)\).

  9. Then by principle of induction (Theorem 1.21), \(Q(n)\) is true for every \(n \geq n_0\).

  10. Since \(Q(n)\) is true for every \(n \geq n_0\), hence \(P(n)\) is also true for every \(n \geq n_0\).

1.5.9. Informal Definitions#

We end this section with the casual descriptions of the set of integers and natural numbers with which we are normally familiar.

Definition 1.80 (Integers)

The set of all integers is the set

\[ \ZZ = \{\dots, -3,-2,-1,0,1,2,3, \dots \}. \]

Definition 1.81 (Natural numbers)

The set of all natural numbers is the set

\[ \Nat = \{1,2,3, \dots \}. \]