0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ It looks like you may end up having contradictory requirements for the system of precedences. $\endgroup$ – Taneli Huuskonen Jan 11 '18 at 22:40
  • $\begingroup$ @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. $\endgroup$ – porton Jan 11 '18 at 22:43
  • $\begingroup$ I was thinking of the case when $>_0$ is nonempty. $\endgroup$ – Taneli Huuskonen Jan 12 '18 at 7:44
  • $\begingroup$ @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) $\endgroup$ – porton Jan 12 '18 at 20:11
  • $\begingroup$ 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. $\endgroup$ – Taneli Huuskonen Jan 12 '18 at 21:15
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.