Lexicographical Order - Case of Multiple Products

Case of Multiple Products

Suppose

\{ A_1, A_2, \cdots, A_n \}

is an n-tuple of sets, with respective total orderings

\{ <_1, <_2, \cdots, <_n \}

The dictionary ordering

\ \ <^{d}

of

A_1 \times A_2 \times \cdots \times A_n

is then

(a_1, a_2, \dots, a_n) <^d (b_1,b_2, \dots, b_n) \iff (\exists\ m > 0) \ (\forall\ i < m) (a_i = b_i) \land (a_m <_m b_m)

That is, if one of the terms

\ \ a_m <_m b_m

and all the preceding terms are equal.

Informally,

\ \ a_1

represents the first letter,

\ \ a_2

the second and so on when looking up a word in a dictionary, hence the name.

This could be more elegantly stated by recursively defining the ordering of any set

\ \ C= A_j \times A_{j+1} \times \cdots \times A_k

represented by

\ \ <^d (C)

This will satisfy

a <^d (A_i) a' \iff (a <_i a')
(a,b) <^d (A_i \times B) (a',b') \iff a <^d (A_i) a' \lor ( a=a' \ \land \ b <^d (B) b')

where B = A_{i+1} \times A_{i+2} \times \cdots \times A_n.

To put it more simply, compare the first terms. If they are equal, compare the second terms – and so on. The relationship between the first corresponding terms that are not equal determines the relationship between the entire elements.

Read more about this topic:  Lexicographical Order

Famous quotes containing the words case, multiple and/or products:

    “The woods were as fresh and full of vegetable life as a lichen in wet weather, and contained many interesting plants; but unless they are of white pine, they are treated with as little respect here as a mildew, and in the other case they are only the more quickly cut down.”
    —Henry David Thoreau (1817–1862)

    “Combining paid employment with marriage and motherhood creates safeguards for emotional well-being. Nothing is certain in life, but generally the chances of happiness are greater if one has multiple areas of interest and involvement. To juggle is to diminish the risk of depression, anxiety, and unhappiness.”
    —Faye J. Crosby (20th century)

    “The measure discriminates definitely against products which make up what has been universally considered a program of safe farming. The bill upholds as ideals of American farming the men who grow cotton, corn, rice, swine, tobacco, or wheat and nothing else. These are to be given special favors at the expense of the farmer who has toiled for years to build up a constructive farming enterprise to include a variety of crops and livestock.”
    —Calvin Coolidge (1872–1933)