# Countable Set equals Range of Sequence

## Theorem

Let $S$ be a set.

Then $S$ is countable if and only if there exists a sequence $\left \langle {s_i} \right \rangle_{i \mathop \in N}$ where $N$ is a subset of $\N$ such that $S$ equals the range of $\left \langle {s_i} \right \rangle_{i \mathop \in N}$.

## Proof

### Necessary Condition

Assume that $S$ is countable.

We need to prove that there exists a sequence $\left \langle {s_i} \right \rangle_{i \mathop \in N}$, $N \subseteq \N$, such that $S$ equals the range of $\left \langle {s_i} \right \rangle_{i \mathop \in N}$.

The range of $\left \langle {s_i} \right \rangle_{i \mathop \in N}$ is defined as $\left\{ {s_i: i \in N} \right\}$.

Case 1. $S$ is empty.

Empty Set is Countable confirms that $S$ is countable.

Define the empty sequence as $\left \langle {s_i} \right \rangle_{i \mathop \in \varnothing}$.

The range of the empty sequence is $\left\{ {s_i: i \in \varnothing} \right\} = \varnothing$.

$S$ equals the range of the empty sequence as $S$ equals $\varnothing$.

This finishes the argument for this case.

Case 2. $S$ is finite and not empty.

Let $n \in \N_{>0}$ be the number of elements of $S$.

Define a sequence $\left \langle {s_i} \right \rangle_{1 \mathop \le \mathop i \mathop \le \mathop n}$ by going through every element of S:

- Let $s_1$ be any element of $S$.

- Let $s_2$ be any element of $S \setminus \left\{ {s_1} \right\}$.

- ...

- Let $s_n$ be the single element of $S \setminus \left\{ {s_i: 1 \le i \le n-1} \right\}$.

From this definition follows that every element of $S$ equals some $s_i$, $1 \le i \le n$.

So, $S \subseteq \left\{ {s_i: 1 \le i \le n} \right\}$.

Every number $s_i$, $1 \le i \le n$, equals some element of $S$.

So, $\left\{ {s_i: 1 \le i \le n} \right\} \subseteq S$.

Accordingly, $S = \left\{ {s_i: 1 \le i \le n} \right\}$.

By the definition of range, $\left\{ {s_i: 1 \le i \le n} \right\}$ equals the range of the sequence $\left \langle {s_i} \right \rangle_{1 \mathop \le \mathop i \mathop \le \mathop n}$.

Therefore, $S$ equals the range of $\left \langle {s_i} \right \rangle_{1 \mathop \le \mathop i \mathop \le \mathop n}$.

This finishes the proof for case 2.

Case 3. $S$ is infinite.

Since $S$ is countable and infinite, $S$ is countably infinite.

By the definition of countably infinite, $S$ can be written:

- $\left\{{t_0, t_1, \ldots, t_n, \ldots}\right\}$

where $n$ runs over all the natural numbers, $\N$.

In other words, we have:

- $S = \left\{ {t_i: i \in \N} \right\}$

We intend to produce a sequence from $S$.

We start with the empty sequence.

Using $\N$, the set to which $S$ is equivalent, we put all the elements of $S$ one by one into the sequence.

The result is $\left \langle {t_i} \right \rangle_{i \mathop \in \N}$.

The range of $\left \langle {t_i} \right \rangle_{i \mathop \in \N}$ is $\left\{ {t_i: i \in \N} \right\}$, which equals $S$.

In other words, $S$ is the range of the sequence $\left \langle {t_i} \right \rangle_{i \mathop \in \N}$.

This finishes the necessary part of the proof.

### Sufficient Condition

Assume that there exists a sequence $\left \langle {s_i} \right \rangle_{i \mathop \in N}$ where $N$ is a subset of $\N$ such that $S$ equals the range of that sequence.

We need to prove that $S$ is countable.

Case 1. $S$ is finite.

By the definition of countable $S$ is countable.

Case 2. $S$ is infinite.

We know that $S$ equals the range of the sequence $\left \langle {s_i} \right \rangle_{i \mathop \in N}$ where $N$ is an infinite subset of $\N$.

The range of $\left \langle {s_i} \right \rangle_{i \mathop \in N}$ is defined as $\left\{ {s_i: i \in N} \right\}$, so we have

- $S = \left\{ {s_i: i \in N} \right\}$

We need to prove that $S$ is countably infinite.

That a set is countably infinite, means that it is of the form:

- $\left\{{t_0, t_1, \ldots, t_n, \ldots}\right\}$

where $n$ runs over all the natural numbers, $\N$.

Accordingly, we need to show that a set $\left\{ {t_i: i \in \N} \right\}$ exists such that:

- $S = \left\{ {t_i: i \in \N} \right\}$

Assume that $N = \N$.

Then $S$ is countably infinite by definition.

The only other alternative is $N \subset \N$.

Define

- $t_i = s_i$ for every $i$ in $N$

- $t_i = s_1$ for every $i$ in $\N \setminus N$

Thus, $t_i$ is defined for every $i$ in $\N$.

We have

\(\displaystyle \left\{ {t_i: i \in \N} \right\}\) | \(=\) | \(\displaystyle \left\{ {t_i: i \in N} \right\} \cup \left\{ {t_i: i \in \N \setminus N} \right\}\) | as $\N = N \cup (\N \setminus N)$ | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \left\{ {s_i: i \in N} \right\} \cup \left\{ {t_i: i \in \N \setminus N} \right\}\) | as $s_i = t_i$ for every $i$ in $N$ | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle S \cup \left\{ {t_i: i \in \N \setminus N} \right\}\) | by the definition of $S$ | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle S \cup \left\{ {s_1} \right\}\) | as $t_i = s_1$ for every $i$ in $\N \setminus N$ | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle S\) | as $\left\{ {s_1} \right\} \subset S$ as $s_1 \in S$ |

All in all, $S = \left\{ {t_i: i \in \N} \right\}$.

Therefore, $S$ is countably infinite and thus countable.

This finishes the last part of the proof.

$\blacksquare$

## Sources

- 1988: H.L. Royden:
*Real Analysis*(3rd ed.): Ch. $1$: Section $6$, Definition