The set of all the partial ordering of $X$ is a partially ordered set.

Question

I have trouble with the following exercise. I don't understand it. Also I think that $x,y\in P$ should be $x,y\in X$. Could someone give an insight of the exercise and also some hint of how to solve the third part, please? Thanks

Let $X$ be a set and let $P$ be the set of all the partial ordering of $X$. We say that one partial ordering $\le \in P$ is a coarser than another partial ordering $\le' \in P$ if for any $x,y\in P$ we have the implication $x\le y \Rightarrow x\le' y$. Let us write $\le \preceq\le' $ if $\le$ is a coarser than $\le ' $.

(1) Show that $\preceq$ turns $P$ into a partially ordered set.

We will show that is partial ordered relation. Clearly if $x\le y \rightarrow x\le y$, i.e., $\le \preceq \le$ which shows that is a reflexive relation. For anti-symmetric relation, suppose that $x\le y \rightarrow x\le' y$ and $x\le' y \rightarrow x\le y$, then we have $x\le y \leftrightarrow x\le' y$ for all $x,y$. Thus $\le = \le'$ since otherwise the logical equivalence doesn't hold. To conclude we have to show that $\preceq$ is a transitive relation. Suppose that $x\le y \rightarrow x\le' y$ and $x\le' y \rightarrow x\le'' y$, thus $x\le y\rightarrow x\le'' y $ which means that if $\le \preceq \le'$ and $\le' \preceq \le''$, so $\le \preceq \le''$, since $x,y$ are given.

(2) There is exactly one minimal element of $P$, what is it?

But I'm not sure of what the minimal element should be I thought it would be the empty relation but since $X$ is not assume to be empty, then the empty relation cannot be reflexive and in particular is not a partial ordering on $X$, i.e., $\le_\varnothing \notin P$

(3) Show that the maximal ordering of $P$ are precisely the total ordering. Using Zorn's lemma show that given any partial ordering $\le$ of $X$ there exists a total ordering $\le'$ such that $\le$ is coarser than $\le'$

We have to show that the set $P$ is non-empty. If $X= \varnothing$ then $\le_\varnothing \in P$ where $\le_\varnothing $ denote the empty relation. In case that $X\not= \varnothing$, then it contains some $x\in X$ and so we can define that $\forall y,z\in X$ we have $y\le_X z \iff (y\not= x \text{ and } y =z) \text{ or } z = x$.

The relation defined above is a partial ordering of $X$. Since is reflexive $y\le_X y$. If $y\le_X z$ and $z\le_X y$ then we have either $z=x$ or $y\not= x$ and $y=z$, If $z=x$, then $z\le_X y$ implies that $y=x$ and so $y=x=z$, in the case that $y\not=x$ and $y=z$ we're done. Now if $y\le_X z$ and $z\le_X w$, we have if $z=x$ so $w=z=x$ and clearly $z\le_X w$, otherwise $y\not= x$ and $y=z$, so $z\not= x$ and $z=w$, i.e., $x\le_X w$. Hence $\le_X \in P$

In either case $P\not= \varnothing$. Now let $\mathcal{C}$ be a totally ordered subset of $P$ we have to show that there is an upper bound. Let $\le_\mathcal{C}$ be defined as follows, we say that for $x,y\in X, \;x\le_\mathcal{C} y \iff \exists \le'\in \mathcal{C}$ such that $x\le' y $.

We have to show $\le_\mathcal{C} $ is well-defined. Suppose $\le, \le' \in \mathcal{C}$ and there exists $x,y \in X$ such that $x\le y$ and $y\le' x$ but $y\not= x$. Since both are in $\mathcal{C}$ either $\le \preceq \le'$ or $\le' \preceq \le$. Without loss of generality suppose that $\le \preceq \le'$, then $x\le y$ implies $x\le' y$ and since $x\not= y$ so $x<' y$ which contradicts our assumption that $y<' x$. Hence $\le_\mathcal{C} $ is well-defined. Also is not difficult to show that is a partial ordering of $X$.

Clearly $\le_\mathcal{C}$ is an upper bound for $\mathcal{C}$ because whenever $x\le' y$ for $\le' \in \mathcal{C}$ would imply $x\le_\mathcal{C} y$, which means $\le' \preceq \le_\mathcal{C}$. Thus by Zorn's lemma $X$ contains at least one maximal element which we call $\le_P$. We claim that $\le_P$ is a total ordering of $X$. Suppose for the sake of contradiction that $\le_P$ is not a total ordering of $X$. Thus there must be a pair $x,y\in X$ for which neither $x\not\le_p y$ nor $y\not\le_p x$. Thus we can define $\le = \le_p$ for all $X\backslash \{x,y\}$ and we set $x\le y$. Thus is a partial ordering of $X$, i.e., $\le \in P$ and also $\le_p \preceq \le$, note that the implication $x\le_p y \rightarrow x\le y$ is vacuously true, which is a contradiction. Hence $\le_p$ is a total ordering of $X$.

Am I right? Other question: What would be the minimum element of $P$?

Answer 1

For the third part, refer to the hint already in the exercise: "Using Zorn's lemma ...".

The relevant partial order is obviously $(P,{\preceq})$, in which case the conclusion of Zorn's lemma is exactly what you're asked to prove. So all you have to do is show that the premise of the Lemma holds for $(P,{\preceq})$. Note that $\preceq$ is actually just the subset relation when each of the relations is viewed as a subset of $X\times X$. So a natural candidate for an upper bound for a chain of relations would be their union ...

Answer 2

Here is what I have so far. What do you think the following is correct or there is one mistake that I cannot see. Thanks in advance.

Let $X$ be a set and let $P$ be the set of all the partial ordering of $X$. We say that one partial ordering $\le \in P$ is a coarser than another partial ordering $\le' \in P$ if for any $x,y\in X$ we have the implication $x\le y \Rightarrow x\le' y$. Let us write $\le \preceq\le' $ if $\le$ is a coarser than $\le ' $.

(1) Show that $\preceq$ turns $P$ into a partially ordered set.

We will show that is partial ordered relation. Clearly if $x\le y \rightarrow x\le y$, i.e., $\le \preceq \le$ which shows that is a reflexive relation. For anti-symmetric relation, suppose that $x\le y \rightarrow x\le' y$ and $x\le' y \rightarrow x\le y$, then we have $x\le y \leftrightarrow x\le' y$. Since $x,y$ was arbitrary elements in $X$ for which $x\le y$ and $x\le'y$ are both true thus $\le = \le'$ since otherwise the logical equivalence doesn't hold. To conclude, we'd like to show $\preceq$ is a transitive relation. Suppose $\le \preceq \le'$ and $\le' \preceq \le''$, in particular $x\le y \rightarrow x\le' y$ and $x\le' y \rightarrow x\le'' y$, thus $x\le y\rightarrow x\le'' y $ which means that $\le \preceq \le''$.

(2) There is exactly one minimal element of $P$, what is it?

If we have that $X= \varnothing$, we claim that just we have $\le_\varnothing \in P$, i.e.,$P= \{\le_\varnothing \}$. Suppose $\le \in P$, then is vacuously true that $\forall x,y\in X$ we have $x \le y \leftrightarrow x\le_\varnothing y$. Thus $\le$ is nothing more than the empty relation.

If $X\not= \varnothing$, we claim that $=\in P$ and also is the minimum element of $P$. Clearly $=$ is a partial ordering of $X$. Then we only check that is a minimal element. Since $\forall x,y\in X$ we have $x = y \rightarrow x\le y$ so $=\preceq \le$ for a given $\le \in P$. In any case the uniqueness follows immediately by anti-symmetry.

(3) Show that the maximal ordering of $P$ are precisely the total ordering.

Suppose for the sake of contradiction that there exists a maximal in $P$ which is not a total ordering of $X$. Then $\exists x',y'\in X$ for which neither $x'\le y'$ nor $y'\le x'$. Let define $\le' $ as follows: $\le' = \le$ for all $x,y\in X\backslash \{ x',y'\}$ such that $x\le y$, and we define some arbitrary order on $x',y'$, for the sake of the concreteness let define $x'\le' y'$. It is not difficult to show that $\le'$ is a partial ordering of $X$ and also that $\forall x,y\in X$ we have $x\le y \rightarrow x\le' y$, the particular case when $x=x'$ and $y=y'$ the implication is vacuously true. It follows that $\le \preceq \le'$ and also $\le \not= \le'$ which contradicts that $\le$ is a maximal element.

(4) Using Zorn's lemma show that given any partial ordering $\le$ of $X$ there exists a total ordering $\le'$ such that $\le$ is coarser than $\le'$.

Let $\le \in P$ be given and define the subclass $\mathcal{C}$ consisting of those ordering that are coarser than $\le$ and those ordering for which $\le$ is courser than, in other words $\le' \in \mathcal{C}\iff \le'\preceq \le $ or $\le\preceq \le' $.

The subclass is clearly non-empty since $\le \in \mathcal{C}$. Also each chain of $\mathcal{C}$ has an upper bound. Let $\mathcal{F}$ be a totally ordered subset of $\mathcal{C}$, and define $\le_\mathcal{F}$ as follows, we say $x\le_\mathcal{F} y \iff \exists \le' \in \mathcal{C}$ such that $x\le' y$. We have to show $\le_\mathcal{F} $ is well-defined, in other words that there not exists ambiguity. Suppose it were the case that $\le', \le'' \in \mathcal{F}$ and there exists $x,y \in X$ such that $x\le' y$ and $y\le'' x$ but $y\not= x$. Since both are in $\mathcal{F}$ which is totally ordered either $\le' \preceq \le''$ or $\le'' \preceq \le'$. Without loss of generality suppose $\le' \preceq \le''$, then $x\le' y$ implies $x\le'' y$ and since $x\not= y$ so $x<'' y$ which contradicts our assumption that $y<'' x$. Hence $\le_\mathcal{F} $ is well-defined. Also is not difficult to show that is a partial ordering of $X$.

Hence we can use Zorn's lemma and conclude that there is a maximal element on $\mathcal{C}$. Let call it $\le_\mathcal{C}$. Clearly is a total ordering of $X$, since otherwise contradicts (3).

To conclude we have to show that $\forall x,y \in X$ such that $x \le y \rightarrow x\le_\mathcal{C} y$, in other words that $\le$ is coarser than $\le_\mathcal{C} $. Since $\le_\mathcal{C} \in \mathcal{C}$, thus either $\le_\mathcal{C} \preceq \le $ or $\le\preceq \le_\mathcal{C} $, clearly the first alternative leads a contradiction and therefore $\le\preceq \le_\mathcal{C} $ as desired.