Ordering cheat sheet

Non-strict orders: ≤

The symbol ≤ denotes a generalization of “less than or equal”, and it defines either a partial or total ordering over a set P (in the table below a,b ∈ P):

Constraint (Non-strict) partial order (Non-strict) total order
Reflexivity: a ≤ a x x
Antisymmetry: if a ≤ b and b ≤ a then a = b x x
Transitivity: if a ≤ b and b ≤ c then a ≤ c x x
Totality: either a ≤ b or b ≤ a x

Strict orders: <

The symbol < denotes a generalization of “less than”, and it defines either a partial or total ordering over a set P (in the table below a,b ∈ P):

Constraint (Strict) partial order (Strict) total order
Irreflexivity: ¬(a < a) x x
Asymmetry: if a < b then ¬(b < a) x x
Transitivity: if a < b and b < c then a < c x x
Totality: either a < b or b < a x

Note the difference between asymmetry and antisymmetry.

Type of relation Constraint
Asymmetric relation if a < b then ¬(b < a)
Antisymmetric relation
(two equivalent definitions)
if a ≤ b and b ≤ a then a = b
if a ≠ b then ¬(b ≤ a)

Leave a Reply