Union of Total Ordering with Lower Sections is Total Ordering

Theorem

Let $\struct {Y, \preceq}$ be a totally ordered set.

Let $X$ be the disjoint union of $Y$ with the set of lower sections of $Y$.

Define a relation $\preceq'$ on $X$ extending $\preceq$ by letting:

$y_1 \preceq' y_2 \iff y_1 \preceq y_2$

$y \preceq' L \iff y \in L$

$L_1 \preceq' L_2 \iff L_1 \subseteq L_2$

$L \preceq' y \iff y \in Y \setminus L$

Then $\preceq'$ is a total ordering.

Proof

First note that by Lower Sections in Totally Ordered Set form Chain:

$\subseteq$ is a total ordering on the set of lower sections.

Also note that by Complement of Lower Section is Upper Section, the complement of each $\preceq$-lower section is a $\preceq$-upper section.

Reflexivity

This follows immediately from the fact that $\preceq$ and $\subseteq$ are reflexive.

Thus $\preceq'$ is reflexive.

$\Box$

Transitivity

There are eight possibilities to consider.

If $y_1 \preceq' y_2$ and $y_2 \preceq' y_3$, then $y_1 \preceq' y_3$ because $\preceq$ is transitive.

If $L_1 \preceq' L_2$ and $L_2 \preceq' L_3$, then $L_1 \preceq' L_3$ because $\subseteq$ is transitive.

If $y_1 \preceq' y_2$ and $y_2 \preceq' L$, then:

$y_1 \preceq y_2$ and $y_2 \in L$

Since $L$ is a lower section in $Y$:

$y_1 \in L$

so:

$y_1 \preceq' L$

If $L \preceq' y_1$ and $y_1 \preceq' y_2$, then:

$y_1 \in Y \setminus L$ and $y_1 \preceq y_2$

Since $Y \setminus L$ is an upper section in $Y$:

$y_2 \in Y \setminus L$

so:

$L \preceq' y_2$

If $y \preceq' L_1$ and $L_1 \preceq' L_2$, then:

$y \in L_1$ and $L_1 \subseteq L_2$

By the definition of subset:

$y \in L_2$

so:

$y \preceq' L_2$

If $L_1 \preceq' L_2$ and $L_2 \preceq' y$, then:

$y \in Y \setminus L_2$ and $L_2 \supseteq L_1$

so:

$y \in Y \setminus L_1$

so:

$L_1 \preceq' y$

If $y_1 \preceq' L$ and $L \preceq' y_2$ then:

$y_1 \in L$ and $y_2 \in Y \setminus L$

Since $L$ is a lower section:

$y_2 \npreceq y_1$

Since $\preceq$ is a total ordering:

$y_1 \preceq y_2$

so:

$y_1 \preceq' y_2$

If $L_1 \preceq' y$ and $y \preceq' L_2$, then:

$y \in L_2$ but $y \notin L_1$

Thus:

$L_2 \nsubseteq L_1$

Since $\subseteq$ is a total ordering on the lower sections:

$L_1 \subseteq L_2$

so:

$L_1 \preceq' L_2$

Thus $\preceq'$ is transitive.

$\Box$

Antisymmetry

There are three cases.

If $y_1 \preceq' y_2$ and $y_2 \preceq' y_1$ then:

$y_1 \preceq y_2$ and $y_2 \preceq y_1$

Since $\preceq$ is antisymmetric:

$y_1 = y_2$

If $L_1 \preceq' L_2$ and $L_2 \preceq' L_1$ then:

$L_1 \subseteq L_2$ and $L_2 \subseteq L_1$

Since $\subseteq$ is antisymmetric:

$L_1 = L_2$

By the definition of $\preceq'$, it is impossible for $y \preceq' L$ and $L \preceq' y$, so the third case cannot occur.

Thus$\preceq'$ is antisymmetric.

$\Box$

Since $\preceq'$ is reflexive, transitive, and antisymmetric, it is an ordering.

$\preceq'$ is a total ordering of $X$ because:

$\preceq$ is a total ordering

the set of lower sections is a chain

and:

for any $y$ and $L$ either $y \in L$ or $y \in Y \setminus L$.

This article, or a section of it, needs explaining. In particular: Specify exactly why it follows from the above that $\preceq'$ is a total ordering You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Explain}} from the code.

$\blacksquare$