Surjections and Enumerability

Surjections

Definition

A function $f : A \to B$ is surjective if:

$\forall b \in B. \exists a \in A. f(a) = b$

Every element of $B$ is “hit” by $f$.

Notation

Write $f : A \twoheadrightarrow B$ for a surjection.

Enumerability

Definition

A set $A$ is enumerable if there exists a surjection $\mathbb{N} \twoheadrightarrow A$.

A set is countable if it is finite or enumerable.

Intuition

An enumerable set can be “listed” in some order (possibly with repetition, possibly never ending).

The surjection $e : \mathbb{N} \twoheadrightarrow A$ gives an enumeration: $e(0), e(1), e(2), \ldots$

Examples

• $\mathbb{N}$: enumerated by identity function
• $\mathbb{Z}$: enumerated by $e(0) = 0$, $e(2n+1) = n+1$, $e(2n) = -n$ for $n > 0$
  • Enumeration: $0, -1, 1, -2, 2, -3, 3, \ldots$
• $\mathbb{N} \times \mathbb{N}$: enumerated by Cantor pairing

Closure Properties

Subsets of Enumerable Sets

If $A$ is enumerable and $B \subseteq A$, then $B$ is countable.

Proof sketch: Let $e : \mathbb{N} \twoheadrightarrow A$. Define $e' : \mathbb{N} \twoheadrightarrow B$ by skipping elements not in $B$.

If $B = \emptyset$, it is finite (countable). If $B \neq \emptyset$, enumerate by visiting each $e(n)$ in order and including it if in $B$.

Sum of Countable Sets

If $A$ and $B$ are countable, then $A + B$ is countable.

Proof: Interleave the enumerations.

Product of Countable Sets

If $A$ and $B$ are countable, then $A \times B$ is countable.

Proof: Given enumerations $e_A$, $e_B$, enumerate pairs via a zigzag path through $\mathbb{N} \times \mathbb{N}$.

The Axiom of Choice

Statement

Every surjection has a section.

$\forall f : A \twoheadrightarrow B. \exists s : B \hookrightarrow A. f \circ s = \text{id}_B$

Equivalence

TFAE:

1. Axiom of Choice (as above)
2. Every family of non-empty sets has a choice function
3. Every set can be well-ordered

For Countable Sets

For countable sets, enumerability provides an explicit section: given $e : \mathbb{N} \twoheadrightarrow A$ and $f : A \twoheadrightarrow B$, define $s(b) = e(\min\{n : f(e(n)) = b\})$.

This is the canonical witness, avoiding AC.

Enumerability of $\mathbb{Z}$

Explicit Bijection

Define $e : \mathbb{N} \to \mathbb{Z}$:

$e(n) = \begin{cases} 0 & n = 0 \\ \frac{n+1}{2} & n \text{ odd} \\ -\frac{n}{2} & n > 0 \text{ even} \end{cases}$

This gives: $e(0) = 0$, $e(1) = 1$, $e(2) = -1$, $e(3) = 2$, $e(4) = -2$, $\ldots$

Check: This is a bijection, hence surjection.

Enumerable Implies Countable

Every enumerable set is countable by definition.

Non-empty countable sets are enumerable (finite = eventually constant enumeration).

---

Summary

• Enumerable: surjection $\mathbb{N} \twoheadrightarrow A$ exists
• Countable: finite or enumerable
• Countable sets closed under subsets, sums, products
• Axiom of Choice: every surjection has a section
• $\mathbb{Z}$, $\mathbb{N} \times \mathbb{N}$, and $\mathbb{Q}$ are countable