MATH 1800
A binary relation \(R\) on a set \(A\) is said to be an ordering relation or order relation if \(R\) is reflexive, antisymmetric, and transitive.
If \(R\) is an ordering relation on \(A\) and \(x,y \in A\), then \(x\) and \(y\) are comparable if \(xR y \vee yR x\) and incomparable otherwise.
Remark. Note that \(R\) given by \(xRy\) iff \(x > y\) (or \(xRy\) iff \(x < y\)) is not an order relation because it is not reflexive. However, it is called a quasi order which is a binary relation that is irreflexive and transitive.
Let \(A\) be a set. Let \(S = {\cal P}(A)\), the power set of \(A\). Then the relation \(R\) given by \(aRb\) iff \(a \subseteq b\) is an ordering relation.
For example, suppose that \(A = \{1,2\}\). Then \(S = \{ \emptyset, \{1\}, \{2\}, \{1,2,\} \}\) and the graph of \(R\) consists of the following pairs:An ordering relation \(R\) on \(S\) is total if \(\forall x, \forall y, xRy \vee yRx\). Such a relation is called a total order or linear order. An ordering relation that is not total is called a partial order.
In the first example above, the less-than-or-equal-to and greater-than-or-equal to relations are total orders.
The second example illustrates a partial order.
Ordering relations appear quite often in advanced mathematics, especially in discrete mathematics, theoretical computer science, and algebra. As you progress in your mathematical studies, you will most certainly encounter them again.
Suppose that we have a binary relation \(R\) on \(S\) that is a total order. If for every nonempty subset \(T\) of \(S\), \(\exists x \in T, \forall y\in T, xRy\) holds, then \(S\) together with the relation \(R\) is called a well-ordered set. In casual terms, every subset of a well-ordered set has a least element.
An important fact, called the well-ordering principle (WOP), is that the natural numbers with the usual less-than-or-equal-to relation is well-ordered. In other words, every nonempty subset of \(\mathbb{N}\) has a least element. The same cannot be said of the set of integers.
The WOP is actually equivalent to the axiom of induction. In other words, one can prove the WOP by mathematical induction and prove that the principle of mathematical induction holds assuming the WOP. We will not give a proof of the equivalence here but will illustrate another common proof technique based on the WOP with some examples.
Let \(n \in \mathbb{N}\). If \(2 \nmid n\), then there exists \(k \in \mathbb{N}\) such that \(n = 2k+1\).
Proof. Let \(S = \{ n \in \mathbb{N} \mid 2 \nmid n \wedge \neg (\exists k \in \mathbb{N}, n = 2k+1\}\). In casual terms, \(S\) is the set of all the counterexamples. We show that \(S\) must be empty.
Assume by way of contradiction that \(S\) is nonempty. Since \(S \subseteq \mathbb{N},\) by the WOP, there exists a least element \(m \in S\). Note that \(m \neq 0\) since \(2 \mid 0\). Also, \(m \neq 1\) because \(1 = 2\cdot 0 + 1\) and \(0\) is a natural number. Thus, \(m \geq 2\). Let \(r = m - 2\). Then \(r \in \mathbb{N}.\) Note that \(2 \nmid r\) because otherwise, \(r = 2s\) for some \(s \in \mathbb{N}\) giving \(m = 2(s+1)\), contradicting that \(2 \nmid m\).
As \(r < m\), \(r \notin S\). This means that there exists \(k' \in \mathbb{N}\) such that \(r = 2k' + 1\), implying that \(m =2(k'+1) + 1\), contradicting that \(m \in S\). Thus, our assumption that \(S\) is nonempty must be false.
Let \(S = \{ d \in \mathbb{N_{>0}} \mid \exists n \in \mathbb{N}, n^2 = 2 d^2\}.\) Prove by contradiction that \(S\) is empty using the well-ordering principle.
Solution.
Suppose that \(S\) is nonempty. Then by the well-ordering principle, there exists a least element \(m \in S.\) Let \(n\in \mathbb{N}_{>0}\) be such that \(n^2 = 2 m^2\) since \(m\) is a positive integer. Then, \(2 \mid n^2\). Note that \(n\) must be even because otherwise, we would have \(n \equiv 1~(\text{mod }2)\), implying that \(n^2 \equiv 1~(\text{mod }2),\) contradicting that \(2 \mid n^2.\) Thus, \(n = 2k\) for some \(k \in \mathbb{N}_{>0}.\) Hence, \[(2k)^2 = 2m^2,\] implying that \(m^2 = 2k^2\). It follows that \(k \in S\). Now, \(m^2 = 2k^2\), implies that \(k^2 < m^2\). Since \(k,m > 0\), we have \(k < m\). This contradicts that \(m\) is the least element of \(S\). Thus, \(S\) must be empty.
Remark. It follows from the statement of this question that \(\sqrt{2}\) is irrational.
Let \(a, b \in \mathbb{N}_{>0}\). Then there exist \(x, y \in \mathbb{Z}\) such that \(\gcd(a,b) = xa + yb\).
Proof. Let \(S\) denote the set of positive integers of the form \(xa + yb\) where \(x, y \in \mathbb{Z}\). Since \(a\) and \(b\) are positive, \(S\) is nonempty. By the WOP, \(S\) has a least element \(d\). We claim that \(d = \gcd(a,b)\).
Let \(g = \gcd(a,b)\). Let \(x'\) and \(y'\) be integers such that \(x'a + y'b = d\). Clearly, \(g \mid d\) since the left-hand side is divisible by \(g\) and so the right-hand side must also be divisible by \(g\).
By the quotient-remainder theorem (see here), there exists an integer \(q\) and a positive integer \(r\) such that \(0 \leq r < d\) and \(a = qd + r\). Then \(r = a - qd = a - q (x'a + y'b) =(1-qx')a + (-qy')b\). If \(r > 0\), then \(r\) is a positive integer of the form \(xa + yb\) for some integers \(x\) and \(y\), implying that \(r \in S\). But this is impossible because \(r < d\) and \(d\) is the least element of \(S\). It follows that \(r = 0\) and so \(d \mid a\). Similarly, \(d \mid b\). Thus, \(d \mid g\).
As we have \(g \mid d\) and \(d \mid g\), we must have \(g = d\).
Remark. Note that the proof given here is an existential proof and it does not tell us how to find the integer \(x\) and \(y\). An algorithm for finding such integers, called the Euclidean Algorithm, is usually discussed in a number theory course.
Explain why Example 2 under Ordering Relations is not a total order.
Let \(d, n \in \mathbb{N}\) with \(d \neq 0.\) Prove that there exists \(r \in \{0,\ldots, d-1\}\) such that \(d \mid (n-r).\)
Let \(m\) be a positive integer. Let \(a\) be a positive integer such that \(\gcd(a,m)=1\). Prove that there exists an integer \(b\) such that \(ab \equiv 1~(\text{mod } m)\).
Let \(S \subseteq \mathbb{N}\). Prove that if \(S\) has no least element, then \(\forall n \in \mathbb{N}, n \notin S.\) (Hint: Let \(P(n)\) denote the predicate “\(n \notin S\)” and prove \(\forall n, P(n)\) using strong induction.)