選擇公理

選擇公理是數學中的一條集合論公理。這條公理宣告，對所有非空指標集族formula_1，總存在一個索引族formula_2，對每一個formula_3，均有formula_4。選擇公理最早於1904年，由恩斯特·策梅洛為證明良序定理而公式化完成。非正式地說，選擇公理宣告：給定一些盒子雙鞋子，則我們可以選取每雙鞋左邊的鞋子構成一個具體的選擇，由於在鞋子之中“存在具體的選擇規則”(左邊的鞋子不同於右邊的鞋子)，故不需要選擇公理，仍可做出有效的選擇。然而，假設有無限雙襪子，且每雙襪子都沒有可區分的特徵，在這種情況下，有效的選擇只能透過選擇公理得到。儘管曾具有爭議性，選擇公理現在已被大多數數學家毫無保留地使用著，例如帶有選擇公理的策梅洛-弗蘭克爾集合論。數學家們使用選擇公理的原因是，有許多被普遍接受的數學定理，比如是吉洪諾夫定理，都需要選擇公理來證明。現代的集合論學家也研究與選擇公理相矛盾的公理，例如決定公理。在一些構造性數學的理論中會避免選擇公理的使用，不過也有的將選擇公理包括在內。陳述.首先定義幾個概念：集族：指由非空集合組成的集合。選擇函式：它是一個集族上的函式。它規定：對於所有在集族formula_5中的集合formula_6，formula_7是"formula_6"的一個元素。那麼，選擇公理表示：對於所有的集族，均存在選擇函式。上述可表示為：formula_9或者：設formula_5是一個集族，則存在著在formula_5上定義的一個選擇函式formula_12。該定理也可表達為：集族上的任意笛卡爾積總是非空的。變體.第二個版本的選擇公理聲稱：給定由相互不交的非空集合組成的任何集合，存在著至少一個集合，它與每個非空集合恰好有一個公共元素。第三個版本聲稱：對於任何集合formula_13，"formula_13"的冪集有一個選擇函式。使用這個版本的作者通常談及“在"formula_13"上的選擇函式”，但要注意這裡選擇函式的概念是稍微不同的。它的定義域是"formula_13"的冪集，因此對任何集合"formula_13"有意義；至於本文中其他地方用的定義，在“集合的蒐集”上的選擇函式的定義域是這個蒐集，所以只對集合的集合有意義。透過這個變體的定義，選擇公理也可以簡潔的陳述為所有集合有一個選擇函式。它等價於對於任何集合"formula_13"有一個函式使得對於"formula_13"的任何非空子集formula_20，formula_21。而選擇公理的否定表達為：有一個集合"formula_13"使得對於所有函式"formula_12"，有一個"formula_20"使得formula_26。術語.以下列出了這篇條目中各種與“選擇公理”相關的縮寫：使用.直到19世紀晚期，選擇公理的使用一直都沒有得到明確宣告。例如，建立了只包含非空集合的集合formula_5之後，當時的數學家可能會直接說"設對於"formula_5"中所有formula_6有formula_30是"formula_6"的成員之一"。一般來說，要是不用選擇公理，是不可能證明formula_32的存在性的。這一點直到策梅洛之前似乎沒有引起人們的注意。不是所有的情況都需要選擇公理。選擇公理對於那些沒有可定義的選擇才有必要。值得指出的是，對於有限集合"formula_5"，選擇公理的有限版本可以透過其他集合論公理推導得出。在這種情況下，它等價於說我們有多個盒子，每個包含至少一個物體，則我們可以從每個盒子恰好選擇一個物體。顯然我們可以這麼做：從第一個盒子開始，選擇其中的一個物體；到下一個盒子，選擇一個物體；如此類推。因為盒子數量有限，所以我們的選擇過程最後一定會結束。這裡給出的選擇函式是明確的：第一個盒子對應於第一個選擇的物體，第二個盒子對應於第二個選擇物體；如此類推——此法之所以可行，是因為序對公理的原因。可以透過數學歸納法做出對所有有限集合的形式證明。例子.對於特定的無限集合"formula_5"，也可以避免使用選擇公理。例如，假設"formula_5"的元素是自然數的集合。每個自然數的非空集合都有一個最小元，所以要指定我們的選擇函式，我們可以簡單的把每個集合對映到這個集合的最小元。這使得我們可以從每個集合明確地選擇元素，以及寫出一個明確的表示式，說明我們的選擇函式如何取值。在能夠指定一個明確選擇方式的時候，選擇公理都是沒有必要的。當缺乏從每個集合得到元素的直觀選擇方式時，困難就出現了。如果我們不能做明確的選擇，我們如何知道我們的這個集合存在？例如，假設"X"是實數的所有非空子集的集合。首先我們也許想套用有限的情況去處理"formula_5"。如果我們嘗試從每個集合選擇一個元素，那麼，因為實數集合是無限不可數，我們的選擇過程永遠不會結束。亦因如此，我們永遠不能生成對"formula_5"的成員的選擇函式。所以這種方法不能奏效。其次我們可以嘗試給每個集合指定最小元素這種方式。但是某些實數的子集沒有最小元素。例如，開區間formula_38沒有最小元素：如果formula_39在formula_38中，則formula_41也在其中，而formula_41總是嚴格的小於formula_39。所以這種方法也不行。我們之所以能夠從自然數的非空子集選擇最小元素，是因為自然數上有一個自然良序：所有自然數的非空子集都有一個唯一的最小元素。因此，我們可以採取這樣的思路，「即使實數的正常排序並非良序，也有可能找到一個排序使得實數是良序的。在這個排序下，總能夠選擇實數非空子集的最小元素。這樣便得到了選擇函式」。問題就變成如何構造這樣的排序。而事實上，“存在一個排序使得所有集合可以是良序的”這一命題成立，當且僅當選擇公理為真。有必要用到選擇公理的證明總是非構造性的：即使證明給出了一個物件，精確地說出那個物件卻是不可能的。如果我們不能寫出選擇函式的定義，則我們的選擇就不是非常明確的。這是一些數學家不喜歡選擇公理的理由之一。例如，構造主義者論斷說所有涉及存在性的證明都應當是完全明確的；構造任何存在的物件應當是可能的。他們拒絕選擇公理#重定向構造性數學.像上面討論的那樣，在ZFC中，選擇公理能為一個不能明確構造出的物件給出“非構造性證明”來證明其存在性。然而，ZFC依然是在經典邏輯下被形式化的。在構造性數學領域，選擇公理仍被深入研究，而當中應用的是非古典邏輯。在構造性數學的不同版本中，選擇公理的狀況也有所差別。在直覺型別論和高階的Heyting算術中，選擇公理的適當陳述可以是作為一個公理，又或者作為一個可證明的定理。認為選擇公理可被視作是構造性的：但在中，迪亞科內斯庫定理表明選擇公理蘊涵了排中律。因此選擇公理在構造性集合論中並非普遍被接受。在型別論中的選擇公理與在構造性集合論中的選擇公理的區別是，前者不具有外延性而後者具有。一些構造性集合論的結果用到了可數選擇公理或依賴選擇公理，這兩個公理在構造性集合論內並不蘊涵排中律。儘管可數選擇公理在構造性數學中的應用特別廣泛，它的使用也受到質疑。強形式公理.可構造性公理與連續統假設都蘊涵了選擇公理，更準確地說，兩者都嚴格強於選擇公理。在類理論中，如馮諾伊曼-博內斯-哥德爾集合論和Morse–Kelley集合論，存在一個叫全域性選擇公理的公理，它比選擇公理要強，因其同時也適用於真類。全域性選擇公理可由大小限制公理推出。結論.哥德爾證明了選擇公理與ZF的相對協調性。保羅·寇恩用力迫法證明了選擇公理獨立於ZF。Translated in: Jean van Heijenoort, 2002. "From Frege to Godel: A Source Book in Mathematical Logic, 1879-1931". New edition. Harvard Univ. Press. ISBN 978-0-674-32449-7.* 1904. "Proof that every set can be well-ordered," 139-41.* 1908. "Investigations in the foundations of set theory I," 199-215.