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 < (n + 1)2n < 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)