対偶による証明

同義語：対偶法対偶証明法対偶proof by contrapositioncontrapositive

概要

前提知識: 含意, 否定, 全称記号

整数 $n$ について「$n^2$ が $3$ で割り切れるならば、$n$ も $3$ で割り切れる」を示したいとする。仮定 $n^2=3m$ から $n$ の形を引き出すのは、そのままでは難しい。ところが向きを変えて「$n$ が $3$ で割り切れないならば、$n^2$ も $3$ で割り切れない」を示すのはやさしい。$n$ が $3$ で割り切れなければ $n=3k+1$ か $n=3k+2$ と書け、どちらでも $n^2$ を $3$ で割った余りは $1$ になるからである。この 2 つの主張は、言い回しは違うが同じことを述べている。条件文「$P$ ならば $Q$」を示す代わりに「$Q$ でないならば $P$ でない」を示す証明の方法を 対偶による証明 という。
対偶による証明の正しさそのものは真理値表で確かめられる短い事実である。実際に使うときに注意が要るのは、結論の否定を正しく作ること、量化の範囲を変えないこと、仮定が複数あるときに残りの仮定を落とさないことの 3 点である。

定義

対偶と対偶による証明

命題 $P,Q$ に対し、条件文 $P\to Q$ の対偶（contrapositive）とは、条件文 $\lnot Q\to\lnot P$ のことである。
集合 $X$ の各元 $x$ について真偽が定まる条件 $P(x),Q(x)$ に対し、主張
$$ \forall x\in X\ \bigl(P(x)\to Q(x)\bigr) $$
の対偶とは、主張
$$ \forall x\in X\ \bigl(\lnot Q(x)\to\lnot P(x)\bigr) $$
のことである。量化の範囲 $X$ と量化子 $\forall$ はそのまま残す。
条件文を証明するために、その対偶を証明する方法を 対偶による証明（proof by contraposition）または 対偶法 という。すなわち、$\forall x\in X\ (P(x)\to Q(x))$ を示すために、$X$ の元 $x$ を任意にとって $\lnot Q(x)$ を仮定し、$\lnot P(x)$ を導く。

条件文 $P\to Q$ に対し、$Q\to P$ を逆、$\lnot P\to\lnot Q$ を裏という（集合と論理：必要条件・十分条件の記事の定義「逆・裏・対偶」、含意の記事の定義「含意」）。4 つの条件文の関係は次のとおりである。

名前	形	もとの $P\to Q$ との真偽
もとの条件文	$P\to Q$	―
対偶	$\lnot Q\to\lnot P$	つねに一致する
逆	$Q\to P$	一致するとは限らない
裏	$\lnot P\to\lnot Q$	一致するとは限らない（逆とはつねに一致する）

$P\to Q$ と $\lnot Q\to\lnot P$ が $P,Q$ の真偽によらず同じ真偽をとることは、論理と命題の記事の命題「基本的な恒真式」と、集合と論理：必要条件・十分条件の記事の定理「対偶の原理」で真理値表によって示されている（Ham18 §2.6、p. 51 にも同じ真理値表がある）。対偶による証明が正しい証明になるのはこの同値による。量化を含む形と、仮定が複数ある形は thm-cp-quantified で示す。逆と裏がつねに同じ真偽をとることは prop-cp-converse-inverse で示す。
対偶による証明は、次の骨組みで書かれる（Ham18 §5.1、p. 129、Lev24 §1.4.3、p. 69）。

「$x\in X$ を任意にとり、$Q(x)$ でないと仮定する。」
仮定 $\lnot Q(x)$ と定義・既知の事実から推論を重ねる。
「したがって $P(x)$ でない。」
「対偶が示されたので、$P(x)$ ならば $Q(x)$ である。」
最初の行で仮定するのは結論の否定 $\lnot Q(x)$ であり、最後の行で得るのは仮定の否定 $\lnot P(x)$ である。途中でもとの仮定 $P(x)$ は使わない。

直感

対偶をとると、仮定と結論の役割が入れ替わり、両方に否定がつく。この入れ替えで得をするのは、否定がついたほうが扱いやすい場合である。

結論の否定が「存在」の形になる場合。「$f$ が単射である」の否定は「$f(x)=f(x')$ となる異なる $x,x'$ がある」で、具体的な 2 点が手に入る。
結論の否定が具体的な場合分けになる場合。「$3$ で割り切れない」は「余りが $1$ か $2$」になる。「合成数である」は「$n=ab$、$1< a,b< n$」という分解になる。
もとの仮定が扱いにくい場合。「$2^n-1$ は素数である」から $n$ について何かを引き出すのは難しいが、「$n$ は素数でない」から $2^n-1$ の約数を作るのはやさしい。
逆に、もとの仮定が具体的で、結論の否定が「すべての〜について〜でない」という扱いにくい形になるなら、直接証明のほうが向く。情報を仮定から結論の向きに運びやすいか、結論の否定から仮定の否定の向きに運びやすいかで選ぶ（Ham18 §5.1、p. 130）。

例

平方が 3 で割り切れる整数

整数 $n$ について、$n^2$ が $3$ で割り切れるならば、$n$ は $3$ で割り切れる。

対偶「$n$ が $3$ で割り切れないならば、$n^2$ は $3$ で割り切れない」を示す。
$n$ が $3$ で割り切れないとする。$n$ を $3$ で割った余りは $1$ か $2$ なので、ある整数 $k$ を用いて $n=3k+1$ または $n=3k+2$ と書ける。
$n=3k+1$ のとき、$n^2=9k^2+6k+1=3(3k^2+2k)+1$ である。
$n=3k+2$ のとき、$n^2=9k^2+12k+4=3(3k^2+4k+1)+1$ である。
どちらの場合も $n^2$ を $3$ で割った余りは $1$ であり、$n^2$ は $3$ で割り切れない。対偶が示されたので、もとの主張が成り立つ。$\square$

この命題から、背理法で $\sqrt3$ が無理数であることが示せる。$\sqrt3=a/b$（$a,b$ は正の整数で、$a/b$ は既約分数、すなわち $a,b$ の少なくとも一方は $3$ の倍数でない）とすると $a^2=3b^2$ なので、この命題により $a=3c$ と書け、$b^2=3c^2$ から同じく $b$ も $3$ の倍数となり、$a,b$ がともに $3$ の倍数となって矛盾する。背理法の中で対偶による証明が部品として使われる典型である。

すべての正の数以下である実数

実数 $x$ が、すべての実数 $\varepsilon>0$ について $x\le\varepsilon$ を満たすならば、$x\le0$ である。

仮定は $\forall\varepsilon>0\ (x\le\varepsilon)$、結論は $x\le0$ である。対偶をとると、仮定の否定 $\lnot\bigl(\forall\varepsilon>0\ (x\le\varepsilon)\bigr)$ が結論になる。否定の記事の定理「否定を内側へ移す規則」により、これは $\exists\varepsilon>0\ \lnot(x\le\varepsilon)$ と同値である（範囲の条件 $\varepsilon>0$ は変わらない）。さらに実数の大小は全順序なので、同じ記事の定理「順序の否定と全順序」により、$\lnot(x\le0)$ は $x>0$ と、$\lnot(x\le\varepsilon)$ は $\varepsilon< x$ と同値である。したがって示すべき対偶は
「$x>0$ ならば、ある $\varepsilon>0$ について $\varepsilon< x$」
である。$x>0$ とし、$\varepsilon:=x/2$ とおく。$\varepsilon>0$ であり、$x-\varepsilon=x/2>0$ なので $\varepsilon< x$ である。$\square$

解析学ではこの命題を次の形で使う。実数 $a,b$ が、すべての $\varepsilon>0$ について $\lvert a-b\rvert\le\varepsilon$ を満たすなら、$x=\lvert a-b\rvert$ に当てて $\lvert a-b\rvert\le0$、したがって $a=b$ である。「任意に小さい誤差でしか違わない 2 数は等しい」という論法の根拠がこれである。仮定が全称 $\forall\varepsilon$ をもつので、対偶の結論は存在 $\exists\varepsilon$ になり、証明では $\varepsilon$ を 1 つ具体的に挙げればよい。

単射の 2 つの書き方

写像 $f\colon X\to Y$ が単射であることの定義は、次のどちらで書かれることもある。
$$ \forall x,x'\in X\ \bigl(f(x)=f(x')\to x=x'\bigr),\qquad \forall x,x'\in X\ \bigl(x\ne x'\to f(x)\ne f(x')\bigr). $$
後者は前者の対偶であり（範囲は $X\times X$ のまま）、thm-cp-quantified により同値である。示しやすいほうを選べばよい。
たとえば $f\colon\mathbb{R}\to\mathbb{R}$ が狭義単調増加（$x< x'$ なら $f(x)< f(x')$）なら、後者の形で単射が示せる。$x\ne x'$ とすると、実数の大小は全順序なので $x< x'$ か $x'< x$ であり、前者なら $f(x)< f(x')$、後者なら $f(x')< f(x)$ で、どちらでも $f(x)\ne f(x')$ である。前者の形で直接示そうとすると、$f(x)=f(x')$ から $x=x'$ を引き出すのに結局同じ場合分けが要る。

指数についての条件

Mersenne素数の記事の系「素数になるための指数の条件」（$2^n-1$ が素数なら $n$ は素数）と、Fermat数の記事の命題「素数になる $2^m+1$ の指数」（$2^m+1$ が素数なら $m$ は $2$ の冪）は、どちらも対偶で示される。仮定「素数である」はそのままでは使いにくいが、結論の否定「$n=ab$（$1< a< n$）」「$m$ は $1$ より大きい奇数の約数をもつ」は因数分解を与え、そこから $2^n-1$ や $2^m+1$ の自明でない約数が作れる。

級数の項による発散の判定

級数の記事の命題「収束する級数の項は0に近づく」は「$\sum a_n$ が収束するならば $a_n\to0$」という条件文である。発散を示すときはその対偶「$a_n\to0$ でないならば $\sum a_n$ は収束しない」を使う。たとえば $a_n=(-1)^n$ は $0$ に近づかないので、$\sum_{n=0}^{\infty}(-1)^n$ は収束しない。逆「$a_n\to0$ ならば収束する」は成り立たない（同じ記事の例「反例：項が0に近づくが発散する級数」）ので、この判定は発散を示すのにしか使えない。

性質

量化と複数の仮定がある条件文の対偶

数学の定理の多くは、「$X$ のどの元 $x$ についても、$x$ が条件 $P_1,\dots,P_k$ を満たすならば $Q$ を満たす」という形をしている。この形の対偶は、量化子を変えずに作れる。さらに、仮定のうち 1 つだけを結論と入れ替えてもよい。

量化と複数の仮定がある条件文の対偶

$X$ を集合とし、$P_1(x),\dots,P_k(x)$（$k\ge1$）と $Q(x)$ を $X$ の各元 $x$ について真偽が定まる条件とする。$1\le i\le k$ を満たす各 $i$ について、次の 2 つの主張は同値である。

$\forall x\in X\ \bigl((P_1(x)\land\cdots\land P_k(x))\to Q(x)\bigr)$
$\forall x\in X\ \bigl((P_1(x)\land\cdots\land P_{i-1}(x)\land\lnot Q(x)\land P_{i+1}(x)\land\cdots\land P_k(x))\to\lnot P_i(x)\bigr)$
特に $k=1$ のとき、$\forall x\in X\ (P(x)\to Q(x))$ とその対偶 $\forall x\in X\ (\lnot Q(x)\to\lnot P(x))$ は同値である。

$x\in X$ を 1 つ固定し、1 の括弧の中の条件文を $A(x)$、2 の括弧の中の条件文を $B(x)$ と書く。$A(x)$ と $B(x)$ がどの $x$ でも同じ真偽をとることを示せばよい。実際、そうであれば、1 は「すべての $x\in X$ について $A(x)$ が真」、2 は「すべての $x\in X$ について $B(x)$ が真」であるから、両者は同値になる。
条件文は、前件が真で後件が偽のときに限り偽であり、それ以外のときは真である（含意の記事の定義「含意」）。連言は、すべての項が真のときに限り真である。これを使って、$A(x)$ と $B(x)$ のそれぞれが偽になる場合を書き出す。

$A(x)$ が偽であるのは、$P_1(x),\dots,P_k(x)$ がすべて真で、かつ $Q(x)$ が偽のときに限る。
$B(x)$ が偽であるのは、$j\ne i$ を満たすすべての $j$ について $P_j(x)$ が真で、$\lnot Q(x)$ が真で、かつ $\lnot P_i(x)$ が偽のときに限る。$\lnot Q(x)$ が真であることは $Q(x)$ が偽であることと、$\lnot P_i(x)$ が偽であることは $P_i(x)$ が真であることと同じなので（否定の記事の定義「否定」）、これは「$P_1(x),\dots,P_k(x)$ がすべて真で、かつ $Q(x)$ が偽」と同じ条件である。
よって $A(x)$ と $B(x)$ は、偽になる場合がちょうど一致する。真偽は真か偽のどちらか一方なので、$A(x)$ と $B(x)$ はつねに同じ真偽をとる。
$k=1$ のときは、2 の前件は $\lnot Q(x)$ だけになり、2 は対偶そのものである。$\square$

この定理から、実際に対偶をとるときの注意が 2 つ読み取れる。

量化子は変わらない。 対偶は、各 $x$ ごとの条件文を同じ真偽の条件文に取り替えるだけなので、$\forall x\in X$ は $\forall x\in X$ のまま残る。主張全体を否定すると $\forall$ が $\exists$ に変わる（全称記号の記事の命題「量化された命題の否定」）が、対偶は否定ではない。変数が複数あっても、$X$ を直積集合にとれば同じである（ex-cp-injective の $X\times X$）。
残りの仮定は仮定のまま残す。 2 では、入れ替えた $P_i$ 以外の仮定 $P_j$ は前件に残っている。たとえば実数 $a,b$ についての「$a\ne0$ かつ $ab=0$ ならば $b=0$」で、仮定 $ab=0$ と結論 $b=0$ を入れ替えると「$a\ne0$ かつ $b\ne0$ ならば $ab\ne0$」となる。$a\ne0$ を落とした「$b\ne0$ ならば $ab\ne0$」は $a=0$ で偽である（下の節「条件を外した反例」の表）。
前件や後件そのものが量化を含むときは、対偶の前件・後件はそれらの否定なので、否定の作り方（否定の記事の定理「否定を内側へ移す規則」）がそのまま要る。prop-cp-epsilon では、仮定の $\forall\varepsilon>0$ が対偶の結論で $\exists\varepsilon>0$ に変わった。このとき変わるのは仮定の内側の量化子であって、主張全体の外側にある量化（prop-cp-epsilon では「実数 $x$ について」）は変わらない。

逆と裏

逆と裏の関係

命題 $P,Q$ について、$P\to Q$ の逆 $Q\to P$ と裏 $\lnot P\to\lnot Q$ は互いに対偶であり、つねに同じ真偽をとる。したがって、$P\leftrightarrow Q$ を示すには、$P\to Q$ と、逆 $Q\to P$ または裏 $\lnot P\to\lnot Q$ のどちらか一方を示せばよい。集合 $X$ 上の条件 $P(x),Q(x)$ についても、$\forall x\in X$ をつけた形で同じことが成り立つ。

裏 $\lnot P\to\lnot Q$ の対偶は $\lnot\lnot Q\to\lnot\lnot P$ である。二重否定 $\lnot\lnot R$ は $R$ と同じ真偽をとる（論理と命題の記事の命題「基本的な恒真式」）ので、$\lnot\lnot Q\to\lnot\lnot P$ は $Q\to P$ と同じ真偽をとる。条件文とその対偶は同じ真偽をとる（thm-cp-quantified の $k=1$ の場合を、1 元集合 $X$ 上の条件として当てればよい）ので、裏と逆は同じ真偽をとる。逆の対偶 $\lnot P\to\lnot Q$ は裏そのものなので、両者は互いに対偶である。
$P\leftrightarrow Q$ は $P\to Q$ と $Q\to P$ がともに真であるときに限り真である。いま示したことから、$Q\to P$ を $\lnot P\to\lnot Q$ に取り替えてもよい。
$X$ 上の条件の場合は、各 $x\in X$ について上の議論を当てると、$Q(x)\to P(x)$ と $\lnot P(x)\to\lnot Q(x)$ はどの $x$ でも同じ真偽をとる。したがって両者に $\forall x\in X$ をつけた主張も同値である。$\square$

必要十分条件を示すときに「$P$ ならば $Q$」と「$P$ でないならば $Q$ でない」を示すのは、この命題による。たとえば整数 $n$ について「$n$ が $3$ の倍数 $\iff$ $n^2$ が $3$ の倍数」は、「$n=3k$ なら $n^2=3\cdot3k^2$」と prop-cp-square-three（「$n^2$ が $3$ の倍数なら $n$ も」）を合わせて示される。後者を示すのに使った対偶「$n$ が $3$ の倍数でないなら $n^2$ も $3$ の倍数でない」は、同値 $n\in3\mathbb{Z}\iff n^2\in3\mathbb{Z}$ の裏にあたる。

背理法・推論規則との関係

条件文 $P\to Q$ を背理法で示すときは、$P$ と $\lnot Q$ をともに仮定して矛盾を導く。対偶による証明で $\lnot Q$ から $\lnot P$ が導けていれば、仮定 $P$ と並べて矛盾 $P\land\lnot P$ が得られるので、対偶による証明は背理法の特別な場合とみなせる（背理法の記事の命題「対偶による証明から得られる背理法」）。逆に、背理法で書かれた証明が、仮定 $P$ を最後の矛盾のところでしか使っていなければ、その証明は対偶による証明に書き直せる。書き直すと、何を仮定して何を導いたかがはっきりする。
推論規則の言葉では、「$P\to Q$ と $\lnot Q$ から $\lnot P$ を結論してよい」という規則を 後件否定式（modus tollens）という。$P\to Q$ が真で $\lnot Q$ が真なら、$\lnot Q\to\lnot P$ も真なので、前件肯定（$\lnot Q$ と $\lnot Q\to\lnot P$ から $\lnot P$）により $\lnot P$ が得られる。後件否定式は、対偶と前件肯定を合わせたものである。

古典論理以外での対偶

ここまでの議論は、命題が真か偽のどちらか一方に決まる古典論理の立場に立っている。直観主義論理では、$(P\to Q)\to(\lnot Q\to\lnot P)$ は証明できるが、逆向きの $(\lnot Q\to\lnot P)\to(P\to Q)$ は一般には証明できない（直観主義論理の記事の例「直観主義論理で証明できる式」の 3）。したがって直観主義論理では、対偶を示しても一般にはもとの条件文は示されない。$P$ を仮定して矛盾を導き $\lnot P$ を得る推論は直観主義論理でも正しいので、「$P$ ならば $Q$ でない」の形の主張（結論が否定の形のもの）を対偶で示すことは、そこでも問題がない。対偶 $\lnot\lnot Q\to\lnot P$ から $P\to\lnot Q$ が出るからである（背理法の記事の注意「直観主義論理では一般には使えない形」も参照）。具体的な反例は次の節の表の最後の行にある。

条件を外した反例

対偶による証明でよく起こる誤りを、正しい手順のどの条件を外したかで整理する。各行の「成り立たなくなること」は、その条件を外したときに正しくなくなる推論である。

外す条件	反例	成り立たなくなること
対偶をとる（逆に取り替えない）	整数 $n$ について「$4$ の倍数ならば偶数」は真、逆「偶数ならば $4$ の倍数」は $n=2$ で偽	逆を示せばもとの条件文が示される
対偶をとる（裏に取り替えない）	同じ条件文の裏「$4$ の倍数でないならば偶数でない」は $n=2$ で偽	裏を示せばもとの条件文が示される
結論の否定を正しく作る	実数 $x$ について「$x^2\le1$ ならば $x< 1$」は $x=1$ で偽。$\lnot(x< 1)$ を $x>1$ と誤ると「$x>1$ ならば $x^2>1$」は真	誤って作った対偶を示せばもとの条件文が示される
量化の範囲を変えない	$X=\{x\in\mathbb{R}\mid x>0\}$ で「$x^2>x$ ならば $x>1$」は真。範囲を $\mathbb{R}$ に広げた「$x\le1$ ならば $x^2\le x$」は $x=-1$ で偽	範囲を書き換えた対偶がもとの主張と同値
残りの仮定を残す（thm-cp-quantified）	実数 $a,b$ について「$a\ne0$ かつ $ab=0$ ならば $b=0$」は真。$a\ne0$ を落とした「$b\ne0$ ならば $ab\ne0$」は $a=0$ で偽	一部の仮定を落として作った対偶がもとの主張と同値
古典論理（排中律）	3 元の鎖 $\{0< h< 1\}$ を真理値とする Heyting代数で、$P$ の値を $1$、$Q$ の値を $h$ とする	$\lnot Q\to\lnot P$ から $P\to Q$ が出る

反例の確かめ

1・2 行目：$4$ の倍数は $4k=2\cdot2k$ と書けるので偶数であり、もとの条件文は真である。$n=2$ は偶数だが $4$ の倍数でないので逆は偽、$4$ の倍数でないのに偶数なので裏も偽である。prop-cp-converse-inverse のとおり、逆と裏の真偽は一致している。
3 行目：$x=1$ では $x^2=1\le1$ だが $x< 1$ でないので、もとの条件文は偽である。「$x>1$ ならば $x^2>1$」は $x^2-1=(x-1)(x+1)>0$ より真である。実数の大小は全順序なので $\lnot(x< 1)$ の正しい形は $1\le x$（否定の記事の定理「順序の否定と全順序」）であり、正しい対偶「$1\le x$ ならば $1< x^2$」は $x=1$ で偽になって、もとの条件文が偽であることと合っている。等号の場合を落とした対偶を示しても、その場合は調べられていない。
4 行目：$x>0$ で $x^2>x$ なら、両辺を $x$ で割って $x>1$ なので、もとの主張は真である。範囲を $\mathbb{R}$ に広げると $x=-1$ で $x\le1$ だが $x^2=1>-1=x$ である。正しい対偶は「$x>0$ かつ $x\le1$ ならば $x^2\le x$」で、これは $x\cdot x\le1\cdot x$ より真である。
5 行目：$a\ne0$ かつ $ab=0$ なら、$a^{-1}$ を掛けて $b=0$ なので、もとの主張は真である。$a=0$、$b=1$ では $b\ne0$ だが $ab=0$ である。thm-cp-quantified の 2 で正しく作ると「$a\ne0$ かつ $b\ne0$ ならば $ab\ne0$」で、これは真である。
6 行目：この Heyting代数では、含意を $x\le y$ のとき $x\Rightarrow y=1$、$x>y$ のとき $x\Rightarrow y=y$、否定を $\lnot x=x\Rightarrow0$ と定める（直観主義論理の記事の例「反例：3 元の鎖と排中律」）。$\lnot Q$ の値は $\lnot h=0$、$\lnot P$ の値は $\lnot1=0$ なので、$\lnot Q\to\lnot P$ の値は $0\Rightarrow0=1$ である。一方 $P\to Q$ の値は $1\Rightarrow h=h\ne1$ であり、$(\lnot Q\to\lnot P)\to(P\to Q)$ の値は $1\Rightarrow h=h\ne1$ となる。直観主義論理の記事の定理「Heyting 代数に関する健全性」により、この式は直観主義論理では証明できない。古典論理の 2 値 $\{0< 1\}$ ではこの式の値はつねに $1$ である。