Bijections and Indicator Functions

Surjections

Definition

A function $f : A \to B$ is surjective (or onto) if:

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

Every element of $B$ is the image of some element of $A$.

Notation

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

Examples

• $f : \mathbb{R} \to \mathbb{R}_{\geq 0}, f(x) = x^2$ is surjective
• $f : \mathbb{Z} \to \mathbb{Z}, f(n) = 2n$ is not surjective (odd numbers not in image)

Injections

Definition

A function $f : A \to B$ is injective (or one-to-one) 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$ or $f : A \rightarrowtail B$ for an injection.

Examples

• $f : \mathbb{Z} \to \mathbb{Z}, f(n) = 2n$ is injective
• $f : \mathbb{R} \to \mathbb{R}, f(x) = x^2$ is not injective ($f(1) = f(-1)$)

Bijections

Definition

A function is a bijection if it is both injective and surjective.

Equivalently: for all $b \in B$, there exists a unique $a \in A$ with $f(a) = b$.

Inverse Function

If $f : A \to B$ is bijective, there exists a unique $f^{-1} : B \to A$ such that:

$f^{-1}(f(a)) = a \quad \text{and} \quad f(f^{-1}(b)) = b$

Notation

Write $f : A \cong B$ or $A \sim B$ to indicate a bijection exists between $A$ and $B$.

Counting Bijections

For finite sets $A, B$:

$|\text{Iso}(A, B)| = \begin{cases} 0 & |A| \neq |B| \\ n! & |A| = |B| = n \end{cases}$

Reason: Build a bijection by successively assigning images. Round $k$ has $n - k$ remaining choices.

Examinable Proof: Isomorphisms are Invertible

Theorem: For $f : A \to B$, TFAE:

1. $f$ is invertible (there exists $g : B \to A$ with $g \circ f = \text{id}_A$ and $f \circ g = \text{id}_B$)
2. $\forall b \in B. \exists! a \in A. f(a) = b$
3. $f$ is bijective

Proof sketch:

$(1 \Rightarrow 2)$: If $g$ is the inverse, take $a = g(b)$. Uniqueness: if $f(a_1) = f(a_2) = b$, then $a_1 = g(f(a_1)) = g(b) = g(f(a_2)) = a_2$.

$(2 \Rightarrow 3)$: Existence gives surjectivity; uniqueness gives injectivity.

$(3 \Rightarrow 1)$: Define $f^{-1}(b)$ as the unique $a$ with $f(a) = b$. Verify both compositions give identity.

Indicator Functions

Definition

For $S \subseteq A$, the indicator function (or characteristic function) $\chi_S : A \to \{0, 1\}$ is:

$\chi_S(a) = \begin{cases} 1 & a \in S \\ 0 & a \notin S \end{cases}$

Comprehension

Given $\phi : A \to \{0, 1\}$, the comprehension is:

$[\phi] = \{a \in A : \phi(a) = 1\}$

Bijection

$\mathcal{P}(A) \cong (A \to \{0, 1\})$

Every subset corresponds to a unique indicator function, and vice versa.

Finite Cardinality

Definition

A set $A$ is finite if there exists $n \in \mathbb{N}$ and a bijection $A \cong [n] = \{0, 1, \ldots, n-1\}$.

The cardinality of $A$, written $|A|$, is this unique $n$.

Isomorphism as Equality of Cardinality

For finite sets: $A \cong B \iff |A| = |B|$.

---

Summary

• Surjection: every $b$ is hit; injection: distinct inputs give distinct outputs
• Bijection = invertible function
• $|\text{Iso}(A, B)| = n!$ if $|A| = |B| = n$
• Indicator functions establish $\mathcal{P}(A) \cong (A \to \{0, 1\})$