Starting at the beginning
The Natural Numbers
Natural numbers are the timeless rhythm of counting, the unbroken melody of integers that resonates through the essence of mathematics, revealing the infinite symphony of order within the boundless realms of number theory.
Introduction
This text endeavors to revisit high school and elementary calculus concepts with rigor, emphasizing a thorough exploration of fundamental principles. Beginning with the basics, particularly the concept of numbers and their properties, we delve into the question of why algebraic rules, such as the distributive property, hold true. This exploration introduces the skill of proving intricate properties from simpler ones, employing mathematical induction as a key tool. We acquaint ourselves with various number systems used in real analysis, progressing from natural numbers to integers, rationals, and real numbers. The text challenges the reader to define natural numbers from scratch, encouraging a step-by-step examination of assumptions deeply ingrained in mathematical thinking.
The author acknowledges the difficulty of temporarily setting aside pre-existing knowledge about natural numbers and proposes a methodical approach to reintroduce concepts without relying on advanced tricks like algebraic rules until they are formally proven. This deliberate suspension of known facts aims to avoid circular reasoning and strengthen the foundational understanding of mathematical concepts. While the presented results may appear trivial, the text underscores the importance of the journey over the destination, asserting that this rigorous approach serves as valuable preparation for more advanced mathematical topics. Once the number systems are adequately constructed, the text suggests a return to utilizing algebraic laws without the need for repeated derivation.
In addition, we will disassociate ourselves from the familiarity of the decimal system, an exceedingly convenient method for numerical manipulation but not inherently fundamental to the nature of numbers. The decimal system, although widely used, is not the only viable system; alternatives such as octal, binary, or Roman numerals yield the same set of numbers. Furthermore, a comprehensive explanation of the decimal system reveals intricacies that may not be as intuitive as commonly perceived.
For instance, questions arise regarding the equivalence of numbers with leading zeros, the distinction between numbers like \(123.4444...\) and \(...444.321\), and the rationale behind carrying digits during addition or multiplication. Ambiguities also surround the relationship between \(0.999...\) and \(1\), as well as the definition of the smallest positive real number, prompting considerations such as whether it is \(0.00...001.\)
To avoid these complexities, we will refrain from assuming any prior knowledge of the decimal system, while still employing familiar numerical names \((1, 2, 3,\text{etc}.)\) instead of alternative notations like \(\textbf{I, II, III}\) or \(0++, (0++)++, ((0++)++)++\) (as illustrated below) to maintain practicality.
1.1 Peano Axioms
We will now introduce one conventional method for defining the natural numbers, utilizing the Peano axioms established by Giuseppe Peano (1858–1932). It is important to note that this is not the sole approach to defining natural numbers; an alternative method involves considering the cardinality of finite sets, where, for example, the number 5 is defined as the count of elements in a set with five members. Nevertheless, for the present discussion, we will adhere to the Peano axiomatic approach.
The Peano axioms, named after the Italian mathematician Giuseppe Peano, form a set of foundational principles for the natural numbers, establishing the groundwork for their construction and fundamental properties. Typically, these axioms are articulated through a set of five statements.
Successor Axiom:
There exists a natural number called \(0\).
For every natural number \(n\), there exists a unique natural number denoted as \(S(n)\), called the successor of \(n\).
Non-Zero Axiom:
- Zero is not the successor of any natural number. In other words, \(S(n) \not= 0\) for any natural number \(n\).
Injective Axiom:
- If the successor of two natural numbers is equal, then the numbers themselves are equal. Formally, if \(S(m)=S(n)\), then \(m=n\).
Inductive Axiom (or Induction Axiom):
- If a set of natural numbers contains zero and includes the successor of every number in the set, then the set must include all natural numbers. This is often expressed through mathematical induction.
The Peano axioms serve as the foundation framework for the development of arithmetic and the natural numbers. They capture the essence of counting and the idea of successive generation of numbers. The axioms are used to deduce many properties of the natural numbers and form the basis for the development of number theory and mathematical logic. They provide a rigorous and formal foundation for the study of arithmetic.
Definition 1.1.1. (Informal)
A natural number is any element of the set \(\mathbb{N} := \{0, 1, 2, 3, 4, . . .\}\), which is the set of all the numbers created by starting with at \(0\) and then counting forward indefinitely. We call \(\mathbb{N}\) the set of natural numbers.
Remark 1.1.1
In certain texts, the convention of commencing natural numbers at \(1\) rather than \(0\) exists, though this primarily pertains to notation. In this context, the set \(\{1, 2, 3, . . .\}\) is denoted as the positive integers \(\mathbf{Z}^{+}\) rather than natural numbers, which are sometimes referred to as whole numbers. While defining natural numbers as elements of the set \(\mathbb{N}\) addresses the question of their identity, it raises further inquiries about the nature of \(\mathbb{N}\).
The intuitive definition of “starting at 0 and counting indefinitely” poses uncertainties: How can we ensure an endless count without cycling back to 0? Additionally, how can operations like addition, multiplication, or exponentiation be performed?
To address the latter question, complex operations can be defined in terms of simpler ones. Exponentiation, for instance, is a sequence of multiplications, while multiplication is repeated addition. However, subtraction and division, not suited for natural numbers, are reserved for integers and rationals, respectively. Regarding addition, it is fundamentally an operation of counting forward or incrementing. Incrementing, as a basic operation, is not reducible to simpler actions; it is the initial operation introduced in numerical understanding, predating the concept of addition itself.
Thus, to define the natural numbers, we will use two fundamental concepts: the zero number \(0\), and the increment operation. In deference to modern computer languages, we will use \(n++\) to denote the increment or successor of \(n\), thus for instance \(3++ = 4, (3++)++ = 5\), etc. This is slightly different usage from that in computer languages such as C, where \(n++\) actually redefines the value of \(n\) to be its successor; however in mathematics, we try not to define a variable more than once in any given setting, as it can often lead to confusion; many of the statements which were true for the old value of the variable can now become false, and vice versa. So, it seems like we want to say that \(\mathbb{N}\) consists of \(0\) and everything that can be obtained from \(0\) by incrementing: N should consist of the objects \(0, 0++,(0++)++,((0++)++)++,\) etc.
If we start writing down what this means about the natural numbers, we thus see that we should have the following axioms concerning \(0\) and the increment operation \(++\):
Axiom 1.1: \(\text{0 is a natural number.}\)
Axiom 1.2: \(\text{If n is a natural number, then n++}\) \(\text{is also a natural number}\)
Thus for instance, from \(\text{Axiom 1.1}\) and two applications of \(\text{Axiom 2.2}\), we see that \((0++)++\) is a natural number. Of course, this notation will begin to get unwieldy, so we adopt a convention to write these numbers in more familiar notation:
Definition 1.1.2
We define 1 to be the number \(0++, 2\) to be the number \((0++)++, 3\) to be the number \(((0++)++)++\), etc. (In other words, \(1 := 0++, 2 := 1++, 3 := 2++\), etc. In this text I use \(“x := y”\) to denote the statement that \(x\) is defined to equal \(y\).) Thus for instance, we have
Proposition 1.1.1: \(\text{3 is a natural number.}\)
Proof: By \(\text{Axiom 1.1}\), \(0\) is a natural number. By \(\text{Axiom 1.2}\), \(0++ = 1\) is a natural number. By \(\text{Axiom 1.2}\) again, \(1++ = 2\) is a natural number. By \(\text{Axiom 1.2}\) again, \(2++ = 3\) is a natural number.
It may seem that this is enough to describe the natural numbers. However, we have not pinned down completely the behavior of \(\mathbb{N}\):
Example 1.1
Consider a number system which consists of the numbers \(0, 1, 2, 3,\) in which the increment operation wraps back from \(3\) to \(0\). More precisely \(0++\) is equal to \(1, 1++\) is equal to \(2, 2++\) is equal to \(3\), but \(3++\) is equal to \(0\) (and also equal to \(4\), by definition of \(4\)). This type of thing actually happens in real life, when one uses a computer to try to store a natural number: if one starts at \(0\) and performs the increment operation repeatedly, eventually the computer will overflow its memory and the number will wrap around back to \(0\) (though this may take quite a large number of incrementation operations, such as \(65, 536\)). Note that this type of number system obeys \(\text{Axiom 1.1}\) and \(\text{Axiom 2.2}\), even though it clearly does not correspond to what we intuitively believe the natural numbers to be like. To prevent this sort of “wrap-around issue” we will impose another axiom:
Axiom 1.3: \(\text{0 is not the successor}\;\) \(\text{of any natural number i.e., we have}\;\)\(n++ \not= 0\;\)\(\text{for every natural number}\;\)\(n\).
Now we can show that certain types of wrap-around do not occur: for instance we can now rule out the type of behavior in \(\text{Example 1.1}\) using
Proposition: \(\text{4 is not equal to 0}\)
Caution is warranted as we explore the definition of the number \(4\). Defined as the increment of the increment of the increment of the increment of \(0\), it is not immediately evident that this number is distinct from zero, despite its apparent obviousness. The term “a priori,” derived from Latin meaning “beforehand,” emphasizes knowledge or assumptions made before initiating a proof or argument. In contrast, “a posteriori” denotes knowledge acquired after the conclusion of a proof or argument.
Illustrating this point, consider \(\text{Example 1.1}\) where \(4\) indeed equaled \(0\). Furthermore, in a conventional two-byte computer representation of a natural number, such as \(65536\), adhering to our definition of \(65536\) as equivalent to \(0\) incremented sixty-five thousand, five hundred and thirty-six times, the equality holds.
Proof: By definition, \(4 = 3++\). By \(\text{Axioms}\) \(1.1\) and \(\text{Axioms 1.2}\), \(3\) is a natural number. Thus by \(\text{Axiom 1.3}\), \(3++ \not= 0\), i.e., \(4 \not= 0\).
However, even with our new axiom, it is still possible that our number system behaves in other pathological ways:
Example 1.2
Consider a number system consisting of five numbers \(0,1,2,3,4,\) in which the increment operation hits a “ceiling” at 4. More precisely, suppose that \(0++ = 1, 1++ = 2, 2++ = 3, 3++ = 4,\ \text{but}\; 4++ = 4\) (or in other words that \(5 = 4,\) and hence \(6 = 4, 7 = 4,\) etc.). This does not contradict \(\text{Axioms 1.1,1.2,1.3}\). Another number system with a similar problem is one in which incrementation wraps around, but not to zero, e.g. suppose that \(4++ = 1\) (so that \(5 = 1\), then \(6 = 2\), etc.).
There are many ways to prohibit the above types of behavior from happening, but one of the simplest is to assume the following axiom:
Axiom 1.4: Different natural numbers must have different successors; i.e., if \(n, m\) are natural numbers and \(n \not= m\), then \(n++ \not= m++\). Equivalently, if \(n++ = m++\) , then we must have \(n = m\).
Thus, for instance, we have
Proposition 1.1.2: \(\text{6 is not equal to 2.}\)
Suppose for contradiction that \(6 = 2\). Then \(5++ = 1++\), so by \(\text{Axiom 1.4}\) we have \(5 = 1\), so that \(4++ = 0++\). By \(\text{Axiom 1.4}\) again we then have \(4 = 0\), which contradicts our previous proposition.
As one can see from this proposition, it now looks like we can keep all of the natural numbers distinct from each other. There is however still one more problem: while the axioms (particularly \(\text{Axioms 2.1, 2.2}\)) allow us to confirm that \(0, 1, 2, 3, . . .\) are distinct elements of \(\mathbb{N}\), there is the problem that there may be other “rogue” elements in our number system which are not of this form:
Example 1.3. (Informal)
Suppose that our number system N consisted of the following collection of integers and half-integers:
\[\mathbb{N} := \{0, 0.5, 1, 1.5, 2, 2.5, 3, 3.5, . . .\}.\] (This example is marked “informal” since we are using real numbers, which we’re not supposed to use yet.) One can check that \(\text{Axioms 1.1,1.4}\) are still satisfied for this set. What we want is some axiom which says that the only numbers in N are those which can be obtained from \(0\) and the increment operation - in order to exclude elements such as \(0.5\). But it is difficult to quantify what we mean by “can be obtained from” without already using the natural numbers, which we are trying to define. Fortunately, there is an ingenious solution to try to capture this fact:
Axiom 1.5: \(\text{(Principle of mathematical induction). Let}\;\)\(P(n)\)\(\text{be any property pertaining to a natural number}\;\)\(n\). \(\text{Suppose that}\;\)\(P(0)\)\(\text{is true, and suppose that whenever}\;\)\(P(n)\)\(\text{is true,}\;\)\(P(n++)\)\(\text{is also true. Then}\;\)\(P(n)\)\(\text{is true for every natural number}\;\)\(n\).
Remark 1.1.2
We are a little vague on what “property” means at this point, but some possible examples of \(P(n)\) might be “n is even”; “n is equal to 3”; “n solves the equation \((n + 1)^2 = n^2 + 2n + 1\)”; and so forth. Of course we haven’t defined many of these concepts yet, but when we do, \(\text{Axiom 1.5}\) will apply to these properties. (A logical remark: Because this axiom refers not just to variables, but also properties, it is of a different nature than the other four axioms; indeed, \(\text{Axiom 1.5}\) should technically be called an axiom schema rather than an axiom - it is a template for producing an (infinite) number of axioms, rather than being a single axiom in its own right. To discuss this distinction further is far beyond the scope of this text, though, and falls in the realm of logic.)
The informal intuition behind this axiom is the following. Suppose \(P(n)\) is such that \(P(0)\) is true, and such that whenever \(P(n)\) is true, then \(P(n++)\) is true. Then since \(P(0)\) is true, \(P(0++) = P(1)\) is true. Since \(P(1)\) is true, \(P(1++) = P(2)\) is true. Repeating this indefinitely, we see that \(P(0), P(1), P(2), P(3)\), etc. are all true - however this line of reasoning will never let us conclude that P(0.5), for instance, is true. Thus \(\text{Axiom 1.5}\) should not hold for number systems which contain “unnecessary” elements such as 0.5. (Indeed, one can give a “proof” of this fact. Apply \(\text{Axiom 2.5}\) to the property \(P(n) = n\) “is not a half-integer”, i.e., an integer plus \(0.5\). Then \(P(0)\) is true, and if \(P(n)\) is true, then \(P(n++)\) is true. Thus \(\text{Axiom 1.5}\) asserts that \(P(n)\) is true for all natural numbers n, i.e., no natural number can be a half-integer. In particular, \(0.5\) cannot be a natural number. This “proof” is not quite genuine, because we have not defined such notions as “integer”, “half-integer”, and “0.5” yet, but it should give you some idea as to how the principle of induction is supposed to prohibit any numbers other than the “true” natural numbers from appearing in \(\mathbb{N}\).) The principle of induction gives us a way to prove that a property \(P(n)\) is true for every natural number n. Thus in the rest of this text we will see many proofs which have a form like this:
Proposition 1.1.3: \(\text{A certain property}\;\)\(P(n)\)\(\text{is true for every natural number}\;\)\(n\).
Proof: We use induction. We first verify the base case \(n = 0\), i.e., we prove \(P(0)\). (Insert proof of \(P(0)\) here). Now suppose inductively that \(n\) is a natural number, and \(P(n)\) has already been proven. We now prove \(P(n++)\). (Insert proof of \(P(n++)\), assuming that \(P(n)\) is true, here). This closes the induction, and thus \(P(n)\) is true for all numbers \(n\).
Of course we will not necessarily use the exact template, wording, or order in the above type of proof, but the proofs using induction will generally be something like the above form.
Remarks 1.1.3
Our definition of natural numbers is axiomatic, not constructive. We refrain from specifying the nature of natural numbers, avoiding questions about their composition, physical existence, or purpose. Mathematics treats objects abstractly, focusing on their properties rather than their intrinsic characteristics. As an illustration, our current definition only establishes the increment operation. Mathematics views numbers as abstract entities, be they arrangements of beads on an abacus, configurations of bits in a computer’s memory, or more abstract concepts without physical substance. As long as these entities adhere to axioms and perform required operations, they qualify as numbers for mathematical purposes.
Natural numbers can be constructed from other mathematical objects, such as sets, but various valid models exist. From a mathematician’s perspective, debates about the “true” model are pointless as long as it adheres to axioms. The recognition that numbers can be treated axiomatically is a relatively recent development, emerging in the past century. Historically, numbers were closely tied to external concepts like counting sets, measuring lengths, or determining masses. This approach posed challenges when transitioning between different number systems, leading to philosophical debates.
In the late nineteenth century, a groundbreaking realization emerged: numbers could be understood abstractly through axioms, freeing them from the necessity of a conceptual model. Mathematicians can still utilize conceptual models for intuition and understanding, but they are not mandatory and can be discarded when deemed obstructive.
Consequences
One consequence of the axioms is that we can now define sequences recursively. Suppose we want to build a sequence \(a_0, a_1, a_2, . . .\) by first defining \(a_0\) to be some base value, e.g., \(a_0 := c\), and then letting \(a_1\) be some function of \(a_0, a_1 := f_0(a_0)\), \(a_2\) be some function of \(a_1, a_2 := f_1(a_1)\), and so forth - in general, we set \(a_{n++} := f_n(a_n)\) for some function \(f_n: \mathbb{N} \to \mathbb{N}.\) By using all the axioms together we will now conclude that this procedure will give a single value to the sequence element \(a_n\) for each natural number \(n\). More precisely
Recursive Definition of the Natural Numbers
Definition 1.1.3
The set of natural numbers may be defined recursively as follows.
Initial Condition: \(0 \in \mathbb{N}.\)
Recursion: If \(n \in \mathbb{N}, \; then\; n + 1 \in \mathbb{ N}\).
There are a number of ways of defining the set \(\mathbb{N}\) of natural numbers recursively. The simplest definition is given above. Here is another recursive definition for \(\mathbb{N}\).
Example: 1.4
Suppose the set \(S\) is defined recursively as follows:
Initial Condition: \(0, 1 \in S\),
Recursion: If \(x, y ∈ S\), then \(x + y \in S\).
Notice that, in the recursive step, \(x\) and \(y\) don’t have to represent different numbers. Thus, having \(x = y = 1 \in S\), we get \(1 + 1 = 2 \in S\). Then we get \(1 + 2 = 3 \in S\). And so on.
It should be noted that there is an extremal clause in recursively defined sets. If you cannot build a given element in a finite number of applications of the recursion then it is not in the set built from the recursive definition. To prove an element is in a recursively defined set, you must show that element can be built in a finite number of steps.
Example 1.5
Prove that the set \(S\) recursively in \(\text{Example 1.4}\) is equal to the set \(\mathbb{N}\) of natural numbers.
Proof: We will show that \(S = \mathbb{N}\) by showing separately that \(S \subseteq \mathbb{N}\) and \(\mathbb{N} \subseteq S\).
- First we show \(\mathbb{N} \subseteq S\). Prove by induction that \(n ∈ S\) for every natural number \(n \ge 0.\)
- Basis Step. \(0, 1 \in S\), by definition.
- Induction Step. Suppose \(n ∈ S\), for some \(n \ge 1\). Then, by the recursion step, \(n ∈ S\) and \(1 ∈ S\) imply \(n + 1 ∈ S\).
Thus, by the first principle of mathematical induction, \(n ∈ S\) for every natural number \(n \ge 0\).
- Now we show \(S \subseteq \mathbb{N}\). This time we apply the second principle of mathematical induction on n to show that if \(s ∈ S\) is produced by applying \(n\) steps ( \(1\) initial condition and \(n − 1\) recursive steps), then \(s \in \mathbb{N}\).
- Basis Step. After one step the only elements produced are \(0\) and \(1\), each of which is in \(\mathbb{N}\).
- Induction Step. Suppose \(n \ge 1\) and assume any element in \(S\) produced by applying n or fewer steps is also an element of N. Suppose \(s ∈ S\) is produced by applying \(n + 1\) steps. Since \(n + 1 \ge 2\), there must be two elements \(x\) and \(y\) in \(S\), such that \(s = x+y\). Both \(x\) and \(y\) must have been produced by applying fewer than \(n+1\) steps, since s is produced by applying \(n+1\) steps, and we use one step to obtain s from \(x\) and \(y\). By the induction hypothesis both \(x\) and \(y\) are elements of \(\mathbb{N}\). Since the sum of two natural numbers is again a natural number we have \(s ∈ \mathbb{N}\).
Proposition 1.1.4: (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 an to each natural number \(n\), such that \(a_0 = c, a_{n++} = f_n(a_n)\) for each natural number \(n\).
Proof: We use induction. We first observe that this procedure gives a single value to \(a_0\), namely \(c.\) (None of the other definitions \(a_{n++} := f_n(a_n)\) will redefine the value of \(a_0\), because of \(\text{Axiom 1.3.)}\) Now suppose inductively that the procedure gives a single value to \(a_n\). Then it gives a single value to \(a_{n++}\), namely \(a_{n++} := f_n(a_n)\). (None of the other definitions \(a_{m++} := f_m(a_m)\) will redefine the value of \(a_{n++},\) because of \(\text{Axiom 1.4.)}\) This completes the induction, and so \(a_n\) is defined for each natural number \(n\), with a single value assigned to each \(a_n\).
Note how all of the axioms had to be used here. In a system which had some sort of wrap-around, recursive definitions would not work because some elements of the sequence would constantly be redefined. For instance, in \(\text{Example 1.1}\), in which \(3++ = 0\), then there would be (at least) two conflicting definitions for \(a_0\), either \(c\) or \(f_3(a_3)\). In a system which had superfluous elements such as \(0.5\), the element \(a_{0.5}\) would never be defined. Recursive definitions are very powerful; for instance, we can use them to define addition and multiplication, to which we now turn.
1.2 Addition
The current state of the natural number system is notably limited, possessing only one operation—increment—and a few axioms. However, we can now progress to constructing more intricate operations, such as addition. The methodology involves a recursive approach. Adding three to five is equivalent to incrementing five three times. This can be further broken down into one more increment than adding two to five, which is one more than adding one to five, and so forth. The recursive definition for addition is formulated accordingly.
Definition 1.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++\) to m by defining \((n++) + m := (n + m)++.\)
Thus \(0 + m\) is \(m\), \(1 + m = (0++) + m\) is \(m++\); \(2 + m = (1++)+m = (m++)++\); and so forth; for instance we have \(2+3 = (3++)++ = 4++ = 5.\) From our discussion of recursion in the previous section we see that we have defined \(n + m\) for every integer \(n\) (here we are specializing the previous general discussion to the setting where \(a_n = n + m\) and \(f_n(a_n) = a_{n++}\)). Note that this definition is asymmetric: \(3 + 5\) is incrementing \(5\) three times, while \(5 + 3\) is incrementing \(3\) five times. Of course, they both yield the same value of 8. More generally, it is a fact (which we shall prove shortly) that \(a+b = b+a\) for all natural numbers \(a, b,\) although this is not immediately clear from the definition.
Right now we only have two facts about addition: that \(0+m = m\), and that \((n++)+m = (n+m)++.\) Remarkably, this turns out to be enough to deduce everything else we know about addition. We begin with some basic lemmas.
Lemma 1.2.1. \(\text{For any natural number n, n + 0 = n}\).
Note that we cannot deduce this immediately from \(0 +m = m\) because we do not know yet that \(a + b = b + a\).
Proof: We use induction. The base case \(0 + 0 = 0\) follows since we know that 0 + m = m for every natural number \(m\), and \(0\) is a natural number. Now suppose inductively that \(n + 0 = n\). We wish to show that \((n++) + 0 = n++\). But by definition of addition, \((n++) + 0\) is equal to \((n + 0)++\), which is equal to \(n++\) since \(n + 0 = n.\) This closes the induction.
Lemma 1.2.2. \(\text{For any natural numbers n and m, n + (m++) =(n + m)++}\)
Again, we cannot deduce this yet from \((n++)+m = (n+m)++\) because we do not know yet that \(a + b = b + a.\)
Proof: We induct on \(n\) (keeping \(m\) fixed). We first consider the base case \(n = 0.\) In this case we have to prove \(0 + (m++) = (0 + m)++.\) But by definition of addition, \(0 + (m++) = m++\) and \(0 +m = m\), so both sides are equal to \(m++\) and are thus equal to each other. Now we assume inductively that n + (m++) = (n + m)++; we now have to show that $(n++)+(m++) = ((n++)+m)++. $The left-hand side is \((n + (m++))++\) by definition of addition, which is equal to \(((n+m)++)++\) by the inductive hypothesis. Similarly, we have \((n++)+m = (n+m)++\) by the definition of addition, and so the right-hand side is also equal to \(((n+m)++)++\). Thus both sides are equal to each other, and we have closed the induction.
Proposition 1.2.1 (Addition is commutative). \(\text{For any natural numbers n and m, n + m = m + n.}\)
Proof: We shall use induction on \(n\) (keeping \(m\) fixed). First we do the base case \(n = 0\), i.e., we show \(0+m = m+0\). By the definition of addition, \(0 + m = m,\) while by \(\text{Lemma 1.2.1}\), \(m + 0 = m\). Thus the base case is done. Now suppose inductively that \(n+m = m+n,\) now we have to prove that \((n++) + m = m + (n++)\) to close the induction. By the definition of addition, \((n++)+m = (n+m)++\). By \(\text{Lemma 1.2.2}\), \(m + (n++) = (m + n)++\), but this is equal to \((n + m)++\) by the inductive hypothesis \(n + m = m + n.\) Thus \((n++) + m = m + (n++)\) and we have closed the induction.
There’s a another way to prove;
Proposition 1.2.1 (Addition is Associative):For any natural numbers \(a, b, c,\) we have \((a + b) + c = a + (b + c).\)
Here we’re going to use the Peano axioms for the definition of natural numbers. With these axioms, addition is defined from the constant \(0\) and the successor function \(S(a)\) by the two rules given below
Proposition 1.2.3 (Cancellation law). Let \(a, b, c\) be natural numbers such that \(a + b = a + c\). Then we have \(b = c\).
Note that we cannot use subtraction or negative numbers yet to prove this Proposition, because we have not developed these concepts yet. In fact, this cancellation law is crucial in letting us define subtraction (and the integers) later on in these notes, because it allows for a sort of “virtual subtraction” even before subtraction is officially defined.
Proof: We prove this by induction on a. First consider the base case \(a = 0.\) Then we have \(0 + b = 0 + c,\) which by definition of addition implies that \(b = c\) as desired. Now suppose inductively that we have the cancellation law for a (so that \(a+b = a+c\) implies \(b = c\)); we now have to prove the cancellation law for \(a++.\) In other words, we assume that \((a++) + b = (a++) + c\) and need to show that \(b = c\). By the definition of addition, \((a++) + b = (a + b)++\) and \((a++)+c = (a+c)++\) and so we have \((a+b)++ = (a+c)++\). By \(\text{Axiom 1.4}\), we have \(a + b = a + c\). Since we already have the cancellation law for a, we thus have \(b = c\) as desired. This closes the induction.
1.3Multiplication
In the previous section we have proven all the basic facts that we know to be true about addition and order. To save space and to avoid belaboring the obvious, we will now allow ourselves to use all the rules of algebra concerning addition and order that we are familiar with, without further comment. Thus for instance we may write things like \(a + b + c = c + b + a\) without supplying any further justification. Now we introduce multiplication. Just as addition is the iterated increment operation, multiplication is iterated addition:
Definition 1.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++\) to \(m\) by defining \((n++) × m := (n × m) + m.\) Thus for instance \(0×m = 0, 1×m = 0+m, 2×m = 0+m+m,\) etc. By induction one can easily verify that the product of two natural numbers is a natural number.
Lemma 1.3.1 (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 particular, if \(n\) and \(m\) are both positive, then nm is also positive.
Lemma 1.3.2.(Multiplication is commutative).
Let \(n, m\) be natural numbers. Then \(n \times m = m \times n\).
Proof:
We will now abbreviate \(n \times m\) as \(nm\), and use the usual convention that multiplication takes precedence over addition, thus for instance \(ab + c\) means \((a × b) + c\), not \(a × (b + c)\). (We will also use the usual notational conventions of precedence for the other arithmetic operations when they are defined later, to save on using parentheses all the time.)
Lemma 2.3.3 (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 particular, if \(n\) and \(m\) are both positive, then \(nm\) is also positive.
Proposition1.3.1 (Distributive law). For any natural numbers \(a, b, c\), we have \(a(b + c) = ab + ac\) and \((b + c)a = ba + ca\).
Proof. Since multiplication is commutative we only need to show the first identity \(a(b + c) = ab + ac\). We keep \(a\) and \(b\) fixed, and use induction on \(c\). Let’s prove the base case \(c = 0\), i.e., \(a(b + 0) = a\times b + a\times 0\). The left-hand side is \(ab\), while the right-hand side is \(ab + 0 = ab\), so we are done with the base case. Now let us suppose inductively that \(a(b + c) = ab + ac\), and let us prove that \(a(b + (c++)) = ab + a(c++).\) The left-hand side is \(a((b + c)++) = a(b+c)+a,\) while the right-hand side is \(ab+ac+a = a(b+c)+a\) by the induction hypothesis, and so we can close the induction.
Proposition 1.3.2 (Multiplication is associative). For any natural numbers \(a, b, c,\) we have \((a × b) × c = a × (b × c)\)
Proposition 1.3.3 (Multiplication preserves order). If \(a, b\) are natural numbers such that \(a < b\), and \(c\) is positive, then \(ac < bc.\)
Proof: Since \(a < b\), we have \(b = a + d\) for some positive \(d.\) Multiplying by \(c\) and using the distributive law we obtain \(bc = ac + dc.\) Since \(d\) is positive, and \(c\) is non-zero (hence positive), \(dc\) is positive, and hence \(ac < bc\) as desired.
Definition 1.2.2 (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 ≥ m\) or \(m ≤ 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 ≥ m\) and \(n\not=m.\)
Thus for instance \(8 > 5\), because \(8 = 5 + 3\) and \(8 \not= 5\). Also note that \(n++ > n\) for any \(n\); thus there is no largest natural number \(n\), because the next number \(n++\) is always larger still.
Proposition 1.3.4 (Basic properties of order for natural numbers). Let \(a, b, c\) be natural numbers. Then
(Order is reflexive) \(a ≥ a\).
(Order is transitive) If \(a \ge b\) and \(b \ge c\), then \(a \ge c\).
(Order is anti-symmetric) If \(a \ge b\) and \(b \ge a\), then \(a = b\).
(Addition preserves order) \(a \ge b\) if and only if \(a + c ≥ b + c\).
\(a < b\) if and only if \(a++ \le b\).
\(a < b\) if and only if \(b = a + d\) for some positive number \(d.\)
Proposition 1.3.4 (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 \le r < q\) and \(n = mq + r.\)
In other words, we can divide a natural number \(n\) by a positive number \(q\) to obtain a quotient \(m\) (which is another natural number) and a remainder \(r\) (which is less than \(q\)). This algorithm marks the beginning of number theory, which is a beautiful and important subject but one which is beyond the scope of this text.
Conclusion
These conclusions collectively establish the foundational properties of the natural numbers, forming the basis for further developments in number theory and mathematical reasoning. In summary, the discussion highlights the foundational and abstract nature of natural numbers, the importance of axioms in defining their properties, and the utility of mathematical reasoning, particularly induction, in proving propositions about them.
See Also
References
“Peano axioms”, Encyclopedia of Mathematics, EMS Press, 2001 [1994]
Burris, Stanley N. (2001). “What are numbers, and what is their meaning?: Dedekind”. Commentary on Dedekind’s work.
