# (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) 