Can we express every partial order with these two combinators?

232 Views Asked by At

Consider the following two combinators:

  • $\alpha<\beta$ meaning “all objects mentioned in $\alpha$ are smaller than the objects mentioned in $\beta$”
  • $\alpha\mid\beta$ meaning “all objects mentioned in $\alpha$ are unordered to the objects mentioned in $\beta$”

Some partial orders can be expressed as a single term with only the $<$ and $\mid$ combinators. For example, a partial order of four objects $a, b, c,$ and $d$ where $a<b,a<c,b<d,$ and $c<d$ can be represented with the term $a<(b\mid c)<d$.

Which partial orders of finite sets cannot be represented as a single term with only these two combinators? Can all partial orders of finite sets be represented this way?