Q1. Let A be the following set:       A = {1, {2},‘1, {2} }}

Determine each of the following cardinalities:

│A │ = │p(A)│ = │A x A │ = │A n p(A)│ =

Q2. Complete each of the following definitions. Be precise.

The power set of a set S is

The Cartesian product of sets A and B is

A function f : X - Y is called injective if

A function f : A - B is called surjective if

(4 pts) Q3. Let A, B, and C be subsets of the universal set 八 . For Q3a and Q3b, draw a Venn diagram with

sets A, B and C in general position, then shade in the regions corresponding to the given sets.

Q3a. Venn diagram for     (A u C) - (A - B).

Q3b. Venn diagram for    (C - A) o (A U B).

Q3c. Compare the Venn diagrams from parts 3a and 3b. What do you conclude?

TRuE.oR.FALsE QuEsT1oNs.

Circle the correct responses.   No justification is needed.

(3 pts) Q4. Let A and B be finite sets.

(a) If f : A - B is an injective (1-1) function, then |A| < |B|.

(b) If |A| < |B|, then every function f : A - B is injective (1-1).

(c) If |A| < |B|, then there exists an injective (1-1) function f : A - B .

(d) There exists a surjective (onto) function f : A - p(A).

(e) There exists a surjective (onto) function f : ╱A x B) - ╱B x A、.

(f) If |A| < |B|, then no function f : A - B is surjective.

T

T

T

T

T

T

F

F

F

F

F

F

(3 pts) Q5. Let u be a universal set u with |u| > 2.

Which of the following statements are true for all subsets A and B of u ?

(a) If A x B = Ø, then A = Ø or B = Ø .

(b) A x B = B x A.

(c) If A C B, then p(A) C p(B).

(d) A o B C A u B .

(e) A e p(A).

T

T

T

T

T

F

F

F

F

F

(f) If A C B, then A C B .

T

F

(3 pts) Q6. Let f , g, and h be three functions defined as follows:

f : ❩ - ╱❩ x ❩、

f (x) = (x, 5 - x)

g :  ╱Q＋ x Q＋、- Q＋

g(r, s) = rs

h : ❩ - N

h(n) = 2n2 + 1

Note. Q＋ denotes the set of positive rational numbers.

Which of the following statements are true regarding the above functions?  Circle the correct response .

(a) f is injective (1-1).

T

F

(b) f is surjective (onto).

T

F

(c) g is injective (1-1).

T

F

(d) g is surjective (onto).

T

F

(e) h is injective (1-1).

T

F

(f) h is surjective (onto).

T

F

LoNc.ANswER QuEsT1oNs.

Detailed solutions are required.

(5 pts) Q7. Let X ,  Y ,  and Z be subsets of the universal set 八 .   Prove the identity below using only the

set identities listed on Page 10. Justify each step by giving the name or number of the corresponding identity.

Do not skip steps or combine several distinct identities into a single step .  You may apply the same identity multiple times in one single step,  but never use more than one  distinct Law per step .  Do not omit necessary parentheses .

Note. Your solution should only need 6 to 12 steps, assuming each step makes use of exactly one Law.

╱x - 2、u╱Y - 2、= 2 u╱x U Y、

(4 pts) Q8. Let f : ╱R＋ x R＋、- ╱R＋ x R＋、be the function defined by f ╱r, s、= ╱ 2r, rs、.

Note. R＋ denotes the set of positive real numbers.

Q8a. Prove that f is injective (one-to-one).

Q8b. Prove that f is surjective (onto).

Q9. Let A and B be subsets of the universal set.

Prove each of the following two theorems, starting your proofs as indicated. Q9a. Theorem 1. If ╱A u B) C A,  then   B C ╱A n B、.

Proof of Theorem 1. (complete this proof )

Assume ╱A u B) C A. Our goal is to prove that	/	、	.
To achieve our goal, we will take an arbitrary element x e B, and we will prove 、 Let x e B be an arbitrary element of B . Then...                                                     (complete this proof )

Q9b. Theorem 2. If B C ╱A n B、,  then ╱A u B、C A.

Proof of Theorem 2. (complete this proof )

Assume B C╱A n B、. Our goal is to prove that / To achieve our goal, we will take an arbitrary element x e (A u B), and we will prove 、 Let x e ╱A u B、be an arbitrary element of A u B . Then...                                  (complete this proof )

Q9c. What have you proved in Q9a. and Q9b. ?  Give a single statement that combines Theorem 1 and Theorem 2 using appropriate connective words such as and, or, if, only if, if and only if, etc.

The overall Theorem proved in Q9: