abstractmath.org

help with abstract math

Produced by Charles Wells.  Home    Website TOC    Website Index   Blog
Back to Functions Head 

Last edited 5/21/2009 3:31:00 PM

 

THE QUOTIENT OF A FUNCTION


 

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.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.

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}

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.)