Countable Sets

A set

A

is countable if

N \sim A

. An infinite set that is not countable is called an uncountable set.

Q

countable,

R

uncountable

i. $Q$ is countable
ii. $R$ is uncountable

Proof
i:
Set $A_{1} = {0}$ and for each $n \geq 2$ let $A_{n}$ be the set defined by:

A_{n} = {\pm \frac{p}{q} | p, q \in N, p + q = n, p, q are in lowest terms}

For example:

A_{1} = {0}, A_{2} = {\frac{1}{1}, \frac{- 1}{1}}, A_{3} = {\frac{1}{2}, \frac{- 1}{2}, \frac{2}{1}, \frac{- 2}{1}}, \dots

We can make the following pairings:

Pasted image 20241006153346.png

Trying to write the explicit formula for $f$ here is a bit awkward. But what's important is given any rational $q \in Q$ then $q = \frac{m}{n}$ so then $q = \frac{m}{n} \in A_{m + n}$ . So $\frac{22}{7} \in A_{29}$ for example. This argument shows surjectivity. To show one-to-one (injective) notice that each $A_{n}$ is disjoint with other $A_{m}$ 's, thus any two rationals that aren't in the same set cannot equal.

ii:
Assume that there does exist some bijection $f : N \to R$ . Then $x_{1} = f (1), x_{2} = f (2), \dots$ so then we can say:

R = {x_{1}, x_{2}, \dots}

and be confident each real $x \in R$ is one of these $x_{i}$ 's.

Using the Nested Interval Property, let $I_{1}$ be a closed interval that does not contain $x_{1}$ . Next, let $I_{2}$ be a closed interval within $I_{1}$ that doesn't contain $x_{2}$ . Repeat this process such that:

$I_{n + 1} \subseteq I_{n}$
$x_{n + 1} \notin I_{n + 1}$

Now consider $⋂_{n = 1}^{\infty} I_{n}$ . If $x_{n_{0}}$ is some real number from the list then $x_{n_{0}} \notin I_{n_{0} + 1}$ . As a result then $x_{n_{0}} \notin ⋂_{n = 1}^{\infty} I_{n}$ . Since $x_{n_{0}}$ was arbitrary then $⋂_{n = 1}^{\infty} I_{n} = \emptyset$ .

However, the Nested Interval Property states that $⋂_{n = 1}^{\infty} I_{n} \neq \emptyset$ , so then there is some $x \in ⋂_{n = 1}^{\infty} I_{n}$ such that it's not in our list of $x_{i}$ 's, which is a contradiction. Thus $R$ must be uncountable.
☐

What about $I$ ? Since $R = Q \cup I$ and via theorem then $I$ must be the $I$ cannot be countable since if it was then otherwise $R$ would be.

A \subseteq B

and

B

is countable, then

A

is either countable or finite.

Theorem

i. If $A_{1}, A_{2}, \dots, A_{m}$ are each countable sets, then the union $A_{1} \cup A_{2} \cup \dots \cup A_{m}$ is countable.
ii. If $A_{n}$ is a countable set for each $n \in N$ then $⋃_{n = 1}^{\infty} A_{n}$ is countable.

The proofs of these are pretty easy to show and are left to the read (always wanted to do that).