Định lýĐã chứng minh

Định lý Cantor

Phát biểu

Với mọi tập $A$ , $|A| < |\mathcal{P}(A)|$ : không có toàn ánh nào từ $A$ lên tập lũy thừa $\mathcal{P}(A)$ của nó, nên tập lũy thừa lớn hơn thực sự.

Vì sao đú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.

Phác thảo chứng minh

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)|$ .

Chủ đề chứa định lý này

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

Chứng minh từng bước

Chưa có chứng minh từng bước cho định lý này.

Tài liệu tham khảo

Paul R. Halmos (1960). Naive Set Theory
Karel Hrbacek, Thomas Jech (1999). Introduction to Set Theory