Nghịch lý Cantor

Trong lý thuyết tập hợp, nghịch lý Cantor chỉ ra rằng không có tập hợp của tất cả các lực lượng. Đây có nguồn gốc từ định lý rằng không có số đếm nào là lớn nhất. Nói một cách không chính thức, nghịch lý này nói rằng tập hợp tất cả các "kích thước vô hạn" có thể không chỉ là vô hạn, mà còn lớn đến mức kích thước vô hạn của chính nó không thể là bất kỳ kích thước vô hạn nào trong tập hợp. Khó khăn này được xử lý trong lý thuyết tập tiên đề bằng cách tuyên bố rằng tập hợp này không phải là một tập hợp mà là một lớp thích hợp ; trong lý thuyết tập hợp von Neumann – Bernays – Gödel, nó dựa trên điều này và tiên đề về giới hạn của kích thước rằng lớp thích hợp này phải là song ánh với lớp của tất cả các tập hợp. Do đó, nó không chỉ có vô số số vô hạn, mà thứ vô hạn này còn lớn hơn bất kỳ số vô hạn nào mà nó liệt kê.Nghịch lý này được đặt theo tên của Georg Cantor, người thường được cho là người đầu tiên chỉ ra nó vào năm 1899 (hoặc giữa các năm 1895 và 1897). Giống như một số "nghịch lý", nó không thực sự mâu thuẫn mà chỉ là biểu hiện của một trực giác sai lầm, trong trường hợp này là về bản chất của vô hạn và khái niệm về một tập hợp. Nói cách khác, nó là nghịch lý trong giới hạn của lý thuyết tập hợp ngây thơ và do đó chứng tỏ rằng việc tiên đề hóa bất cẩn của lý thuyết này là không phù hợp.

Phát biểu và chứng minh 
Để phát biểu nghịch lý này, cần phải hiểu rằng các lực lượng thừa nhận một thứ tự, để người ta có thể nói về một số lớn hơn hoặc nhỏ hơn một số khác. Khi đó, nghịch lý của Cantor được phát biểu là:

Định lý: Không có số lực lượng lớn nhất.

Thực tế này là hệ quả trực tiếp của định lý Cantor về tính cơ bản của tập hợp lũy thừa của một tập hợp.

Chứng minh: Giả sử xảy ra điều ngược lại, ta gọi C là số lực lượng lớn nhất. Khi đó (trong công thức von Neumann của lực lượng) C là một tập hợp và do đó có một tập lũy thừa 2C (tập chứa tất cả các tập hợp con của C), theo định lý Cantor, có lực lượng lớn hơn C. Việc chứng minh một lực lượng (cụ thể là 2C) lớn hơn C, mà được giả định là lực lượng lớn nhất, làm sai lệch định nghĩa của C. Sự mâu thuẫn này cho thấy rằng một lực lượng như vậy không thể tồn tại.

Một hệ quả khác của định lý Cantor là các số chính tạo thành một lớp thích hợp . Có nghĩa là, tất cả chúng không thể được thu thập cùng nhau như các phần tử của một tập hợp duy nhất. Đây là một kết quả phần nào tổng quát hơn.

Định lý: Nếu S là một tập bất kỳ thì S không thể chứa các phần tử của tất cả các lực lượng. Trên thực tế, có một giới hạn trên nghiêm ngặt đối với các lực lượng của các phần tử của S.

Chứng minh: Gọi S là một tập hợp, và gọi T là hợp các phần tử của S. Khi đó mọi phần tử của S là một tập con của T, và do đó có lực lượng nhỏ hơn hoặc bằng lực lượng của T. Khi đó định lý đường chéo Cantor ngụ ý rằng mọi phần tử của S đều có lực lượng nhỏ hơn lực lượng của 2T.

Tham khảo
 
 

Nghịch lý