Isomorphisms

Definition

A function $f : A \to B$ is an isomorphism if there exists $g : B \to A$ with:

$g \circ f = \text{id}_A \quad \text{and} \quad f \circ g = \text{id}_B$

We write $f : A \cong B$ or $A \cong B$.

Uniqueness of Inverse

If $f$ is an isomorphism, its inverse $g$ is unique, denoted $f^{-1}$.

Proof: If $g_1$ and $g_2$ are both inverses, then $g_1 = g_1 \circ \text{id}_B = g_1 \circ f \circ g_2 = \text{id}_A \circ g_2 = g_2$.

Isomorphism is Equivalence

Reflexivity

$\text{id}_A : A \cong A$ with inverse $\text{id}_A$.

Symmetry

If $f : A \cong B$ with inverse $g$, then $g : B \cong A$ with inverse $f$.

Transitivity

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

Proof: $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$, since $(g \circ f) \circ (f^{-1} \circ g^{-1}) = g \circ \text{id}_B \circ g^{-1} = \text{id}_C$.

Isomorphism via Injection and Surjection

Examinable Proof

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

1. $f$ is an isomorphism
2. $f$ is both injective and surjective
3. $\forall b \in B. \exists! a \in A. f(a) = b$

Proof:

$(1 \Rightarrow 2)$: If $f$ has inverse $g$, then:

• Injective: $f(a_1) = f(a_2) \Rightarrow g(f(a_1)) = g(f(a_2)) \Rightarrow a_1 = a_2$.
• Surjective: For any $b$, $f(g(b)) = b$, so $b$ is in the image.

$(2 \Rightarrow 3)$: Surjectivity gives existence; injectivity gives uniqueness.

$(3 \Rightarrow 1)$: Define $f^{-1}(b) =$ the unique $a$ with $f(a) = b$. Verify $f^{-1}(f(a)) = a$ and $f(f^{-1}(b)) = b$.

Counting Isomorphisms

For finite sets with $|A| = |B| = n$:

$|\text{Iso}(A, B)| = n!$

Combinatorial Argument

Build a bijection by successively assigning images:

• $f(a_1)$: $n$ choices
• $f(a_2)$: $n-1$ remaining choices
• …
• $f(a_n)$: 1 remaining choice

Product: $n \cdot (n-1) \cdot \ldots \cdot 1 = n!$

Useful Isomorphisms

Cartesian Product

$[m] \times [n] \cong [mn]$

Via $f(i, j) = n \cdot i + j$ (row-major encoding).

Disjoint Union

$[m] + [n] \cong [m+n]$

Via $f(0, i) = i$ and $f(1, j) = m + j$.

Powerset

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

Via indicator functions.

Powerset with One Extra Element

$\mathcal{P}(X + [1]) \cong \mathcal{P}(X) + \mathcal{P}(X)$

Reason: A subset of $X + \{*\}$ either does or does not contain $*$, giving two copies of subsets of $X$.

Finite Cardinality

For finite sets, $A \cong B$ means $|A| = |B|$.

The combinatorial results above verify:

• $|A \times B| = |A| \cdot |B|$
• $|A + B| = |A| + |B|$
• $|\mathcal{P}(A)| = 2^{|A|}$

---

Summary

• Isomorphism = invertible function = bijection
• $\cong$ is an equivalence relation on sets
• $|\text{Iso}(A, B)| = n!$ if $|A| = |B| = n$
• Key isomorphisms: products, disjoint unions, powersets