# Kernel equivalence and natural mapping

For a mapping %:A -> B, let == denote the kernel equivalence of %, and let *:A -> A== denote the natural mapping. Define $:A== -> B by $([a]) = %(a) for every equivalence class [a] in A==.

1. Show that $ is well defined and one-to-one, and that $ is onto if % is onto. Furthermore, show that % = $*, so that % is the composite of an onto mapping followed by a one-to-one mapping.

2. If %(A) is a finite set, show that the set A== of equivalence classes is also finite and that the cardinality of A== is equal to the cardinality of %(A) (called the Bijection Theorem).

3. In each of the following two cases, find the cardinality of A== for the given set A and the given mapping %:

i. A = U X U, where U = {1, 2, 3, 4, 6, 12}, and %:A -> Q is defined by %(n, m) = n/m, where Q is the set of all rational numbers.

ii. A = {n: n is an element of Z and 1 <= n <= 99}, where Z is the set of all integers, and %:A -> N is defined by %(n) = the sum of the digits of n, where N is the set of all natural numbers.

#### Solution Preview

The following are the steps in the solution of this problem:

1. First, we show that $ is well defined and one-to-one, that $ is onto if % is onto, and that %=$*.

a. To show that $ is well defined, we need to show that if a1 == a2 then $([a1]) = $([a2]). So assume that a1 == a2. By the definition of kernel equivalence, %(a1) = %(a2). Thus by the definition of $ and the fact that a1 == a2, we have $([a1]) = %(a1) = %(a2) = $([a2]). Hence $ is well defined.

b. To show that $ is one-to-one, show that if [a1] and [a2] are elements of A== such that $([a1]) = $([a2]), then [a1] = [a2]. So assume that $([a1]) = $([a2]). By the definition of $, we have $([a1]) = %(a1) and $([a2]) = %(a2). Since $([a1]) = $([a2]), we see that %(a1) = %(a2). Thus a1 == a2, by the definition of ==. Hence [a1] = [a2], so $ is one-to-one.

c. Assume that % is onto. To show that $ is onto, let b be an element of B. Since % is onto, there is some element a of A such that %(a) = b. By the definition of $, we have $([a]) = %(a) = b. Hence $ is onto.

d. Note that % and * have the same domain, namely, A. Thus to show that % = $*, we need to show that for every element a of A: %(a) = $*(a). So let a be an element of A. By definition of *, we have ...

#### Solution Summary

The solution consists of step-by-step proofs of all the indicated properties of % and $ that apply to a general set A, as well as a step-by-step determination of the cardinality of the set of equivalence classes for each of the two specific pairs (A, %).