Linear Orderings
A linear order is a kind of ordering relation.
Loosely, a linear order on a set A is a way to put elements of A “into a line”. One example is the integers Z with their usual ordering:
⋯≤−2≤−1≤0≤1≤2≤⋯
A more exotic example is the natural ordering on Q, wherein between every two elements there are an infinite number of other elements (i.e., Q has a dense order).
Formally, a we define total orders to be binary relations ≤ satisfying:
Reflexivity: always
a≤a
Transitivity: if
a≤b and
b≤c then
a≤c
Antisymmetry: if
a≤b and
b≤a then
a=b
Totality: always
a≤b or
b≤a