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) |