Linear Ordering

Linear Orderings

A relation ≤ is said to be a linear ordering if the following three statements hold:

  • If tex:$$ a \leq b $$ and tex:$$ b \leq a $$ then tex:$$ a = b $$,
  • For any tex:$$ a $$ and tex:$$ b $$, either tex:$$ a \leq b $$ or tex:$$ b \leq a $$, and
  • If tex:$$ a \leq b $$ and tex:$$ b \leq c $$, it follows that tex:$$ a \leq c $$.

Given tex:$$ n $$ objects which are related via a linear relationship, they may be ordered tex:$$ a_1, a_2, \ldots, a_n $$ such that tex:$$ a_1 \leq a_2 \leq \mdots \leq a_n $$. If two or more objects are equal, the ordering is not unique.

Strict Linear Ordering

A relation < is said to be a strict linear ordering if the following two statements hold:

  • For any tex:$$ a $$ and tex:$$ b $$, exactly one of tex:$$ a < b $$, tex:$$ a = b $$, or tex:$$ b < a $$ must be true, and
  • If tex:$$ a < b $$ and tex:$$ b < c $$, it follows that tex:$$ a < c $$.

Lexicographical Ordering

If two m-tuplets tex:$$ (a_1, a_2, \ldots, a_m) $$ where each tex:$$ a_k $$ comes from a linearly ordered set, then the relationship tex:$$ (a_1, a_2, \ldots, a_m) < (b_1, b_2, \ldots, b_m) $$ if and only if there exists some value tex:$$ k $$ where tex:$$ 1 \leq k \leq m $$ such that tex:$$ a_j = b_j $$ for tex:$$ j = 1, \ldots, k - 1 $$ and tex:$$ a_k < b_k $$. Equality occurs if all entries are equal.

The most common lexicographical ordering is that on strings of characters: "cap" < "cat" < "cup" < "cut" < "map" < "mat". In general, a space is considered to greater than any character and therefore "mat" < "match" < "pat".

Examples

  • Integers, rational numbers, and real numbers are all linearly ordered using the usual relation,
  • The characters a, b, ..., z are linearly ordered using the alphabetical ordering,
  • The lexicographical ordering defines a linear relationship on any Cartesian product of linearly ordered objects; for example, strings of characters.

References