Pseudo-order

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. It is not possible for two elements to each be less than the other. That is, .
  2. For all x, y, and z, if x < y then either x < z or z < y. That is, .
  3. Every two elements for which neither one is less than the other must be equal. That is,

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 or comparison 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 nontrivial 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

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 ≤ y is defined as the negation of y < x, then we have

Using classical logic one would then conclude that x ≤ y or y ≤ 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 (one can construct) a rational number greater than the former and less than the latter. In other words, x < y if there exists a rational number z such that x < z < y.

Co-transitivity

The second condition deserves some considerations by itself. It is called co-transitivity since a relation is transitive iff its complement satisfies condition 2. Moreover, its following properties can be proven using classical logic.

If R is a co-transitive relation, then

Sufficient conditions for a co-transitive relation R to be transitive also are:

A semi-connex relation R is also co-transitive if it is symmetric, left or right Euclidean, transitive, or quasitransitive. If incomparability w.r.t. R is a transitive relation, then R is co-transitive if it is symmetric, left or right Euclidean, or transitive.

Notes
  1. For symmetric R, semiorder axiom 3 even coincides with co-transitivity.
  2. Transitivity of incomparability is required e.g. for strict weak orderings.
  3. unless the domain is a singleton set
gollark: You might just need to use a smaller model.
gollark: For more than a minute.
gollark: Int8 apparently causes it to just output random noise and I never got round to trying quantisation aware training for it.
gollark: It's quite strange that apparently BERT can be statically quantized without any extra training and retains decent accuracy but GPT-Neo emits nonsense going through the same process.
gollark: I was looking into quantization-aware training a while ago, but on the 125M model, and running that for a bit made it produce English-looking nonsense instead of random noise.

References
  • Heyting, Arend (1966). Intuitionism: an introduction (2nd ed.). Amsterdam: North-Holland Pub. Co. p. 106.


    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.