Pseudo-order

From Wikipedia, the free encyclopedia

In constructive mathematics, a pseudo-order is a constructive generalisation of a linear order to the continuous case. The usual trichotomy law does not hold in the constructive continuum because of its indecomposability, so this condition is weakened.

A pseudo-order is a binary relation satisfying the following conditions:

  1. \neg (x < y \wedge y < x)
  2. x < y \to (x < z \vee z < y)
  3. \neg (x < y \vee y < x) \to x=y

This first condition is simply asymmetry. It follows from the first two conditions that a pseudo-order is transitive. The second condition is often called co-transitivity and is the constructive substitute for trichotomy. In general, given two elements of a pseudo-ordered set, it is not always the case that either one is less than the other or else they are equal, but given any interval, any element is either above the lower bound, or below the upper bound.

The third condition is often taken as the definition of equality. The natural apartness relation on a pseudo-ordered set is given by x < y \vee y < x, and equality is defined by the negation of apartness.

The negation of the pseudo-order is a partial order which is close to a total order: if x \le y is defined as \neg(y<x), then we have that \neg(\neg(x \le y) \wedge \neg(y \le x)). Using classical logic one would then conclude that x \le y \vee y \le x, so it would be a total order. However this inference is not valid in the constructive case.

The prototypical pseudo-order is that of the real numbers: one real number is less than another if there exists a rational number greater than the former and less than the latter.


 This mathematical logic-related article is a stub. You can help Wikipedia by expanding it.