As usual, let’s review the definitions before starting to solve the exercise.
Definition: “The sets A and B have the same cardinality if and only if there is a one-to-one correspondence from A to B. When A and B have the same cardinality, we write |A| = |B|.”
Definition: “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.”
Both definitions were taken from the textbook Discrete Mathematics and its Applications by Rosen.
Now, using the definitions above, let’s solve the exercise.
Table of Contents
- a) the integers greater than 10
- b) the odd negative integers
- c) the integers with absolute value less than 1,000,000
- d) the real numbers between 0 and 2
- e) the set A×Z+ where A={2,3}
- f) the integers that are multiples of 10
a) the integers greater than 10
This set is countably infinite.
The one-to-one correspondence can be specified as follow:
f(x) = x – 10
You can easily prove that the above function is a one-to-one correspondence. First, you prove that the function is one-to-one (see an example here). Secondly, you show that the function is onto (see an example here).
Another way to show the correspondence is by listing the set in a sequence as follows:
11, 12, 13, 14, 15, …
b) the odd negative integers
The set is countably infinite.
-1, -3, -5, -7, …
c) the integers with absolute value less than 1,000,000
The set is finite.
Notice that because the elements of the set are the ones with absolute values less than 1 million, it is the same that the set of integers from 0 to 1 million. Therefore, it is a finite set.
d) the real numbers between 0 and 2
Uncountable.
e) the set A×Z+ where A={2,3}
Countably infinite.
If A=(2,3), then AxZ+={(a,b)| a∈{2,3} ^ b ∈Z+}.
The one-to-one correspondence can be specified as follows:
(2,1) —- 1
(3,1) —- 2
(2,2) —- 3
(3,2) —– 4
….
f) the integers that are multiples of 10
Countable infinite.
You can list the elements of the set as follow:
10, -10, 20, -20, 30, -30, 40, -40, …
Related posts:
- Give an example of two uncountable sets A and B such that A−B is
- Show that if A and B are sets and A⊂B then |A|≤|B|
- Show that a finite group of guests arriving at Hilbert’s fully occupied Grand Hotel can be given rooms without evicting any current guest.
- 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
- Show that if A, B, C, and D are sets with |A|=|B| and |C|=|D|, then |A×C|=|B×D|