Any function has an equivalence
kernel, which is an equivalence relation on the domain, and a quotient set, a
partition on the domain. The equivalence kernel and the quotient set correspond
to each other according to the Fundamental Theorem
on equivalence relations. An important example
of this pair of concepts is the kernel and its set of cosets of a group homomorphism.
Definition
Let be a function.
The equivalence
kernel of F is the
equivalence relation on A determined by requiring that if and only if . The quotient set of F is
the partition of A
determined by the Fundamental Theorem
on equivalence relations, which means that the block is the set of all for which .
Terminology
The quotient set of a function may be denoted S/F and may be called the quotient of F. This terminology is not
common, and neither is the notation for the equivalence kernel.
Example
Let S be the set . Let be the function shown in the picture. Its quotient set is obtained by grouping the elements of S
into sets according to their value under F.
In this example, . It is a partition, with blocks {1}, {2,
7}, {3, 4, 5} and {6}.
Other examples
¨
The quotient set of the squaring
function is the
set . Note that every block except one has two elements.
For example, {2, 2} and are blocks.
The only exception is the block {0}, which has only one element since 0
= 0.
¨
The quotient set of an injective
function consists of singletons. It is worth
doing to play with examples until this becomes obvious!
¨
Let be a homomorphism of groups
with kernel K. Then the quotient set of h is the set of cosets of K.
In this case the quotient set is denoted by G/K, which is not ambiguous because once you know K (which must be a normal subgroup) you know all the cosets of K.
The key fact here is that G/K has
a natural group structure since the equivalence kernel determined by h is a congruence.
This idea occurs in many other categories of mathematical structures.
References
Algebra, by Saunders MacLane and Garrett Birkhoff, American Mathematical
Society, 1999. ISBN 0821816462,
9780821816462
Charles Wells, Class Notes for Discrete Mathematics, 1999.
131. The kernel equivalence of
a function
If F : A - B is a function, it induces an equivalence relation K(F)
on its domain A by identifying elements that go to the same
thing in B. Formally:
131.1 Definition: kernel equivalence
If F: A - B is
a function, the kernel equivalence of F on A, denoted K(F), is defined by
aK(F)a' ⇔ F(a) = F(a')
131.1.1 Fact It is easy to see that the kernel
equivalence of a function is an equivalence relation.
131.1.2 Example The congruence relations described in the
preceding section are kernel equivalences. Let k be a
fixed integer ≥ 2. The remainder function F: Z -
Z is defined by F(n) = n (mod k), the remainder
when n is divided by k. Theorem
130.2, reworded, says exactly that the relation of congruence (mod k) is
the kernel equivalence of the remainder function.
131.1.3 Exercise Give
an example of a function F: N →N with the property that 3K(F)5 but ¬(3K(F)6.
(Answer on page 250.)
120. The quotient of a function
We mentioned the partition Z/n
= {Cr I 0 ≤ r <n} in
section 117.2. It is a special case of a construction which works for any function:
120.1 Theorem
Let F
: A -~ B be a function. Then
the family of sets
{F −1(b) I bEImF}
is a
partition of A.
|
120.2 Definition:
quotient set
The
set {F −1(b) I b E ImF} is denoted A/F and is called the quotient set of
F.
120.2.1
Example Consider the function F: {1,2,3} -~ {2,4,5,6} defined by F(1) = 4 and F(2) = F(3) = 5. Its quotient set (of a function) is {{1}, {2, 3}}.
120.2.2
Example The quotient set (of a function)
of the squaring function S: R-~R defined by S(x)=x2 is
R/S={{r,—r} I rER}
Every
block of R/S has two elements with the
exception of the block {0}. The notation “{{r,—r} I r E R}” for R/S lists {0} as {0,—0}, but that is the same set
as {0}. Note that every set except {0} is listed twice in the expression “{{r,—r} I r E R}”.
120.2.3
Example Let’s look at the remainder function Rn(k)
= k mod n
for a fixed integer n. This function takes an
integer k to its remainder when divided by n. (As earlier, we use
floored division for negative k). For a particular remainder r, the set of integers which
leave a remainder of r when divided by n is the set we called
Cr earlier in the section. Thus the quotient set of Rn is the set we called Z/n.
120.3 Proof of Theorem
120.1
We must show that the blocks of
A/F are nonempty and that every element of A is in exactly one block of A/F.
That the blocks are nonempty follows the fact that A/F consists of those F −1 (b) for which b E ImF; if b E ImF, then there is some a E A with F(a) = b, which implies that a E F −1(b),
so that F −1(b)
is nonempty. Since a E F −1(F(a)),
every element of A is in at least one
block. If a E F −1 (b) also, then F(a) = b by definition, so
F −1 (F(a))
= F −1
(b), so no element is in
more than one block.
120.3.1
Exercise For a function F: S -~ T, define a condition on the
quotient set S/F which is true if and only if F is injective. (Answer on
page 250.)
120.3.2 Exercise Give
examples of two functions F : N -+ N and G : N -+ N with the property that F
is surjective, G is
not surjective and F and G
have the same quotient set. (Thus, in contrast to Exercise
120.3.1, there is no condition on the quotient set of a function that forces
the function to be surjective.)
120.4 Exercise set
In Problems 120.4.1 through
120.4.5, provide an example of a function F : R -+R for which R/F has the given property.
120.4.1
R/F has at least one block with exactly three elements.
(Answer on page 250.)
120.4.2 R/F has
exactly three blocks.
120.4.3 R/F is
finite.
120.4.4 Every block of R/F is finite.
120.4.5 Every block of R/F has exactly two elements.
120.4.6 Exercise Suppose
F: A -+ B is a function, and x and y are distinct elements of B. Suppose also that lAl=7, lBl=4, ImF=B−{y}, and that the function Fl (A − F −1(x)) is injective.
a)How
many elements does A/F have?
b)How many elements are there in each block of A/F?
120.4.7
Exercise (hard) Let A be a set, II a partition
of A and B a subset of A. Define the set IIlB of subsets of B by
IIlB = {CflB l CEII and CflB=6∅}
a)Prove that IIlB is a partition of B.
b)Give
an example to show that the set {C fl B l C E II}
need not be a partition of B.
120.4.8 Exercise (hard) Let A be a set, II a partition of A, and a partition of II. For
any block C E , let B be the union of all the blocks B E II for which B E C. Show that {B l C E } is a partition of A. (For many people, this
exercise will be an excellent example
of a common phenomenon in conceptual mathematics: It seems incomprehensible at first, but when you finally
figure out what the notation means, you see that it is obviously
true.)