Question

Show that a subset of a countable set is also countable.

Short answer

The subset of a countable set is also countable.

Step-by-step solution

Definition

Definition of Finite, Countable Infinite and Uncountable Infinite sets.

• A set is finite if it contains a limited number of elements (thus it is possible to list every single element in the set).

• A set is countably infinite if the set contains an unlimited number of elements and if there is a one-to-one correspondence with the positive integers.

• A set is uncountable if the set is not finite or countably infinite.

X is a subset of Y if every element of X is also an element of Y . Notation: $X\subseteq Y$

Definition : If there is a one-to-one function from A to B , then$\left|A\right|\le \left|B\right|$.

Step 2

Given: A and B are sets, B is countable and $A\subseteq B$

To proof: A is countable

By the definition of a subset: If $a\in A$then $a\in B$

We can then define the function f as:

$f:A\to B,f\left(a\right)=a$

We need to check that the function f is one-to-one. Let . By the definition of , we then obtain a = b . Thus f is one-to-one.

Since f is a one-to-one function from $A,\left|A\right|\le \left|B\right|$ (see definition ).

is countable:

$\left|B\right|\le \left|{\mathrm{Z}}^{+}\right|$

Combining $\left|A\right|\le \left|B\right|\text{and}\left|B\right|\le \left|Z^{+}\right|$, we then obtain

$\begin{array}{r}\left|A\right|\le \left|Z^{+}\right|\\ \left|A\right|\le \left|Z^{+}\right|\end{array}$is true, we can then conclude that A is countable.