then there is exactly one function from T to S no matter what S is. If T 6; and

=

S = ;, then there are no functions from T to S. If both are nonempty, we suppose

by induction that the conclusion is true for sets with fewer elements than T , let

t 2 T and T0 = T ¡ ftg. A function from T to S is determined by a function from

T0 to S plus an element of S for t to go to. Thus the number of such functions is

#(S)#(T0 )#(S) = #(S)#(T )¡1 #(S) = #(S)#(T )

which is still ¯nite. Thus the category of ¯nite sets is cartesian closed. The two-

element set is also ¯nite so the category of ¯nite sets has a subset classi¯er.

4. It is not quite su±cient to point out that when S is in¯nite, the set 2S of subsets

»

of S is not countable. The point to be made is that Hom(1; 2S ) = Hom(S; 2)

(where here 2 is the set f0; 1g) and the latter set of functions is not countable,

while there is no countable or ¯nite set T for which Hom(1; T ) is not countable

or ¯nite. Thus there is no ¯nite or countable set that has the universal mapping

property required to be the powerset 2S .

Section 5.2

1. In the category of sets, - = 2 so we must verify that

Hom(B; 2A ) » Hom(A £ B; 2) » Sub(A £ B)

= =

If f : B ¡ 2A is a function, let Á(f ) : A £ B ¡ 2 by Á(f)(a; b) = Á(b)(a). If

! !

g : A£B ¡ 2 is a function, let Ã(g) = f(a; b) j g(a; b) = 1g µ A£B. If U µ A£B

!

is a subset, then let

½

1 if (a; b) 2 U

½(U )(b)(a) =

0 if (a; b) 2 U

=

It is immediate that ½ ± Ã ± Á = idHom(B;2A ) and similarly for the other two serial

composites, from which it is immediate that each of them is invertible, with

inverse the composite of the other two.

2. For x 2 S, let [x] denote the equivalence class containing it. Then [x] = [y] if

and only if (x; y) 2 E. Let d 0 ; d 1 : E ¡ S be the two arrows mentioned above

!

and let d : S ¡ S=E denote the arrow x 7 [x]. Then for (x; y) 2 E, d ± d 0 (x; y) =

! !

d(x) = [x] = [y] = d(y) = d ± d (x; y) so that d coequalizes d 0 and d 1 .

1

Now suppose that e0 ; e1 : T ¡ S such that d ± e0 = d ± e1 . Then for all x 2

!

T , [e (x)] = [e (x)]; equivalently (e0 (x); e1 (x)) 2 E. Thus we can let f : T ¡

0 1

!

0 1 0± 00 1 0

E by de¯ning f(x) = (e (x); e (x)). Then d f(x) = d (e (x); e (x)) = e (x)

1±

f(x) = e (x). Finally if g : T ¡ E is such that d 0 ± g(x) =

1

!

and similarly d

d (e (x); e (x)) = e (x) and d g(x) = e (x), then g(x) = (e0 (x); e1 (x)) = f(x).

00 1 0 1± 1

94 Solutions for section 5.2

3. a. Suppose that d, e form an equivalence relation. This means that for any

monoid N , the pair

Hom(N; d); Hom(N; e) : Hom(N; E) ¡ Hom(N; M )

!

gives an equivalence relation on the latter. This is another way of saying that

hHom(N; d); Hom(N; e)i : Hom(N; E) ¡ Hom(N; M ) £ Hom(N; M )

!

is an equivalence relation. Since

»

Hom(N; M ) £ Hom(N; M ) = Hom(N; M £ M )

we have that hd; ei : E ¡ M £ M is monic. Since the image of a monoid homo-

!

morphism is a submonoid, the image is a submonoid. By letting N = N, whence

Hom(N; E) and Hom(N; M ) are the underlying sets of E and M respectively,

we conclude that the image of hd; ei is also an equivalence relation on the set

underlying M . Thus it is a congruence.

Conversely, let d; e : E ¡ M have the given property. Then up to isomorph-

!

ism, we may suppose that E µ M £ M is both a submonoid and an equivalence

relation and that d and e are the inclusion followed by the product projections.

Then for any monoid N , Hom(N; E) consists of those pairs of arrows f; g : N

¡ E such that for all x 2 N , (f (x); g(x)) 2 E. Since E is an equivalence rela-

!

tion, it is immediate that this makes Hom(N; E) into an equivalence relation on

Hom(N; M ).

b. Let us suppose that E µ M £ M is a submonoid and simultaneously an

equivalence relation. For an x 2 M , let [x] denote the equivalence class contain-

ing x. If x0 2 [x] and y 0 2 [y], then (x; x0 ) 2 E and (y; y 0) 2 E, whence so is

(x; x0 )(y; y 0 ) = (xy; x0 y 0 ). Thus x0 y 0 2 [xy] which means there an unambiguous

multiplication de¯ned on the set M=E of equivalence classes by [x][y] = [xy].

The associativity is obvious as is [1][x] = [x][1] = [x]. Thus M=E is a monoid

and evidently the arrow p : M ¡ M=E, x 7 [x] is a monoid homomorphism.

! !

p(x) = p(x ) if and only if x 2 [x] if and only if (x; x0) 2 E so E is the kernel pair

0 0

of p.

4. Let f be the coequalizer of the two arrows e0 ; e1 : E ¡ C and let the ker-

!

0 1 0 1

nel pair be d ; d : K ¡ C. Since f ± e = f ± e , it follows from the universal

!

mapping property of kernel pairs that there is a unique arrow e : E ¡ K such

!

0± 0 1± 1 0± 1±

that d e = e and d e = e . Now d f = d f is one of the de¯ning prop-

erties of kernel pairs. If g : C ¡ B is an arrow such that g ± d 0 = g ± d 1 , then

!

g ± e = g ± d e = g ± d e = g ± e1 . Since f is the coequalizer of e0 and e1 ,

0 0± 1±

there is a unique h : D ¡ B such that h ± f = g.

!

5. Let S = fag, T = fa; bg and f : S ¡ T be the inclusion. The kernel pair d 0 ,

!

d of f is the equality relation on S, that is d 0 = d 1 , but f is not the coequalizer.

1

Solutions for section 5.2 95

For any set U with more than one element and any function g : S ¡ U there are

!

many functions h : T ¡ U such that h ± f = g, since g(b) can be any element of

!

U.

6. Let T be a set, T0 µ T a subset and f : T0 ¡ S be an arbitrary function.

!

b

De¯ne f : T ¡ S [ f¤g by

!

½

f (x) if x 2 T0

b

f (x) =

¤ otherwise

b

Then T0 = fx 2 T j f (x) 2 Sg, which is another way of saying that

f-

T0 S

? ?

- S [ f¤g

T b