I have a transitive relation $\subset$ on a (finite and small) set S and a list of pairs $x_i\subset y_i.$ I would like to check if my list is complete in the sense that if $x\subset y$ then there are appropriate indices $i,j,\ldots,k$ such that $$x=x_i\subset y_i=x_j\subset y_j=\cdots=x_k\subset y_k=y.$$
To do this I will need to prove assertions of the form $x\not\subset y$ for many pairs $(x,y).$ Since this is hard (each one is a proof!) I'd like to do the least number possible. I'm looking for an algorithm to give such a minimal list (which should be unique).
My initial idea:
- With a new element $\top$, add $s\subset\top$ to the list for all $s\in S$.
- Take the transitive reduction of the list (if $a\subset b$ and $b\subset c$ are on the list, remove $a\subset c$ from the list).
- For each element $y\in S\cup\{\top\}$ find all $x_i$ such that $x_i\subset y$ is on the list.
- For each pair $i\ne j$ check that $x_i\not\subset x_j$.
The question: Does my algorithm work? That is, does it generate the (1) enough pairs to check such that, if all noninclusions are verified, the (original) list is complete, and (2) no smaller set of pairs could be checked to reach the first conclusion?
Bonus: Give a better algorithm (a correct one if mine is wrong, or a simpler/faster one if mine is right).