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:

    “Rhetoric may be defined as the faculty of observing in any given case the available means of persuasion.”
    —Aristotle (384–323 B.C.)

    “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)

    “Isn’t it odd that networks accept billions of dollars from advertisers to teach people to use products and then proclaim that children aren’t learning about violence from their steady diet of it on television!”
    —Toni Liebman (20th century)