strict weak ordering

A strict weak ordering is a binary relation < on a set S that is a strict partial order (a transitive relation that is irreflexive, or equivalently, that is asymmetric) in which the relation neither a < b nor b < a is transitive. Therefore, a strict weak ordering has the following properties:

  • For all x in S, it is not the case that x < x (irreflexivity).
  • For all x, y in S, if x < y then it is not the case that y < x (asymmetry).
  • For all x, y, z in S, if x < y and y < z then x < z (transitivity).
  • For all x, y, z in S, if x is incomparable with y (neither x < y nor y < x hold), and y is incomparable with z, then x is incomparable with z (transitivity of incomparability).

This list of properties is somewhat redundant, as asymmetry follows readily from irreflexivity and transitivity.

离散数学中的relation: Given a function f (which models a binary relation) over a domain D, and a, b ∈ D:

  • Reflexivity: f (a, a) is true.
  • Asymmetry: For a ≠ b, if f(a, b) is true, f(b,a) is false
  • Anti-symmetry: If f(a, b) and f(b, a) are both true iff a ≡ b
  • Transitivity: If f(a, b) and f(b, c) are true, then f(a, c) is true
  • Incomparability: Neither f(a, b) nor f(b, a) is true
  • Transitivity of incomparability: If a and b are incomparable, and so are b and c, then a and c are incomparable.