Ordered Set - Chains

Question

Let $P$ be a poset. Let $\mathcal{C}_{a,b}$ be a chain from $a$ to $b$ and let $\mathcal{D}_{b,c}$ be a chain from $b$ to $c$.

(a) Show that $\mathcal{C}_{a,b} \cup \mathcal{D}_{b,c}$ is a chain from $a$ to $c$.

(b) Show that if $\mathcal{C}_{a,b}$ and $\mathcal{D}_{b,c}$ are maximal chains, then so is $\mathcal{C}_{a,b} \cup \mathcal{D}_{b,c}$.

A nonempty subset $S$ of $P$ is a chain in $P$ if $S$ is totally ordered by $\leq$.

A maximal chain from $a$ to $b$ is a chain from $a$ to $b$ that is not contained in a larger (in the sense of set inclusion) chain from $a$ to $b$.

Part (a) was thinking about considering $a<b $ and $b<c$, then $a<c$, and therefore $\mathcal{C}_{a,b} \cup \mathcal{D}_{b,c}$ is a chain from $a$ to $c$, will this type of reasoning be correct?.

Somebody help me please.

Answer 1

Let $E=\mathcal{C}_{a,b} \cup \mathcal{D}_{b,c}$.

To show that $E$ is a chain from $a$ to $c$, we need to show that

• $E$ is a chain (i.e., $E$ is totally ordered).$\\[4pt]$
• $E$ has $a$ as a bottom element.$\\[4pt]$
• $E$ has $c$ as a top element.

To show that $E$ is a chain, we need to show that for all $x,y\in E$, we have $x\le y$ or $y\le x$.

Thus, let $x,y$ in $E$.

Consider cases . . .

• If $x,y\in \mathcal{C}_{a,b}$, then since $\mathcal{C}_{a,b}$ is a chain, we have $x\le y$ or $y\le x$.$\\[4pt]$
• If $x,y\in \mathcal{D}_{b,c}$, then since $\mathcal{D}_{b,c}$ is a chain, we have $x\le y$ or $y\le x$.$\\[4pt]$
• If $x\in \mathcal{C}_{a,b}$ and $y\in \mathcal{D}_{b,c}$, then from $x\in \mathcal{C}_{a,b}$, we get $x\le b$, and from $y\in \mathcal{D}_{b,c}$, we get $b\le y$, hence $x\le b\le y$, so $x\le y$.$\\[4pt]$
• If $y\in \mathcal{C}_{a,b}$ and $x\in \mathcal{D}_{b,c}$, then from $y\in \mathcal{C}_{a,b}$, we get $y\le b$, and from $x\in \mathcal{D}_{b,c}$, we get $b\le x$, hence $y\le b\le x$, so $y\le x$.$\\[4pt]$

In all cases, we have $x\le y$ or $y\le x$, hence $E$ is a chain.

To show that $a$ is a bottom element of $E$, we need to show

• $a\in E$.$\\[4pt]$
• $a\le x$ for all $x\in E$.

Since $a\in \mathcal{C}_{a,b}$, we have $a\in E$.

Next let $x\in E$.

• If $x\in \mathcal{C}_{a,b}$, then $a\le x$.$\\[4pt]$
• If $x\in \mathcal{D}_{b,c}$, then $b\le x$, hence $a\le b\le x$, so $a\le x$.

In both cases we have $a\le x$, hence $a$ is a bottom element of $E$.

By analogous reasoning (I'll leave the steps to you), $c$ is a top element of $E$.

It follows that $E$ is a chain from $a$ to $c$.

Next suppose $\mathcal{C}_{a,b}$ is a maximal chain from $a$ to $b$, and $\mathcal{D}_{b,c}$ is a maximal chain from $b$ to $c$.

We want to show that $E$ is a maximal chain from $a$ to $c$.

We've already shown that $E$ is a chain from $a$ to $c$.

Let $F$ be a chain from $a$ to $c$ such that $E\subseteq F$.

To show that $E$ is a maximal chain from $a$ to $c$, we want to show $F=E$.

We already have the inclusion $E\subseteq F$.

To show the reverse inclusion, let $f\in F$.

Since $F$ is a chain from $a$ to $c$, we have $a \le f\le c$.

Since $E\subseteq F$, we have $b\in F$, hence, since $F$ is a chain, either $f\le b$ or $b\le f$.

Thus either $a\le f\le b$ or $b\le f\le c$.

First suppose $a\le f\le b$.

Let $G=C_{a,b}\cup \{f\}$.

Since $C_{a,b}\subseteq E\subseteq F$, and $f\in F$, we get $G\subseteq F$, hence $G$ is a chain.

Note that $G$ has bottom element $a$ and top element $b$, hence $G$ is a chain from $a$ to $b$.

But $C_{a,b}\subseteq G$, hence, since $C_{a,b}$ is a maximal chain from $a$ to $b$, it follows that $G=C_{a,b}$.

Then from $f\in G$, we get $f\in C_{a,b}$, hence $f\in E$.

Thus for the case $a\le f\le b$, we have $F\subseteq E$.

The argument for the case $b\le f\le c$ is analogous, and I'll let you work out the details.

Thus $F\subseteq E$, hence, since we have both inclusions, we get $F=E$.

It follows that $E$ is a maximal chain from $a$ to $c$, as was to be shown.