Number Theory Primer : Proving Properties of Natural Numbers Using Proof by Induction

authored by Premmi and Beguène

Previous Topic: An Axiomatic Study of Natural Numbers – Peano’s Axioms

Introduction

Building upon the foundational principles of Peano’s Axioms, we now turn our attention to a critical tool in number theory: proof by induction. How can we rigorously establish that a property holds true for all natural numbers? The answer lies in this powerful technique of proof by induction, a cornerstone for proving properties within the natural number system. We will explore both the set-based and predicate-based approaches to proof by induction, providing a clear understanding of its mechanics. We will then illustrate its use by proving a key lemma directly derived from Peano’s Axioms. Finally, we’ll demonstrate how this proof enables a rigorous definition of addition, laying the groundwork for further exploration of natural number arithmetic.

Proof by Induction

Suppose we want to prove that the natural numbers satisfy some property. Since a property is expressed as a predicate, we can prove that the natural numbers satisfy some property by showing that the predicate $P(n)$ representing this property is true for all $n \in \mathbb{N}_0$ .

Set-Based Induction

The formal way to proceed would be to first define the set $T$ to be those natural numbers which satisfy $P(n)$ and then use the Axiom of Induction to verify whether $T = \mathbb{N}_0$ .

The set $T$ defined using set-builder notation is of the form

T = \big\{n \in \mathbb{N}_0 \,|\, P(n)\big\}

where $P(n)$ is a predicate known to be true or false for each $n \in \mathbb{N}_0$ . We then

show that $0 \in T$ ,
show that $n \in T \implies S(n) \in T \text{ for all } n \in \mathbb{N}_0$ and finally,
invoke the Axiom of Induction to deduce that $T = \mathbb{N}_0$ .

This method of proving that natural numbers satisfy some property using the Axiom of Induction is called Proof by Induction.

Predicate-Based Induction

The less cumbersome, but just as valid, way of proving the same would be to use the Principle of Mathematical Induction and show that the predicate $P(n)$ holds for all $n \in \mathbb{N}_0$ . We do this by

(i) showing that $P(0)$ is true,

(ii) showing that if $P(n)$ is true then $P(S(n))$ is true $\text{for all } n \in \mathbb{N}_0$ ,

(iii) invoking the Principle of Mathematical Induction to deduce that $P(n)$ is true $\text{for all } n \in \mathbb{N}_0$ .

In practice, the Principle of Mathematical Induction $(\text{Axiom } 9)$ may not be invoked explicitly. The proof may be phrased entirely in terms of a predicate $P(n)$ , and, when steps (i) and (ii) are established, the conclusion “ $P(n) \text{ is true for all } n"$ is said to be established “by induction”. This should always be interpreted as an implicit use of Axiom $9$ , which is referred to as the Principle of Mathematical Induction for this very reason. During the course of such a proof, the assumption that $P(n)$ is true is called the induction hypothesis and the proof that $P(n) \implies P(S(n))$ is called the induction step.

In our subsequent discussions, where we will demonstrate proofs of various properties of natural numbers, we will utilize the set-based approach to induction, thus making the definition of set $T$ explicit. That is, we will use the Axiom of Induction, as explained earlier, to prove that the set $T$ consisting of the natural numbers satisfying some property is the set of all natural numbers, $\mathbb{N}_0$ ; this proves that every natural number has the said property.

Example of Proof by Induction

Let us explain through an example how to use proof by induction to show that natural numbers have a certain property.

We have seen during our discussion of Peano’s Axioms that a natural number is either $0$ or a successor of some other natural number. We will now use proof by induction to re-establish this fact, using the Axiom of Induction as our foundation. This lemma will be useful when we define the operations of addition and multiplication from the Peano Axioms.

Lemma

If $n \in \mathbb{N}_0$ and $n \neq 0$ then there exists a unique $m \in \mathbb{N}_0$ such that $n = S(m)$ .

Proof. First we will prove for any $n \in \mathbb{N}_0$ where $n \neq 0$ , the existence of $m \in \mathbb{N}_0$ such that $n = S(m)$ and then we will prove that such an $m$ is unique.

Existence:

Let T be the subset of \mathbb{N}_0 defined as T = \{n \in \mathbb{N}_0 \,|\, n = 0 \text{ or } n = S(m) \text{ for some } m \in \mathbb{N}_0\}.

We will first prove that T = \mathbb{N}_0 using the Axiom of Induction, which will imply the existence part of the lemma.
- Base Case $\textbf{(}\mathbf{0 \in T}\textbf{):}$ By the definition of $T$ , $0 \in T$ .
- Inductive Step:
  - Inductive Hypothesis: Let $l \in T$ .
  - To prove: We need to show that $S(l) \in T$ .
  - Argument:
    - Since $T \subset \mathbb{N}_0$ and $l \in T$ , $l \in \mathbb{N}_0$ . Therefore, by the definition of the successor function $(\text{Peano's Axiom 6}), \, l \text{'s successor } S(l)$ is also a natural number.
    - By the definition of the set $T$ , any natural number that is the successor of a natural number is in $T$ .
    - Since $S(l)$ is a successor of $l$ , therefore, $S(l) \in T$ .
- Conclusion by Induction: By the Axiom of Induction, $T = \mathbb{N}_0$ .
Uniqueness
- Assumption: Suppose there exist $m_1, m_2 \in \mathbb{N}_0$ such that $n = S(m_1) \text{ and } n = S(m_2)$ .
- Deduction:
  - $S(m_1) = S(m_2)$ .
  - By Peano’s Axiom 8 (the successor function is injective), $m_1 = m_2$ .
- Conclusion: Therefore, $m$ is unique.

Application of the Lemma: Defining Addition Step-by-Step

Suppose we want to define the addition of two natural numbers, say $l, n \in \mathbb{N}_0$ . The lemma we just proved states that for any $n \in \mathbb{N}_0$ , either $n = 0$ or $n = S(m)$ for some $m \in \mathbb{N}_0$ . This lemma is important because it allows us to define addition by considering these two cases for the second number, $n$ .

Specifically, since every natural number is either $0$ or a successor of another natural number, defining addition for the following two cases ensures that the operation is completely defined for all pairs of natural numbers $l \text{ and } n$ :

Case $\mathbf{1}$ : Adding Zero (Base Case)
- $l + 0$
Case $\mathbf{2}$ : Adding a Successor
- $l + S(m)$

The lemma’s guarantee that $m$ is unique when $n = S(m)$ ensures that our definition of $l + S(m)$ will be unambiguous and consistent. The uniqueness of $m$ guarantees that for any given $n$ , there is only one possible value for $l + n$ or equivalently, $l + S(m)$ , thus ensuring that addition is unambiguous. Furthermore, this uniqueness ensures that the rules we establish for addition do not lead to contradictions or conflicting results in any application of addition, maintaining the consistency of our definition. By defining these two cases, we establish a step-by-step definition that encompasses all possible additions of natural numbers. The details of how these additions are actually defined will be our focus in the next section.

This approach demonstrates how a fundamental lemma about the structure of natural numbers allows us to rigorously and completely define more complex operations such as addition.

Building Arithmetic and Number Systems from Peano’s Axioms

With these Peano Axioms as a base, we will in the next section rigorously develop all the usual properties of arithmetic and in the subsequent sections build up the other number systems including integer, rational, real and complex numbers.

To be continued…