悖論

理髮師悖論又稱為羅素悖論，是由伯特蘭·羅素在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％ 。這是個更難的問題需要用到取捨原理。結果(假設生日依然按照平均分佈)正像在標準生日問題中那樣令人吃驚: