As usual, we first go to the definitions.
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 that we have the definitions, we can solve the exercises.
a) the negative integers
We know from previous courses in mathematics that negative numbers are infinite. Now, we must show whether it is countable or not.
To show that this set is countable, we must find a one-to-one correspondence from this set (the set of negative integers) and the set of integers.
If we assign to each negative number, the corresponding positive number, we have a one-to-one correspondence.
-1 —— 1
-2 —— 2
-3 —— 3
…
Because we found a one-to-one correspondence with the set of positive numbers, we proved that the set of negative integers and the set of positive integers have the same cardinality. Therefore, the set of negative integers is countable infinite.
If you want to do it in a different way, you can do it as follows.
Consider the following function from the set of negative integers to the set of positive integers:
f(x) = -x
Let’s suppose that f(a)=f(b).
-a=-b, therefore a=b. we proved is a one-to-one function
Now let’s prove that is onto.
Let x be a positive integer, the corresponding value in the domain for any positive integer x is -x. Therefore, it is onto, because every element in the range or image has a corresponding element in the domain.
Therefore, the set of negative integers is countably infinite.
b) the even integers
Another way you can show that a set is countably infinite is by listing the elements of the set in a sequence.
In this case, we can list the elements of this set as follows:
0, 2, -2, 4, -4, …
Therefore, the set is countably infinite.
Alternatively, we can find a function that assigns to each element of the set of even integers a positive integer and prove that it is a one-to-one correspondence.
c) the integers less than 100
This set is also countably infinite. Notice that the integers less than 100 also include the negative integers, therefore it is infinite.
We can list the elements of the set in the following sequence:
99, 98, 97, 96, ….
d) the real numbers between 0 and 21
This set is uncountable.
e) the positive integers less than 1,000,000,000
This set is finite. Notice that the negative integers are not included, and the positive integers that are included are less than 1 billion.
f) the integers that are multiples of 7
We can list all the multiples of 7 in the following infinite sequence:
0, 7, -7, 14, -14, 21, -21, …
Therefore, the set is countably infinite.
Related posts:
- Show that if A and B are sets and A⊂B then |A|≤|B|
- Determine whether each of these sets is finite, countably infinite, or uncountable.
- Show that a finite group of guests arriving at Hilbert’s fully occupied Grand Hotel can be given rooms without evicting any current guest.
- Give an example of two uncountable sets A and B such that A−B is
- Show that if A, B, C, and D are sets with |A|=|B| and |C|=|D|, then |A×C|=|B×D|