Discrete Computational Structures Homework Assignment #6

CS 230 : Discrete Computational Structures

Homework Assignment #6

Suggested Reading: Rosen Section 2.5
For the problems below, explain your answers and show your reasoning.
1. [14 Pts] Show that the following sets are countably infinite, by defining a bijection between
N (or Z
+) and that set. You do not need to prove that your function is bijective.
(a) [4 Pts] the set of non-negative integers divisible by 5
{5n | n ∈ N}
(b) [5 Pts] the set of integers divisible by 5
{(−5n, 5n) | n ∈ N}
(c) [5 Pts] {0, 1, 2, 3} × N
{((0, n),(1, n),(2, n),(3, n)) | n ∈ N}
2. [14 Pts] Determine whether the following sets are countable or uncountable. Prove your
answer. To prove countable, describe your enumeration precisely, There is no need to define
a bijection.
(a) [7 Pts] the set of real numbers with decimal representation consisting of all 5’s (5.55
and 55.555 . . . are such numbers).
This can be enumerated by defining the set of all real numbers with n fives before and
m fives after the decimal. (n, m) ∈ N × N, where n and m count the number of fives
before and after the decimal. N × N is countably infinite, so these numbers are also
countably infinite.
(b) [7 Pts] the set of real numbers with decimal representation consisting of 1’s, 3’s and 5’s.
Suppose r ∈ R, where r = 0.di1di2di3...dij , for dij ∈ {1, 3, 5}
r1 . d11 d12 d13 ...
r2 . d21 d22 d23 ...
r3 . d31 d32 d33 ...
r4 . d41 d42 d43 ...
... ... ... ... ...
Now, z = 0.z1z2z2z3, where
zi =
(
1 dii ∈ {3, 5}
5 dii ∈ {1, 3}
In general, for all k, zk 6= dkk so z 6= rk
So, z 6∈ {r1, r2, r3, ...}, but z is in all numbers with digits 1, 3, 5 and within [0, 1]
We assume [0, 1] ∈ {r1, r2, r3, ...}. Contradiction! This set of numbers is uncountable.
3. [6 Pts] Prove that the set of functions from N to N is uncountable, by using a diagonalization
argument. If all functions from N to N is countable, then these functions are listable as
F = {f1, f2, f3, ...}
I define a function g(x) = 2f(x). However, this makes g(x) 6∈ F, but still from N to N
Contradiction! This set of functions is uncountable.
4. [6 Pts] Argue that a countably infinite union of countable infinite sets is countably infinite.
Suppose S1, S2, S3, ..., Si are countably infinite sets. These sets are countable as {si1, si2, si3, ..., sij}.
Even if all these sets are disjoint, the union can be counted as {s11, s12, s13, ..., s1j , s21, s22, s23, ..., s2j , ...}.
If they aren’t disjoint, then those unions will too be countable. They simply have less elements
because they will have repeated values between sets.