Tiên đề chọn

Trong toán học, tiên đề chọn () hay AC, là một tiên đề trong lý thuyết tập hợp tương đương với phát biểu "một tích Descartes của một tập các tập hợp không rỗng thì không rỗng". Nói đơn giản hơn, tiên đề chọn cho phép từ một tập các thùng, mỗi thùng chứa ít nhất một vật nào đó, ta có thể chọn đúng một vật từ mỗi thùng, ngay cả khi số thùng là vô hạn. Chính xác hơn, đây là khẳng định với mỗi họ chỉ số gồm các tập khác rỗng, tồn tại một họ chỉ số gồm các phần tử sao cho với mọi Tiên đề chọn được Ernst Zermelo phát biểu năm 1904 để hoàn tất chứng minh của ông cho định lý thứ tự tốt.
Trong nhiều trường hợp, việc chọn như thế có thể được thực hiện mà không cần tiên đề chọn, ví dụ như nếu số tập hợp là hữu hạn, hoặc tồn tại một quy tắc chọn – một tính chất phân biệt nào đó đúng với duy nhất một phần tử trong mỗi tập hợp. Một ví dụ là họ các tập hợp chứa số tự nhiên. Từ những tập này, ta luôn có thể chọn phần tử nhỏ nhất, chẳng hạn với các tập tập chứa các phần tử nhỏ nhất tương ứng là . Trong trường hợp này, quy tắc "chọn số nhỏ nhất" là một hàm chọn. Ngay cả khi ta có vô hạn tập chứa các số tự nhiên, ta vẫn luôn có thể chọn được số nhỏ nhất từ mỗi tập, tức hàm chọn này có thể được dùng cho mọi họ các tập số tự nhiên. Tuy nhiên, không có hàm chọn nào được biết có thể dùng cho họ tất cả tập con khác rỗng của tập số thực (nếu tồn tại số thực không dựng được). Khi đó, ta phải sử dụng tiên đề chọn.
Bertrand Russell đưa ra một phép so sánh: với mọi tập các đôi giày (có thể vô hạn), ta luôn có thể chọn chiếc giày trái từ mỗi đôi làm lựa chọn, tạo thành một hàm chọn. Mặt khác, với một tập các đôi vớ "vô hạn" (giả sử hai chiếc vớ đều giống nhau), không có cách nào hiển nhiên để định nghĩa một hàm chọn một chiếc vớ từ mỗi đôi, mà không sử dụng tiên đề chọn.
Mặc dù vốn gây ra nhiều tranh cãi, tiên đề chọn hiện nay được hầu hết các nhà toán học sử dụng, và được đưa vào dạng tiêu chuẩn của lý thuyết tập hợp tiên đề, lý thuyết tập hợp Zermelo–Fraenkel với tiên đề chọn (ZFC). Một lý do là bởi một số kết quả toán học được chấp nhận rộng rãi, ví dụ như định lý Tychonoff, cần tiên đề chọn để chứng minh. Các nhà lý thuyết tập hợp hiện nay cũng nghiên cứu các tiên đề không tương thích với tiên đề chọn, ví dụ như tiên đề xác định. Một số ngành của toán học, đặc biệt các nhánh của toán học kiến thiết, tránh việc sử dụng tiên đề chọn.
Phát biểu.
Một hàm chọn (còn gọi là cách chọn) là một hàm số , định nghĩa trên họ gồm các tập hợp khác rỗng, sao cho với mỗi tập hợp trong , là một phần tử của . Với khái niệm này, tiên đề có thể được phát biểu như sau:
Tiên đề có thể được biểu diễn bằng ký hiệu như sau
Từ đây phủ định của tiên đề chọn nói rằng tồn tại một họ các tập hợp khác rỗng mà không có hàm chọn.
Mỗi hàm chọn trên họ các tập hợp khác rỗng là một phần tử trong tích Descartes của các tập hợp trong . Mỗi phần tử trong tích Descartes của họ là một bộ chứa một phần tử từ mỗi tập thuộc , và do đó ứng với một cách chọn. Tiên đề chọn khẳng định luôn tồn tại một phần tử như thế, và do đó nó tương đương với phát biểu:
Danh pháp ZF, AC, và ZFC.
Trong bài viết này và trong những cuộc thảo luận khác về tiên đề chọn, các cụm viết tắt sau rất thường gặp:
Phát biểu khác.
Có nhiều phát biểu khác tương đương với tiên đề chọn. Chúng tương đương theo nghĩa là, sử dụng những tiên đề tập hợp cơ bản khác, từ chúng suy ra tiên đề chọn và từ tiên đề chọn suy ra được chúng.
Một phát biểu tránh việc dùng hàm chọn, thay vào đó là tập giá trị của nó:
Một phát biểu khác chỉ xét những tập là tập lũy thừa của một tập hợp:
Những nhà toán học dùng phát biểu này thường chỉ nói "hàm chọn trên ", với hàm chọn ở đây mang nghĩa là chọn trên tập lũy thừa của (bỏ tập rỗng), trong khi hàm chọn ở những nơi khác trong bài xác định trên "họ các tập hợp", hay tập chứa các tập. Với khái niệm hàm chọn trên, tiên đề chọn có thể được phát biểu ngắn gọn thành
tương đương với
Mệnh đề phủ định của tiên đề chọn sẽ là:
Giới hạn với họ hữu hạn.
Phát biểu của tiên đề chọn không nói cụ thể họ tập khác rỗng là hữu hạn hay vô hạn. Trong trường hợp hữu hạn, phát biểu đó có thể được chứng minh trong lý thuyết tập hợp Zermelo–Fraenkel mà không cần tiên đề chọn (ZF) bằng quy nạp toán học. Trong trường hợp đơn giản nhất, chỉ có "một" tập, một hàm chọn tương ứng với một phần tử duy nhất, khi ấy tiên đề chọn nói có thể mọi tập khác rỗng chứa một phần tử và là hiển nhiên đúng. Tiên đề chọn có thể được coi là phiên bản tổng quát cho tính chất này của các họ hữu hạn lên các họ tùy ý.
Sử dụng.
Cho đến cuối thế kỷ 19, tiên đề chọn thường được dùng một cách ngụ ý mà chưa được phát biểu cụ thể. Ví dụ, sau khi chỉ ra tập chỉ chứa những tập hợp khác rỗng, một nhà toán học có thể nói "gọi là một phần tử của với mọi thuộc " để định nghĩa một hàm số Nhìn chung, không thể chứng minh tồn tại mà không dùng tiên đề chọn, tuy nhiên điều này dường như chỉ bắt đầu được để ý từ Zermelo.
Không phải mọi trường hợp đều cần tiên đề chọn. Với những tập hữu hạn , tiên đề chọn có thể được suy ra từ những tiên đề tập hợp cơ bản khác. Khi ấy, một phát biểu tương đương có thể là nếu ta có một số (hữu hạn) hộp, mỗi hộp chứa ít nhất một vật, thì ta có thể chọn đúng một vật từ mỗi hộp. Ta có thể thực hiện việc chọn bằng cách bắt đầu với hộp thứ nhất, chọn một vật; sang hộp thứ hai, chọn một vật; và cứ thế. Do số hộp là hữu hạn nên quá trình chọn của ta sẽ kết thúc. Kết quả khi ấy là một hàm chọn cụ thể: ứng với mỗi hộp là một vật ta đã chọn (chứng minh chặt chẽ cho tất cả họ hữu hạn sẽ dùng quy nạp toán học để chứng minh "với mỗi số tự nhiên , mọi họ gồm tập khác rỗng đều có một hàm chọn"). Tuy nhiên, phương pháp này không thể áp dụng cho họ vô hạn đếm được các tập khác rỗng, khi ấy ta cần tiên đề chọn đếm được. Nếu dùng phương pháp này cho họ vô hạn các tập khác rỗng, ở mỗi bước ta chỉ có một hàm chọn cho một phần hữu hạn, chứ không thể tạo ra một hàm chọn cho toàn bộ họ, nếu không có quy tắc nào khác. Một hàm chọn tổng quát không thể được xây dựng trong ZF mà không có tiên đề chọn.
Ví dụ.
Bản chất của mỗi tập hợp khác rỗng trong họ tập hợp có thể giúp ta tránh tiên đề chọn, ngay cả với họ vô hạn. Ví dụ, nếu mỗi tập thuộc họ chỉ chứa các số tự nhiên, ta có thể lấy hàm chọn là hàm giá trị nhỏ nhất của mỗi tập. Điều này cho ta một phép chọn cụ thể một phần tử từ mỗi tập mà không cần đến tiên đề chọn.
Khó khăn xuất hiện trong những trường hợp tổng quát hơn. Nếu ta không thể đưa ra lựa chọn rõ ràng, liệu tập hợp ta chọn có tồn tại? Ví dụ, giả sử tập là tập tất cả tập con khác rỗng của tập số thực Giả sử ta chọn giống như trong trường hợp họ hữu hạn, khi ấy vì là vô hạn nên quá trình chọn của chúng ta sẽ không bao giờ dừng, và do đó không thể tạo ra một hàm chọn cho toàn bộ Tiếp theo ta có thể chọn phần tử nhỏ nhất của mỗi tập, nhưng một số tập con của tập số thực không có phần tử nhỏ nhất, ví dụ như khoảng mở không có phần tử nhỏ nhất: nếu là một số trong khoảng thì cũng nằm trong khoảng đó và nhỏ hơn . Do đó cách chọn này cũng không khả thi.
Một ví dụ khác, xét đường tròn đơn vị và các tác động lên bởi nhóm gồm tất cả các phép quay hữu tỉ, tức những phép quay bởi góc là bội hữu tỉ của số . Ở đây là đếm được trong khi là không đếm được. Do đó phân thành vô hạn không đếm được các "quỹ đạo" dưới Dùng tiên đề chọn, ta có thể lấy một điểm từ mỗi quỹ đạo, tạo thành một tập con không đếm được của với tính chất mọi ảnh xoay của nó dưới đều rời với Tập hợp những ảnh xoay đó phân hoạch đường tròn thành một họ vô hạn đếm được các tập con, mỗi tập đều đôi một lệch nhau một góc hữu tỉ. Vì không đo được với mọi phép đo hữu hạn cộng tính đếm được bất biến quay trên , việc tìm một thuật toán để chọn một điểm từ mỗi quỹ đạo yêu cầu phải có tiên đề chọn.
Ta có thể chọn phần tử nhỏ nhất từ các tập con của tập số tự nhiên là vì các số tự nhiên được sắp thứ tự tốt: mọi tập con khác rỗng của tập số tự nhiên có một phần tử nhỏ nhất theo thứ tự tự nhiên. Nếu ta nói "Mặc dù thứ tự thông thường của số thực không cho phép ta chọn, có thể có một thứ tự khác của số thực là thứ tự tốt. Khi ấy hàm chọn của ta có thể lấy phần tử nhỏ nhất theo thứ tự tốt đó". Vấn đề khi ấy trở thành tìm một thứ tự tốt cho tập số thực, và điều này hóa ra lại cần có tiên đề chọn; mỗi tập hợp có thứ tự tốt khi và chỉ khi tiên đề chọn là đúng.
Phê bình và chấp nhận.
Một chứng minh sử dụng tiên đề chọn có thể thừa nhận sự tồn tại của một vật mà không định nghĩa vật đó rõ ràng trong ngôn ngữ lý thuyết đồ thị. Ví dụ, mặc dù từ tiên đề chọn suy ra có một thứ tự tốt cho số thực, có những mô hình lý thuyết tập hợp với tiên đề chọn mà trong đó không thể định nghĩa một thứ tự tốt cho số thực. Tương tự, mặc dù có thể chứng minh sự tồn tại của một tập số thực không đo được Lebesgue sử dụng tiên đề chọn, việc không có tập nào như thế định nghĩa được là nhất quán với ZFC.
Tiên đề chọn chứng minh sự tồn tại của những vật thể mơ hồ này, nhưng không thể bảo đảm chúng có thể được xây dựng, và do đó có thể đi ngược lại với một số nguyên lý triết học.. Vì không có một thứ tự tốt chính tắc nào cho mọi tập hợp, việc xây dựng dựa trên một thứ tự tốt có thể không tạo ra một kết quả chính tắc, ngay cả khi mong muốn một kết quả chính tắc (như trong lý thuyết phạm trù). Đây đã được dùng để phản đối việc sử dụng tiên đề chọn.
Một luận điểm khác chống lại tiên đề chọn là từ nó có thể suy ra sự tồn tại của những vật thể phản trực giác. Một ví dụ là nghịch lý Banach–Tarski nói rằng có thể chia một quả cầu 3 chiều thành một số hữu hạn các mảnh, rồi chỉ dùng phép quay và tịnh tiến, ráp chúng lại thành hai quả cầu giống hệt quả cầu ban đầu. Những mảnh ghép trong việc phân chia này được xây dựng bằng tiên đề chọn và là tập hợp không đo được.
Mặc cho những kết quả nghịch lý này, hầu hết các nhà toán học công nhận tiên đề chọn là đúng trong quá trình chứng minh toán học. Cuộc tranh luận cũng đặt ra một số câu hỏi thú vị, trong đó có những định lý trong ZFC (ZF + AC) là tương đương logic với tiên đề chọn (sử dụng các tiên đề ZF).
Có thể chứng minh nhiều định lý mà không cần cả tiên đề chọn lẫn phủ định của nó; những định lý đó sẽ đúng trong bất cứ mô hình nào của ZF, bất kể tính đúng sai của tiên đề chọn trong mô hình đó. Khi giới hạn trong ZF, một mệnh đề dựa trên tiên đề chọn hoặc phủ định của nó là không thể chứng minh được. Ví dụ, nghịch lý Banach–Tarski không thể được chứng minh là đúng hoặc sai chỉ trong ZF: không thể xây dựng một cách chia quả cầu đơn vị trong ZF, nhưng cũng không thể chứng minh là không có cách chia nào tồn tại. Những mệnh đề như nghịch lý Banach–Tarski có thể được phát biểu lại thành mệnh đề điều kiện, ví dụ như, "Nếu tiên đề chọn là đúng, thì tồn tại cách chia quả cầu như trong nghịch lý Banach–Tarski". Những mệnh đề điều kiện như thể có thể được chứng minh trong ZF nếu mệnh đề gốc có thể được chứng minh trong ZFC.
Trong toán học kiến thiết.
Như đã nói ở trên, trong ZFC, từ tiên đề chọn ta có thể đưa ra những "chứng minh không kiến thiết" trong đó sự tồn tại của một vật thể được chứng minh, nhưng không có ví dụ nào được đưa ra. Tuy nhiên, ZFC vẫn được phát biểu chặt chẽ trong logic cổ điển. Tiên đề chọn cũng đã được nghiên cứu trong bối cảnh toán học kiến thiết, sử dụng logic phi cổ điển.
Trong lý thuyết hình thái Martin-Löf và số học Heyting bậc cao, phát biểu phù hợp của tiên đề chọn được bao gồm làm một tiên đề hoặc có thể chứng minh dưới dạng định lý. Errett Bishop cho rằng tiên đề chọn là chấp nhận được về mặt kiến thiết, nói
Tuy nhiên, trong lý thuyết tập hợp kiến thiết, định lý Diaconescu cho thấy tiên đề chọn kéo theo luật bài trung (điều này không đúng trong lý thuyết hình thái Martin-Löf). Do đó tiên đề chọn thường không được sử dụng trong lý thuyết tập hợp kiến thiết. Một lý do cho sự khác nhau này đó là trong lý thuyết hình thái, tiên đề chọn không có tính ngoại diên như tiên đề chọn trong lý thuyết tập hợp kiến thiết.
Một số kết quả trong lý thuyết tập hợp kiến thiết sử dụng tiên đề chọn đếm được hoặc tiên đề chọn phụ thuộc, mà không bao hàm luật bài trung. Mặc dù tiên đề chọn đếm được tương đối thông dụng trong toán học kiến thiết, việc sử dụng nó cũng đặt ra một số nghi vấn.
Tính độc lập.
Năm 1938, Kurt Gödel chỉ ra rằng "phủ định" của tiên đề chọn không thể được chứng minh trong ZF bằng cách xây dựng một nội mô hình (một vũ trụ dựng được) thỏa mãn ZFC và từ đó cho thấy ZFC là nhất quán nếu bản thân ZF nhất quán. Năm 1963, Paul Cohen sử dụng kỹ thuật ép (forcing), để chỉ ra rằng, giả sử ZF là nhất quán, tiên đề chọn không thể được chứng minh trong ZF. Ông xây dựng một mô hình phức tạp hơn nhiều thỏa mãn ZF¬C (ZF với phủ định của AC) và từ đó chứng minh rằng ZF¬C là nhất quán.
Những kết quả này cho thấy tiên đề chọn độc lập logic với ZF. Giả định ZF là nhất quán không ảnh hưởng gì vì nếu không nhất quán, việc thêm một tiên đề không tác động đến các kết quả đã có. Bởi sự độc lập này, ta không thể dựa vào những tiên đề khác trong lý thuyết tập hợp để quyết định có dùng tiên đề chọn hay không.
Một luận điểm thường được đưa ra cho tiên đề chọn là nó giúp ta chứng minh một số định đề mà nếu không dùng AC sẽ không thể chứng minh được. Nhiều định lý chứng minh dùng tiên đề chọn có một tính tổng quát đẹp: mọi ideal trong một vành chứa trong một ideal tối đại, mọi không gian vectơ có một đại số, và mọi tích của không gian compact là compact. Không có tiên đề chọn, những định lý này có thể sai với những vật thể toán học có lực lượng lớn.
Kết quả độc lập này cũng cho thấy một lớp các mệnh đề toán học, bao gồm tất cả những mệnh đó có thể được phát biểu trong ngôn ngữ số học Peano, là chứng minh được trong ZF nếu và chỉ nếu nó chứng minh được trong ZFC. Những mệnh đề trong lớp này bao gồm mệnh đề khẳng định P = NP, giả thuyết Riemann, và nhiều bài toán chưa có lời giải khác. Khi tìm lời giải cho những bài toán thuộc lớp này, việc sử dụng ZF hay ZFC không khác gì nhau nếu câu hỏi duy nhất là tồn tại một chứng minh. Tuy nhiên, đôi khi chứng minh trong ZFC ngắn hơn là trong ZF.
Tiên đề chọn không phải là mệnh đề quan trọng duy nhất độc lập với ZF. Ví dụ, giả thuyết continuum tổng quát (GCH) không chỉ độc lập với ZF mà còn độc lập với cả ZFC. Tuy nhiên, ZF + GCH kéo theo AC, khiến GCH là mệnh đề mạnh hơn AC, mặc dù cả hai đều độc lập với ZF.
Tiên đề mạnh hơn.
Tiên đề tính dựng được và giả thuyết continuum tổng quát đều bao hàm tiên đề chọn và vì vậy mạnh hơn nó. Trong những thuyết lớp như lý thuyết tập hợp von Neumann–Bernays–Gödel và lý thuyết tập hợp Morse–Kelley, tồn tại một tiên đề gọi là tiên đề chọn toàn cục, mạnh hơn tiên đề chọn cho tập hợp bởi nó cũng áp dụng cho các lớp chính quy. Tiên đề chọn toàn cục có thể được suy ra từ tiên đề giới hạn kích thước. Một tiên đề khác mạnh hơn tiên đề chọn là tiên đề Tarski, được dùng trong lý thuyết tập hợp Tarski–Grothendieck và phát biểu rằng mỗi tập hợp thuộc về một vũ trụ Grothendieck nào đó.
Tương đương.
Có nhiều mệnh đề quan trọng mà trong hệ tiên đề ZF nhưng không có AC lẫn ¬AC, là tương đương với tiên đề chọn. Những mệnh đề quan trọng nhất là bổ đề Zorn và định lý thứ tự tốt. Thực tế, Zermelo ban đầu đưa ra tiên đề chọn để có thể hoàn thành chứng minh định lý thứ tự tốt của mình.