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$).)