Homework 3 (assigned July 6, due July 12)

Reading: Rosen chapter 2, sections 2.1–2.3.

Written assignment : Solve the following "Do" exercises and assigned problems. Only solutions to the assigned problems should be turned in. Note: You are responsible for the material covered in both "Do" exercises and assigned problems.

"Do" Exercises (not to be handed in):

1. Sets A, B, C, D, E are defined as follows. The variables x, y, z assume values from the set of natural numbers N = {0, 1, 2, …}.
   A = {0, 1, 2, 3}
   B = {x | (∀y ∈ A)(x > y²)}
   C = {z | z ∉ A ∪ B}
   D = {x | (∃y ∈ C)(x² = y)}
   E = {z | (z ∉ B) ∧ (∃y) (z = y²)}
   In each of the following cases, find the required element(s).
   • The smallest element of B.
   • Four elements of ℘(B), the power set of B.
   • All the elements of C.
   • All the elements of D.
   • All the elements of E.
   • The largest element of C − E.
   • The smallest element of A ∪ D.

2. Prove the following statements using set containment arguments.
   • For all sets A and B, A ⊆ B if and only if A ∪ B = B.
   • For all sets A, B, and C, A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).

3. Suppose that 100 senators voted on three separate senate bills as follows: 70% of the senators voted for the first bill, 65% voted for the second bill, and 60% voted for the third bill. At most what percentage of the senators voted for all three bills?

4. Let [x] denote the greatest integer less than or equal to x. For example, [4.3] = 4, [−2.1] = −3, and [7] = 7. The function that maps x to [x] is called the floor function.
   Let f : R → Z be defined by f (x) = [x/2], where R is the set of real numbers and Z is the set of integers.
   • Is f one-to-one? Prove or disprove.
   • Is f onto? Prove or disprove.

5. Is the function f (x) = x + 1 a bijection when the domain and the codomain are N, the set of natural numbers? Is it a bijection when the domain and the codomain are Z, the set of integers? Prove your answers.

6. Theorem. If S is a finite set with n elements, then S has 2ⁿ subsets.
   • Prove the theorem by induction on n.
   • Give a direct proof of the theorem.

Assigned problems (to be handed in):

1. True or false? If ℘(A) = ℘(B) holds for two sets A and B, then A = B. Prove your answer. (5 points)
   (℘(S) denotes the power set of the set S.)

2. Is cancellation possible for the Cartesian product? That is, if X × Y = X × Z for some sets X, Y, and Z, does it necessarily follow that Y = Z? Prove your answer. (5 points)

3. Prove that for any two sets A and B, (A − B) ∪ (B − A) = (A ∪ B) − (A ∩ B). You should prove set containment in both directions. (5 points)

4. Let A = {x ∈ R : x² − 2x − 3 < 0} and let B = {x ∈ R : −1 < x < 3}, where R is the set of real numbers. Prove A = B. You should prove set containment in both directions. (10 points)

5. How many numbers are left in the set {1, 2, 3, …, 1000} after all multiples of 2, 3, 5, and 7 are removed? Use the inclusion-exclusion principle. (5 points)

6. Decide which of the following functions Z → Z are one-to-one and which are onto. Z is the set of integers. Prove your answers. Does anything in the answer change if we consider them as functions R →R, where R is the set of real numbers? (5 points for each part)
   1. f (x) = 1 + x.
   2. f (x) = 1 + x².
   3. f (x) = 1 + x³.
   4. f (x) = 1 + x² + x³.

7. The letter grades in the US and Canada usually come from the following set X = {A, B, C, D, E, F}, where A is the highest grade and F is the lowest. In the country of Mathematica, the letter grades also come from the set X, but they have a different meaning. (For example, F could mean the highest grade, and D might have no meaning at all!) Pali Básci (a famous mathematician) traveled a lot from the US to Mathematica, and as an aid for converting grades, he came up with a function f : X → X that maps the US-style grades to the Mathematica-style grades. Consider the following two independent scenarios:
   1. Pali Básci observed that f  is one-to-one. Must f  be onto? Prove or give a counterexample. (5 points)
   2. Pali Básci observed that f  is onto. Must f  be one-to-one? Prove or give a counterexample. (5 points)
   3. What is the last name of Pali Básci? (1 bonus point)

8. Poll for Denis's office hours. Vote for one. (5 points)