| tags:[ math ]

# Partial preorders

Let us have a preorder ↗ that is unknown to us. Our ultimate goal is to discover it entirely but before that we have only partial information. For every pair A and B we can have

- $A \le B$,
- $A \not\le B$, or
- unknown.

When we know relations in both directions between two elements we may get

- $A \not\le B \land B \not\le A$ implies that $A$ and $B$ are incomparable,
- $A \le B \land B \not\le A$ implies $A < B$ (and vice-versa), or
- $A \le B \land B \le A$ implies $A = B$.

Preorders inherently encode more information than we need to describe them due to transitivity. Given $A \le B$ and $B \le C$ implies $A \le C$. Let us compute the relations of the preorder explicitly.

Starting with a partial preorder we can infer two rules to add explicit relations from transitivity. First is a straightforward application. \[ A \le B \land B \le C \implies A \le C \] Second is a contrapositive \[ A \not\le C \land A \le B \implies B \not\le C \text{ and } A \not\le C \land B \le C \implies A \not\le B. \]

To list all the relations created by the first inference we aim to have edges not only to direct children but to all descendants. By this logic, we can design an algorithm that for each element tranverses all descendants and adds respective relations. This is $\mathcal O(n^3)$.

Next, we can apply the second rule. We take every element $C$ one by one. Then collect all $A$ such that $A \not\le C$. Collect all predecessors $P$ of $A$s and descendants $D$ of $C$; note that these two sets cannot overlap as transitivity would imply $A \le C$. Now we add $p \not\le d$ for every $p \in P$ and $d \in D$ as otherwise we would have $A \le p \le d \le C$ (a contradiction with $A \not\le C$). Predecessors and descendants are already parents and children because we already added all transitive relations by the first rule. This is also implementable in $\mathcal O(n^3)$.