EF Properties

Section 13.2 Properties

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.

🔗

Proposition 13.2.1. Countability properties.

🔗

🔗
Every subset of $N$ is countable.
🔗
If there exists an injection $A ↪ N,$ then the set $A$ is countable.
🔗
Suppose $A \subseteq B .$ If $B$ is countable, then so is $A .$
🔗
Suppose $A \subseteq B .$ If $A$ is uncountable, then so is $B .$
🔗
If $A$ and $B$ are countable, then $A \cup B$ and $A \cap B$ are both countable.

🔗

Proof outline.

Assume $A \subseteq N .$ If $A$ is finite, then it is countable by definition. So assume that $| A | = \infty .$ We can construct a sequence ${a_{k}}$ that contains each element of $A$ exactly once as follows.
$\begin{aligned} a_{0} & = smallest number in A, \\ a_{1} & = next smallest number in A, \\ a_{2} & = next smallest number in A, \\ ⋮ \end{aligned}$
Therefore, $A$ is countable.
If $f : A ↪ N$ is injective, then $f : A \to 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 \to N .$ Then ${f |}_{A} : A \to N$ is an injection. Apply Statement 2.
This is the contrapositive of Statement 3, under the common assumption $A \subseteq B .$
For $A \cap B,$ consider $A \cap B \subseteq A$ and apply Statement 3.

Now consider $A \cup B .$ For simplicity, we will assume $A \cap B = \emptyset,$ so that $A \cup B = A ⊔ B .$ Since $A$ and $B$ are countable, we can write their elements as sequences:

$\begin{aligned} A & = {a_{0}, a_{1}, a_{2}, \dots}, & B & = {b_{0}, b_{1}, b_{2}, \dots} . \end{aligned}$

We can then write the elements of $A ⊔ B$ in a sequence by interleaving these two sequences:

$A ⊔ B = {a_{0}, b_{0}, a_{1}, b_{1}, a_{2}, b_{2}, \dots} .$

🔗

Checkpoint 13.2.2.

🔗

Prove

A \cup B

is countable even in the case

A \cap B \neq \emptyset .

Hint.

Consider the sets

\begin{aligned} A^{'} & = A ∖ (A \cap B), & B^{'} & = B ∖ (A \cap B), & C & = A^{'} ⊔ B^{'} . \end{aligned}

Then

A \cup B

is the disjoint union of

C

and

A \cap B .

🔗

Example 13.2.3. Primes are countable.

🔗

The set of prime numbers is countable, since it is a subset of

N .

🔗

Example 13.2.4. Unit interval is uncountable.

🔗

The unit interval

(0, 1)

on the real number line is uncountable because it contains the uncountable subset

C

from Lemma 13.1.7.

🔗

Theorem 13.2.5.

🔗

Set

R

is uncountable.

🔗

Proof.

This follows from Lemma 13.1.7 and Statement 4 of Proposition 13.2.1.

🔗

Example 13.2.6.

🔗

The Cartesian product set

R^{2} = R \times R

is uncountable because it has an uncountable subset: the

x

-axis has the same size as

R .

Elementary Foundations: An introduction to topics in discrete mathematics

Search Results: