lexicographic order


Let A be a set equipped with a total orderMathworldPlanetmath <, and let An=A××A be the n-fold Cartesian productMathworldPlanetmath of A. Then the lexicographic orderMathworldPlanetmath < 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) <a<b<<y<z is the dictionary order. To compare words of different length, one simply pads the shorter with s from the right. For example, prove<proved<proven.

Properties

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