FUNCTIONS

Chapter 2

2.1, 2.2 Functions and equivalence relations

2.3 Permutations

Forward | Back | Table of Contents | About this document

Functions and equivalence relations

Example 2.1.1. Let S = { 1,2,3 } and T = { u,v,w }. The subsets
F₁ = { (1,u), (2,v), (3,w) } and
F₂ = { (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₃ = { (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₃ 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<sub>4</sub> = { (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<sub>4</sub> 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₁) = f(x₂) implies x₁ = x₂ for all elements x₁, x₂ 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 }.

Example. (S/f) 2.2.2. Let f:S->T be any function. For x₁, x₂ S we define
x₁ x₂ if f(x₁) = f(x₂). Then for all x₁, x₂, x₃ S we have
(i) f(x₁) = f(x₁);
(ii) if f(x₁) = f(x₂), then f(x₂) = f(x₁);
(iii) if f(x₁) = f(x₂) and f(x₂) = f(x₃), then f(x₁) = f(x₃).
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₁ x₂ if f(x₁) = f(x₂), for all x₁, x₂ 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 } .

Permutations

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₁) = a₂, (a₂) = a₃, . . . , (a_k-1) = a_k, (a_k) = a₁, and

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

We can also write = (a₂,a₃,...,a_k,a₁) or = (a₃,...,a_k,a₁,a₂), 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₁,a₂,...,a_k) and = (b₁,b₂,...,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₁,a₂) 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.

Forward | Back | Table of Contents | About this document