Problems: (1) Set Basics- Section 1. Problems 1 - 5; (2) Set Identities - Section 1. Problems 6-11; (3) Proofs and Venn Diagrams - Section 1. Problems 12 - 14; (4) Sets of Sets - Section 1. Problems 15 - 20; (5) Basic Relations - Section 2. Problems 1 - 3; (6) Functional Relations - Section 2. Problems 4 - 10; (7) One-to-one Functions - Section 2. Problems 11 - 14; (8) Permutations and Counting Functions - Section 2. Problem 15 - 17; (9) Inverse Images - Section 2. Problems 18-21:

BEFORE LOOKING AT THESE SOLUTIONS BE SURE TO TRY TO WORK THE PROBLEMS ON YOUR OWN!

(1) Set basics - Section 1. Problems 1, 16:

(1) (a) Yes. (b) No. 2 is in {1,2,3,4} but not {2}. (c) Yes. The set {3} is one of the elements of {1, {2}, {3}}. (d) Yes. Every element of {1, 2} is also an element of {1, 2, {1,2}, {3,4}}. (e) No. {1} is an element, but not 1. (f) Yes. A set is always a subset of itself.

(2) Be sure to draw these diagrams in "most general form." In (b), for example, B and C are disjoint, but A and B should show no special relationship.

NOTE: You should be prepared to list any set in "lexicographic order" when asked to do so In order to specify a set it is not required that you specify an ordering of the elements of the set, but a "list" has an ordering specified. It is an important distinction. Sometimes "to enumerate" is used as a synonym for "to list." When we say "list" the elements of a set, we mean in some order. Leave off the braces { } when making a list. Use nothing or use ( ) to include the elements of the list. If we ask for a particular linear order for the list elements use that. If not use any order that seems natural to you. Use braces { } for sets when order is not an issue. We will make this clearer with the examples to follow. Programmers use lexicographic order based on the extended alphabet called the ASCII Character Set.

(3)

(a) In lexicographic order, the elements of A x B are (w,a), (w,b), (x,a), (x,b), (y,a), (y,b), (z,a), (z,b). This is the order that the words wa, wb, xa, xb, etc., would appear in Webster's Baby-Talk Dictionary.The set A x B = {(w,a), (w,b), (x,a), (x,b), (y,a), (y,b), (z,a), (z,b)}, when written in braces, does not formally imply any particular ordering of the elements. Generally though, any representation of a set will utilize some implicit ordering of the elements as a part of the "data structure" used.

(b) In lexicographic order, the elements of B x A are (a,w), (a,x), (a,y), (a,z), (b,w), (b,x), (b,y), (b,z). The set B x A = {(a,w), (a,x), (a,y), (a,z), (b,w), (b,x), (b,y), (b,z)} = {(a,z), (b,w), (a,w), (a,x), (a,y), (b,x), (b,y), (b,z)} = {(a,x), (a,y), (a,z), (b,w), (a,w), (b,x), (b,y), (b,z)}= etc.

(c) In lexicographic order (called lex order for short), the elements of A x A are (w,w), (w,x), (w,y), (w,z), (x,w), (x,x), (x,y), (x,z), (y,w), (y,x), (y,y), (y,z), (z,w), (z,x), (z,y), (z,z). A x A = {(w,w), (w,x), (w,y), (w,z), (x,w), (x,x), (x,y), (x,z), (y,w), (y,x), (y,y), (y,z), (z,w), (z,x), (z,y), (z,z)}.

(d) In lexicographic order, the elements of B x B are (a,a), (a,b), (b,a), (b,b). B x B = {(a,a), (a,b), (b,a), (b,b)}.

(4)

(a) In lex order the list is (1, (u,m)), (1, (u,n)), (1, (v,m)), (1, (v,n)), (2, (u,m)), (2, (u,n)), (2, (v,m)), (2, (v,n)), (3, (u,m)), (3, (u,n)), (3, (v,m)), (3, (v,n)). This list has twelve elements, each a pair of elements. The first elements of the pair are ordered by the order on integers (1,2,3). The second elements are ordered lexicographically based on the order of the alphabet. Lexicographic order as we are using it deals with "words over an alphabet," where the underlying alphabet is linearly ordered, or equivalently products of linearly ordered sets. Lexicographic order is itself a linear order. (b) In lex order: ((1,u),m), ((1,u), n), ((1,v),m), ((1,v), n), ((2,u),m), ((2,u), n), ((2,v),m), ((2,v), n), ((3,u),m), ((3,u), n), ((3,v),m), ((3,v), n). The first components of these pairs are ordered lexicographically based on lex order on A x B in the first component and alphabetic order on the second components. (c) In lex order: (1,u,m), (1,u,n), (1,v,m), (1,v,n), (2,u,m), (2,u,n), (2,v,m), (2,v,n), (3,u,m), (3,u,n), (3,v,m), (3,v,n). This is lexicographic order on A x B x C based on numerical order in the first component and alphabetic order in each of the remaining two components. As a set, A x B x C = {(1,u,m), (1,u,n), (1,v,m), (1,v,n), (2,u,m), (2,u,n), (2,v,m), (2,v,n), (3,u,m), (3,u,n), (3,v,m), (3,v,n)}.

(5)

(a) Here is the set of palindromes of length less than or equal to 4, listed in Webster's lex order: e, x, xx, xxx, xxxx, xyx, xyyx, y, yxxy, yxy, yy, yyy, yyyy.

(b) In length-first lex order: e, x, xx, xy, xxx, xxy, xyx, xyy. In Webster's lex order: x, xx, xxx, xxy, xy, xyx, xyy. Do you see how to describe the difference? If Websters used length-first lex, zoo would come before able in the dictionary.

(c) (xxxx, xxxy, xxyx, xxyy, xyxx, xyxy, xyyx, xyyy, yxxx, yxxy, yxyx, yxyy, yyxx, yyxy, yyyx, yyyy).

(2) Set Identities - Section 1. Problems 6-11:

(6)

(a) False. Take A and B to be nonempty disjoint sets. Take C = A.

(b) False. Take C = 0 and A not 0.

(c) False. Take A=C not empty. Take B=0. The left hand side is A, the right hand side is 0.

(d) False. Take C = 0 and take A to be a proper subset of B.

(e) False. Take C to be nonempty, A=C, B=0.

(f) False. Take A=B=C not empty. A - (B - C) = A, (A - B) - C = 0 - C = 0.

(7)

(a) If x is in A then, since A is contained in B and A is contained in C, x is in B ^ C. Thus A is contained in B ^ C.

(b) Let x be in A v B. Thus either x is in A or x is in B. Since A is contained in C and B is contained in C, x is in C. Thus A v B is contained in C.

(8) . If x is in (A-B) ^ (C-B) then x is in A-B and hence in A. Also, x is in C-B and hence in C. Thus, x is in A ^ C. Since x is in A-B, x is not in B. Thus x is in A ^ C, x is not in B. Thus, x is in (A ^ C) - B. Conversly, if x is in (A ^ C) - B then x is in A but not in B and x is in C but not in B. Thus x is in (A-B) ^ (C-B). Thus, (A-B) ^ (C-B) = (A ^ C) - B. Note the general form of the element argument used show two sets X and Y are equal. First assume x is in X and show it is in Y, then assume x is in Y and show it is in X. You must show both directions.

(9)

(a) Let U be the universal set. If A is contained in B, then we show that U-B is contained in U-A. Suppose x is in U-B. Then x is not in B. Since A is contained in B, x is not in A. Thus x is in U-A. Thus, U-B is contained in U-A.

(b) Show A contained in B implies A ^ C contained in B ^ C. Assume x is in A ^ C. Since A is contained in B, x is in B. Thus, x is in B ^ C. Thus, A ^ C is contained in B ^ C.

(c) Taking set complements and using (a) gives (U-A) contained in (U-B). Using (a) again and De Morgan's rule applied to (b) gives (U-A) v (U-C) is contained in (U-B) v (U-C). Since A, B, and C are ``arbitrary'' so are (U-A), (U-B), and (U-C). Be sure to think about that last sentence and make sure you understand why it proves the assertion made in the problem.

(10)

(a) A mathematician would make use of "if and only if" statements use in succession here: Proof: (x,y) is in A x (B v C) iff (x is in A) and (y is in B v C) iff (x is in A) and (y is in B or y is in C) iff (x is in A and y is in B) or (x is in A and y is in C) iff (x,y) is in A x B or (x,y) is in A x C iff (x,y) is in (A x B) v (A x C). Thus A x (B v C) = (A x C) v (A x C).

(b) Proof: (x,y) is in A x (B ^ C) iff (x is in A) and (y is in B ^ C) iff (x is in A) and (y is in B and y is in C) iff (x is in A and y is in B) and (x is in A and y is in C) iff (x,y) is in A x B and (x,y) is in A x C iff (x,y) is in (A x B) ^ (A x C). Thus A x (B ^ C) = (A x C) ^ (A x C).

Note: (23) and (24) show that set product x distributes over both set union and intersection. You should draw a picture that represents these identities. One way is to use the Cartesian plane U = R^2 just like you use in high school math. Let [s, t] denote the set of real numbers x, s<= x <= t. Take the set A to be [0, 3]. Let B=[0, 1.25] and C=[.75, 2]. Show the sets in the identities of (a) and (b) above.

(11)

(a) Using B' to indicate the set complement of B, we must show that (A ^ B') ^ C' = (A ^ C') ^ B' (by 5.2.2.10) . (A ^ B') ^ C' = A ^(B' ^ C') by 5.2.2.2. A ^(B' ^ C') = A ^(C' ^ B') by 5.2.2.1. A ^(C' ^ B') = (A ^ C') ^ B' by 5..2.2.2. Thus, (A ^ B') ^ C' = (A ^ C') ^ B' or (A-B)-C = (A-C)-B.

(b) Show that (A-B) v (B-A) = (A v B) - (A ^ B). This operation on sets is called the "symmetric difference" of A and B. To prove the validity of this identity, start with the right side: (A v B) - (A ^ B)= (A v B) ^(A ^ B)' = (A v B) ^(A' v B') = ((A v B) ^A') v (A v B) ^B') = (A ^ A') v (B ^ A') v (A v B') v (B ^ B') = (B ^ A') v (A v B') = (B-A) v (A-B) = (A-B) v (B-A).

(c) (A-B)-C = (A ^ B') ^ C' = A ^ (B' ^ C') = A ^ (B v C)' = A - (B v C).

(3) Proofs and Venn Diagrams I - Section 1. Problems 12-14:

(12)

(a) True. Proof: (A-C) ^ (B-C) ^ (A-B) = A ^ C' ^ B ^ C' ^ A ^ B' = A ^ C' ^ C' ^ A ^ (B ^ B') = 0 since B ^ B' = 0. Below is the Venn diagram with the contiguous regions numbered 1 to 8. A-C consists of regions {2, 3}, B-C consists of regions {3, 4}, and A-B consists of regions {2, 5}. There is no region common to all three of these sets, so (A-C) ^ (B-C) ^ (A-B) = 0. A "proof using Venn diagrams" of this fact thus consists of drawing the appropriate Venn diagram with contiguous regions labled (below) and noting that {2,3}^{3,4}^{2,5} = 0.

(b) Using the Venn diagram below, the proof that A^(U-B) = 0 becomes {4,5}^{1,2}=0.

(c) Using the above Venn diagram: A^(U-(B^C)) becomes {4,5}^{1,2,5,6}={5} so the intersection is not empty. The assertion that A^(U-(B^C))=0 is FALSE. Note that another way of representing the above Venn diagram is to draw the general Venn diagram and put a 0 in all regions that must be empty as a consequence of the condition A<= B. All other regions get a 1 as indicated below:

You can now label the nonempty regions 1,2,3,4,5,6 and repeat the argument just given.

(d) False. Counter Example: Take A = U. The statement asserts that B' ^ C' = 0 for all sets B' and C'. This is obviously false (take B' = C' not empty).

(e) False. Counter Example: A={a}, B={b}, A x B = {(a,b)}. U={a,b}.

(13) We use the notation A + B = (A-B) v (B-A) for symmetric difference. Note that A + B = (A ^ B') v (B ^ A'). By 5.2 (33), A + B = A v B - (A ^ B). In words, A + B consists of everything in A or B that is not in both A and B. For this problem, we refer to the following Venn diagram:

(a) B + C consists of regions {5, 8, 3, 4}. A + (B + C) consists of regions {4, 8, 2}. A + B consists of regions {2, 5, 4, 7}. (A + B) + C consists of regions {2, 4, 8}. The final set of regions, {2, 4, 8} is the same in both cases. Thus, A + (B + C) = (A + B) + C. We can thus write A + B + C for A + (B + C), (A + B) + C, A + (C + B), (A + C) + B, etc. A + B + C consists of everything in A v B v C that belongs to exactly one of A, B, or C.

(b) A + 0 = (A v 0) - (A ^ 0) = A - 0 = A.

(c) A + A' = (A v A') - (A ^ A') = U - 0 = U. (Note: A + U = A')

(d) A + A = (A v A) - (A ^ A) = A-A = 0.

(e) If A + C = B + C then (A + C) + C = (B + C) + C or A + (C + C) = B + (C + C) or A + 0 = B + 0 or A = B.

(14) Use the Venn diagram:

(a) Must be disjoint. A-B has regions {2, 5}. B-C has regions {3, 4}. There are no regions in common.

(b) May not be disjoint. A-B has regions {2, 5}. C-B has regions {5, 8}. Region 5 is common to both and may be nonempty.

(c) Must be disjoint. A - (B v C) consists of region {2}. B - (A v C) consists of region {4}. There are no regions in common.

(d) May not be disjoint. A - (B ^ C) consists of regions {2, 3, 5}. B - (A ^ C) consists of regions {3, 4, 7}. Region 3 is common to both and may be nonempty.

NOTE: We are using Venn diagrams for two or three sets. For more than that, it can get very awkward, especially using the artificial constraint that each set is represented by a simply connected region. Here is a Venn diagram for three sets:

Here we have added a fourth set, represented by the eight squares. There are now 16 basic regions.

(4) Sets of Sets - Section 1. Problems 15 - 20:

NOTE: The sets Ai that are the elements of a partition are called the "blocks" or "cells" of the partition. We use the term blocks. The term "cells"s is more common in probability and statistics.

(15) (a) Yes. (b) No. (c) Yes.

(16) The number of refinements is the product of the Bell numbers: B3 x B3 x B4 = 5^2 x 15 = 375.

(17)

(a) {1, 2, 3} has three elements. List them 1, 2, 3. There are 2^3 = 8 elements in the power set. One way to list them is to simply list the binary numbers with three digits: 000, 001, 010, 011, 100, 101, 110, 111. There are, of course, 2^3=8 of them. You can represent each subset of A v B by a table (corresponding to 101 here):

where it is understood that the subset represented by the table is the set {1, 3} of elements in the first row that have a 1 below them (in the second row). This is called the "characteristic function representation" of the subset. To list all of the subsets, it is not necessary to list the first row more than once:

(b) X x Y = {(a, x), (a, y), (b, x), (b, y)}. In characteristic function format the power set, P(X x Y), of X x Y is as follows:

(18)

(a) Given any set S, the power set P(S) = {0, S, ... } contains the empty set 0, the set S, plus all proper non-empty subsets of S. Thus, for S=0, P(0) = {0, 0, ...) = {0, 0} = {0}. where 0 is the empty set. Thus, P(S) is the set with one element, the empty set.

(b) P(P(0)) = PP(0) = {0, {0}}.

(c) In characteristic function format, the power set of {0, {0}} is as follows:

In "braces" format: PPP(0) = { 0, {{0}}, {0}, {0, {0}}}.

(d) Characteristic function format is essential beyond this point. PPPP(0) =

(19)

(a) The first is a proper subset of the other whenever both A and B are nonempty . Example: A={1}, B={2}. P(A)={0, {1}}, P(B)={0, {2}}, P(A) v P(B) = {0, {1}, {2}}. Note that {1, 2} is an element of P(A v B) = P({1,2}) but not an element of P(A) v P(B). Thus P(A) v P(B) is a proper subset of P(A v B).

(b) They are equal. Proof: X is an element of P(A ^ B) iff X is a subset of A ^ B iff X is a subset of both A and B iff X is an element of P(A) and P(B) iff X is an element of P(A) ^ P(B). We have shown that P(A ^ B) = P(A) ^ P(B).

(c) For any sets A and B, P(A) x P(B) and P(A x B) have no elements in common. The set P(A) x P(B) consists of pairs of subsets (S, T), S contained in A and T contained in B. P(A x B) has elements W which are collections of pairs (x, y), x from A and y from B. (S, T) cannot equal W. They are from different universal sets. When can P(A) x P(B) and P(A x B) have the same number of elements? Take A=B=0, the empty set. P(A)=P(B)={0} so P(A) x P(B) has 1 element, (0,0). But A x B = 0 so P(A x B) = {0}. Although, 0 does not equal (0,0), the sets P(A) x P(B) and P(A x B) have the same number of elements in this case.

In general, if A has n elements and B has m elements then P(A) x P(B) has 2^(n+m) elements but P(A x B) has 2^(nm) elements. They have, as just shown, the same number of elements when A and B are empty (m=n=0). They also have the same number of elements if n=m=2. Otherwise (i.e., not both 0 or both 2), if both A and B have more than one element then P(A x B) has more elements than P(A) x P(B), otherwise (one of A or B has less than 2 elements and not both zero elements) the reverse is true: P(A) x P(B) has more elements than P(A x B).

(20) As an example, take n=8. T1 is given by the first 8 rows of the following table and S1 is given by the last 8 rows:

The table, in general contains 2^n entries. The first half of the rows of the table, 2^(n-1) rows total, correspond to T1 and the second 2^(n-1) rows correspond to S1.

(5) Basic Relations - Section 2. Problems 1 - 3

NOTE: The terminology needs some thought here. A relation FROM A to B is a subset of A x B. This is also called a relation ON A x B. Thus, the set of all relations from A to B (or on A x B) is the set of all subsets of A x B. This is the same as the power set P(AxB). If A=B then we can speak of a relation from A to A, a relation on A x A, or, for short, a BINARY relation ON A. Another terminology for a binary relation on A is a DIRECTED GRAPH ON A. This is also called a DIGRAPH on A. Basically, a "relation" is a subset of something. But what is that something? It is up to us to be clear about that.

(1)

(2) (a) No (not true for empty set) (b) Yes. (c) No.

(3)

(a) Pictorially, this relation S on B can be drawn as follows (there are many other ways...):

(b) This is the mod 3 relation restricted to {2,3,4,5,6,7,8}:

Note: We use double arrows to indicate (x,y) and (y,x) rather than two arrows as is sometimes done.

(6) Functional Relations - Section 2. Problems 4 - 10

(4) The set of all binary relations from {a,b} to {x,y} by definition, the set of all subsets of {a,b} x {x,y}. In characteristic function form this is

Those binary relations that are functions must include exactly one 1 in the first two columns and one 1 in the second two columns. There are four possibilities: 0101, 0110, 1001, and 1010 (rows 6, 7, 10, and 11). There are 12 relations that are not functions, shown in the table.

(5) S = {(3,6), (4,4), (5,5)} and S^(-1) = {(6,3), (4,4), (5,5)}.

(6)

(a) Explanation: |A x B| = mn. For any set S, |S|=k, there are 2^k subsets. Thus there are 2^(mn) subsets of A x B or, same thing, 2^(mn) relations from A to B.

(b) Explanation: Consider the definition of a function. Each x in A must be paired with a y in b, so the pair (x,y) must appear in the relation that defines the function exactly once. For each x in A there are |B|=n choices. List the elements of A as a1, a2, ... , am. There are n choices to pair with a1, n choices to pair with a2 , etc. until finally n choices to pair with am. The total number of choices is n*n*n* ... *n = n^m.

(7) There are 24 such vectors. Think about choosing the two sets {x1, x2}, {x3, x4, x5}. They must be disjoint and have union {1,2,3} if the inverse relation is to be functional. There are six possibilities for the pair of sets ({x1, x2}, {x3, x4, x5}): ({1}, {2,3}), ({1,2}, {3}), ({1, 3}, {2}), ({2,3}, {1}), ({3}, {1,2}), ({2}, {1,3}). These choices correspond, in order, to the following number of vectors: 6, 2, 2, 2, 6, 6. The total is 24 functions. To understand these numbers, look at the case ({x1, x2}, {x3, x4, x5})=({1}, {2,3}). We get {(1,1), (1,1), (2,2), (3,2), (3,2)} = {(1,1), (2,2), (3,2)} as a functional inverse corresponding to x1=x2=1, x3=2, x4=3, x5=3. The five other choice for the vector are x1=x2=1, x3=3, x4=2, x5=3; x1=x2=1, x3=3, x4=3, x5=2; x1=x2=1, x3=2, x4=2, x5=3; x1=x2=1, x3=2, x4=3, x5=2; x1=x2=1, x3=3, x4=2, x5=2. Note that we are counting the number of vectors, not the number of distinct functional inverses.

(8) There are 17 edges in the digraph. To explain, list them all or draw a picture of the digraph.

(9)

(10)

(7) One-to-one Functions - Section 2. Problems 11 - 14:

(11)

( a) and (b) are contrapositives of each other and hence logically equivalent. Both are correct definitions of injective or one-to-one.

(c) Consider A={a,b}, B={c}, f(a)=f(b)=c. The statement given is, in fact, the definition of a function. Thus, the assertion is that all functions are one-to-one or injective.

(d) Correct. This is the definition of one-to-one.

(12)

(a) g is one-to-one. If g(s)=g(t) then 3s-1 = 3t-1 or 3s = 3t or s = t. Thus, g is one-to-one.

(b) g is not onto. Note that image(g)={k: k=2 (mod 3)}.

(c) g is onto in this case. Proof: If s is in R the g((s+2)/3) = s.

(13)

(a) f is not one-to-one. Here is what the graph of x/(x^2+1) looks like:

(b) f is one-to-one. Solve for x=1/(f-2), valid if f is not 2. But f(x) = (2x+1)/x = 2 + 1/x is never 2.

(c) f(x) = (x-1)/(x+1) for all real numbers x != -1. The inverse function x(f) = (f+1)/(f-1) where f != 1. But f(x) = 1 - 2/(x+1) is never 1.

(14)

(a) Remember, for the allowable values of b, s=t if and only if b^s=b^t. Set s=logb(xy) and t=logb(x) + logb(y).

(b) The general rule is that log base b of x is k times log base b^k of x.

(8) Permutations and Counting Functions - Section 2. Problem 15 - 17:

NOTE: Here is a quick review of the three basic notations regularly used to specify permutations. The most basic is two-line notation. This is just a two-line table with the elements of the domain listed on the first line and the corresponding values of the permutation listed on the second line. The permutations

are in two-line notation. Two-line notation can be used to represent any function with finite domain. The second standard notation is one-line notation. This is used when the ordering on the domain is understood and is thus redundant. The above two permutations in one-line notation are

Given the one-line notation, it is easy to reconstruct the tables needed for the corresponding two-line notation. Where you have to be careful in using one-line notation is in those cases where a natural ordering of the domain might not be understood. For example, consider the permutation, in one-line notation,

of the eight characters shown. How do we construct the corresponding two-line notation? It is impossible unless the domain ordering of these symbols is specified. With two-line notation, there is no doubt:

The third basic way of describing permutations is cycle notation. The permutations (1 5 9 7 ) (2 8 4 6) and (1 9 4 8) (2 7 3 6) (5) are in cycle notation and represent the permutaions of {1, ... , 9} given above in two-line notation. The first has two cycles and the second has three. The cycle (1 5 9 7) specifies that the permutation sends 1 to 5, 5 to 9, 9 to 7, and 7 to 1. The cycles (5 9 7 1), (9 7 1 5), and (7 1 5 9) specify the same thing and can be used interchangeably. The order of cycles in cycle notation doesn't matter either: (1 5 9 7 ) (2 8 4 6) and (2 8 4 6) (1 5 9 7 ) are the same permutation. The cycle (5) specifies that the permutation sends 5 to 5. The element 5 is called a "fixed point" of the permutation.

(15)

(16)

(a) 3! = 6.

(b) 5*4*3 = (5)3 where (n)m is the falling factorial n(n-1) ... (n-m+1) also denoted by P(n,m), the m-permutations of n elements.

(c) If m>n the answer is zero. Otherwise, the answer is the falling factorial (n)m = n(n-1) ... (n-m+1). Another form for this answer is m!C(n,m) where C(n,m) is the binomial coefficient "n choose m." Choose in C(n,m) ways the image of size m of the function. There are m! ways to define a one-to-one function to that chosen image.

NOTE: For the next problem, we review the concept of a coimage of a function. Recall that the sets that are the elements of a partition are called the "blocks" of the partition. Here is a function f from {1,2, ... , 9} to {1, 2, 3, 4}:

The elements x of the set {2, 4, 7, 9} all have f(x) = 1. The elements x of {1, 3, 6} all have f(x)=2 and the elements x of {5, 8} all have f(x) = 3. The partition {{2, 4, 7, 9}, {1, 3, 6}, {5, 8}} of the domain {1,2, ... , 9} is called the "coimage of f" or the "coimage partition of f," denoted by coimage(f). If f: X -> Y and y is in the image(f)={f(x): x in X}, then let By = {x: x in X, f(x)=y}. The collection of sets By with y in image(f) is defined to be the coimage(f). The sets By are the blocks of the coimage(f). In the example just given, B1={2, 4, 7, 9}, B2={1, 3, 6}, B3={5, 8}, image(f)={1,2,3}, coimage(f)={B1,B2,B3}.

(17)

(a) Let the elements of the domain be {a,b,c} and the elements of the codomain be {u,v}. We can construct two onto functions with a given coimage {S, T}, one by taking S=Bu and T=Bv and the other by the reverse, S=Bv and T=Bu. The number of choices for {S,T} is the number of partitions of {a,b,c} into two blocks. There are three such partitions: {{a,b},{c}}, {{a,c},{b}}, and {{a}, {b,c}}. There are thus six onto functions from {a,b,c} to {u,v}.

(b) None. |Image(f)| is always less than or equal to |domain(f)|. For an onto function, Image(f)=codomain(f) which has five elements but the domain has only three. Thus no onto function is possible here.

(c) The number of possible coimages is equal to the number of partitions of a set of four elements into two blocks. Each such coimage gives rise to two onto functions, just like in part (a). There are various ways to organize the list of all partitions of four things{a,b,c,d} into two blocks {S, T}. There are three partitions of {a,b,c} into two blocks, listed for part (a) above as follows: {{a,b},{c}}, {{a,c},{b}}, and {{a}, {b,c}}. Each of these gives rise to two partitions of {a,b,c,d} into two blocks by first placing d in the first block listed and then in the second block listed: {{a,b,d},{c}}, {{a,c,d},{b}}, {{a,d}, {b,c}}, {{a,b},{c,d}}, {{a,c},{b,d}}, {{a}, {b,c,d}}. There is one partition missed here, the one where d is alone in a block {d}, namely {{a,b,c}, {d}}. There are thus seven partitions of four things into two blocks and 14 onto functions.

(d) If m<n there are none. Otherwise, there are two natural methods for solving this problem. The first method is to use the idea of (c). If S(m,n) denotes the number of partitions of m things into n blocks, we have shown in part (c) (extend the argument) that S(m,n)=nS(m-1,n)+S(m-1,n-1). For (c) this is S(4,2)=2S(3,2) + S(3,1)=2*3+1=7. Since c(m,n)=n!S(m,n), we can multiply both sides of S(m,n)=nS(m-1,n)+S(m-1,n-1) by n! to get c(m,n)=n(c(m-1,n) + c(m-1,n-1)). It is possible to get this latter recursion directly: There are two types of onto functions f from {1,2, ... , m} to {1,2, ... , n}. Type 1 are those f such that {f(1), ... , f(m-1)} = {1,2, ... , n}. Those functions satisfy the "onto" property without considering f(m). For each such function we can choose any of n values for f(m) and still have an onto function. Thus, there are n*c(m-1,n) such functions of Type 1. Type 2 functions are those where f(m) matters in satisfying the onto property. Again, there are n choices for f(m). If f(m) = y then {f(1), f(2), ... , f(m-1)} must equal {1,2, ... , n} - {y}. There are c(m-1,n-1) ways to make that happen so the number of Type 2 functions is n*c(m-1,n-1) since there are n choices for y. Once again, we get c(m,n)=n(c(m-1,n) + c(m-1,n-1)). Below are the tables for S(m,n) and c(m,n), 1<= m,n <= 5.

For example, to compute the number of onto functions from a set of 5 elements to a set of three elements, look up c(5,3) from the table (answer 150). Or, look up S(5,3) and multiply by 3! to get 150. The general answer is expressed as either S(m, n) n! or as c(m, n).

(18) Suppose we first choose the set to be the Image(f). Then, by the problem (17), there are S(m, k) k! (or c(m, k)) functions with that specified Image(f). But the set Image(f) can be chosen in (binomial coefficient) C(n,k) different ways. Thus the final answer is C(n,k)S(m, k)k!.

(9) Inverse Images - Section 2. Problems 19-21:

(19)

(a) Assume f:X -> Y and g:Y -> Z are functions and g o f: X -> Z is onto. Must f and g be onto? The answer is no. Let X=Y={a,b} and let Z={c}. Define f(a)=f(b)=b. Define g(a)=g(b)=c. then g o f: X -> Z is onto but f is not onto. In this example, g is onto. That is always the case. To show that g is onto, we pick any z in Z and show that there is a y in Y such that g(y)=z. Since g o f is onto, there is an x in X such that g o f(x) = g(f(x)) = z. Take y=f(x).

(b) In this case, f must be one-to-one, but g need not be.

(20)

(21)

(a) False. Find the simplest counter example you can!

(b) False. Suppose X={a} and Y={c,d}. Let f(a)=c and take the set C of the problem to be Y. Is the statement true for this example? Remember, to show that P=Q for two sets P and Q, you must show that P is a subset of Q and Q is a subset of P.

(c) True.