I guessed that the weak incompleteness result must be standard. After some searching (thanks Claude), we have the following: Suppose we have a strict partial order <. Weak incompleteness is equivalent to saying that the incomparable-or-equal-to[1] (henceforth incompeq) [2] relation is transitive. Transitivity means that If A is incompeq with B and B is incompeq with A’ then A must be incompeq with A’, and this is clearly equivalent (visually: if you can’t draw two of the arrows in the triangle A B C, then drawing the third would be a strong incompleteness).
A strict partial order whose incompeq is transitive is called a strict weak order. This means that incompeq is an equivalence relation, so you can look at the equivalence classes, and you then have a total order on them with the same proof as in the post.
Unfortunately I can’t see a neat insight that this digression gives us, besides that weak incomplete just means incompeq is transitive.
Further links that don’t seem that useful: the wiki page on comparability graphs gives a characterization for what sorts of graphs are the graphs of comparability of a partial order. The page on indifference graphs gives a bunch of characterizations of graphs where each node has a “utility” and there’s an edge between two nodes when the difference is smaller than 1. Maybe someone else will win a mathematical theorem hunting lottery.
Yes, the name sucks. I didn’t want to conflate “indifferent” from “uncomparable”. ↩︎
Wikipedia uses “incomparable” to mean “neither x < y nor y < x”, but to me “incomparable” shouldn’t include the case x=y. ↩︎
I guessed that the weak incompleteness result must be standard. After some searching (thanks Claude), we have the following: Suppose we have a strict partial order <. Weak incompleteness is equivalent to saying that the incomparable-or-equal-to[1] (henceforth incompeq) [2] relation is transitive. Transitivity means that If A is incompeq with B and B is incompeq with A’ then A must be incompeq with A’, and this is clearly equivalent (visually: if you can’t draw two of the arrows in the triangle A B C, then drawing the third would be a strong incompleteness).
A strict partial order whose incompeq is transitive is called a strict weak order. This means that incompeq is an equivalence relation, so you can look at the equivalence classes, and you then have a total order on them with the same proof as in the post.
Unfortunately I can’t see a neat insight that this digression gives us, besides that weak incomplete just means incompeq is transitive.
Further links that don’t seem that useful: the wiki page on comparability graphs gives a characterization for what sorts of graphs are the graphs of comparability of a partial order. The page on indifference graphs gives a bunch of characterizations of graphs where each node has a “utility” and there’s an edge between two nodes when the difference is smaller than 1. Maybe someone else will win a mathematical theorem hunting lottery.
Yes, the name sucks. I didn’t want to conflate “indifferent” from “uncomparable”. ↩︎
Wikipedia uses “incomparable” to mean “neither x < y nor y < x”, but to me “incomparable” shouldn’t include the case x=y. ↩︎