## (solution) please read carefully and finish on time if you have no

please read carefully and finish on time if you have no confidence to finish it, then don't pick it up

Homework 3 CSE 191 Fall 2016 Due: Friday 10/7/2016

This assignment has some examples of different proof methods as well as problems regarding set

notation. There are a total of 100 points on the assignment.

(1) (8 points) Prove that there is no positive integer n such that:

200 &lt; (n + 1)2n &lt; 300

Hint: try a proof by cases.

(2) (8 points) Prove or disprove the following statement:

If a and b are rational numbers then ab is a rational number.

(3) An integer m is a multiple of an integer a if there exists an integer k such that m = ak.

E.g., m is a multiple of 2 if there exists an integer c such that m = 2c.

E.g., m is a multiple of 5 if there exists an integer d such that m = 5d.

(8 points) Prove that if n2 is a multiple of 5, then n is a multiple of 5.

?

(4) (8 points)

Prove

that

5 is not a rational number. (hint: look at how the book/lecture

?

shows 2 is not rational)

(5) Let A, B, C, and D be the following sets:

A = {1, 2, 3, 4}

B = {1, 1, 3}

C = {1, {3}, 1, {1, 3}, {3, 3, 1}, {{1, 3}}}

D = {2, 2, 2, 3, 3, 4}

Provide the answer to the following questions about the above sets, providing a short

justification for each (1+1 points each, for a total of 32 points).

(5a) Is B ? A?

(5b) Is B ? C?

(5c) Is B ? D?

(5d) What is |A|?

(5e) What is |B|?

(5f) What is |C|?

(5g) What is |D|?

(5h) Is B ? A?

(5i) Is B ? C? (5j) What is A ? C?

(no justification needed for (5j))

(5k) What is A ? C?

(no justification needed for (5k))

(5l) What is B × D?

(no justification needed for (5l))

(5m) What is P(B)?

(no justification needed for (5m))

(5n) Is B ? P(C)?

(5o) Give a partition of A by 3 sets.

(5p) Does a partition of B by 3 sets exist? (6) For each of the following statements, state if it is always true for any two set s A and B. If

the statement is not always true, provide a counter example (4 points each, for a total of

20 points).

(6a) If A ? B, then A ? B.

(6b) If A ? B, then A ? B.

(6c) If A = B, then A ? B.

(6d) If A = B, then A ? B.

(6e) For any two sets, A and B, if A ? B, then A2 ? B2

(7) Using the set identities in section 3.5 of the zyBook, name the set identity used to justify

each of the identities given below (2 points each, for a total of 10 points)

(7a) (B ? C) ? (B ? C) = U

(7b) A ? (A ? B) = A

(7c) A ? (B ? C) = A ? (B ? C)

(7d) (B ? A) ? (B ? A) = (B ? A)

(7e) ((A ? B) ? C) ? ? = ?

(8) Prove or disprove that ? = {?}. (6 points)

Solution details:
STATUS
QUALITY
Approved

##### Pay using PayPal (No PayPal account Required) or your credit card . All your purchases are securely protected by .

STATUS

QUALITY

Approved

Sep 13, 2020

EXPERT

Tutor 