Relevant definitions:
“A set that is either finite or has the same cardinality as the set of positive integers is called countable. A set that is not countable is called uncountable. When an infinite set S is countable, we denote the cardinality of S by א0 (where א is aleph, the first letter of the Hebrew alphabet). We write |S| = א0 and say that S has cardinality aleph null.”
“The function f is a one-to-one correspondence, or a bijection, if it is both one-to-one and onto. We also say that such a function is bijective.”
The definitions above are from the textbook Discrete Mathematics and its Applications by Rosen.
Table of Contents
- a) integers not divisible by 3
- b) integers divisible by 5 but not by 7
- c) the real numbers with decimal representations consisting of all 1s
- d) the real numbers with decimal representations of all 1s or 9s
According to the previous definitions, to prove that a set is countably infinite, we just need to find a one-to-one correspondence between the set and the set of positive integers.
One way we can find such correspondence is to list the elements of the set, and the bijection will be to assign the position of each element to the element itself.
a) integers not divisible by 3
Let S be the set of all multiples of 3.
Z-S is a subset of Z and is the set of integers not divisible by 3.
We can list this set as follows:
0, 1, -1, 2, -2, 4, -4, 5, -5, 7, -7, …
We can assign to each element the index in the list, 1, 2, 3, .. and this is a bijection to the set of integer numbers.
Therefore, this set is countably infinite.
b) integers divisible by 5 but not by 7
As this set is a subset of the set of integer numbers, we can proceed in the same way as in the previous exercise.
5, -5, 10, -10, 15, -15, 20, -20, 25, -25, 30, -30, 40, -40, …
Therefore, the set is countably infinite.
c) the real numbers with decimal representations consisting of all 1s
We can list the elements of this set as follow:
1, 1.1, 11, 11.1, 11.11, 1.11, 111, 111.1, 111.11, 1.111, …
Therefore, this set is countably infinite.
d) the real numbers with decimal representations of all 1s or 9s
Let S1 be the set of real numbers with decimal representations of all 1s. We know that this set is countably infinite (previous exercise).
Let S2 be the set of real numbers with decimal representations of all 9s. Following a similar approach to the previous exercises, we can conclude that this set is also countable infinite.
Theorem 1 from the textbook states that “If A and B are countable sets, then A ∪ B is also countable.”
This set can be expressed as S1 U S2.
Therefore, it is countably infinite.
Related exercises:
- 3. Determine whether each of these sets is countable or uncountable. For those that are countably infinite, exhibit a one-to-one correspondence between the set of positive integers and that set
- 6. Suppose that Hilbert’s Grand Hotel is fully occupied, but the hotel closes all the even numbered rooms for maintenance. Show that all guests can remain in the hotel
- 7. Suppose that Hilbert’s Grand Hotel is fully occupied on the day the hotel expands to a second building which also contains a countably infinite number of rooms. Show that the current guests can be spread out to fill every room of the two buildings of the hotel
- 8. Show that a countably infinite number of guests arriving at Hilbert’s fully occupied Grand Hotel can be given rooms without evicting any current guest
- ∗9. Suppose that a countably infinite number of buses, each containing a countably infinite number of guests, arrive at Hilbert’s fully occupied Grand Hotel. Show that all the arriving guests can be accommodated without evicting any current guest
