Injections and Countability

Injections

Definition

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

$\forall a_1, a_2 \in A. (f(a_1) = f(a_2) \Rightarrow a_1 = a_2)$

Equivalently: $a_1 \neq a_2 \Rightarrow f(a_1) \neq f(a_2)$.

Notation

Write $f : A \hookrightarrow B$ for an injection.

Injectivity and Cardinality

Intuition

An injection $A \hookrightarrow B$ shows $A$ is “at most as large as” $B$.

For finite sets: if there is an injection $A \hookrightarrow B$, then $|A| \leq |B|$.

For Infinite Sets

An injection $\mathbb{N} \hookrightarrow A$ shows $A$ is “at least as large as” $\mathbb{N}$.

Definition

A set $A$ is countable if there exists an injection $A \hookrightarrow \mathbb{N}$.

Equivalence: If $A \neq \emptyset$, this is equivalent to: there exists a surjection $\mathbb{N} \twoheadrightarrow A$.

Closure Properties

Composition of Injections

If $f : A \hookrightarrow B$ and $g : B \hookrightarrow C$, then $g \circ f : A \hookrightarrow C$.

Proof: If $(g \circ f)(a_1) = (g \circ f)(a_2)$, then $g(f(a_1)) = g(f(a_2))$. Since $g$ injective, $f(a_1) = f(a_2)$. Since $f$ injective, $a_1 = a_2$.

Injections and Products

If $f : A \hookrightarrow B$ and $g : C \hookrightarrow D$, then $f \times g : A \times C \hookrightarrow B \times D$.

Cantor-Bernstein-Schroeder Theorem

Statement

If there exist injections $f : A \hookrightarrow B$ and $g : B \hookrightarrow A$, then $A \cong B$.

Significance

This allows us to prove two sets have the same cardinality by constructing injections in both directions, without explicitly building a bijection.

Proof Idea

Using $f$ and $g$, partition $A = A_A \cup A_B$ and $B = B_A \cup B_B$ such that:

• $f$ bijects $A_A \cong B_A$
• $g^{-1}$ bijects $B_B \cong A_B$

The union gives $A \cong B$.

Well-Ordering and Choice

Every Surjection Has a Section

Given $f : A \twoheadrightarrow B$, for each $b \in B$, the fibre $f^{-1}(b) \subseteq A$ is non-empty.

A section chooses one element from each fibre.

Axiom of Choice: Such a section exists for every surjection.

Injectivity from Choice

Given a section $s : B \to A$ with $f \circ s = \text{id}_B$, the section $s$ is injective.

Proof: If $s(b_1) = s(b_2)$, then $b_1 = f(s(b_1)) = f(s(b_2)) = b_2$.

Enumeration via Injection

Theorem

For non-empty $A$: $A$ is enumerable iff there exists an injection $A \hookrightarrow \mathbb{N}$.

Proof Sketch:

$(\Rightarrow)$: If $e : \mathbb{N} \twoheadrightarrow A$ is surjective, define $s(a) = \min\{n : e(n) = a\}$. This is injective (the section).

$(\Leftarrow)$: If $i : A \hookrightarrow \mathbb{N}$ is injective, enumerate $A$ in order of increasing $i(a)$.

Countability of $\mathbb{Q}$

Argument

An injection $\mathbb{Q} \hookrightarrow \mathbb{N} \times \mathbb{N}$: send $\frac{p}{q}$ (in lowest terms) to $(p, q)$.

An injection $\mathbb{N} \times \mathbb{N} \hookrightarrow \mathbb{N}$: Cantor pairing function.

Thus $\mathbb{Q}$ is countable.

Explicit Enumeration

Enumration of positive rationals via Stern-Brocot tree or diagonal enumeration.

---

Summary

• Injection: distinct inputs give distinct outputs
• $A$ countable iff injection $A \hookrightarrow \mathbb{N}$ exists
• Cantor-Bernstein-Schroeder: injections both ways implies bijection
• Every surjection has a section (Axiom of Choice)
• $\mathbb{Q}$ is countable via embedding into $\mathbb{N} \times \mathbb{N}$