The natural order on \(\symbb{N}\)
An Introduction to Real Analysis
2025-10-12
Given sets \(X\) and \(Y\), suppose the expression \(E(x, y)\) is either true or false for all ordered pairs \((x, y) \in X \times Y\). Informally, consider \(x\) and \(y\) to be related if \(E(x, y)\) is true. A binary relation \(R\) on \(X\) and \(Y\) is a formalization in terms of set theory of these relationships between elements of \(X\) and elements of \(Y\) implied by \(E\). The binary relation \(R\) is exactly the set of ordered pairs \((x, y)\) for which \(E(x, y)\) is true: \(R \coloneq \{ (x, y) \in X \times Y \colon E(x, y) \text{ is true} \}\). For the most common types of binary relations, \(X = Y\), in which case the binary relation \(R\) may be said to be on \(X\). It is assumed henceforth that \(X = Y\).
The nature of the expression \(E\) may impose certain types of structure on exactly which pairs \((x_1, x_2) \in X \times X\) satisfy the expression. For example, for all \(x \in X\), is \(E(x, x)\) true? For all \((x_1, x_2) \in X \times X\), does the truth of \(E(x_1, x_2)\) imply the truth of \(E(x_2, x_1)\)? For all \(x_1, x_2, x_3 \in X\), does the truth of \(E(x_1, x_2)\) and \(E(x_2, x_3)\) imply the truth of \(E(x_1, x_3)\)?
In practice, the set-theoretic definition of \(R\) is forgotten. Commonly the truth of the expression can be expressed via an infix operator, for example \(x_1 \sim x_2\). In this case the set formally defining the the binary relation goes unmentioned and the infix operator itself may be referred to as the binary relation. Henceforth this practice will be followed.
Some of the most important characteristics that a binary relation \(\sim\) might possess are the following:
- reflexivity: for all \(x \in X\), \(x \sim x\);
- irreflexivity: for all \(x \in X\), \(x \nsim x\);
- symmetry: for all \((x_1, x_2) \in X \times X\), \(x_1 \sim x_2 \implies x_2 \sim x_1\);
- transitivity: for all \(x_1, x_2, x_3 \in X\), \((x_1 \sim x_2) \land (x_2 \sim x_3) \implies x_1 \sim x_3\); and
- totality: for all \((x_1, x_2) \in X \times X\), \((x_1 \sim x_2) \lor (x_2 \sim x_1) \lor (x_1 = x_2)\).
Reflexive, symmetric and transitive binary relations are called equivalence relations. Equivalence relations are intimately related with partitions, and more specifically with the various quotient constructions that arise in algebra such as quotient groups, quotient rings, and quotient vector spaces. For further discussion of equivalence relations in these contexts, see Chapter 1 and Appendix A in Katznelson and Katznelson (2008). Of particular relevance to these notes is that equivalence relations are used in the constructions of the integers \(\symbb{Z}\) from the natural numbers \(\symbb{N}\), and the rational numbers \(\symbb{Q}\) from the integers \(\symbb{Z}\). See the Section 1.2.1 and Section 1.3.1 notes for Katznelson and Katznelson (2024), respectively.
Irreflexive, transitive and total binary relations are called total orders, or linear orders. Intuitively a total or linear order on \(X\) implies that the elements of \(X\) can be arranged sequentially.
Proposition 1 Let \(\sim\) be a total order on \(X\). For all \((x_1, x_2) \in X \times X\), exactly one of \((x_1 \sim x_2)\), \((x_2 \sim x_1)\) and \((x_1 = x_2)\) is true.
Proof. By definition of totality, for all \((x_1, x_2) \in X \times X\) at least one possibility is true. To show that more than one cannot be true, proceed by contradiction.
Suppose that there exists \((x_1, x_2) \in X \times X\) such that \((x_1 \sim x_2) \land (x_1 = x_2)\). Then \(x_1 \sim x_1\), which contradicts irreflexivity. By the same reasoning, there cannot be \((x_1, x_2) \in X \times X\) such that \((x_2 \sim x_1) \land (x_1 = x_2)\).
Suppose that there exists \((x_1, x_2) \in X \times X\) such that \((x_1 \sim x_2) \land (x_2 \sim x_1)\). Then by transitivity \(x_1 \sim x_1\), which again contradicts irreflexivity.
Lastly, if there exists \((x_1, x_2) \in X \times X\) such that \((x_1 \sim x_2) \land (x_2 \sim x_1) \land (x_1 = x_2)\) then again \(x_1 \sim x_1\), which contradicts irreflexivity. \(\blacksquare\)
For \(m, n \in \symbb{N}\), Katznelson and Katznelson (2024, sec. 1.1.2) define the notation \(m < n\) if and only if there exists \(k \in \symbb{N}\) such that \(n = m + k\). In order to show that \(<\) is a total order on \(\symbb{N}\), it is necessary to continue the development of the natural numbers that began in the Section 1.1.1 notes for Katznelson and Katznelson (2024). In those notes the arithmetic properties of \(\symbb{N}\) were established; these notes develop the order properties of \(\symbb{N}\).
Lemma 1 For all \(a, b \in \symbb{N}\), \(a + b \neq b\).
Proof. For chosen \(a \in \symbb{N}\), define the set \(M_a \coloneq \{ b \in \symbb{N}\colon a + b \neq b \} \subseteq \symbb{N}\). By definition, \(a + 1 = \sigma(a) \neq 1\) because \(1 \notin \symup{img}(\sigma)\), so \(1 \in M_a\). Next assume that \(b \in M_a\), so \(a + b \neq b\). Then \[\begin{align*} a + \sigma(b) &= a + (b + 1)\\[0.75em] &= (a + b) + 1\\[0.75em] &= \sigma(a + b)\\[0.75em] &\neq \sigma(b) \end{align*}\] because \(\sigma\) is injective. Therefore \(\sigma(b) \in M_a\), so \(M_a = \symbb{N}\). Since \(a \in \symbb{N}\) was arbitrary, this argument applies for any \(a \in \symbb{N}\). \(\blacksquare\)
The following proposition, which relies heavily on Lemma 1, will be directly applicable to establishing that \(<\) is a total order on \(\symbb{N}\).
Proposition 2 For all \(a, b \in \symbb{N}\), exactly one of the following is true: \[\begin{align} a &= b \label{eq:1} \\[0.75em] \exists m \in \symbb{N}\text{ such that } a &= b + m \label{eq:2} \\[0.75em] \exists n \in \symbb{N}\text{ such that } b &= a + n \label{eq:3}. \end{align}\]
The proof of Proposition 2 applies the principle of induction, as do most proofs in the Section 1.1.1 notes for Katznelson and Katznelson (2024). However, the proof is streamlined by observing that for all \(a, b \in \symbb{N}\), at most one of \(\eqref{eq:1}\)–\(\eqref{eq:3}\) is true. To prove this, proceed by contradiction. For chosen \(a\) and \(b\), suppose \(\eqref{eq:1}\) and \(\eqref{eq:2}\) are true. Then \(m + b = b + m = a = b\), which contradicts Lemma 1. Similarly, if \(\eqref{eq:1}\) and \(\eqref{eq:3}\) are true, then \(n + a = a + n = b = a\), which contradicts Lemma 1. If \(\eqref{eq:2}\) and \(\eqref{eq:3}\) are true, then \((n + m) + a = a + (n + m) = (a + n) + m = b + m = a\), which contradicts Lemma 1. If \(\eqref{eq:1}\)–\(\eqref{eq:3}\) are true then reasoning as above shows again that Lemma 1 is contradicted. Therefore in the following case analyses it is only necessary to show that one of \(\eqref{eq:1}\)–\(\eqref{eq:3}\) is true, since the others must then be false.
To provide intuition for the proof, observe that \(\eqref{eq:2}\) and \(\eqref{eq:3}\) can informally be interpreted as \(a \overset{!}{>}b\) and \(b \overset{!}{>}a\), respectively. These informal interpretations provide guidance in determining which of \(\eqref{eq:1}\)–\(\eqref{eq:3}\) to prove in the cases below.
Proof. For chosen \(a \in \symbb{N}\), define the set \(M_a \coloneq \{ b \in \symbb{N}\colon \text{ exactly one of \eqref{eq:1}--\eqref{eq:3} is true} \}\). Either \(a = 1\) or \(a \neq 1\). If \(a = 1\) and \(b = 1\), then \(\eqref{eq:1}\) is true. If \(a \neq 1\) and \(b = 1\), then \(a \overset{!}{>}b\) so it should be expected that \(\eqref{eq:2}\) will be true. Indeed, \(a \in \symup{img}(\sigma)\), so there exists \(a^- \in \symbb{N}\) such that \(\sigma(a^-) = a\). Since by definition \(\sigma(a^-) = a^- + 1\), there exists \(m \in \symbb{N}\) such that \(a = b + m\). In particular, take \(m = a^-\) so that \(b + m = 1 + a^- = a^- + 1 = \sigma(a^-) = a\), so \(\eqref{eq:2}\) is true. Therefore \(1 \in M_a\).
Next assume that \(b \in M_a\), so exactly one of \(\eqref{eq:1}\)–\(\eqref{eq:3}\) is true for \(a\) and \(b\). For each of the three possibilities for \(a\) and \(b\), it is necessary to show that one of \(\eqref{eq:1}\)–\(\eqref{eq:3}\) is true for \(a\) and \(\sigma(b)\).
First suppose \(\eqref{eq:1}\) is true for \(a\) and \(b\). Since \(a = b\) it should be expected that \(a \overset{!}{<}\sigma(b)\), so \(\eqref{eq:3}\) should be true for \(a\) and \(\sigma(b)\). Indeed, \(\sigma(b) = b + 1 = a + 1\), so take \(n = 1\) and \(\eqref{eq:3}\) is true for \(a\) and \(\sigma(b)\).
Next suppose \(\eqref{eq:2}\) is true for \(a\) and \(b\). Since \(a \overset{!}{>}b\) it should be expected that either \(a \overset{!}{=}\sigma(b)\) or \(a \overset{!}{>}\sigma(b)\), so \(\eqref{eq:1}\) or \(\eqref{eq:2}\) should be true for \(a\) and \(\sigma(b)\), respectively. Either \(m = 1\) or \(m \neq 1\). If \(m = 1\), then \(a = b + 1 = \sigma(b)\), so \(\eqref{eq:1}\) is true for \(a\) and \(\sigma(b)\). If \(m \neq 1\), then \(m \in \symup{img}(\sigma)\) so there exists \(m^- \in \symbb{N}\) such that \(\sigma(m^-) = m\). Then \[\begin{align*} \sigma(b) + m^- &= (b + 1) + m^-\\[0.75em] &= b + (1 + m^-)\\[0.75em] &= b + (m^- + 1)\\[0.75em] &= b + \sigma(m^-)\\[0.75em] &= b + m\\[0.75em] &= a, \end{align*}\] so \(\eqref{eq:2}\) is true for \(a\) and \(\sigma(b)\).
Lastly suppose \(\eqref{eq:3}\) is true for \(a\) and \(b\). Since \(b \overset{!}{>}a\) it should be expected that \(\sigma(b) \overset{!}{>}a\), so \(\eqref{eq:3}\) should be true for \(a\) and \(\sigma(b)\). Indeed, \[\begin{align*} \sigma(b) &= b + 1\\[0.75em] &= (a + n) + 1\\[0.75em] &= a + (n + 1)\\[0.75em] &= a + \sigma(n) \end{align*}\] so \(\eqref{eq:3}\) is true for \(a\) and \(\sigma(b)\).
In all three cases, exactly one of \(\eqref{eq:1}\)–\(\eqref{eq:3}\) is true for \(a\) and \(\sigma(b)\), so \(\sigma(b) \in M_a\) and therefore \(M_a = \symbb{N}\). Since \(a \in \symbb{N}\) was arbitrary, this argument applies for any \(a \in \symbb{N}\). \(\blacksquare\)
With the preceding foundations, it can now be proven that \(<\) as defined by Katznelson and Katznelson (2024, sec. 1.1.2) is a total order on \(\symbb{N}\).
Theorem 1 For all \(a, b \in \symbb{N}\), define the binary relation \(<\) on \(\symbb{N}\) by \(a < b\) if and only if there exists \(k \in \symbb{N}\) such that \(b = a + k\). Then \(<\) is a total order on \(\symbb{N}\).
Proof. To prove irreflexivity, suppose there exists \(a \in \symbb{N}\) such that \(a < a\). Then there exists \(k \in \symbb{N}\) such that \(a = a + k\). Since this contradicts Lemma 1, \(a \nless a\), so \(<\) is irreflexive.
To prove transitivity, suppose for \(a, b, c \in \symbb{N}\) that \(a < b\) and \(b < c\), so there exists \(k \in \symbb{N}\) such that \(b = a + k\) and \(l \in \symbb{N}\) such that \(c = b + l\). Then \(c = (a + k) + l = a + (k + l)\), so \(a < c\), whence \(<\) is transitive.
Lastly, by the definition of \(<\) and Proposition 2, for all \((a, b) \in \symbb{N}\times \symbb{N}\), \((a < b) \lor (b < a) \lor (a = b)\), so \(<\) is total. \(\blacksquare\)
Corollary 1 (Trichotomy law) For all \(a, b \in \symbb{N}\), exactly one of \(a < b\), \(a = b\), and \(a > b\) is true.
Proof. This is an application of Proposition 1 to the total order \(<\) on \(\symbb{N}\). \(\blacksquare\)
Proposition 3 For all \(a, b, c \in \symbb{N}\), if \(a < b\) then \(a + c < b + c\) and \(ac < bc\).
Proof. Since \(a < b\) there exists \(k \in \symbb{N}\) such that \(b = a + k\). By associativity and commutativity of addition, \(b + c = (a + k) + c = (a + c) + k\), so \(a + c < b + c\). By distributivity, \(bc = (a + k)c = ac + kc\), so \(ac < bc\). \(\blacksquare\)