Graphics Reference
In-Depth Information
Definition.
Let
X
be a set. A
partial order
on
X
is a reflexive, antisymmetric, and
transitive relation on
X
. A
total order
on
X
is a partial order £ with the additional
property that for all x, y Œ
X
either x £ y or y £ x. A
well-ordering
on
X
is a total order
£ with the property that every nonempty subset
A
of
X
has a
smallest element
in
A
,
that is, there is an a Œ
A
such that a £ a¢ for all a¢Œ
A
.
Notation.
Given a total order £ on a set
X
, we shall let < denote the relation on
X
defined by x < y if and only if x £ y and x π y. Note that the relation < obtained in this
way is not a total order because it is not reflexive, but we get back to the total order
£ by simply adding the relations x £ x. Throughout this topic, when we have a rela-
tion denoted by “<” and call it an ordering, we will always assume that it came from
some associated total order £. Expressions such as “the total order <” or “the well-
ordering <” will mean “the total order £” or “the well-ordering £”, respectively.
The standard example of a total order is the usual £ relation on numbers, which
explains our choice of notation for such a relation. The usual £ relation is a well-
ordering of the set of nonnegative integers. On the other hand, the usual < relation is
not a total order on numbers by itself because it is not reflexive. If one desires to have
stand-alone definitions for natural orderings like <, one can introduce a notion of
strict
partial orders (which basically removes the reflexive property),
strict
total
orders, and a corresponding version of well-ordering and smallest element. This is not
needed in this topic. It should also be noted that there are some slight variations in
the definitions for orderings in the literature and readers might have to be careful
when they see these terms. However, any differences are technical only and do not
change the essential concepts they are trying to capture.
B.3
Permutations
Definition.
A
permutation
of a set
X
is a bijection s :
X
Æ
X
. The set of permuta-
tions on
X
will be denoted by S(
X
). Given two permutations s and t of
X
, define their
product
s
t to be the composition of the two maps, namely,
(
)( )
=
(
()
)
st
x
st
x
for x
Œ
X
.
actually makes S(
X
) into a (noncommutative) group (see the
next section for the definition of a group), but this will not play a role in the current
discussion.
The operation
Definition.
The set of permutations of {1,2, . . . ,n} together with the operation
is
called the
symmetric group of degree n
and is denoted by S
n
.
This section collects a few basic facts about S
n
.
Definition.
A permutation t in S
n
is called a
transposition
if it interchanges two
numbers and leaves all others fixed, that is, there are i, j Œ{1,2,...,n} with i π j such
that t(i) = j, t(j) = i, and t(k) = k, for k π i or j.
