Discrete Computational Exercises Section 2-5 Essay
COT3103
10/21/2014
Exercises Section 2.5
2. Determine whether each of these sets is finite, countably infinite, or uncountable. For those that are
countably infinite, exhibit a one to one correspondence between the set of positive integers and that
set.
a. The integers greater than 10.
This is countably infinite.
Starting from the first integer greater than 10, which is 11, one can infinitely count upwards since
there is no boundary on the right side of the number line for this instance.
The equation Ζ(x) = x + 11 can be used to show a one to one correspondence. x: 1, 2, 3, 4, 5, 6, ...
Ζ(x): 11, 12, 13, 14, 15, 16 ...
b. The odd negative integers.
This is countably infinite.
Starting from the first odd negative integer closest to 0, which ... Show more content on
Helpwriting.net ...
a. Integers not divisible by 3.
This set is countable.
The integers in the set are Β±1, Β±2, Β±4, Β±5, Β±7, and so on.
We can list these numbers in the order 1, β1, 2, β2, 4, β4, 5, β5, 7, β7, ... , thereby establishing the
desired correspondence. x: 1, 2, 3, 4, 5, 6, ...
Ζ(x): 1, 1, 2, 2, 3, 3, ...
b. Integers divisible by 5 but not by 7.
This is countably infinite.
This is similar to part (a); we can simply list the elements of the set in order of increasing absolute
value, listing each positive term before its corresponding negative: (x): 1, 2, 3, 4, 5, 6, 7, 8, 9...
Ζ(x): 5, 5, 10, 10, 15, 15, 20, 20, 25, 25, 30, 30 40, 40, ...
c. The real numbers with decimal representations consisting of all 1s.
This set is countable but a little tricky.
We can arrange the numbers in a 2 dimensional table as follows:
Thus we have shown that our set is the countable union of countable sets (each of the countable sets is
one row of this table).
Therefore by Exercise 27, the entire set is countable.
For an explicit correspondence with the positive integers, we can zigzag along the positive sloping