lexicographic order
Let A be a set equipped with a total order <, and let An=A×⋯×A be the n-fold Cartesian product of A. Then the lexicographic order < on An is defined as follows:
If a=(a1,…,an)∈An and b=(b1,…,bn)∈An, then a<b if a1<b1 or
a1 | = | b1, | ||
⋮ | ||||
ak | = | bk, | ||
ak+1 | < | bk+1 |
for some k=1,…,n-1.
Examples
-
•
The lexicographic order yields a total order on the field of complex numbers.
-
•
The lexicographic order of words of finite length consisting of letters (space) is the dictionary order. To compare words of different length, one simply pads the shorter with s from the right. For example, .
Properties
-
•
The lexicographic order is a total order.
-
•
If the original set is well-ordered, the lexicographic ordering on the product is also a well-ordering.
Title | lexicographic order |
---|---|
Canonical name | LexicographicOrder |
Date of creation | 2013-03-22 15:14:05 |
Last modified on | 2013-03-22 15:14:05 |
Owner | matte (1858) |
Last modified by | matte (1858) |
Numerical id | 13 |
Author | matte (1858) |
Entry type | Definition |
Classification | msc 06A99 |
Defines | dictionary order |