Prove that $\succeq = \bigcap L \left(\succeq \right)$ - understanding elementary order theory

Question

Dear reader of this post,

I am working on a elementary question on order relations. I would be very glad to receive some guidance since I think understanding this question is important for making further progress with order relations. The question is as follows: Let $\left(X,\succeq \right) $ be a preordered set ($\succeq $ being a transitive and reflexive relation) , and define $L \left( \succeq \right)$ as the set of all complete preoders that extend $\succeq$. Prove that $\succeq = \bigcap L \left(\succeq \right)$.

With the two replies by Brian and Hagen (thank you!), I'd like to proceed proving the claim. I am not yet familiar about the usual procedure for answering own questions so I hope I do not violate the etiquette. I would be glad to receive some remarks about my prove. I relegated previous thoughts to the end.

To make use of Szpilrajn's theorem, I will at first create a partially ordered set (poset) out of the preordered set and then extent this poset to a linearly ordered set. ( @ Brian: I expect that the technical details you mention in your post refer to the different elements which can are equivalent in the preordered set but not in the poset. Is this correct?) Let $ \sim $ denote the symmetric part of $\succeq$. Then $ \left( X/~,\succeq^{\star} \right)$ is a poset where $\succeq^{\star} $ is defined on $X/ \sim $ by $[x]_{\sim} \succeq^{\star} [y]_{\sim} \ \text{iff} \ x \succeq y$.

I will no show that $\succeq^{\star} = \bigcap L(\succeq^{\star} ) $. I know that every extension must satisfy $\succeq^{\star} \subseteq \unrhd$. So for each new poset $[x]_{\sim} \unrhd [y]_{\sim} \ \text{iff} \ [x]_{\sim} \succeq^{\star} [y]_{\sim} $ holds. For all other equivalence classes $[h]_{\sim},[g]_{\sim}$ for which $ [h]_{\sim} \not \succeq^{\star} [g]_{\sim}, \ \text{and} \ [g]~ \not \succeq^{\star} [h]~ $ the extended poset differ between whether $[h]_{\sim} \unrhd [g]_{\sim} $ or the other way round. Thus, the intersection of the different extension cannot include any relation which is not stated in the original poset already and $\succeq^{\star} = \bigcap L(\succeq^{\star} ) $.

Can someone give me some hints about the mistakes my prove contains?

Previous thoughts I know that $\succeq \subseteq \unrhd$ ($\unrhd$ being the extension) so the complete preorder is a larger set than the original preoder. I imagine that extensions generate relations among the previously unrelated elements. For $\succeq = \bigcap L \left(\succeq \right)$ to hold, I know that the extension generates at least one complete preorder. To prove the claims, I expect to show that every relationship contained in the original preoder is an element of each extended preorder. Hence, I basically need to show that both sets (the original preorder and the intersection of the new complete preorders) contain exactly the same relationships.

I would like to ask the following questions in particular:

• I do not understand how one can generate different complete preoders. Could I name them $L_i \left(\succeq \right)$? (Or would $L \left(\succeq_i \right)$ be more precise ?) In what respect do the complete preorders differ?
• I have no idea how to show that both sets contain the same relations. Suppose that $x,y \in X$, could one then have $(x,y) \in \succeq $?

I am looking forward for your replies.

Answer 1

I suggest working first with partial orders rather than preorders; complete extensions are then linear orders. The main ideas are the same, but there are slightly fewer technical details to worry about. Once you’ve got the result for partial orders, generalizing it to preorders shouldn’t be too hard.

First, here’s a simple example. Let $A=\{0,1,1',2\}$, and let $\preceq$ be the partial order on $A$ whose Hasse diagram is this:

                 2  
                / \  
               1   1'  
                \ /  
                 0

Then $\preceq$ can be extended to precisely two linear orders on $A$:

$$0<_11<_11'<_12,\qquad\text{and}\qquad 0<_21'<_21<_22\;.$$

I’ll leave it to you to check that $\le_1\cap\le_2=\preceq$.

Since $\succeq$ is a subset of every order in $L(\succeq)$, it’s clear that $\succeq\subseteq\bigcap L(\succeq)$. What you have to show is that if $x,y\in X$, $x\nsucceq y$, and $y\nsucceq x$, then there are linear orders $\ge_1$ and $\ge_2$ in $L(\succeq)$ such that $x\ge_1 y$ and $y\ge_2 x$, since then neither $\langle x,y\rangle$ nor $\langle y,x\rangle$ can belong to $\bigcap L(\succeq)$.

The example at the beginning should help you start thinking about how to construct such linear extensions $\ge_1$ and $\ge_2$. You may want to consider the sets $\{z\in A\setminus\{x,y\}:x\succeq z\text{ or }y\succeq z\}$, $\{z\in A\setminus\{x,y\}:z\succeq x\text{ or }z\succeq y\}$, and $\{z\in A\setminus\{x,y\}:z\nsucceq x\nsucceq z\text{ and }z\nsucceq y\nsucceq z\}$.

Answer 2

1. As $L(\succeq)$ denotes the set of complete preorders extending $\succeq$, you should not use $L_i(\succeq)$ or $L(\succeq_i)$ to denote extensions of $\succeq$. Rather, I suggest $\succeq_i$. A preorder on $\{a,b,c\}$ might be given by $a\succeq b$ and $b\succeq c$ (plus reflexivity). It is not specified whether $b\succeq c$ or $c\succeq b$. You obtain a total preorder by adding (at least) one of these two relations. So different completions differ in how they compare elements that were not comparable before.

2. From ${\succeq} \subseteq {\succeq_i}$ for every completion ${\succeq_i}\in L(\succeq)$, you already have ${\succeq} \subseteq \bigcap L(\succeq)$. Remains to show that the intersection is not bigger. So you need to show for every $x,y$ with $x\not\succeq y$, there exists a completion $\unrhd$ with $x\not \unrhd y$. By completeness, you will necessarily have $y\unrhd x$, but that is of course not enough