##EasyReadMore##

9.30.2011

素樸集合論的困難

素樸集合論(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
  • (把質數由小到大排列)第一百個質數
  • x4 - 17x3 + 101x2 - 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]

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