Ánh xạ và lực lượng

Điều này cho thấy không có "vô hạn lớn nhất" nào cả — từ bất kỳ tập nào, dù lớn đến đâu, ta luôn có thể xây một tập lớn hơn thực sự chỉ bằng cách lấy tập lũy thừa của nó. Đây là định lý khiến một hệ thống phân tầng vô hạn của các vô hạn trở nên không thể tránh khỏi, và kỹ thuật chứng minh bằng đường chéo của nó là tổ tiên trực tiếp của các lập luận dùng để chỉ ra một số bài toán là không thể tính được.

Giả sử phản chứng rằng có một toàn ánh $f : A \to \mathcal{P}(A)$; ta sẽ suy ra mâu thuẫn, chứng tỏ không thể tồn tại toàn ánh như vậy.

Định nghĩa tập "đường chéo" $D = \{x \in A : x \notin f(x)\}$: nó gom mọi phần tử của $A$ mà không thuộc ảnh của chính nó qua $f$. Vì $D$ là tập con của $A$, nó là một phần tử của $\mathcal{P}(A)$.

Vì $f$ được giả sử là toàn ánh, phải tồn tại $a_0 \in A$ với $f(a_0) = D$. Bây giờ đặt câu hỏi quyết định: $a_0 \in D$ hay không?

Nếu $a_0 \in D$, thì theo định nghĩa của $D$, $a_0 \notin f(a_0)$; nhưng $f(a_0) = D$, nên điều này có nghĩa $a_0 \notin D$ — mâu thuẫn. Nếu thay vào đó $a_0 \notin D$, thì theo định nghĩa của $D$ (loại trừ đúng những phần tử có $a_0 \in f(a_0)$), điều này buộc $a_0 \in f(a_0) = D$ — lại mâu thuẫn.

Dù theo cách nào ta cũng gặp mâu thuẫn, nên không thể tồn tại toàn ánh $f : A \to \mathcal{P}(A)$. Kết hợp với đơn ánh $x \mapsto \{x\}$ từ $A$ vào $\mathcal{P}(A)$, điều này cho đúng $|A| < |\mathcal{P}(A)|$.

So sánh lực lượng chỉ bằng đơn ánh (mỗi tập vừa khít vào tập kia) đã buộc hai tập phải có cùng kích thước hệt như với tập hữu hạn. Điều này cho phép chứng minh $|A|=|B|$ bằng cách xây hai phép nhúng một chiều dễ dàng thay vì một song ánh trực tiếp khó — đây chính xác là cách các ví dụ dưới đây cho thấy khoảng $[0,1]$ và $(0,1)$ có cùng lực lượng.

Gọi $f : A \to B$ và $g : B \to A$ là hai đơn ánh đã cho. Ý tưởng là truy vết, với mỗi phần tử, chuỗi tổ tiên thu được bằng cách lần lượt gỡ ngược $f$ và $g$, rồi xây song ánh cuối cùng từng phần tùy theo mỗi chuỗi "bắt đầu" ở đâu.

Với $a \in A$, định nghĩa chuỗi lùi $a, g^{-1}(a), f^{-1}(g^{-1}(a)), \ldots$, tiếp tục miễn là nghịch đảo cần dùng còn xác định, và tương tự với $b \in B$. Chuỗi của mỗi phần tử hoặc lùi mãi mãi, hoặc dừng ở một phần tử của $A$ không có tiền ảnh qua $g$, hoặc dừng ở một phần tử của $B$ không có tiền ảnh qua $f$. Điều này chia $A$ thành ba phần $A_A$ (chuỗi dừng ở $A$), $A_B$ (chuỗi dừng ở $B$), $A_\infty$ (chuỗi không bao giờ dừng), và tương tự chia $B$ thành $B_A, B_B, B_\infty$.

Trên các chuỗi dừng ở $A$ hoặc không bao giờ dừng, chính $f$ đã cho một song ánh từ phần đó của $A$ lên phần tương ứng của $B$ (vì các phần tử này đạt được qua đơn ánh và không có gì "hết" ở phía $B$ trước). Trên các chuỗi dừng ở $B$, chính $g$ cho một song ánh từ phần tương ứng của $B$ ngược về phần đó của $A$, nên nghịch đảo $g^{-1}$ của nó cho một song ánh từ phần đó của $A$ lên phần đó của $B$.

Định nghĩa $h : A \to B$ bởi $h(a) = f(a)$ nếu $a \in A_A \cup A_\infty$, và $h(a) = g^{-1}(a)$ nếu $a \in A_B$. Vì ba phần rời nhau và mỗi phần ánh xạ song ánh lên phần khớp của $B$ ($f$ lên $B_A \cup B_\infty$, $g^{-1}$ lên $B_B$), ánh xạ gộp $h$ là một song ánh từ toàn bộ $A$ lên toàn bộ $B$, chứng minh $|A|=|B|$.