: Order relations<a class="btn btn-sm" href="/UUID/EDB/1YY/?lang=eng"><span class="ttfamily"><small class="scriptsize">[1YY]</small></span></a>

3.4 Order relations[1YY]

Let \((X,≤)\) an orderered set, non-empty (cf definition 48)

Definition 52

[229]Given \(x,y∈ X\) remember that \(x{\lt}y\) means \(x≤ y∧ x≠ y\).

When we have that \(x≤ y\) or \(y≤ x\) we will say that the two elements are ”comparable”. Conversely if neither \(x≤ y\) nor \(y≤ x\) then we will say that the two elements are ”incomparable”.
An element \(m∈ X\) is called maximal if there is no element \(z∈ X\) such that \(m{\lt}z\).
An element \(m∈ X\) is called minimal if there is no element \(z∈ X\) such that \(z{\lt}m\).
An element \(m∈ X\) is called maximum, or greatest element, if, for any element \(z∈ X\), \(z \le m\).
An element \(m∈ X\) is called minimum, or least element, if, for any element \(z∈ X\), \(z \le m\).

Note that the definitions of minimum/minimal can be obtained from maximum/maximal by reversing the order relation (and vice versa).

E52

[1WJ]Given an ordered set, show that the maximum, if it exists, is unique.

E52

[067] (Solved on 2022-10-13) Show that for any two \(x,y∈ X\) one of the following (mutually exclusive) cases holds

\(x=y\),
\(x{\lt}y\),
\(x{\gt}y\),
\(x,y\) are incomparable.

Hidden solution: [UNACCESSIBLE UUID ’068’]

E52

[29D]Show that if \(x{\lt}y \land y\le z\) or \(x\le y \land y{\lt} z\) then \(x{\lt}z\).

E52

[069]Show that \(m∈ X\) is maximal if and only if ”for every \(z∈ X\) you have that \(z≤ m\) or \(z,m\) are incomparable”.

Hidden solution: [UNACCESSIBLE UUID ’06B’]

E52

[1WM]Let \(f:A→ B\) be a function, let \(⪯\) an order relation on \(B\); consider the relation \(R\) between elements of \(A\) given by

\[ xRy\iff f(x)⪯ f(y)\quad ; \]

is it an order relation? What if we also assume that \(f\) is injective?

E52

[1WN] Show that, if every non-empty subset admits minimum, then the order is total.

E52

[1YJ] Consider \(A=ℝ^ 2\) and consider the relation

\[ (x,y)⪯ (x',y') \iff ( x≤ x'∧ y≤ y') \]

show that it is an order relation; is it partial or total?
Define \(B=\{ (x,y):x^ 2+y^ 2 ≤ 1\} \), let’s consider it as an ordered set with the sorting \(⪯\) : are there maxima? minima? maximals? minimals?

E52

[06C](Proposed on 2022-12) Let \((X,≤)\) be a finite and ordered non-empty set then it has maximals and minimals. Hidden solution: [UNACCESSIBLE UUID ’06D’]

E52

[06F]Build an order \(⪯\) on \(ℕ\) with this property: for each \(n∈ℕ\)

the set \(\{ k∈ℕ , k≠ n,k⪯ n\} \) of the elements preceding \(n\) has exactly two maximals,
the set \(\{ k∈ℕ , k≠ n,n⪯ k\} \) of the elements following \(n\) has exactly two minimals.

E52

[06J](Proposed on 2022-12) Let \(X\) be a non-empty set and \(R⊆ X^ 2\) an order relation, then there is a total order \(T\) that extends \(R\) (i.e. \(R⊆ T\), considering relations as subsets of \(X^ 2\)).

E52

[263] Prerequisites:134,1.(Solved on 2022-10-13) Let \(X\) be ordered (partially). Show that these are equivalent

in each non-empty subset \(A\subseteq X\) there is at least one minimal element;
there are no strictly decreasing functions \(f:ℕ→ X\).

Hidden solution: [UNACCESSIBLE UUID ’07Y’]

Direct and filtering order[2FJ]

Definition 53

[06M] (Solved on 2022-11-24) Let \((X,≤)\) be a (partially) ordered set, we will say that it is filtering ¹ if

\begin{equation} \label{eq:filtrante} ∀ x,y∈ X ~ ∃ z∈ X,~ x< z∧ y< z\quad . \end{equation}

The sets \(ℝ,ℕ,ℚ,ℤ\) endowed with their usual order relations, are filtering.

Definition 55

[06N] A directed set is an ordered set \((X,≤)\) for which

\begin{equation} \label{eq:ord_ diretto} ∀ x,y∈ X ~ ∃ z∈ X,~ x≤ z∧ y≤ z\quad . \end{equation}

Obviously a filtering order is direct.

Remark 57

[0NB]We have added the antisymmetric property to the usual definition of "Directed Set", see [ 14 ] (or other references in [ 38 ] ).

This choice simplify the discussion (in particular it eases the use of concepts already used in the theory of ordered sets, such as maximum and maximal); at the same time, by 236, this choice does not hinder the usufulness and power of the theory developed in this Section and in Section 7.4.

Definition 58

[06P] Given a directed set \((X,≤_ X)\) a subset of it \(Y⊆ X\) is called cofinal if

\begin{equation} \label{eq:cofinale} ∀ x∈ X ~ ∃ y∈ Y,~ y≥_ X x \end{equation}

More in general, another directed set \((Z,≤_ Z)\) is said to be cofinal in \(X\) if there exists a map \(i : Z→ X\) monotonic weakly increasing and such that \(i(Z)\) is is cofinal in \(X\); i.e.

\begin{equation} \label{eq:cofinale_ Z,X} ( ∀ z_ 1,z_ 2∈ Z, z_ 1≤_ Z z_ 2⇒ i(z_ 1)≤_ X i(z_ 2) ) ~ ~ ∧~ ~ (∀ x∈ X ~ ∃ z∈ Z,~ i(z)≥_ X x) \end{equation}

(This second case generalizes the first one, where we may choose \(i:Y→ X\) to be the injection map, and \(≤_ Y\) to be the restriction of \(≤_ X\) to \(Y\).)

Definition 61

[231] If \(X\) is filtering, ”a neighborhood of \(∞\) in \(X\)” is a subset \(U⊆ X\) such that

\[ ∃ k∈ X ∀ j∈ X,j≥ k ⇒ j∈ U~ . \]

E61

[06Q] (Proposed on 2022-11) Let \((X,\le )\) be a filtering ordered set, prove that it is an infinite set. Hidden solution: [UNACCESSIBLE UUID ’06R’]

E61

[06S] (Solved on 2022-10-27) Let \((X,≤)\) be a directed set: show that if there is a maximal element in \(X\) then it is the maximum. Hidden solution: [UNACCESSIBLE UUID ’06T’]

E61

[06V] Prerequisites:53,2.(Solved on 2022-11-24) Let \((X,≤)\) be a directed set. Show that these properties are equivalent:

\((X,≤)\) satisfies the filtering property 54,
\((X,≤)\) has no maximum,
\((X,≤)\) has no maximals.

Hidden solution: [UNACCESSIBLE UUID ’06W’]

E61

[06X]Prerequisites:58.Let \((X,≤)\) be a directed set, and \(Y⊆ X\) cofinal: show that \((Y,{≤}_{|{Y}})\) is a directed set.

Similarly, if \((X,≤)\) is filtering, show that \((Y,{≤}_{|{Y}})\) it is filtering.

E61

[232]Prerequisites:61.Given \(U_ 1,U_ 2⊆ J\) two neighborhoods of \(∞\) show that the intersection \(U_ 1∩ U_ 2\) is a neighborhood of \(∞\). Hidden solution: [UNACCESSIBLE UUID ’236’] .

E61

[234]Prerequisites:58,61.If \((X,≤)\) a filtering set, \(Y⊆ X\) is cofinal, and \(U⊆ X\) is a neighborhood of \(∞\) in \(X\), show that \(U∩ Y\) is a neighborhood of \(∞\) in \(Y\). Hidden solution: [UNACCESSIBLE UUID ’235’]

A directed ordered set \((X,≤)\) is a framework in which we can generalize the notion seen in 160.

Definition 62

[06Y] (Solved on 2022-10-27) Let P(x) be a logical proposition that depends on a free variable \(x∈ X\). We will say that

P(x) holds eventually for \(x∈ X\) if	\(∃ y∈ X, ∀ x∈ X,x≥ y⇒\) P(x) holds;
P(x) frequently applies for \(x∈ X\) if	\(∀ y ∈ X, ∃ x∈ X, x≥ y\) such that P(x) holds.

E62

[070] (Proposed on 2022-10-27) The 3 property reformulates in this way.

Show that «P(x) frequently applies for \(x∈ X\)» if and only if the set

\[ Y=\{ x∈ X: P(x)\} \]

is cofinal in \(X\).

E62

[233]Prerequisites:62,5.Show that «P(x) eventually holds for \(x∈ X\)» if and only if the set

\[ U=\{ x∈ X: P(x)\} \]

is a neighborhood of \(∞\) in \(X\).

E62

[06Z]Prove that the properties 1, 2, 4 and 5 seen in Sec. 4.7 also apply in this more general case 62.

E62

[2B2]Suppose that on the set \(X\) there is a relation \(R\) that is reflexive and transitive and satisfies

\begin{equation} \label{eq:ord_ diretto_ R} ∀ x,y∈ X ~ ∃ z∈ X,~ xRz, yR z\quad . \end{equation}

(as seen in ??)

This pair \((X,R)\) is a "Directed Set" according to the usual definition (see [ 14 ] or other references in [ 38 ] ).

Show that there exists another relation \(≤\) such that

\(≤\) is a partial order and it satisfies ??;
\(R\) extends \(≤\) that is;

\[ ∀ x,y∈ X ~ x≤ y⇒~ x R y\quad ; \]
moreover \((X,≤)\) is cofinal in \((X,R)\).

Hidden solution: [UNACCESSIBLE UUID ’2GM’]

Further exercises on the subject are 175,8, and in Section 7.4.

Lexicographic order[2FH]

Definition 64

[071] Given two ordered sets \((X,≤_ X)\) and \((Y,≤_ Y)\), setting \(Z=X× Y\), we define the lexicographic order \(≤_ Z\) on \(Z\); let \(z_ 1=⦗x_ 1,y_ 1⦘\in Z\) and \(z_ 2=⦗x_ 2,y_ 2⦘\in Z\), then:

in the case \(x_ 1≠ x_ 2\) , then \(z_ 1≤_ Z z_ 2\) if and only if \(x_ 1≤_ X x_ 2\);
in the case \(x_ 1= x_ 2\) , then \(z_ 1≤_ Z z_ 2\) if and only if \(y_ 1≤_ Y y_ 2\).

This definition is then extended to products of more than two sets: given two vectors, if the first elements are different then we compare them, if they are equal we compare the second elements, if they are equal the thirds, etc.

E64: [1WP]Verify that \(\le _ Z\) is an order relation.
E64: [072] If \((X,≤_ X)\) and \((Y,≤_ Y)\) are total orders, show that \((Z,≤_ Z)\) is a total order.
E64: [073] If \((X,≤_ X)\) and \((Y,≤_ Y)\) are well ordered, show that \((Z,≤_ Z)\) is a well ordering.
E64: [074] Let \(X=ℕ^ℕ\) be ordered with lexicographic order. Build a function \(f:X→ℝ\) that is strictly increasing. Hidden solution: [UNACCESSIBLE UUID ’075’]
E64: [076]Consider \(X=ℝ× \{ 0,1\} \) ordered with lexicographic order. Show that there is no function \(f:X→ℝ\) strictly growing. Hidden solution: [UNACCESSIBLE UUID ’077’]

Total order, sup and inf[2FM]

Let \(≤\) a total order on a non-empty set \(X\).

Definition 65

[22R] Let \(A⊆ X\). The majorants of \(A\) (or upper bounds) are

\[ M_ A{\stackrel{.}{=}}\{ x∈ X:∀ a∈ A, a≤ x\} \quad . \]

A set \(A\) is bounded above when there exists an \(x∈ X\) such that \(∀ a∈ A, a≤ x\), i.e. exactly when \(M_ A≠∅\).

If \(M_ A\) has minimum \(s\), then \(s\) is th supremum, a.k.a. least upper bound, of \(A\), and we write \(s=\sup A\).

By reversing the order relation in the above definition, we obtain the definition of minorants/lower bounds, bounded below, infimum/greatest lower bound.

Lemma 66

[22S]Let \(A⊆ X\) be a not empty set. We recall these properties of the supremum.

If \(A\) has maximum \(m\) then \(m=\sup A\).
Let \(s∈ X\). We have \(s=\sup A\) if and only if
- for every \(x∈ A\) we have \(x≤ s\).
- for every \(x∈ X\) with \(x{\lt}s\) there exists \(y∈ A\) with \(x{\lt} y\).

This last property is of very wide use in the analysis!

The proof is left as a (useful) exercise. Hidden solution: [UNACCESSIBLE UUID ’22T’]

E66

[078] (Proposed on 2022-10-13) Let \(B\) be a non-empty set that is bounded from below, let \(L\) the set of minorants of \(B\); we note that \(L\) is upper bounded, and suppose that \(𝛼=\sup L\) exists: then \(𝛼∈ L\) and \(𝛼=\inf B\). Hidden solution: [UNACCESSIBLE UUID ’079’]

E66

[07B]Prerequisites:1.(Proposed on 2022-10-13) Show that if for the total ordering of \(X\) all ”suprema” exist then all ”infima” also exist; and vice versa. Precisely, show that these are equivalent:

Every non-empty set bounded from below in \(X\) admits greatest lower bound;
every non-empty set bounded from above in \(X\) admits least upper bound.

Hidden solution: [UNACCESSIBLE UUID ’207’]

Total ordering, intervals[2DW]

Let \(≤\) a total order on a non-empty set \(X\).

Definition 67

[07C] A set \(I⊆ X\) is an interval if for every \(x,z∈ I\) and every \(y∈ X\) with \(x{\lt}y{\lt}z\) we have \(y∈ I\).

Note that the empty set is an interval.

Definition 68

[07D] Given \(x,z∈ X\) the following standard intervals are defined

\[ \begin{aligned} (x,z)& =& \{ y∈ X: x{\lt}y{\lt}z \} \\ {} (x,z]& =& \{ y∈ X: x{\lt}y≤ z \} \\ {} (x,∞)& =& \{ y∈ X: x{\lt}y \} \\ {} [x,z)& =& \{ y∈ X: x≤ y{\lt}z \} \\ {} [x,z]& =& \{ y∈ X: x≤ y≤ z \} \\ {} [x,∞)& =& \{ y∈ X: x≤ y \} \\ {} (-∞,z)& =& \{ y∈ X: y{\lt} z \} \\ {} (-∞,z]& =& \{ y∈ X: y≤ z \} \\ {} (-∞,∞)& =& X~ ~ . \end{aligned} \]

[24Y]Note that there are 9 cases, 3 for the LHS and 3 for the RHS. We concord that \(∞,-∞\) are symbols and not elements of \(X\); if \(X\) has a maximum \(m\) then the intervals are preferably written as \((x,∞)=(x,m]\) and \([x,∞)=[x,m]\); similarly if \(X\) has a minimum.

E68

[07F] Prerequisites:67,68,3.

Let \(\mathcal F\) be a non-empty family of intervals.

Show that the intersection \(\underline⋂{\mathcal F}\) of all intervals is an interval.

Suppose the intersection \(\underline⋂{\mathcal F}\) is not empty, show that the union \(\underline⋃{\mathcal F}\) is an interval.

Hidden solution: [UNACCESSIBLE UUID ’07G’]

E68

[07H] Prerequisites:67,68.(Solved on 2022-10-13)

Find an example of a set \(X\) with total ordering, in which there is an interval \(I\) that does not fall into any of the categories viewed in 68.

Hidden solution: [UNACCESSIBLE UUID ’07J’]

E68

[07K] Prerequisites:67,68,1.(Proposed on 2022-10-13)

Let \(A⊆ X\) be a non-empty set; let\(I\) the smallest interval that contains \(A\); this is defined as the intersection of all intervals that contain \(A\) (and the intersection is an interval, by 1). Let \(M_ A\) be the family of majorants of \(A\), \(M_ I\) of \(I\); show that \(M_ A=M_ I\). In particular \(A\) is bounded from above if and only \(I\) is bounded from above; if moreover \(A\) has supremum, then \(\sup A=\sup I\). (Similarly for the minorants and infimum). Hidden solution: [UNACCESSIBLE UUID ’07M’]

E68

[07N] Prerequisites:67,68,1,3.

Let \(X\) be a totally ordered set. Show that the following two are equivalent.

Every \(A⊆ X\) non-empty bounded from above and from below admits supremum and infimum.
Each non-empty interval \(I⊆ X\) falls in one of the categories seen in 68.

Hidden solution: [UNACCESSIBLE UUID ’07P’]

E68

[206]Prerequisites:67,68,1.Difficulty:*.

At the beginning of the section we assumed that the ordering \(≤\) on \(X\) be total. The definitions of interval in 67 and 68 however, they can also be given for an order that is not (necessarily) total. What happens in exercise 1 when the order is not total? Which result is true, which is false, and if so what counterexample can we give?

[UNACCESSIBLE UUID ’07Q’]

Order types

Definition 69

[07V]Given two ordered non-empty sets \((X,≤_ X)\) and \((Y,≤_ Y)\), we will say that ”they have the same order type”, or ”order-isomorphic”, or more briefly that they are ”equiordinate” ² , if there is a strictly increasing monotonic bijective function \(f:X→ Y\), whose inverse \(f^{-1}\) is strictly increasing. The function \(f\) is the “order isomorphism”.

Remark 70

[21R](Solved on 2021-11-18) Note that if \((X,≤_ X)\) and \((Y,≤_ Y)\) are equiordinate then \(X\) and \(Y\) are equipotents; but given an infinite set \(X\), there exist on it orders of different types — even if we consider only the well orders. (See for example exercise 1)

Remark 71

[21V]Note that if two sets are equiordinate, then they enjoy the same properties: if one is totally ordered, so is the other; if one is well ordered, so is the other; etc etc .... See 2.

E71

[220](Proposed on 2021-11-18) Show that the relation "having the same order type" is an equivalence relation. Given a set \(X\), let’s consider all possible orders on \(X\), the relation therefore defines equivalence classes, and each class is (precisely) an“order type” on \(X\).

E71

[22P](Proposed on 2023-01-17) Given two ordered non-empty sets \((X,≤_ X)\) and \((Y,≤_ Y)\), and \(f:X→ Y\) as defined in 69.

If \(A⊆ X\) and \(m=\max A\) then \(f(m)=\max f(A)\); similarly for the minimums;
\((X,≤_ X)\) is totally ordered if and only if \((Y,≤_ Y)\) is;
\((X,≤_ X)\) is well ordered if and only if \((Y,≤_ Y)\) is.
Suppose that \((X,≤_ X)\) and \((Y,≤_ Y)\) are well ordered, let \(S_ X\) and respectively \(S_ Y\) be the functions ”successor”, 105, then we have that \(x\) is not the maximum of \(X\) if and only if \(f(x)\) is not the maximum of \(Y\), and in this case \(y=S_ X(x)\) if and only if \(f(y) = S_ Y(f(x))\).

E71

[21P]Given two totally ordered non-empty sets \((X,≤_ X)\) and \((Y,≤_ Y)\), suppose there exists a strictly increasing monotonic bijective function \(f:X→ Y\): show that then its inverse \(f^{-1}\) is strictly increasing, and consequently \((X,≤_ X)\) and \((Y,≤_ Y)\) are equiordinate. Hidden solution: [UNACCESSIBLE UUID ’21T’]

E71

[21Q]Find a simple example of two non-empty (partially) ordered sets \((X,≤_ X)\) and \((Y,≤_ Y)\), for which there exists a strictly increasing monotonic bijective function \(f:X→ Y\), whose inverse \(f^{-1}\) is not strictly increasing. Hidden solution: [UNACCESSIBLE UUID ’21S’]

Concatenation

Definition 72

[21W]Given two ordered sets \((X,≤_ X)\) and \((Y,≤_ Y)\), with \(X,Y\) disjoint, the concatenation of \(X\) with \(Y\) is obtained defining \(Z=X∪ Y\) and providing it with the ordering \(≤_ Z\) given by:

if \(z_ 1,z_ 2∈ X\) then \(z_ 1≤_ Z z_ 2\) if and only if \(z_ 1≤_ X z_ 2\);
if \(z_ 1,z_ 2∈ Y\) then \(z_ 1≤_ Z z_ 2\) if and only if \(z_ 1≤_ Y z_ 2\);
If \(z_ 1∈ X\) and \(z_ 2∈ Y\) then you always have \(z_ 1≤_ Z z_ 2\).

This operation is sometimes denoted by the notation \(Z = X⧺ Y\).

If the sets are not disjoint, we can replace them with disjoint sets defined by \(\tilde X=\{ 0\} × X\) and \(\tilde Y=\{ 1\} × Y\), then we may "copy" the respective orders, and finally we can perform the concatenation of \(\tilde X\) and \(\tilde Y\).

E72: [21X]Let \(k∈ℕ\) and let \(I=\{ 0,\ldots ,k\} \) with the usual ordering of \(ℕ\): show that the concatenation of \(I\) with \(ℕ\) has the same type of order as \(ℕ\); while the concatenation of \(ℕ\) with \(I\) does not have the same type of order.
E72: [21Y]Prerequisites:64,69.Let \((X_ 1,≤_ 1)\), \((X_ 2,≤_ 2)\) be two disjoint and partially ordered sets and with the same order type. Let \(I=\{ 1,2\} \) with the usual order; let \(Z=I× X_ 1\) equipped with lexicographical order; Let \(W\) be the concatenation of of \(X_ 1\) with \(X_ 2\): show that \(Z\) and \(W\) have the same type of order. Hidden solution: [UNACCESSIBLE UUID ’221’]
E72: [21Z]Let \(X_ 1,X_ 2\) be two disjoint and well-ordered sets. Let \(W\) be the concatenation of \(X_ 1\) with \(X_ 2\): show that it is well ordered.