素樸集合論的困難

素樸集合論（naive  set theory）是這樣定義集合的：

{x | x符合條件A、B、C…}

意思是，把符合A、B、C…這些條件的東西蒐集起來，就可以得到一個集合。

例如，屬於{x | x是猫}這個集合裡的東西都是猫，屬於{x | x是上帝}這個集合裡的東西都是上帝。可能有人會爭論{x | x是上帝}是不是空集合，如果不是的話那個集合裡有幾個東西，不過這對素樸集合論沒什麼威脅。真正的麻煩是，有些集合的條件會產生悖論。

1906年G. G. Berry提出了{x | x是可以用一行字定義的正整數（x is a positive integer definable in one line of type）} 這個集合。這個集合裡的東西有：

• 12345
• （把質數由小到大排列）第一百個質數
• x⁴ - 17x³ + 101x² - 247x + 210 = 0這個多項式的解
• …

然而，有些正整數沒辦法只用一行字定義，因此不屬於{x | x是可以用一行字定義的正整數} 這個集合。不過我們可以為這些沒辦法只用一行字定義的正整數排大小，最小的那個數可以用下列這句話定義：

最小的不可以用一行字定義的正整數。

而這句話只有一行，所以該數屬於{x | x是可以用一行字定義的正整數} 這個集合！但是怎麼會有東西不屬於{x | x是可以用一行字定義的正整數}而且屬於{x | x是可以用一行字定義的正整數}呢？


另一個悖論來自羅素（Russell），所以叫羅素悖論（Russell's paradox），不過Ernst Zermelo也自行想到這個悖論。

1902年時，羅素提出了{x | x ∉ x}這個集合，這個集合蒐集不屬於自己的東西。這個集合裡的東西有：

• {x | x是猫}（{x | x是猫}這個集合裡蒐集的東西是猫，{x | x是猫}是集合而不是猫，所以{x | x是猫}這個集合裡不會蒐集「{x | x是猫}」這個東西）
• {x | x是上帝}
• …

那麼，{x | x ∉ x}這個集合屬不屬於自己？{x | x ∉ x}要嘛屬於自己，要嘛不屬於自己，如果它屬於自己，表示它滿足{x | x ∉ x}中x ∉ x這個條件，那麼它不屬於自己。如果它不屬於自己，表示它沒有滿足{x | x ∉ x}中x ∉ x這個條件，所以它屬於自己。

不管{x | x ∉ x}這個集合屬不屬於自己，都會產生矛盾。

參考資料：
P.4-6, Enderton, H. B. (1977) Elements of set theory [Academic Press]

相關文章：
羅素悖論 - 哲學與思方