Algebra for min/max bounds I am trying to model some set operations which are only well-defined if one is a subset of the other. The way the sets are constructed, I'll have a series of constraints of the form $x \subseteq y$, including the two sets in question and some other ones too. I won't know anything about individual element membership, so need to operate at the set level, and would like to be able to determine whether $a \subseteq b$ is implied by the given constraints.

This sounds like the sort of thing that's been studied before (e.g., for SMT solvers or linear programming), but I can't seem to hit the right keywords to search on. Are there known efficient representations/algorithms for this sort of problem?



Here's what I've roughly thought of doing:

type Set = Symbol;
type Bound = {kind: 'upper' | 'lower', arg: Set};
type Constraint = {kind: 'lt' | 'gt', arg: Bound};

const max = (b1: Bound, b2: Bound): Bound =&gt; ...;
const min = (b1: Bound, b2: Bound): Bound =&gt; ...;
const checker = (a: Constraint, b: Constraint): bool =&gt; ...;


My idea would be to build two Constraints, one for $a$ and one for $b$. $a$ would have a lt constraint and $b$ would have a gt constraint. I suspect Bound forms an algebra with max and min, which would allow me to put two Bounds in quasi-canonical form and break things down that way.

I'm not certain this will work, so before I spend several hours fleshing this out figured I'd ask if this had been solved before!
After posting the above I realized there was a possible solution with a different model. By viewing sets as nodes in a directed graph and edges as constraints, where $x \subseteq y$ would be translated to x -&gt; y, the final checker would simply look for a path between $a$ and $b$ in this graph. (Using DFS or BFS per this SO question).