Order Relations

Just like we have equivalence relations we can also define so called order relations. The equivalence relation worked in a similar way to our normal understanding of equivalence. The order relation works in a similar way to our normal understanding of order so that one thing is less than or equal to another thing and vice versa.

Partial Order

We can define a so called partial order \(R\) on a set \(X\) as a homogeneous relation or in other words a binary relation between the same sets, that is reflexive, antisymmetric and transitive. This is sometimes also called a weak order or a order relation. Because the relation \(R\) defines an ordering it is often denoted by the symbol \(\leq\).

The pair \(P=(X, R)\) or simply \((X, \leq)\) is then called a partially ordered set or often abbreviated as poset.

For a relation \(R\) to be a partial order, it must satisfy the following properties:

• Reflexivity: For all \(a \in X\), \(a R a\) (or \(a \leq a\)).
• Antisymmetry: For all \(a, b \in X\), if \(a R b\) and \(b R a\), then \(a = b\) (or \(a \leq b\) and \(b \leq a\) implies \(a = b\)).
• Transitivity: For all \(a, b, c \in X\), if \(a R b\) and \(b R c\), then \(a R c\) (or \(a \leq b\) and \(b \leq c\) implies \(a \leq c\)).

So the only difference between a partial order and an equivalence relation is that the partial order is antisymmetric instead of symmetric. This means that if two elements are related to each other, they must be equal. In other words, if \(a \leq b\) and \(b \leq a\), then \(a = b\). Whereas in an equivalence relation, if \(a \equiv b\) then \(b \equiv a\) is true but \(a\) and \(b\) do not have to be equal.

We can also compare this to our normal understanding of “less than or equal to”:

• We say that two things that are the same are less than or equal to each other because they are equal (reflexive and antisymmetric).
• If something is less than or equal to something else, then a third thing that is less than or equal to the second thing is also less than or equal to the first thing (transitive).

Strong Partial Order

A strong or also called strict partial order is a homogeneous relation \(R\) often denoted by the symbol \(< \) on a set \(X\) that satisfies the following properties:

• Irreflexivity: For all \(a \in X\), it is not the case that \(a R a\) (or \(a < a\)).
• Asymmetry: For all \(a, b \in X\), if \(a R b\), then it is not the case that \(b R a\) (or \(a < b\) does not imply \(b < a\)).
• Transitivity: For all \(a, b, c \in X\), if \(a R b\) and \(b R c\), then \(a R c\) (or \(a < b\) and \(b < c\) implies \(a < c\)).

So the difference between a strong partial order and a partial order is that the strong partial order is irreflexive and asymmetric instead of reflexive and antisymmetric. Important to note is that asymmetric and antisymmetric are not the same. Asymmetric means that if \(a < b\) then it is not the case that \(b < a\). Antisymmetric means that if \(a \leq b\) and \(b \leq a\), then \(a = b\).

So we can see that where the weak order was like our normals understanding of “less than or equal to”, the strong order is like our normal understanding of “less than”. We can see this in the properties of the relation:

• We say that two things that are the same are not less than each other (irreflexive).
• If something is less than something else, then that something else is not less than the first thing (asymmetric).
• If something is less than something else, and that something else is less than a third thing, then the first thing is also less than the third thing (transitive).

Total Order

The reason a total order is a special case of a partial order is that it imposes an additional requirement: every pair of elements must be comparable. In other words, for any two elements \(a\) and \(b\) in the set, either \(a \leq b\) or \(b \leq a\) must hold.

Hasse Diagram

We can create a so called ordering graph where the vertices are the elements of the set and the edges represent the relation between the elements. If the relation is a partial order, this results in a so called Hasse diagram.

Importantly the Hasse diagram draws the so called “cover” relations, which are the relations that cannot be derived from other relations in the diagram. This means that if \(a \leq b\) and there is no element \(c\) such that \(a \leq c \leq b\), then there is an edge between \(a\) and \(b\) in the Hasse diagram. This is best seen when drawing the Hasse diagram for the power set of a set \(X\) and the subset relation \(\subseteq\). The Hasse diagram will not contain edge from the empty set to the set \(X\) if it has more than one element because there are other subsets \(c\) such that \(\emptyset \subseteq c \subseteq X\).

This can also be seen in the Hasse diagram of the natural numbers \(\mathbb{N}\) with the “less than or equal to” relation \(\leq\). The Hasse diagram will contain an edge from \(1\) to \(2\), from \(2\) to \(3\), and so on, but it will not contain an edge from \(1\) to \(3\) because there is the element \(c=2\) such that \(1 \leq 2 \leq 3\).

If the relation is a total order, the Hasse diagram is a linear graph where all elements are connected in a single line. Hence the total order is also called a linear order.

Ordering of Real Numbers

We can define a weak total ordering on the set of real numbers \(\mathbb{R}\) by defining the relation \(\leq\) between two real numbers \(a\) and \(b\):

We can also define such a relation on the rational numbers \(\mathbb{Q}\) in a similar way. However, the key difference between the real numbers and the rational numbers is the that the ordering of the real numbers has the completeness property. This means that for any two non-empty sets of real numbers \(A\) and \(B\) such that \(\forall a \in A, b \in B: a \leq b\), there exists at least one real number \(c\) such that \(\forall a \in A, b \in B: a \leq c \leq b\). So in a more intuitive way, this means that for any number \(a\) in set \(A\) and any number \(b\) in set \(B\), we can always find a real number \(c\) that lies between them, this then also means that for any two real numbers \(a\) and \(b\) such that \(a < b\), there exists a real number \(c\) such that \(a < c < b\) as we could just define \(A = \{a\}\) and \(B = \{b\}\).

This can’t be done with the rational numbers for example if the two sets are construct in such a way that the only number in between \(a\) and \(b\) is irrational such as \(\sqrt{2}\). You can see a proof of why \(\sqrt{2}\) is not a rational number in the proof of irrational numbers.

The real numbers \(\mathbb{R}\) have the arithmetic operations of addition and multiplication defined on them, which are compatible with the ordering relation \(\leq\). This means that we can add and multiply real numbers while preserving the order.

Using these properties we can show a multitude of things such as that the additive inverse of a real number \(a\) is unique. If we assume that there are two additive inverses \(b\) and \(c\) such that \(a + b = 0\) and \(a + c = 0\), then we can show that \(b = c\):

The same goes for the multiplicative inverse of a real number \(a\) where \(a \neq 0\). If we assume that there are two multiplicative inverses \(b\) and \(c\) such that \(a \cdot b = 1\) and \(a \cdot c = 1\), then we can show that \(b = c\):

We already used the fact that \(0 \cdot a = 0\) in the proof of multiplication preserving order. However, we can also show this in a more general way. We can show that \(0 \cdot a = 0\) for all real numbers \(a\) and that \((-1) \cdot a = -a\) for all real numbers \(a\) using the distributive property of multiplication over addition.

specifically we can also show that \((-1)^2 = 1\) using \(a=-1\):

We can also show that the negation of a positive real number is negative. If we assume that \(0 \leq a\) for some real number \(a\), then we can show that \(-a \leq 0\):

In a similar way we can also show that the square of a real number is non-negative. If we assume that \(a \in \mathbb{R}\), then we can show that \(0 \leq a^2\). The case where \(a = 0\) is trivial, so we first assume that \(0 < a\). Then we can show that \(0 \leq a^2\):

We can also show that if \(a < 0\), then \(0 \leq a^2\). If \(a\) is negative then we have \(a=-b\) for some positive real number \(b\). We can then show that \(0 \leq a^2\):

This comes from the previous proof where \(0 \leq b\) so then \(0 \cdot b \leq b \cdot b\) and therefore \(0 \leq b^2\).

Archimedean Property

The Archimedean property, named after the ancient Greek mathematician Archimedes is an interesting property which the real numbers have. There are multiple interpreations and ways to state this property, but the most common one is that for any two real numbers \(x > 0\) and \(y \in \mathbb{R}\), there exists an integer \(n \in \mathbb{N}\) such that the following holds:

So if we have a real number then we can always create a multiple of another positive real number with a natural number that is larger.

An alternative way to state the Archimedean property is that for any real number \(x \in \mathbb{R}\), there exists exactly one integer \(n \in \mathbb{Z}\) such that:

So we can always find an integer that is smaller than a real number and when we add 1 to that integer we get an integer that is larger than the original real number. So in other words, we can always bound a real number between two integers. This also leads to the conclusion that the set of natural numbers \(\mathbb{N}\) is unbounded and has an infinite number of elements. Because the natural numbers are an infinite set and also a subset of the integers \(\mathbb{Z}\), the set of integers is also unbounded and has an infinite number of elements the same goes for the other sets of numbers such as the rational numbers \(\mathbb{Q}\) and the real numbers \(\mathbb{R}\).

Roots of Real Numbers

Using these properties we can now show that we can always find a solution to the equation \(x^2 = t\) for any real number \(t \geq 0\). In other words, we can always find the square root of a real number that is greater or equal to 0.

Young’s Inequality

From the properties of the real numbers we can quickly come up with that the following quadratic inequality holds for all real numbers \(a\) and \(b\):

This can be expanded to:

The idea is now that we want to approximate a bound for the product \(2ab\) by a weighted sum of the squares of \(a\) and \(b\). This is done by introducing a scaling factor \(\epsilon > 0\) to the inequality, which is commonly chosen as \(\epsilon = \frac{|a|}{|b|}\) where \(b \neq 0\). Depending on the scaling factor the approximation becomes better or worse. This leads us to Young’s inequality for all real numbers \(a\) and \(b\) and for all \(\epsilon > 0\):