Necessary and sufficient condition for existence of a partial order

Question

I'm trying to find a necessary and sufficient condition for the existence of a partial order such that an arbitrary relation on a set X is a subset of the partial order.

So far all I have is that since a partial order is reflexive, transitive, and symmetric, the partial order must only have elements related to themselves in order for any relation to be a subset of it, since the relation in question may be symmetric. Any help would be appreciated.

Answer 1

Assume R is a relation for S.

A necessary condition for R to be a subset of an order for S is:
there does not exist distinct x,y with xRy and yRx.

A sufficient condition for R to be a subset of an order for S is;
there does not exist distinct x,y with xTy and yTx,
where T is the reflexive and transitive closure of R.

Answer 2

$R$ is a subset of a partial order if and only if for all lists $x_1,x_2,\dots,x_n$ of elements in $R$, we have $$ x_1\def\R{\,R\,}\R x_2\R x_3\R\dots \R x_n\R x_1\implies x_1=x_2=\dots=x_n $$

In graph theory terms, $R$ must be acyclic. This is a generalization of $R$ being anti-symmetric, which says that $x_1\R x_2\R x_1\implies x_1=x_2$.

If $R$ is a subset of a partial order $\le$, then $x_1\def\R{\,R\,}\R x_2\R x_3\R\dots \R x_n\R x_1$ would imply $x_1\le x_2\le \dots\le x_n\le x_1$, which combined with transitivity and anti-symmetry implies all $x_i$ are equal.

Conversely, if that condition holds, then let $\le$ be the transitive closure of $R$, where $x\le y$ if there is a chain $x\R z_1\R z_2 \R\dots\R z_k \R y$. Then $\le$ is easily shown to be transitive (connect the chains), and the given condition allows you to show anti-symmetry.