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


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,


  • $\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


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


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.