Q1. In each part, give an example of a non-empty binary relation R on the set A = {1, 2, 3} that has the prescribed properties:                                                  (you do not need to justify your answers )

[Q1 out of 4 points]

Q2. Let  A = {f1 , f2 , f3 , f4 , f5 , f6 , f7 , f8 , f9 },

where f1 , . . . , f9  are the following functions from R to R:

f1 (x) = x2

f2 (x) = (x _ 1)2

f3 (x) = x2 _ 1

f4 (x) = 2x

f5 (x) = 0

f6 (x) = 1

f7 (x) = 2x _ 1

x + 1

2

2

Let R be the relation on A defined by the following rule:

For all fi , fj  e A,        /fi , fj、e R   if and only if   fi (1) = fj (1)

Note. R is an equivalence relation on A but you do not need to prove that in order to answer these questions.

[Q2 out of 6 points]

Q3.   Let f and g be functions defined as follows:

f : /Q × Q、→ /Q × Q、

f (q, r) = /q + r, 2q、

g : Q → /Q × Q、

g(x) = /3x, 5 _ x、

For the following questions, no justification is needed; only your final answers will count.

[Q3 out of 6 points]

MuLrIPLE.CHoIcE QuEsrIoNs.

Indicate the correct responses in the appropriate boxes.   No justification is needed.

Q4. Let A and B be finite sets, and let f : A → B and g : B → A be two functions.  Which three of the following statements are true in general?

(A)  If f_1  exists, then f_1 。f is the identity function on B .

(B)  If f_1  exists, then f_1 。f is the identity function on A.

(C)  If f_1  exists, then f is a bijection.

(D)  If f and g are both bijections, then f 。g = g 。f .

(E)  If f and g are both bijections, then f 。g is a bijection.

(F)  If f and g are both bijections, then f 。g is the identity function.

True statements of Q4:

and

and

[Q4 out of 3 points]

Q5. Let A and B be finite sets. Which two of the following statements are true in general? (A)  The set of all binary relations from A to B is p /A × B、.

(B)  The set of all binary relations on the set A is p /A、.

(C)  The number of binary relations from A to B is IAI . IBI.

(D)  The number of binary relations from A to B is 2|A|. |B| .

(E)  If A = Ø, then there are no binary relations from A to B .

True statements of Q5:

and

[Q5 out of 2 points]

Q6. Let X = {1, 2, 3}. Recall that p(X) =,S : S S X}.

Define a relation R on p(X) according to the following rule:

For all A, B e p(X),     /A, B、e R   if and only if    A n B  Ø .

Which three of the following statements are true?

(A)  R is reflexive.

(B)  R is symmetric.

(C)  R is antisymmetric.

(D)  R is transitive.

(E)   /{3}, X、e R.

(F)   /X, X、e R.

True statements of Q6:

and

and

[Q6 out of 3 points]

Q7. Let X = {1, 2, 3, 4, 5, 6, 7}.

Which two of the following collections is not a partition of X ?

(A)  91  = {{1, 4, 5}, {2, 3, 6, 7}}

(B)  92  = {{1, 2, 3}, {3, 4}, {4, 5, 6, 7}}

(C)  93  = {{1, 2}, {4, 5, 6, 7}}

(D)  94  = {{1, 2, 3, 4, 5, 6, 7}}

(E)  95  =    {1}, {2}, {3}, {4}, {5}, {6}, {7}

The non-partitions of Q7:

and

[Q7 out of 2 points]

LoNc.ANswER QuEsrIoNs.

Detailed solutions are required.

Q8. Let A, B, and C be sets, and let f : A → B and g : B → C be two functions.

For the following statement, determine whether it is true or false.

. If you claim that the statement is true, give a proof.

. If you claim that the statement is false, give a concrete counterexample (i. e.  specify the elements of the sets A, B, and C and the functions f : A → B and g : B → C

which demonstrate that the statement can be false).

Statement:  If f and g are both surjective, then g · f is surjective.

[Q8 out of 5 points]

Q9. Let R be a binary relation on the set ❩ defined by the following rule:

For all m, n e ❩ ,    /m, n、e R   if and only if   m = qn   for some q e Q+ Note. Q+  denotes the set of positive rational numbers.

Prove that R is an equivalence relation on ❩ .

[Q9 out of 5 points]