Countable sets

A set $\mathbb{A}$ is said to be countable, if and only if it is either finite, or there is a bijection from $\mathbb{N}$ to $\mathbb{A}$.
In the latter case, $\mathbb{A}$ is said to be countably infinite.
If a set $\mathbb{A}$ is not countable, then $\mathbb{A}$ is said to be uncountable.
Using this concept we may summarize some of our above results as follows, for a non-empty set $\mathbb{A}$.

• There is an injection $\alpha: \mathbb{A} \rightarrow \mathbb{N}$, if and only if $\mathbb{A}$ is countable.
• There is a surjection $\alpha: \mathbb{N} \rightarrow \mathbb{A}$, if and only if $\mathbb{A}$ is countable.
• A countably infinite set $\mathbb{A}$ is not finite.

We also have the following results relating countable sets.
Let $\mathbb{A}$ and $\mathbb{B}$ be non-empty sets and $f: \mathbb{A}\rightarrow \mathbb{B}$ be a map.

• If $f$ is an injection and $\mathbb{B}$ is countable, then so is $\mathbb{A}$.
• If $f$ is an injection and $\mathbb{A}$ is uncountable, then so is $\mathbb{B}$.
• If $f$ is a surjection and $\mathbb{A}$ is countable, then so is $\mathbb{B}$.
• If $f$ is a surjection and $\mathbb{B}$ is uncountable, then so is $\mathbb{A}$.

The set $\mathbb{N}\times \mathbb{N}$ is countably infinite.
A quick way to map $\mathbb{N}\times \mathbb{N}$ injectively into $\mathbb{N}$ is to map $(m, n)$ to the positive integer $2^m 3^n$, for each $(m, n) \in \mathbb{N}\times\mathbb{N}$.
By prime factorization, this is an injection into $\mathbb{N}$, so $\mathbb{N}\times \mathbb{N}$ is countable.
But $\mathbb{N}\times \mathbb{N}$ is not finite, since it is not empty and there is an injection from $\mathbb{N}$ to $\mathbb{N}\times \mathbb{N}$, given by $n \rightarrow (n, n)$ for each $n \in\mathbb{N}$.
So $\mathbb{N}\times \mathbb{N}$ is countably infinite, as required. Then we have the theorem:

• A countable union of countable sets is countable.
  Let $\mathbb{A}$ be a non-empty countable set and let $\mathbb{B}_a$ be a countable set, given for each $a \in \mathbb{A}$.
  Let $\mathbb{B} = \bigcup_{a\in \mathbb{A}} \mathbb{B}_a$.
  Then $\mathbb{B}$ is countable.

We may assume that $\mathbb{B}$ is non-empty and that each $\mathbb{B}_a$ is non-empty, at the cost of replacing $\mathbb{A}$ by a subset, still countable and non-empty.
Since $\mathbb{A}$ is countable, there is a surjection $\alpha: \mathbb{N} \rightarrow \mathbb{A}$.
Then we have:

$$\mathbb{B}= \bigcup_{n\in \mathbb{N}} \mathbb{B}_{\alpha(n)}.$$

So without loss of generality, we may assume that $\mathbb{A} = \mathbb{N}$ and we have:

$$\mathbb{B}= \bigcup_{n\in \mathbb{N}} \mathbb{B}_{n}.$$

Here each $\mathbb{B}_n$ is countable and non-empty.
Next for each $m \in \mathbb{N}$ choose a surjection $\beta_m: \mathbb{N}\rightarrow \mathbb{B}_n$.
Finally define a map $\beta$ from $\mathbb{N}\times \mathbb{N}$ to $\mathbb{B}$, by the formula: $\beta(m, n) = \beta_m(n)$, for any $(m, n) \in \mathbb{N}\times\mathbb{N}$. Then $\beta$ is well-defined. Also if $x \in \mathbb{B}$, then $x \in \mathbb{B}_m$, for some $m \in \mathbb{N}$. Then we have $x = \beta_m(n)$, for some $n \in\mathbb{N}$, which gives $x = \beta(m, n)$, so $\beta$ is surjective and $\mathbb{B}$ is countable and we are done.

If $\mathbb{Z}$ denotes the integers, and $\mathbb{Z}^+$ and $\mathbb{Z}^-$ the positive and negative integers, respectively, then $\mathbb{Z}^+ = \mathbb{N}$, so $\mathbb{Z}^+$ is countably infinite. Also the map $n \rightarrow - n$, for any $n \in\mathbb{N}$, gives a bijection from $\mathbb{N}$ to $\mathbb{Z}^-$, so $\mathbb{Z}^-$ is countably infinite. Also the set $\{0\}$ is countable, having one element.
So the set $\mathbb{Z} = \mathbb{Z}^+ \cup \{0\}\cup \mathbb{Z}^-$, being a countable union of countable sets, is countably infinite.

If $\mathbb{Q}^+$ and $\mathbb{Q}^-$ denote the positive and negative rationals, respectively, then there are surjections $s_\pm$ (automatic, by definition of $\mathbb{Q}^\pm$) from $\mathbb{N}\times \mathbb{N} \rightarrow \mathbb{Q}^\pm$, which map any $(m, n) \in \mathbb{N}\times\mathbb{N}$ to the rational $${s_\pm(m, n) = \pm \frac{m}{n}}$$.
So $\mathbb{Q}^+$ and $\mathbb{Q}^-$ are each countably infinite (being not finite, since they each contain an infinite number of integers as subsets).
So the set $\mathbb{Q} = \mathbb{Q}^+ \cup \{0\} \cup \mathbb{Q}^-$ is countably infinite.