4
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ For (2), note that the empty relation is not a partial order (since it looks like your text requires partial orders to be reflexive). So $\varnothing$ is not an element at all, and therefore in particular not a minimal element. $\endgroup$ – Henning Makholm Jan 13 '14 at 20:48
  • $\begingroup$ I understand, the empty relation fails to be partially ordered because is not reflexive since $X$ is not assume to be empty. Am I right? $\endgroup$ – Jose Antonio Jan 13 '14 at 21:09
  • $\begingroup$ So, for the minimal element... :S $\endgroup$ – Jose Antonio Jan 13 '14 at 21:10
  • 2
    $\begingroup$ The minimal element is $=$ because $=\in P$ and, for every $\le\in P$ we have $=\subseteq\le$, that is, $x=y\Rightarrow x\le y$ $\endgroup$ – bof Jan 14 '14 at 1:02
  • $\begingroup$ @bof: Thanks for your help is little difficult to me understand this topic, because is explained in the book in a few pages and is my first time learning partial ordering. For the above exercise I think that $x,y\in P$ should be $x,y \in X$. Am I right? Really sorry for being annoying but I'd like to understand the topic. $\endgroup$ – Jose Antonio Jan 14 '14 at 1:39
1
$\begingroup$

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 ...

$\endgroup$
  • $\begingroup$ The book use other definition different but equivalent to relation a function $f$ from $X\times X$ to a two valued set $\{0,1\}$ $\endgroup$ – Jose Antonio Jan 13 '14 at 21:13
  • $\begingroup$ @JoseAntonio: In which case $\preceq$ is just pointwise comparison of integers, and the upper bound might be the pointwise maximum... $\endgroup$ – Henning Makholm Jan 13 '14 at 21:15
  • $\begingroup$ Thanks for your help but to be completed honest none of terms in your last comment are explained in the book. So, it is a little complicated to me follow your argument, indeed is easier if we think in $\preceq$ as a subset of $X\times X$ and just show that their union is an upper bound. Sorry if I'm a little annoying but when thinks in the other model how the upper bound looks like? $\endgroup$ – Jose Antonio Jan 13 '14 at 22:43
  • $\begingroup$ @JoseAntonio: If your chain is $Q\subseteq P$ and the elements of $Q$ are functions, then the upper bound would be represented by $$g(x) = \max\{q(x)\mid q\in Q\}$$ or equivalently, $$g(x)=\begin{cases}1 & \text{if there is }q\in Q\text{ with }q(x)=1 \\ 0 & \text{otherwise}\end{cases}$$ $\endgroup$ – Henning Makholm Jan 13 '14 at 22:48
  • $\begingroup$ I'll do some changes in my answer. Thanks for your help just continue without know what the minimum of $P$ would be. $\endgroup$ – Jose Antonio Jan 14 '14 at 0:52
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.