Countable Sets and Closure Properties

A set $S$ is countable if $|S|\le\aleph_0$, i.e. there is an injection $S\hookrightarrow\mathbb{N}$ (equivalently, $S$ is finite or can be listed as $s_0,s_1,s_2,\dots$). The whole theory rests on one identity:

$\aleph_0\cdot\aleph_0=\aleph_0,$

witnessed by Cantor's pairing $\mathbb{N}\times\mathbb{N}\to\mathbb{N}$, $(i,j)\mapsto\tfrac{(i+j)(i+j+1)}{2}+j$. From it three closure rules follow.

The three closure rules

The surjection lemma (used everywhere above)

For a nonempty codomain,

$\exists\ \text{surjection } f:B\twoheadrightarrow A\iff |A|\le|B|.$

A surjection always points from the bigger set to the smaller one. Given $f$ onto, pick one preimage per target to build an injection $A\hookrightarrow B$; conversely any injection $A\hookrightarrow B$ can be inverted (and padded) to a surjection $B\to A$. So "$B$ is countable and $f:B\to A$ is onto" instantly gives "$A$ is countable."

Mini-example

Is the set of all finite-length bit strings $\{0,1\}^{*}$ countable? Yes: $\{0,1\}^{*}=\bigcup_{n\ge 0}\{0,1\}^{n}$, a countable union of finite sets, hence countable. Contrast this with $\{0,1\}^{\mathbb{N}}$ (infinite strings), which has cardinality $2^{\aleph_0}=\mathfrak{c}$ — uncountable.

Where it breaks: countable does not mean small

Closure is about countable ingredients. If you enlarge a continuum-sized set $X$ (so $|X|=\mathfrak{c}$), then:

• the collection of all countable subsets of $X$ has cardinality $\mathfrak{c}^{\aleph_0}=\bigl(2^{\aleph_0}\bigr)^{\aleph_0}=2^{\aleph_0}=\mathfrak{c}$ (each countable subset is the range of a sequence $\mathbb{N}\to X$);
• the full power set $P(X)$ jumps to $2^{\mathfrak{c}}$.

Restricting to countable subsets collapses the power set back down to $\mathfrak{c}$.

Exam trick: A surjection $f:B\twoheadrightarrow A$ goes big-to-small, so it forces $|A|\le|B|$ — never the reverse. To kill a closure or cardinality claim, check the direction of the implied inequality, and remember $\aleph_0\cdot\aleph_0=\aleph_0$ but $\mathfrak{c}^{\aleph_0}=\mathfrak{c}$ while $2^{\mathfrak{c}}>\mathfrak{c}$.