Linearly extend an induced subposet

Question

Suppose $P$ is a finite poset with partial order $\le_P$ and $Q$ an induced subposet, its partial order being ${\le_Q} = {\le_P}\cap Q^2$. Suppose we linearly extend $\le_Q$ to a linear order $\preceq_Q$ on $Q$.

Is the transitive closure of ${\le_P} \cup {\preceq_Q}$ as a relation on $P$ anti-symmetric? That is, can we linearly order induced subposets of $P$ and obtain an extension of $\le_P$?

Answer 1

Let $\preceq$ be the transitive closure of $\le_P\cup\preceq_Q$. Suppose that $x,y\in P$ are such that $x\preceq y\preceq x$, but $x\ne y$.

Since $x\preceq y$, there are $u_0=x,u_1,\ldots,u_n=y$ in $P$ such that either

• $\langle u_{2k},u_{2k+1}\rangle\in{\le_P}$ and $\langle u_{2k+1},u_{2k+2}\rangle\in(\preceq_Q\setminus\le_P)$ for all $k$ for which the pairs are defined,

or

• $\langle u_{2k},u_{2k+1}\rangle\in(\preceq_Q\setminus\le_P)$ and $\langle u_{2k+1},u_{2k+2}\rangle\in{\le_P}$ for all $k$ for which the pairs are defined.

Since $y\preceq x$, there must be a similar chain from $y$ to $x$. It may take a little thought to see it, but this implies that there are $u_0,\ldots,u_n,v_0,\ldots,v_n\in P$ for some $n\ge 0$ such that

• $\langle u_k,v_k\rangle\in{\le_P}$ for $k=0,\ldots,n$,
• $\langle v_k,u_{k+1}\rangle\in(\preceq_Q\setminus\le_P)$ for $k=0,\ldots,n-1$, and
• $v_n=u_0$.

Let $S=\{u_k:0\le k\le n\}\cup\{v_k:0\le k\le n\}$. Then $S\subseteq Q$, and

$${\le_S}=\{\langle u_k,v_k\rangle:k=0,\ldots,n\}={\le_Q}\cap(S\times S)\subseteq{\preceq_Q}\cap(S\times S)\;.$$

But clearly

$$\{\langle v_k,u_{k+1}\rangle:0\le k<n\}\subseteq{\preceq_Q}$$

as well, so

$$u_0\preceq_Qv_0\preceq_Qu_1\preceq_Qv_1\preceq_Q\ldots\preceq_Qu_n\preceq_Qv_n=u_0\;,$$

which is absurd, since $\preceq_Q$ is a linear order. It follows that $\preceq$ is antisymmetric.