# All Science Fair Projects

## Science Fair Project Encyclopedia for Schools!

 Search    Browse    Forum  Coach    Links    Editor    Help    Tell-a-Friend    Encyclopedia    Dictionary

# Science Fair Project Encyclopedia

For information on any area of science that interests you,
enter a keyword (eg. scientific method, molecule, cloud, carbohydrate etc.).
Or else, you can start by choosing any of the categories below.

# Lexicographical order

(Redirected from Lexicographic ordering)

In mathematics, the lexicographical order, or dictionary order, is a natural order structure of the cartesian product of two ordered sets. Given A and B, two ordered sets, the lexicographical order in the cartesian product A × B is defined as

(a,b) ≤ (a′,b′) if and only if a < a′, or a = a′ and bb′.

The name comes from its generalizing the order given to words in a dictionary: a sequence of letters (i.e. a word)

a1a2 ... ak

appears in a dictionary before a sequence

b1b2 ... bk

if and only if the first ai which is different from bi comes before bi in the alphabet. That assumes both have the same length; what is usually done is to pad out the shorter word for symbols for 'blanks', and to consider that a blank is a new minimum ('bottom') element.

For the purpose of dictionaries, etc., one may assume that all words have the same length, by adding blank spaces at the end, and considering the blank space as a special character which comes before any other letter in the alphabet. This also allows ordering of phrases. See alphabetical order.

An important property of the lexicographical order is that it preserves well-orders, that is, if A and B are well-ordered sets, then the product set A × B with the lexicographical order is also well-ordered.

## Case of multiple products

Suppose

$\{ A_1, A_2, \dots, A_n \}$

is a collection of sets, with respective to 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 defined recursively by 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) a' \lor ( a=a' \ \land \ b <^d (B) b')$

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

Or, more simply put, compare the first terms if they are equal compare the second — and so on.

## Monomials

In algebra it is traditional to order terms in a polynomial, by ordering the monomials in the indeterminates. This is fundamental, in order to have a normal form. Such matters are typically left implicit in discussion between humans, but must of course be dealt with exactly in computer algebra. In practice one has an alphabet of indeterminates X, Y, ... and orders all monomials formed from them by a variant of lexicographical order. For example if one decides to order the alphabet by

X > Y > ...

and also to look at higher terms first, that means ordering

... > X3 > X2 > X

and also

X > Yk for all k.

There is some flexibility in ordering monomials, and this can be exploited in Gröbner basis theory.

Last updated: 05-26-2005 06:51:38
03-10-2013 05:06:04
Science kits, science lessons, science toys, maths toys, hobby kits, science games and books - these are some of many products that can help give your kid an edge in their science fair projects, and develop a tremendous interest in the study of science. When shopping for a science kit or other supplies, make sure that you carefully review the features and quality of the products. Compare prices by going to several online stores. Read product reviews online or refer to magazines.

Start by looking for your science kit review or science toy review. Compare prices but remember, Price \$ is not everything. Quality does matter.
 Science Fair Coach What do science fair judges look out for? ScienceHound Science Fair Projects for students of all ages
 All Science Fair Projects.com Site All Science Fair Projects Homepage Search | Browse | Links | From-our-Editor | Books | Help | Contact | Privacy | Disclaimer | Copyright Notice