Strict weak ordering
From Free net encyclopedia
A strict weak ordering is a binary relation R on a set S whose omissions determine an equivalence relation. Two elements x and y of S are equivalent under this equivalence relation if x R y and y R x are both false—i.e., if x and y are R-unrelated.
A strict weak ordering has the following properties. For all x and y in S,
- irreflexive: x R x is false
- antisymmetric: if x ≠ y and x R y then not y R x
- transitive: if x R y and y R z then x R z
- transitivity of equivalence: If x is equivalent to y (under the equivalence relation defined above) and y is equivalent to z, then x is equivalent to z.
Note that this list of properties is somewhat redundant, as antisymmetry follows readily from irreflexivity and transitivity.
A strict weak ordering is a strict partial order that satisfies transitivity of equivalence.
Example: a<b<d, a<c<d, no other elements or relationships. Then b and c are equivalent.
Example of a strict partial order that is not a strict weak order: a<b<c<e. a<d<e. The pairs {b,d} and {d,c} are R-unrelated but {b,c} is R-related, so this relation fails to satisfy the transitivity of equivalence condition.
An example of a strict weak ordering is the less than relationship over real numbers.