反證法（proof by contradiction）

反證法藉由顯示「否定某主張會導致荒謬」來證明該主張。這是偵探的策略：先說「假設管家是清白的」，然後推導出兩個時鐘必須同時顯示不同時間——一件不可能的事——所以管家畢竟還是有罪。你假設你想要的反面，忠實地順著邏輯走，然後撞上某件不可能為真的事。既然正確的推理永遠不會產生矛盾，你一開始的假設必定是錯的。

形式總是相同。要證明陳述 S，你改為假設「非 S」並當作真的，然後只用有效的推理一步步推出後果，直到抵達一個矛盾——某件既真又假的事，例如「一個有限集合的元素比它自己還多」或「0 = 1」。因為推導本身嚴謹，但結論卻不可能，唯一可能出錯的就是假設「非 S」。因此 S 為真。經典例子證明 2 的平方根是無理數：假設它等於一個已完全約分的分數 p/q，推出 p 和 q 都必須是偶數，與「完全約分」相矛盾。

這個技巧在計算理論裡無所不在。非正規性證明假設某語言是正規的，援引幫浦引理，把一個字串幫浦到語言之外以達到矛盾。停機問題的不可判定性假設存在一台能判定停機的機器，餵給它一個自我指涉的輸入，迫使它與自己唱反調。在每一種情形裡，那個不可能的結論就是收穫，它扼殺了引發它的那個假設。