Editing Lexicographic order (section)

==Cartesian products==

The lexicographical order defines an order on an ''n''-ary [[Cartesian product]] of ordered sets, which is a total order when all these sets are themselves totally ordered. An element of a Cartesian product <math>E_1 \times \cdots \times E_n</math> is a sequence whose <math>i</math><sup>th</sup> element belongs to <math>E_i</math> for every <math>i.</math> As evaluating the lexicographical order of sequences compares only elements which have the same rank in the sequences, the lexicographical order extends to Cartesian products of ordered sets.

Specifically, given two [[partially ordered set]]s <math>A</math> and <math>B,</math> the {{visible anchor|lexicographical order on the Cartesian product|Lexicographic order on Cartesian products}} <math>A \times B</math> is defined as
<math display=block>(a, b) \leq \left(a^{\prime}, b^{\prime}\right) \text{ if and only if } a < a^{\prime} \text{ or } \left(a = a^{\prime} \text{ and } b \leq b^{\prime}\right),</math>

The result is a partial order. If <math>A</math> and <math>B</math> are each [[Total order|totally ordered]], then the result is a total order as well. The lexicographical order of two totally ordered sets is thus a [[linear extension]] of their [[product order]].

One can define similarly the lexicographic order on the Cartesian product of an infinite family of ordered sets, if the family is indexed by the [[natural number]]s, or more generally by a well-ordered set. This generalized lexicographical order is a total order if each factor set is totally ordered.

Unlike the finite case, an infinite product of well-orders is not necessarily well-ordered by the lexicographical order. For instance, the set of [[countably infinite]] binary sequences (by definition, the set of functions from natural numbers to <math>\{ 0, 1 \},</math> also known as the [[Cantor space]] <math>\{ 0, 1 \}^{\omega}</math>) is not well-ordered; the subset of sequences that have precisely one <math>1</math> (that is, {{math|{ 100000..., 010000..., 001000..., ... }{{void}}}}) does not have a least element under the lexicographical order induced by <math>0 < 1,</math> because {{math|100000... > 010000... > 001000... > ...}} is an [[infinite descending chain]].<ref name="Harzheim">{{cite book|author=Egbert Harzheim|title=Ordered Sets|year=2006|publisher=Springer|isbn=978-0-387-24222-4|pages=88–89}}</ref> Similarly, the infinite lexicographic product is not [[Noetherian relation|Noetherian]] either because {{math|011111... < 101111... < 110111 ... < ...}} is an infinite ascending chain.