13.2: Properties
( \newcommand{\kernel}{\mathrm{null}\,}\)
The following facts outline some relationships countability and the set operations. They can be used to more easily prove that a set is countable or uncountable using the already-known countability or uncountability of a related set.
- Every subset of N is countable.
- If there exists an injection A↪N, then the set A is countable.
- Suppose A⊆B. If B is countable, then so is A.
- Suppose A⊆B. If A is uncountable, then so is B.
- If A and B are countable, then A∪B and A∩B are both countable.
- Proof outline.
-
- Assume A⊆N. If A is finite, then it is countable by definition. So assume that |A|=∞. We can construct a sequence {ak} that contains each element of A exactly once as follows.
a0= smallest number in A,a1= next smallest number in A,a2= next smallest number in A,⋮
Therefore, A is countable.- If f:A↪N is injective, then f:A→f(A) is a bijection, so that A and its image f(A) have the same size. But f(A) is countable by Statement 1, so using the definition of countable along with Fact 12.3.2, conclude that A is countable.
- If B is countable, then by definition there exists a bijection f:B→N. Then f|A:A→N is an injection. Apply Statement 2.
- This is the contrapositive of Statement 3, under the common assumption A⊆B.
- For A∩B, consider A∩B⊆A and apply Statement 3.
Now consider A∪B. For simplicity, we will assume A∩B=∅, so that A∪B=A⊔B. Since A and B are countable, we can write their elements as sequences:
A={a0,a1,a2,…},B={b0,b1,b2,…}.
We can then write the elements of A⊔B in a sequence by interleaving these two sequences:A⊔B={a0,b0,a1,b1,a2,b2,…}.
Checkpoint 13.2.1
Prove A∪B is countable even in the case A∩B≠∅.
- Hint.
-
Consider the sets
A′=A∖(A∩B),B′=B∖(A∩B),C=A′⊔B′.
Then A∪B is the disjoint union of C and A∩B.
The set of prime numbers is countable, since it is a subset of N.
The unit interval (0,1) on the real number line is uncountable because it contains the uncountable subset C from Lemma 13.1.1.
The Cartesian product set R2=R×R is uncountable because it has an uncountable subset: the x-axis has the same size as R.