nLab irreflexive comparison

Redirected from "connected irreflexive comparison".
Irreflexive comparison

Irreflexive comparison

Idea

Just as preorders generalise equivalence relations and total orders, irreflexive comparisons should generalise apartness relations and strict total orders

Definitions

An irreflexive comparison on a set SS is a (binary) relation <\lt on SS that is both irreflexive and a comparison. That is:

  • x<xx \lt x is always false;
  • If x<zx \lt z, then x<yx \lt y or y<zy \lt z

Properties

A set SS equipped with an irreflexive comparison is a category (with SS as the set of objects) enriched over the cartesian monoidal category TV opTV^\op, that is the opposite of the poset of truth values, made into a monoidal category using disjunction. TV opTV^\op is a co-Heyting algebra.

Preorder of an irreflexive comparison

An important part of an irreflexive comparison is that it is a preorder.

Theorem

The negation of an irreflexive comparison is transitive.

Proof

The contrapositive of comparison says that

for all xx, yy, and zz, if x<yx \lt y or y<zy \lt z is false, then x<zx \lt z is false.

By one of de Morgan's laws, that x<yx \lt y or y<zy \lt z is false is logically to equivalent to that ¬(x<y)\neg(x \lt y) and ¬(y<z)\neg(y \lt z), and substituting this into the original statement results in

if ¬(x<y)\neg(x \lt y) and ¬(y<z)\neg(y \lt z), then ¬(x<z)\neg(x \lt z)

which is precisely transitivity for the negation of the irreflexive comparison.

Theorem

The negation of an irreflexive comparison is reflexive.

Proof

Irreflexivity states that ¬(x<x)\neg (x \lt x) is true, which is precisely reflexivity for the negation of the strict weak order.

Theorem

The negation of an irreflexive comparison is a preorder.

Corollary

The incomparability relation of a strict weak order, ¬(x<y)¬(y<x)\neg (x \lt y) \wedge \neg (y \lt x), is an equivalence relation

Proof

For every preorder, (xy)(yx)(x \leq y) \wedge (y \leq x) is an equivalence relation. Since ¬(x<y)\neg (x \lt y) is a preorder, ¬(x<y)¬(y<x)\neg (x \lt y) \wedge \neg (y \lt x) is an equivalence relation.

Theorem

If the irreflexive comparison is a connected relation, then its negation is a partial order.

Proof

The connectedness condition states that ¬(x<y)¬(y<x)\neg (x \lt y) \wedge \neg (y \lt x) implies equality, which is precisely the antisymmetry condition for the negation of the strict weak order, implying that its negation is a partial order.

Theorem

If the irreflexive comparison is an apartness relation, then its negation is an equivalence relation.

Proof

The symmetry condition of the apartness relation states that x<yx \lt y implies y<xy \lt x for all xx and yy. It’s contrapositive states that ¬(y<x)\neg(y \lt x) implies ¬(x<y)\neg(x \lt y) for all xx and yy, which is the symmetry condition for the negation of <\lt. A symmetric preorder is the same thing as an equivalence relation, which means that the negation of <\lt is an equivalence relation.

Theorem

If the irreflexive comparison is a tight apartness relation, then its negation is the equality relation.

Proof

This follows from the previous two theorems.

 Examples

Connected irreflexive comparisons

  • An irreflexive comparison that is also a connected relation (if x<yx \lt y is false and y<xy \lt x is false, then x=yx = y) is a connected irreflexive comparison.

  • If the set is an inequality space, then an irreflexive comparison is strongly connected if xyx \neq y implies x<yx \lt y or y<xy \lt x.

Last revised on December 26, 2023 at 00:42:44. See the history of this page for a list of all contributions to it.