対偶・背理法
アプリで開く →
進み具合を記録できるアプリ版です（ノード単位の直リンクはありません）
要点
対偶が元の命題と同値であるのは、集合で見ればP⊂QとQの補集合⊂Pの補集合が同じことを表しているから。この一枚の絵を持っていれば、直接証明しにくい命題も対偶を取れば一瞬で見通しがつくことがある。背理法は、結論の否定と仮定を組み合わせて矛盾を導く手法で、「√2が無理数」の証明が最も有名な型。整数・無理数の論証ではこの2つが標準装備になる。
こんなときに使う
- 「nが偶数ならば」型の証明で直接示しにくいときは対偶を疑う
- 「〜は無理数である」「〜は存在しない」型の証明は背理法が第一候補
- 証明の中で『すべて』『存在しない』という否定しにくい主張が出てきたら背理法
手順
- 1. 対偶：元の命題の逆かつ否定（¬q⇒¬p）を作り、それを直接示す
- 2. 背理法：結論を否定すると仮定し、既知の事実と組み合わせて矛盾を導く
- 3. 矛盾が出たら、仮定（結論の否定）が誤りだったと結論する
例題
n²が偶数ならばnは偶数であることを示せ。
解答
- 対偶「nが奇数ならばn²は奇数」を示す。
- nが奇数のときn=2k+1（kは整数）とおける。
- n²=(2k+1)²=4k²+4k+1=2(2k²+2k)+1 で、これは奇数の形。
- ∴ 対偶が真なので、元の命題も真。
別解・ほかの見方
- 直接証明を試みて行き詰まったら対偶に切り替える、という判断力も重要
落とし穴
- 対偶を作るときに逆にするのを忘れる（¬q⇒¬pではなくq⇒¬pなどの誤り）
- 背理法で仮定した否定を最後まで使い切らずに終える
- 背理法の仮定を最後まで使い切らない
なぜ大事か
整数・無理数の論証で必須
東大での出方
整数の論証、無理数の証明で頻出。単独の証明問題として、また整数問題の一部として組み込まれる。
確認問題
- √3が無理数であることを背理法で示せ
- n²が3の倍数ならばnも3の倍数であることを対偶で示せ
発展
無限降下法（背理法の一種で、最小の反例を仮定してより小さい反例を作り矛盾を導く）。x²+y²=3z²型の非存在証明で使う。
前提になるノード
このノードを前提にするノード
「集合と命題」のノード
解説は自作です。誤りに気づいたら お問い合わせ（/contact/）から教えてください。