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 of, case, multiple and/or products:

    “If a playwright tried to see eye to eye with everybody, he would get the worst case of strabismus since Hannibal lost an eye trying to count his nineteen elephants during a snowstorm while crossing the Alps.”
    —James Thurber (1894–1961)

    “The youngest of four sons, but not the youngest of the family!—you conceive the sort of negligence that creeps over even the kindest maternities, in such case ...”
    —Walter Pater (1839–1894)

    “Creativity seems to emerge from multiple experiences, coupled with a well-supported development of personal resources, including a sense of freedom to venture beyond the known.”
    —Loris Malaguzzi (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)