How to define an total order on $P$?

Question

Consider the finite set $X = \{a_1, \cdots, a_n\}$ where $a_i \in \mathbb{R}$ for all $1 \leq i \leq n$ and let $P = \wp(X) - \{\emptyset\}$. An exercise in my book of discrete mathematics has a question to define a total order $\sqsubseteq$ on $P$, which in the particular case for $Y, Z \in P$ when Y and Z have a cardinality equal to 1, the order is the same to the usual order $\leq$ on $\mathbb{R}$. How is the definition of $\sqsubseteq$?

Answer 1

There are several ways to order $P$. A good way to start could be to partition $P$ into more manageable parts, put these parts into a total order, and then totally order each part internally. This would make a total order on all of $P$ where two elements are compared first by checking whether they are from different parts, and if not compare them within the part.

If totally ordering each part isn't obvious, the process can be repeated ad nauseam. You can also use different rules for each "level" of partitioning.

For instance, you could make a partition of $P$ depending on the largest element of the sets. Or you could partition depending on the number of elements.

Answer 2

There is no harm in assuming that the members of $X$ have been labelled so that $a_1<a_2<\ldots<a_n$. The exercise then tells you that $\sqsubseteq$ must be defined so that $\{a_1\}\sqsubseteq\{a_2\}\sqsubseteq\ldots\sqsubseteq\{a_n\}$. After that you have complete freedom so long as you end up with a total order: these $n$ sets can be at the ‘bottom’ of your order, at the ‘top’, or scattered through it.

Arthur’s answer gives one approach that can be implemented to produce a great variety of total orders compatible with the requirements of the exercise. It’s not the only way to approach the problem, but it probably is the most natural. One less natural but rather elegant way is to associate to each $S\in P$ a string $b_n^{(S)}b_{n-1}^{(S)}\ldots b_1^{(S)}$ of $n$ binary digits according to the following rule:

$$b_k^{(S)}=\begin{cases}1,&\text{if }a_k\in S\\ 0,&\text{if }a_k\notin S\;. \end{cases}$$

For instance, if $n=3$ the $\{a_1\}$ would be assigned the string $001$, the set $\{a_2,a_3\}$ would be assigned the string $110$, and so on. Now interpret these strings as binary numbers; in this example the number for $\{a_1\}$ is $1$, and the number for $a_n$ is $6$. This is clearly a total order, since it is just the ordinary numerical order on a finite set of positive integers. I will leave it to you to verify that it meets the requirement on the one-element sets.