# Existence of minimum partial order satisfying given conditions

In this question I formulated the concept of system of precedences which can be described either axiomatically or as a concrete set of sets.

Meanwhile I found that system of precedences (equivalent to the definition in that question) can be defined as as a pair of:

• a nonstrict partial order $\subseteq_U$;
• a strict partial order $<_U$ conforming to the inequality $\mathord{\not>}_U \supseteq (\mathord\supseteq_U\circ \mathord{\not>}_U\circ\mathord\subseteq_U)$ where $\circ$ is composition of relations.

Now having given nonstrict partial order $\subseteq_U$ and a strict partial order $>_0$ I want to check if there exists the smallest partial order $>_U$ such that $\mathord{>_U}\supseteq\mathord{>_0}$ and $(\subseteq_U,>_U)$ is a system of precedences.

I asked an algorithm to check this in CS.SE question but now I am asking a different question: Does the smallest partial order $>_U$ always exist? (Taneli Huuskonen pointed in a comment that there may be no system of precedences with given $\subseteq_U$ and $\mathord{>_U}\supseteq\mathord{>_0}$. Let us assume that such a system of precendences exists.) Well, finding an algorithm to find it would resolve this math.SE question too, but while we do not know the algorithm, this is a different (probably easier) question.

I am considered to make a numeric experiment to find a counterexample against existence of smallest $>_U$. For this I even installed SageMath, but don't know how to use it for this particular problem (SO question).

Note: It is quite easy to check that if we drop the requirement for $>_U$ to be a partial order (but allow any binary relation) the existence of biggest $\not>_U$ (and thus smallest $>_U$) becomes almost obvious.

Remark: I am afraid that finding a reasonably fast algorithm (https://cs.stackexchange.com/q/85951/39512) may take me several years. I am going to work on this problem nevertheless until I find a solution. Your help is appreciated. (Well, I also consider that I need to think how to change the question if it does not always have a definite solution (minimum $>_U$).)

• It looks like you may end up having contradictory requirements for the system of precedences. – Taneli Huuskonen Jan 11 '18 at 22:40
• @TaneliHuuskonen In no way. Existence of a system of precedences is trivial: Just get any set $U$ with the usual $\subseteq$ relation on it and $>_U$ being the empty relation. – porton Jan 11 '18 at 22:43
• I was thinking of the case when $>_0$ is nonempty. – Taneli Huuskonen Jan 12 '18 at 7:44
• @TaneliHuuskonen Every set of nonempty subsets of some (fixed) poset produces a system of precedences. It is yet unknown however if the smallest system conforming to the conditions of the question exist (this is the point of the question) – porton Jan 12 '18 at 20:11
• You misunderstood me. I was just pointing out that if, for instance, there are elements $a,b$ such that $a\subseteq_{U} b$ and $a >_0 b$, then there is no $>_U$ satisfying the conditions given in your question. Anyway, if one exists, then there is a unique smallest one. – Taneli Huuskonen Jan 12 '18 at 21:15

## 1 Answer

There is always a unique smallest relation $>'$ such that

1. ${>_0}\subseteq {>'}$;
2. $>'$ is transitive;
3. for all $a,b,a',b'\in U$ such that $a\subseteq_U a'$, $b\subseteq_U b'$, and $a' >' b'$, it holds that $a >' b$.

There is an easy but inefficient algorithm for finding $>'$: start from $>_0$ and iterate adding any pairs that must be there by conditions (2) and (3), until there is nothing more to add. Now, if $>'$ is irreflexive, then it is also asymmetric because it's transitive, and we're done: set ${>_U} := {>'}$. Otherwise, no extension of $>'$ is irreflexive, so there is no solution.

Edited to add: I haven't checked this carefully, but I sketched a proof that $>'$ is actually the transitive closure of ${\supseteq_U} \circ {>_0} \circ {\subseteq_U}$. If that is correct, you may want to look at efficient algorithms to calculate transitive closures and compositions.

• Shouldn't we also check if the found $>'$ to be asymmetric? – porton Jan 15 '18 at 22:18
• The condition (3) may be replaced with: $(a,b)\in(\supseteq_U\circ>'\circ\subseteq_U) \implies a>'b$ – porton Jan 15 '18 at 22:40
• If $a >' b$ and $b >'a$, then $a>'a$ by transitivity, so your suggested edit is technically correct but unnecessary. – Taneli Huuskonen Jan 16 '18 at 9:42