理髮師悖論又稱為羅素悖論,是由伯特蘭·羅素在1901年提出的。它的出現是由於樸素集合論對於元素的不加限制的定義。由於當時集合論以稱為數學理論的基礎,這一悖論的出現直接導致了第三次數學危機,也引發了眾多的數學家對這一問題的補救,最終形成了現在的公理化集合論。同時,羅素悖論的出現促使數學家認識到將數學基礎公理化的必要性。
內容

一個城市裡唯一的理髮師只給所有不給自己理髮的人理髮。這個城市不可能存在,因為:

* 如果理髮師不給自己理髮,他需要遵守規則,給自己理髮
* 如果理髮師給自己理髮,如遵守規則,他不准給自己理髮

換用集合語言:

可以把集合分為兩類,凡不以自身為元素的集合稱為第一類集合;凡以自身作為元素的集合稱為第二類集合。顯然每個集合或為第一類集合或為第二類集合。設mathbf{A}為第一類集合的全體組成的集合。

* 如果mathbf{A}是第一類集合,由集合mathbf{A}的定義知:mathbf{A}應該是mathbf{A}的元素,這表明mathbf{A}是第二類集合
* 如果mathbf{A}是第二類集合,那麼mathbf{A}是它自身的元素

二者皆導出矛盾,而整個討論邏輯上是沒有問題的。問題只能出現在集合的定義上。

補救

由於羅素悖論的出現所引發的第三次數學危機,公理化集合論勢在必行。德國數理邏輯學家策梅洛(Zermelo,1871年-1953年)應用自己的公理系統,使得集合在公理的限制下不會太大,從而避免了羅素悖論。經過改進,這一系統形成了現在被稱為ZF系統的公理集合論體系。這個體系至今沒有發現悖論。

悖論,亦作弔詭或詭局,是指一種導致矛盾的命題。悖論的英文paradox一詞,來自希臘語「para+dokein」,意思是「多想一想」。 如果承認它是真的,經過一系列正確的推理,卻又得出它是假的;如果承認它是假的,經過一系列正確的推理,卻又得出它是真的。古今中外有不少著名的悖論,它們震撼了邏輯和數學的基礎,激發了人們求知和精密的思考,吸引了古往今來許多思想家和愛好者的注意力。解決悖論難題需要創造性的思考,悖論的解決又往往可以給人帶來全新的觀念。
唐吉訶德悖論是指記載在唐吉訶德小說中的一個涉及悖論的故事。
注意:下文記有作品情節、結局或其他相關內容,可能降低欣賞原作時的興致。

桑丘·潘薩在他治理的島上頒佈一條法例,規定過橋的旅客必需誠實地表示自己的目的,否則就會被絞死。 有一個旅客在見到橋上的告示後,宣稱自己過橋是要被絞死的。

這使執法者感到為難:如果該人的言論為真,則他應被釋放,但如此一來其言論即變為假。如其言論為假,則他會被絞死,但如此一來其言論即變為真。該旅客被帶到桑丘面前,而桑丘最後把他釋放。

祖父悖論是一種時間旅行的悖論,科幻故事中常見的主題。最先由法國科幻小說作家雷納·巴雅瓦(René Barjavel)在他1943年的小說《不小心的旅遊者》(Le Voyageur Imprudent)中提出。情景如下:

假設你回到過去,在自己父親出生前把自己的祖父母殺死;因為你祖父母死了,就不會有你的父親;沒有了你的父親,你就不會出生;你沒出生,就沒有人會把你祖父母殺死;若是沒有人把你的祖父母殺死,你就會存在並回到過去且把你的祖父母殺死;等等。

物理中的祖父悖論

[編輯] 平行宇宙

物理學家認為,也許世界是由無數個平行宇宙組成的,而當你回到過去殺你的祖父母時,你殺的其實是另一個宇宙的人(或者你的這個舉動也可以創造一個新的平行宇宙),而這個人(你的「祖父」或「祖母」)的死只會使那個平行宇宙的「你」不再存在,而這個平行宇宙的「你」則平安無事。

* 在量子物理中,「多個世界」理論可以如此理解:對於每一個似乎隨機的事件來說,只要它的可能性不是零,它所有可能的情形都會在不同的平行世界中發生,造成歷史的分支。物理學家大衛·多伊奇(David Deutsch)認為,當你回到過去去殺你的祖父母時,你其實進入了另一個世界,殺的是另一個世界的人。
* M理論,作為至今最有可能結合5種不同的弦論的理論,是如此解釋平行宇宙的:多個三維的「膜」可以同時在一個四維的宇宙(不是愛因斯坦的三維空間加一維時間;見膜宇宙學)中存在;這些膜之間的撞擊會在膜中產生大量的能量——這也可以解釋大爆炸是如何起源的。可是,M理論並不能解釋不同膜的歷史之間的關係,也不能肯定,當你回到過去時,你會進到另一個膜裡面。

生日悖論是指,如果一個房間里有23個或23個以上的人,那麼至少有兩個人的生日相同的機率要大於50%。這就意味著在一個典型的標準小學班級(30人)中,存在兩人生日相同的可能性更高。對於60或者更多的人,這種機率要大於99%。從引起邏輯矛盾的角度來說生日悖論並不是一種悖論,從這個數學事實與一般直覺相抵觸的意義上,它才稱得上是一個悖論。大多數人會認為,23人中有2人生日相同的機率應該遠遠小於50%。計算與此相關的機率被稱為生日問題, 在這個問題之後的數學理論已被用於設計著名的密碼攻擊方法:生日攻擊。
對此悖論的解釋

理解生日悖論的關鍵在於領會相同生日的搭配可以是相當多的。如在前面所提到的例子,23個人可以產生C(23,2)= 23 × 22/2 = 253 種不同的搭配,而這每一種搭配都有成功相等的可能。從這樣的角度看,在253種搭配中產生一對成功的配對也並不是那樣的不可思議。

換一個角度,如果你進入了一個有著22個人的房間,房間里的人中會和你有相同生日的機率便不是50:50了,而是變得非常低。原因是這時候只能產生22種不同的搭配。生日問題實際上是在問任何23個人中會有兩人生日相同的機率是多少。

應用

生日悖論普遍的應用於檢測哈希函數:N-位長度的哈希表可能發生碰撞測試次數不是2N次而是只有2N/2次。這一結論被應用到破解密碼學散列函數的生日攻擊中。

生日問題所隱含的理論已經在[Schnabel 1938]名字叫做capture-recapture的統計試驗得到應用,來估計湖裡魚的數量。

[編輯] 不平衡機率

就像上面提到的,真實世界的人口出生日期並不是平均分佈的。這種非均衡生日機率問題也已經被解決。[Klamkin 1967]

[編輯] 近似匹配

此問題另外一個范化就是求得要在隨機選取多少人中才能找到2個人生日相同,相差1天,2天等的機率大於50% 。這是個更難的問題需要用到取捨原理。結果(假設生日依然按照平均分佈)正像在標準生日問題中那樣令人吃驚:

cloud
Author

邁入攻城獅 N 年。愛好無厘頭的事物、旅遊、攝影、減肥、慢跑、占星、展覽、食記、偶爾在邏輯的世界亂轉