- 2.1, 2.2 Functions and equivalence relations
- 2.3 Permutations

Forward | Back | Table of Contents | About this document

The subset { y T | (x,y) F for some x S } of the codomain is called the

**Example** 2.1.1.
Let S = { 1,2,3 } and T = { u,v,w }.
The subsets

F_{1} = { (1,u), (2,v), (3,w) } and

F_{2} = { (1,u),(2,u),(3,u) }

of S × T
both define functions since in both cases each element of S
occurs exactly once among the ordered pairs. The subset

F_{3} = { (1,u),(3,w) }

does not define a function with domain S because the element
2 S does not appear
as the first component of any ordered pair.

Note that F_{3}
is a function if the domain is changed to the set { 1,3 }.

Unlike the conventions used in calculus, the domain and codomain
must be specified as well as the ``rule of correspondence''
(list of pairs) when you are presenting a function. The subset

F_{4} = { (1,u),(2,u),(2,v),(3,w) }

does not define a function since 2 appears as the
first component of two ordered pairs.
When a candidate such as F_{4}
fails to be a function in this way, we say that it is not ``well-defined.''

**2.1.2. Definition.**
Let f:S->T and g:T->U be functions. The
**composition**
g ° f of f and g
is the function from S to U defined by the formula
(g ° f)(x) = g(f(x)) for all
x S.

**2.1.3. Proposition.**
Composition of functions is associative.

**2.1.4. Definition.**
Let f:S->T be a function.
Then f is said to map S
** onto **
T if for each element y T
there exists an element x S with f(x) = y.

If f(x_{1}) =
f(x_{2}) implies
x_{1} = x_{2}
for all elements x_{1},
x_{2} S,
then f is said to be a
**one-to-one**
function.

If f is both one-to-one and onto, then it is called a
**one-to-one correspondence**
from S to T.

**2.1.5. Proposition.**
Let f:S->T be a function.
Suppose that S and T are finite sets with the same number of elements.
Then f is one-to-one if and only if it is onto.

**2.1.6. Proposition.**
Let f:S->T and g:T->U be functions.

**(a)**If f and g are one-to-one, then g ° f is one-to-one.**(b)**If f and g are onto, then g ° f is onto.

1_{S}(x) = x
for all x S.

g ° f =
1_{S}
and f ° g = 1_{T}.

**2.2.1. Definition.**
Let S be a set.
A subset R of S × S is called an
**equivalence relation**
on S if

**(i)**for all a S, (a,a) R;**(ii)**for all a,b S, if (a,b) R then (b,a) R;**(iii)**for all a,b,c S, if (a,b) R and (b,c) R, then (a,c) R.

** 2.2.2. Definition.**
Let
be an equivalence relation on the set S.
For a given element a S, we define the
**equivalence class**
of a to be the set of all elements of S that are equivalent to a.

We will use the notation [a].
In symbols,

[a] = { x S | x a }.

The notation S/ will be used for the collection of all equivalence classes of S under .
**Example. (S/f)** 2.2.2.
Let f:S->T be any function.
For x_{1},
x_{2} S we define

x_{1}
x_{2}
if f(x_{1}) =
f(x_{2}).
Then for all x_{1}, x_{2},
x_{3} S
we have

(i) f(x_{1}) =
f(x_{1});

(ii) if f(x_{1}) =
f(x_{2}), then
f(x_{2}) =
f(x_{1});

(iii) if f(x_{1}) =
f(x_{2}) and
f(x_{2}) =
f(x_{3}), then
f(x_{1}) =
f(x_{3}).

This shows that we have defined an equivalence relation on the set S.
The proof of this is easy because the equivalence relation is defined
in terms of equality of the images f(x),
and equality is the most elementary equivalence relation.

The collection of all equivalence classes of S under
will be denoted by S/f.

**2.2.3. Proposition.**
Let S be a set, and let
be an equivalence relation on S.
Then each element of S belongs to exactly one of the
equivalence classes of S determined by the relation
.

**2.2.4. Definition.**
Let S be any set. A family P of subsets of S is called a
**partition**
of S if each element of S belongs to exactly one of the members of P.

**2.2.5. Proposition.**
Any partition P of a set S determines an equivalence relation.

**2.2.6. Theorem.**
If f:S->T is any function, and
is the equivalence relation defined on S by letting

x_{1}
x_{2} if
f(x_{1}) =
f(x_{2}), for all
x_{1},
x_{2} S,
then there is a one-to-one correspondence between
the elements of the image f(S) of S under f
and the equivalence classes S/f of the relation
.

If f:S ->T is a function and y belongs to the image f(S), then
the ** inverse image ** of y is

f^{ -1}(y) =
{ x S | f(x) = y } .

The set of all permutations of S will be denoted by Sym(S).

The set of all permutations of the set { 1, 2, ..., n } will be denoted by S

Proposition 2.1.6 shows that the composition of two permutations in Sym(S) is again a permutation. It is obvious that the identity function on S is one-to-one and onto. Proposition 2.1.8 shows that any permutation in Sym(S) has an inverse function that is also one-to-one and onto. We can summarize these important properties as follows:

**(i)**If , Sym(S), then Sym(S);**(ii)**1_{S}Sym(S);**(iii)**if Sym(S), then^{-1}Sym(S).

(a_{1}) =
a_{2},
(a_{2}) =
a_{3}, . . . ,
(a_{k-1}) =
a_{k},
(a_{k}) = a_{1}, and

(x)=x for all other elements
x S with
x a_{i}
for i = 1, 2, ..., k.

We can also write
=
(a_{2},a_{3},...,a_{k},a_{1}) or
=
(a_{3},...,a_{k},a_{1},a_{2}),
etc. The notation for a cycle of length k
can thus be written in k different ways,
depending on the starting point.
The notation (1) is used for the identity permutation.

**2.3.3. Definition.**
Let =
(a_{1},a_{2},...,a_{k})
and =
(b_{1},b_{2},...,b_{m})
be cycles in Sym(S), for a set S.
Then
and are said to be
**disjoint**
if a_{i} b_{j}
for all i,j.

**2.3.4. Proposition.**
Let S be any set. If
and
are disjoint cycles in Sym(S), then

=
.

**2.3.5. Theorem.**
Every permutation in S_{n}
can be written as a product of disjoint cycles.
The cycles that appear in the product are unique.

**2.3.6. Definition.**
Let S_{n}.
The least positive integer m such that
^{m} = (1) is called the
**order**
of .

**2.3.7. Proposition.**
Let S_{n}
have order m. Then for all integers j,k we have

^{j} =
^{k}
if and only if j k (mod m).

**2.3.9. Definition.**
A cycle (a_{1},a_{2})
of length two is called a
**transposition**.

**2.3.10 Proposition.**
Any permutation in S_{n}, where
n 2,
can be written as a product of transpositions.

**2.3.11. Theorem.**
If a permutation is written as a product of transpositions in two ways,
then the number of transpositions is either even in both cases
or odd in both cases.

**2.3.12. Definition.**
A permutation
is called
**even**
if it can be written as a product of an even number of transpositions, and
**odd**
if it can be written as a product of an odd number of transpositions.