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:

Với một họ các tập hợp khác rỗng bất kỳ, tích Descartes của chúng là một tập khác rỗng.

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ó:
Với mọi tập  gồm các tập hợp khác rỗng đôi một rời nhau, tồn tại ít nhất một tập hợp  mà có chung đúng một phần tử với mỗi tập thuộc .

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:
Với mọi tập hợp , tập lũy thừa của  (bỏ tập rỗng) có một hàm chọn.
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
Mỗi tập hợp đều có một hàm chọn.
tương đương với
Với mọi tập hợp  tồn tại hàm số  sao cho với mỗi tập con khác rỗng  của ,  thuộc 
Mệnh đề phủ định của tiên đề chọn sẽ là:
Tồn tại một tập hợp  sao cho với mọi hàm số  (định nghĩa trên các tập con khác rỗng của ) tồn tại một tập con khác rỗng  của  sao cho  không thuộc

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.

Lý thuyết tập hợp
Định lý thứ tự tốt: Mọi tập hợp đều có thể được sắp thứ tự tốt. Hệ quả là mọi số đếm có một số thứ tự ban đầu.
Định lý Tarski về lựa chọn: Với mọi tập vô hạn , tồn tại một song ánh giữa các tập hợp  và 
Tam phân: Giữa hai tập hợp, hoặc chúng có cùng lực lượng, hoặc một tập hợp có lực lượng nhỏ hơn tập hợp kia.
Cho hai tập hợp khác rỗng, tồn tại một toàn ánh từ một tập này sang tập còn lại.
Tích Descartes của mọi họ các tập khác rỗng là khác rỗng.
Định lý König: Nói đơn giản, tổng một chuỗi các số đếm là bé hơn tích của chuỗi các số đếm lớn hơn. ("nói đơn giản" là vì tổng hay tích của một "chuỗi" các số đếm không thể được định nghĩa mà không có một số yếu tố của tiên đề chọn.)
Mọi toàn ánh có một hàm ngược bên phải.
Lý thuyết thứ tự
Bổ đề Zorn: Mọi tập sắp thứ tự một phần khác rỗng trong đó mọi xích (tức tập con sắp thứ tự toàn phần) có cận trên chứa ít nhất một phần tử tối đại.
Nguyên lý tối đại Hausdorff: Trong một tập sắp thứ tự một phần, mọi tập con sắp thứ tự toàn phần được chứa trong một tập con sắp thứ tự toàn phần tối đại. Nguyên lý yếu hơn "Mọi tập sắp thứ tự một phần có một tập con sắp thứ tự toàn phần tối đại" cũng tương đương với AC trong ZF.
Bổ đề Tukey: Mọi họ có đặc trưng hữu hạn có một phần tử tối đại đối với phép chứa.
Nguyên lý đối xích: Mọi tập sắp thứ tự một phần có một đối xích tối đại.
Đại số trừu tượng
Mọi không gian vectơ có một cơ sở.
Định lý Krull: Mọi vành có đơn vị không tầm thường chứa một ideal tối đại.
Với mọi tập khác rỗng  tồn tại phép toán hai ngôi định nghĩa trên  biến nó thành nhóm. (Một phép toán hai ngôi có tính giản ước là đủ, xem cấu trúc nhóm và tiên đề chọn.)
Mọi tập hợp là một đối tượng xạ ảnh trong phạm trù Set của các tập hợp.
Tôpô tập điểm
Định lý Tychonoff: Mọi tích của các không gian tôpô compact thì compact.
Trong không gian tôpô tích, đóng của tích các tập con bằng tích của các đóng.
Logic toán học
Nếu  là một tập các phát biểu logic bậc nhất và  là một tập con nhất quán của  thì  được chứa trong một tập tối đại trong số những tập con nhất quán của .
Lý thuyết đồ thị
Mọi đồ thị liên thông có một cây bao trùm.

Chú thích

Tham khảo
 
 
 
 
 
 
 Per Martin-Löf, "100 years of Zermelo's axiom of choice: What was the problem with it?", in Logicism, Intuitionism, and Formalism: What Has Become of Them?, Sten Lindström, Erik Palmgren, Krister Segerberg, and Viggo Stoltenberg-Hansen, editors (2008). 
 
 , available as a Dover Publications reprint, 2013, .
 

 
 
George Tourlakis, Lectures in Logic and Set Theory. Vol. II: Set Theory, Cambridge University Press, 2003. 
 
Ernst Zermelo, "Untersuchungen über die Grundlagen der Mengenlehre I," Mathematische Annalen 65: (1908) pp. 261–81. PDF download via digizeitschriften.de
Translated in: Jean van Heijenoort, 2002. From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931. New edition. Harvard University Press. 
1904. "Proof that every set can be well-ordered," 139-41.
1908. "Investigations in the foundations of set theory I," 199–215.

Liên kết ngoài
Axiom of Choice  trong Springer Encyclopedia of Mathematics. 
Axiom of Choice and Its Equivalents tại ProvenMath.
Consequences of the Axiom of Choice , based on the book by Paul Howard  and Jean Rubin.
.

chọn