第6章 逆否與反證
6.1 逆命題 不等於逆否命題
原命題P⇒Q的逆命題是Q⇒P；逆否命題是¬Q⇒¬P。第4章已用失敗真值相同證明，原命題與逆否命題同真。這條規則讓我們改變起點，但不改變要證明的內容。
例如「4的倍數一定偶」與「非偶整數一定不是4的倍數」同真；「偶整數一定是4的倍數」則不是等價改寫。若只看見箭頭反向就使用規則，容易把逆命題誤當逆否。
6.2 反證法的暫時假設
要證明命題T，可暫時假設¬T，並在已允許的背景條件下推出矛盾。古典邏輯據此排除¬T而得到T。矛盾必須是某句和其否定同時成立，或與已建立的事實直接衝突；「很奇怪」不是矛盾。
要證明P⇒Q時，反證可同時假設P和¬Q，再導出矛盾。與逆否證明相比，兩者常共用計算，但成稿要交代最後排除了哪個暫時假設。
6.3 例題
例題1 平方偶則原數偶
對n∈ℤ證明：若n²為偶數，則n為偶數。改證逆否：若n不是偶數，整數除以2的餘數性質使n=2k+1，k∈ℤ。
平方得到n²=4k²+4k+1=2(2k²+2k)+1，為奇數，因此不是偶數。這證明逆否，便得到原命題。此處使用的是整數的偶奇分解，不能改在任意實數上仍說「非偶即奇」。
例題2 √2不是有理數
反設√2為有理數，寫成p/q，其中p、q為互質整數且q>0。這樣的最簡形式可由整數分子分母除以共同最大公因數得到。平方並乘q²，得p²=2q²，所以p²偶；由例題1，p也偶，設p=2r。
代回得到4r²=2q²，整理成q²=2r²，故q也偶。於是2同時整除p、q，與兩者互質衝突。因此反設不成立，√2不是有理數。證明依賴已引入的正實數平方根，不在這裡重新構造實數。
例題3 不存在最大的整數
反設m是最大整數，即m∈ℤ且每個n∈ℤ都有n≤m。因整數對加1封閉，m+1也是整數，卻有m+1>m，與最大性矛盾。
這也可直接寫成「對每個整數m，都能構造更大的m+1」。選擇反證或直接證明取決於何者最清楚，不是一定要把簡單構造改寫得更長。
例題4 三整除平方的必要條件
對n∈ℤ證明：若3∣n²，則3∣n。採逆否，若3不整除n，整數除法餘數使n=3k+1或3k+2。
第一種平方為9k²+6k+1=3(3k²+2k)+1；第二種平方為9k²+12k+4=3(3k²+4k+1)+1。兩種平方除以3都餘1，不被3整除，所以逆否成立。不能把這條結論不加檢查地換成任意合數：4∣2²卻4不整除2。
6.4 不要用待證結論證明自己
例題2若開頭就說「√2不能化成分數，所以無理」，只是重述目標。合法起點是反設一個最簡分數存在，再使用整數與偶性結果導出衝突。
反證不是「找不到答案就當不存在」。要證明不存在，必須讓任意假設的合格候選都遭遇同一個矛盾。只試到分母1000仍沒找到，只是有限搜尋結果。
6.5 練習
- B05-C06-Q01 寫出「若整數n是6的倍數，則n是3的倍數」的逆命題與逆否命題，判斷真假。
- B05-C06-Q02 對整數n，用逆否證明：若n²為奇數，則n為奇數。
- B05-C06-Q03 證明不存在最小的正實數。
- B05-C06-Q04 由√2無理，證明3+√2無理。
- B05-C06-Q05 對整數a、b，證明若ab為奇數，則a、b都為奇數。
- B05-C06-Q06 以模3餘數證明√3無理，交代最簡分數資格。
- B05-C06-Q07 「若4∣n²則4∣n」是否可照例題4直接推廣？
- B05-C06-Q08 證明若x∈ℝ且x>0，則1/x>0；使用反設時哪些運算先有資格？
- B05-C06-Q09 有人說「前一千個分母都找不到√2的分數表示，所以它無理」。指出缺口。
- B05-C06-Q10 用反證證明：若有限集合A、B滿足A⊆B且有相同元素個數，則A=B。
6.6 完整解答
Q01
逆命題是「若3∣n，則6∣n」，為假，n=3就是合格反例。逆否是「若3不整除n，則6不整除n」，為真，因它與原命題同真；原命題由n=6k=3(2k)直接得到。不要把「非3倍數」改成「非整數」。
Q02
逆否是「若n不是奇數，則n²不是奇數」。整數n非奇即偶，寫n=2k，便有n²=2(2k²)為偶，故非奇。這個逆否證明完成原命題，沒有先假設n本來就是奇數。
Q03
反設m是最小正實數，則m>0。m/2也是正實數，且0<m/2<m，與最小性矛盾。與最大整數的例子相比，這裡構造的是更小且仍留在正實數論域的對象。
Q04
反設r=3+√2為有理數。整數3為有理數，有理數對減法封閉，所以√2=r−3也為有理數，與已證結果矛盾。因此3+√2無理。需要明說封閉性，不能只憑外觀保留根號就斷言無理。
Q05
若a、b並非都奇，則至少一個為偶。假設a偶，依第5章得ab偶；若b偶同理。兩種情形都與ab奇矛盾，故兩者都奇。這裡把「且」的否定正確轉成了「至少一邊非奇」。
Q06
反設√3=p/q，p、q∈ℤ互質且q>0。平方得p²=3q²，故3∣p²；由例題4得p=3r。代入後9r²=3q²，即q²=3r²，再得3∣q。於是p、q同有因數3，與互質矛盾，所以√3無理。
Q07
不能。取整數n=2，平方為4，所以4∣n²；但2不是4的倍數，結論失敗。例題4對3的餘數分類有明確計算，並不是一條任意換除數仍成立的規則。
Q08
x>0先保證x≠0，所以1/x已有定義。若反設1/x≤0，兩邊乘正數x不改不等號方向，得到1≤0，與實數次序矛盾。不能在尚未確定x非零前就把倒數當作合法對象。
Q09
分母可能超過一千，有限搜尋沒有覆蓋全部正整數分母。要證明無理，須處理任意可能的整數p與正整數q；例題2的最簡分數矛盾就是一般排除理由。搜尋失敗既不是一般不存在證明，也沒有推翻可能更大的候選。
Q10
反設A≠B。因A⊆B，必有至少一個b∈B卻b∉A。有限的B於是至少包含A的全部元素再加一個不同元素，故|B|≥|A|+1，與個數相同矛盾，得到A=B。有限性是本題關鍵；無窮集合可能與真子集有雙射，第10章會看到例子。
6.7 本章回看
改走逆否時保留原論域；走反證時標明暫時假設與最後的衝突。下一章把這些條件用來拆解看似合理卻無效的論證。