Proving covering relation for a product of ordered sets

covering-spacesdiscrete mathematicsorder-theory

Prove that if L and M are two ordered sets, then $(a_2, b_2)$ covers $(a_1, b_1)$ in $L × M$ iff $(a_1 = a_2$ and $b_2$ cover $b_1$ ) or ($a_2$ cover $a_1$ and $b_1 = b_2$).

Best Answer

For the direct implication, take $(a_1,b_1) \prec (a_2,b_2)$.
It follows that $a_1 \leq a_2$ and $b_1 \leq b_2$.
If $a_1 < a_2$ and $b_1 < b_2$, then $(a_1,b_1) < (a_2,b_1) < (a_2,b_2)$, a contradiction.
Hence $a_1 = a_2$ or $b_1 = b_2$.
If $a_1 = a_2$ and $b_1 < c < b_2$, then $(a_1,b_1) < (a_1,c) < (a_2,b_2)$, a contradiction. Hence $b_1 \prec b_2$.
Analogously if $b_1 = b_2$ then $a_1 \prec a_2$.

Now for the converse, if $b_1 \prec b_2$, and $(a,b_1) \leq (c,d) \leq (a,b_2)$, then $$a \leq c \leq a,$$ whence $a=c$, and $$b_1 \leq d \leq b_2,$$ whence $d=b_1$ or $d=b_2$. It follows that $(a,b_1)\prec(a,b_2)$.
Analogously, if $a_1 \prec a_2$, then $(a_1,b_1) \prec (a_2,b_2)$.

Related Question