Existence of a minimal set of linear order that is equivalent to the given partial order

124 Views Asked by At

Let $\{(P, \leq_{\alpha})\}_{\alpha \in A}$ be a set of linear order on set $P$, $(P,R)$ be a partial order on the same set $P$. We say that the former is equivalent to the later, iff: $$\forall a, b \in P[\forall \alpha \in A(a \leq_{\alpha}b) \leftrightarrow a R b]$$

Now given $(P, R)$, can we find a $\subset$-minimal set that is equivalent to it?

Added: It's already been known from this question that we can construct a (not necessarily minimal)set that is equivalent to $(P,R)$.

1

There are 1 best solutions below

1
On

By Dushnik-Miller theorem every partial order is the intersection of linear orders (E.Harzheim, Ordered Sets, Springer, 2005). The minimal number of such linear orders is called a dimension of poset.