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:

    “A new talker will often call her caregiver “mommy,” which makes parents worry that the child is confused about who is who. She isn’t. This is a case of limited vocabulary rather than mixed-up identities. When a child has only one word for the female person who takes care of her, calling both of them “mommy” is understandable.”
    —Amy Laura Dombro (20th century)

    “Pardon me, you are not engaged to any one. When you do become engaged to some one, I, or your father, should his health permit him, will inform you of the fact. An engagement should come on a young girl as a surprise, pleasant or unpleasant, as the case may be. It is hardly a matter that she could be allowed to arrange for herself.”
    —Oscar Wilde (1854–1900)

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

    “Good wine needs no bush,
    And perhaps products that people really want need no
    hard-sell or soft-sell TV push.
    Why not?
    Look at pot.”
    —Ogden Nash (1902–1971)