EF Total orders

Section 19.4 Total orders

comparable elements: 🔗
elements $a, b$ in a partially ordered set such that either $a ⪯ b$ or $b ⪯ a$
incomparable elements: 🔗
elements that are not comparable

Example 19.4.1. Comparable and incomparable subsets.

Let

U

represent some universal set containing at least two elements, and consider

P (U)

partially ordered by

\subseteq .

🔗
Both the empty set $\emptyset$ and the universal set $U$ are comparable to every element of $P (U) .$
🔗
For $x, y \in U$ with $x \neq y,$ then ${x}, {y}$ are incomparable.
🔗
In fact, for every non-empty, proper subset $A ⫋ U$ there exists a subset $B \subseteq U$ which is incomparable to $A :$ take $B = A^{c} .$

🔗

However, do not let the second two points above lead you astray: it is not necessary for subsets to be disjoint in order to be incomparable. As long as each of a pair of subsets contains an element that the other doesn’t, then the two will be incomparable by

\subseteq .

🔗

total order: 🔗
a partial order on a set such that every pair of elements is comparable
totally ordered set: 🔗
a set equipped with a total order

🔗

Example 19.4.2. Subset order is not total.

🔗

For universal set

U,

order

\subseteq

P (U)

is not total except when

| U | \leq 1 .

🔗

Example 19.4.3. Usual order of numbers is total.

🔗

Our usual order for numbers,

\leq,

is a total order on

N,

Z,

Q,

or on

R .

🔗

Example 19.4.4. Total order on alphabet induces total order on words.

🔗

⪯

is a total order on an alphabet

Σ,

then the lexicographic order

⪯^{*}

described in Example 19.2.7 is a total order on the set of words

Σ^{*} .

🔗

Example 19.4.5. Pulling back a total order through an injection.

🔗

B

is totally ordered and we use an injection

f : A ↪ B

to “pull back” the order on

B

to an order on

A

(see Example 19.2.11), then the newly created order on

A

will also be total.

🔗

Example 19.4.6. Countable can be totally ordered.

🔗

A

is a countably infinite set, then there exists a bijection

f : N \to A .

We can use the inverse

f^{- 1} : A \to N

to “pull back” the usual total order

\leq

N

to a total order on

A

(see Example 19.4.5).

🔗

Another point of view on this is that our bijection

f

creates an infinite sequence

a_{0}, a_{1}, a_{2}, \dots,

🔗

where each element of

A

appears exactly once. This sequence can be turned into a specification of the total order on

A

by just turning the commas into

\leq

symbols:

a_{0} \leq a_{1} \leq a_{2} \leq \dots .

🔗

Remark 19.4.7.

🔗

The pattern of Example 19.4.6 becomes even simpler when we apply it to a finite set: a total order on a finite set is no different than an ordering of the set elements into a list, as