Math 3100/5100 - Written Homework 3
Due: Thursday, January 30 at 11:59 pm on Gradescope
Complete the following problems worth 35 total points. You must show all work and include justifications to receive full credit. When submitting your work on Gradescope, please double check that your scans/images are clear and that you matched each problem with the correct page(s) of your work when prompted.
1. (4 points) To show that the set A of odd numbers is countable, we considered in class the function f : N → A such that f (k) = 2k − 1. Prove that f is a bijection.
2. (4 points) To show that the set of integers Z is countable, we considered in class the function f : N → Z such that
Prove that f is a bijection.
3. (5 points)
Definition. Let Λ be a nonempty set and suppose that for each α ∈ Λ, there is a correspond- ing set Aα . The family of sets {Aα | α ∈ Λ} is called an indexed family of sets indexed by Λ . Each α ∈ Λ is called an index and Λ is called an indexing set.
Let Λ be a nonempty subset of N. Let {Aα }α ∈Λ be an indexed family of countable sets. Prove that ∪α ∈ΛAα is a countable set.
(Hint: Since each Aα is countable, there is an injection gα : Aα → N. Define f : ∪α ∈ΛAα → N×Nby f(x) = (gα0 (x), α0), where α0 is the smallest natural number of Λ such that x ∈ Aα0 . Show that f is injective).
4. (4 points) Let a, b, candd be any real numbers such that a < band c < d. Show that [a, b] and [c.d] have the same cardinality.
5. (4 points) Show that (0, 1] and [0, 1] have the same cardinality.
6. (4 points) Let P and Q be infinite sets. Prove that iff : Q → P is a bijection then Q is uncountable if and only ifP is uncountable. Do not use proof by contradiction.
7. Recall that a sequence a = {ak}
∞
k=1 of numbers is an infinite list
a = (a1 , a2 , a3, a4 , ...)
where each element akis a number. Let S be the set of sequences whose elements are either
0 or 1, in other words,
For example, the following sequences are elements of the set S:
a = (0, 0, 0, 0, 0, 0, ...) ∈ S
b = (0, 1, 0, 1, 0, 1, ...) ∈ S
c = (0, 0, 1, 1, 0, 0, ...) ∈ S
d = (1, 1, 1, 1, 1, 1, ...) ∈ S
(a) (3 points) Give two non-trivial examples of functions from N to S. (b) (4 points) Consider the function f : S → P(N) defined as
f (a) = {k ∈ N | ak = 1}
where P(N) is the power set of N. Hence,f takes a sequence a ∈ S and outputs the indices where a is equal to 1. For example:
f (0, 0, 0, 0, 0, 0, 0, 0, ...) = 0/
f (1, 0, 1, 0, 1, 0, 1, 0, ...) = {1, 3, 5, 7, ...}
f (0, 0, 1, 1, 0, 0, 0, 0, ...) = {3, 4}
f (1, 1, 1, 1, 1, 1, 1, 1, ...) = {1, 2, 3, 4, 5, 6, ....} = N
Prove that f : S → N is a bijection.
(c) (3 points) Combine part (b), Problem 6 and Cantor’s theorem to thoroughly explain whether S is countable or uncountable.
8. (BONUS, 5 points) Prove the following generalization of the result of Problem 3: if Λ is a countable set, and {Aα }α ∈Λ is an indexed family of countable sets, then ∪α ∈ΛAα is a countable set.