§A3.7背理法

最終更新

直接には手がかりの無い主張でも、否定を仮定すると具体的な式が手に入ることがあります。本記事では、否定の仮定から得られる式を利用する証明の方法を定めます。

1 背理法の手順

定義 1.1 (背理法). 証明したい主張を否定して仮定し、その仮定と既知の事実とから矛盾を導くことによって、もとの主張が正しいと結論する証明の方法を 背理法 (proof by contradiction) という。

背理法によって主張PPを証明するときは、次の順に証明を進めます。

  1. PPの否定¬P\lnot Pを仮定します。「もしPPでないとすると」と書き出し、¬P\lnot Pが具体的に何を主張しているのかを、式や条件の形で書き下します。
  2. 仮定した¬P\lnot Pと、すでに示されている事実とから推論を進めます。
  3. 矛盾に到達します。矛盾とは、ある命題QQについてQQと¬Q\lnot Qの両方が導かれること、または1=01 = 0のように偽であることが分かっている命題が導かれることです。
  4. 矛盾がどの仮定から出たのかを明示します。証明の中で用いた仮定は、もとの主張の前提と、手順1で置いた¬P\lnot Pの二つです。前提は正しいものとして与えられているので、誤っているのは¬P\lnot Pのほうです。
  5. ¬P\lnot Pが誤りであると結論し、PPが正しいとします。

手順1と手順4を省略しないことが重要です。手順1で否定を正確に書き下すことができなければ、その後の推論は別の主張についての議論になってしまいます。手順4を書かなければ、読み手は、導かれた矛盾がどの仮定を否定する根拠になるのかを判断することができません。

2 対偶による証明との違い

命題p⇒qp \Rightarrow qを対偶によって証明するときは、¬q\lnot qを仮定して¬p\lnot pを導きます。背理法によって証明するときは、ppと¬q\lnot qを仮定して、両立しない二つの命題を導きます。ppが成り立つという前提の下で矛盾が生じるため、追加した仮定¬q\lnot qを棄却し、qqが成り立つと結論します。

対偶による証明では、導くべき命題は¬p\lnot pと定まっています。背理法では、ppと¬q\lnot qの両方を用いることができますが、導く矛盾がどの二つの命題の間に生じるかは、個々の議論によって異なります。

証明の方法を選ぶときは、結論を否定するとどのような式や条件を得ることができるかを調べます。¬q\lnot qから¬p\lnot pを導く手がかりがある場合は対偶を用い、否定した結論と前提から両立しない命題を導く手がかりがある場合は背理法を用います。

3 背理法による証明の例

定理 3.1 (2\sqrt{2}の無理性).2\sqrt{2}は無理数である。

2\sqrt{2}が無理数であることを直接示そうとすると、無理数であることは「有理数として表すことができない」という否定的な主張なので、手がかりを取り出すことが困難です。この主張の否定を仮定すると、逆に手がかりが増えます。

証明 (背理法).2\sqrt{2}が有理数であると仮定する。互いに素な整数m,nm,nを取り、n≠0n\ne0かつ2=m/n\sqrt{2}=m/nと書く。両辺を2乗すると

m2=2n2m^2=2n^2

である。m2m^2は偶数なので、§A3.6 定理 2.1によりmmは偶数である。m=2km=2kとなる整数kkを取ると、4k2=2n24k^2=2n^2よりn2=2k2n^2=2k^2となる。再び§A3.6 定理 2.1によりnnも偶数である。m,nm,nはともに2で割り切れるので、互いに素であることに矛盾する。したがって、2\sqrt{2}が有理数であるという仮定は誤りであり、2\sqrt{2}は無理数である。▨

2\sqrt{2}が有理数であると仮定したことによって、「mn\dfrac{m}{n}と書くことができる」という具体的な式が得られました。そのため、以降の議論は整数の計算として進めることができました。背理法は、直接には手がかりのない主張について、計算することができる形の仮定を作り出す方法です。

例 3.2. 正の有理数の中に最小の数は存在しない。最小の正の有理数mmが存在すると仮定する。最小性から、どの正の有理数rrに対してもm≤rm\le rである。mmは正の有理数なので、m/2m/2も正の有理数であり、m/2<mm/2<mである。ところがr=m/2r=m/2とするとm≤m/2m\le m/2となり、矛盾する。したがって、最小の正の有理数は存在しない。

閑話休題：無理数がもたらした最初の衝撃2\sqrt2が無理数であるというこの背理法の証明は、数学史上もっとも古い衝撃の一つでした。古代ギリシャのピタゴラス学派は、万物は整数の比によって表すことができると考えていましたが、正方形の対角線と一辺の比（2\sqrt2）がどのような整数比によっても表すことができないことが、この証明によって明らかになります。伝説では、この事実を学派の外へ漏らしたヒッパソスが、海に投げ込まれて命を落としたと伝えられています。

背理法は、PPと¬P\lnot Pのどちらか一方は必ず正しいという排中律と深く結び付いています。存在を示す証明には、条件を満たす対象を一つ具体的に作って示すものと、存在することだけを示すものがあります。たとえば、無理数aa、bbでaba^bが有理数になる組が存在します。22\sqrt2^{\sqrt2}を考え、22\sqrt2^{\sqrt2}が有理数であればa=b=2a=b=\sqrt2とすれば済みます。22\sqrt2^{\sqrt2}が無理数であればa=22a=\sqrt2^{\sqrt2}、b=2b=\sqrt2とすると

(22)2=22=2\left(\sqrt2^{\sqrt2}\right)^{\sqrt2}=\sqrt2^2=2

で有理数です。どちらの場合にも組は存在することが分かりますが、この証明では、二つの場合のどちらが成り立つのかを特定していません。排中律を認めない立場では、対象を構成することなく存在だけを示すこのような証明を疑い、対象を実際に構成することを求めます。

4 例題

レベル2 — 背理法の構造

次の主張を背理法で証明する。(1) 何を仮定するか（主張の否定）、(2) その仮定からどんな矛盾が導かれるか、を書け。

解法の型手順は固定: 示したい主張 P の否定¬P\neg Pを仮定する→\to計算を進める→\to矛盾（Q かつ¬Q\neg Q）に到達する→\to¬P\neg Pが誤りなので P が正しい

次の主張を背理法で示すとき、何を仮定し、どんな矛盾が導かれるかを書け。

例 4.1.

素数は無限に存在する\text{素数は無限に存在する}

答

仮定する否定 (¬P)素数は有限個で、その全部が p1,p2,…,pn である。導かれる矛盾N=p1p2⋯pn+1 はどの pi で割っても余りが 1 なので、N の素因数は p1,…,pn のどれでもない。「これで全部」に矛盾。\begin{array}{ll} \text{仮定する否定} \ (\lnot P) & \text{素数は有限個で、その全部が } p_1, p_2, \ldots, p_n \ \text{である。} \\ \text{導かれる矛盾} & N = p_1 p_2 \cdots p_n + 1 \ \text{はどの } p_i \ \text{で割っても余りが } 1 \ \text{なので、} N \ \text{の素因数は } p_1, \ldots, p_n \ \text{のどれでもない。「これで全部」に矛盾。} \end{array}

注意 仮定したのは「素数が有限個で、そのリストが全部である」。矛盾したのは、その「全部である」という部分（リストにない素因数が作れてしまう）。N 自身が素数かどうかは問題ではない。 対偶証明との違い: 「P⇒\RightarrowQ」を示すとき、対偶法は¬Q\neg Qだけを仮定して¬P\neg Pを直接導く。背理法は P と¬Q\neg Qの両方を仮定して矛盾を導く（使える材料が1つ多い代わりに、最後に「何と矛盾したか」を明示する必要がある）。

例 4.2.

a が 0 でない有理数、b が無理数ならば ab は無理数であるa \ \text{が 0 でない有理数、} b \ \text{が無理数ならば } ab \ \text{は無理数である}

答

仮定する否定 (¬P)ab=r が有理数である。導かれる矛盾a≠0 より b=ra は有理数どうしの商で有理数。これは b が無理数であることに矛盾。\begin{array}{ll} \text{仮定する否定} \ (\lnot P) & ab = r \ \text{が有理数である。} \\ \text{導かれる矛盾} & a \ne 0 \ \text{より } b = \dfrac{r}{a} \ \text{は有理数どうしの商で有理数。これは } b \ \text{が無理数であることに矛盾。} \end{array}

注意 仮定したのは「積が有理数」。矛盾したのは前提「b は無理数」。a≠\ne0 がないと r/a を作れないので、この条件がどこで効くかを必ず確認すること。 対偶証明との違い: 「P⇒\RightarrowQ」を示すとき、対偶法は¬Q\neg Qだけを仮定して¬P\neg Pを直接導く。背理法は P と¬Q\neg Qの両方を仮定して矛盾を導く（使える材料が1つ多い代わりに、最後に「何と矛盾したか」を明示する必要がある）。

例 4.3.

合成数 n は n 以下の素因数をもつ\text{合成数 } n \ \text{は } \sqrt{n} \ \text{以下の素因数をもつ}

答

仮定する否定 (¬P)n の素因数はすべて n より大きい。導かれる矛盾n は合成数なので n=ab (1<a≤b<n) と書ける。a,b の素因数もすべて n より大きいから a>n, b>n 。よって ab>n となり ab=n に矛盾。\begin{array}{ll} \text{仮定する否定} \ (\lnot P) & n \ \text{の素因数はすべて } \sqrt{n} \ \text{より大きい。} \\ \text{導かれる矛盾} & n \ \text{は合成数なので } n = ab \ (1 < a \le b < n) \ \text{と書ける。} a, b \ \text{の素因数もすべて } \sqrt{n} \ \text{より大きいから } a > \sqrt{n}, \ b > \sqrt{n} \ \text{。よって } ab > n \ \text{となり } ab = n \ \text{に矛盾。} \end{array}

注意 仮定したのは「素因数がすべて √n より大きい」。矛盾したのは n==ab（積が n を超えてしまう）。素数判定で √n までの試し割りで済ませてよい根拠がこれ。 対偶証明との違い: 「P⇒\RightarrowQ」を示すとき、対偶法は¬Q\neg Qだけを仮定して¬P\neg Pを直接導く。背理法は P と¬Q\neg Qの両方を仮定して矛盾を導く（使える材料が1つ多い代わりに、最後に「何と矛盾したか」を明示する必要がある）。

例 4.4.

n2 が 3 の倍数ならば n は 3 の倍数である(n は整数)n^2 \ \text{が 3 の倍数ならば } n \ \text{は 3 の倍数である} \quad (n \ \text{は整数})

答

仮定する否定 (¬P)n2 は 3 の倍数、かつ n は 3 の倍数でない。導かれる矛盾n=3k±1 とおくと n2=3(3k2±2k)+1 で、3 で割った余りは 1 。これは n2 が 3 の倍数であることに矛盾。\begin{array}{ll} \text{仮定する否定} \ (\lnot P) & n^2 \ \text{は 3 の倍数、かつ } n \ \text{は 3 の倍数でない。} \\ \text{導かれる矛盾} & n = 3k \pm 1 \ \text{とおくと } n^2 = 3(3k^2 \pm 2k) + 1 \ \text{で、3 で割った余りは } 1 \ \text{。これは } n^2 \ \text{が 3 の倍数であることに矛盾。} \end{array}

注意 仮定したのは「n² は 3 の倍数」かつ「n は 3 の倍数でない」。矛盾したのは n² を 3 で割った余り。余りで場合分けして（n==3k ± 1）計算するのが手順。 対偶証明との違い: 「P⇒\RightarrowQ」を示すとき、対偶法は¬Q\neg Qだけを仮定して¬P\neg Pを直接導く。背理法は P と¬Q\neg Qの両方を仮定して矛盾を導く（使える材料が1つ多い代わりに、最後に「何と矛盾したか」を明示する必要がある）。

例 4.5.

n+1 個のものを n 個の箱に入れると、2 個以上入る箱がある（鳩の巣原理）n + 1 \ \text{個のものを } n \ \text{個の箱に入れると、2 個以上入る箱がある（鳩の巣原理）}

答

仮定する否定 (¬P)どの箱にも高々 1 個しか入っていない。導かれる矛盾入っているものの総数は高々 n 個。実際には n+1 個入れたので矛盾。\begin{array}{ll} \text{仮定する否定} \ (\lnot P) & \text{どの箱にも高々 1 個しか入っていない。} \\ \text{導かれる矛盾} & \text{入っているものの総数は高々 } n \ \text{個。実際には } n + 1 \ \text{個入れたので矛盾。} \end{array}

注意 仮定したのは「どの箱も高々1個」（結論「2個以上入る箱がある」の否定）。矛盾したのは総数の勘定。個数を数え上げて矛盾を作る典型例。 対偶証明との違い: 「P⇒\RightarrowQ」を示すとき、対偶法は¬Q\neg Qだけを仮定して¬P\neg Pを直接導く。背理法は P と¬Q\neg Qの両方を仮定して矛盾を導く（使える材料が1つ多い代わりに、最後に「何と矛盾したか」を明示する必要がある）。

例 4.6.

2+3 は無理数である（6 が無理数であることは既知とする）\sqrt{2} + \sqrt{3} \ \text{は無理数である（} \sqrt{6} \ \text{が無理数であることは既知とする）}

答

仮定する否定 (¬P)2+3=r が有理数である。導かれる矛盾両辺を2乗して 5+26=r2 、よって 6=r2−52 は有理数。これは 6 が無理数であることに矛盾。\begin{array}{ll} \text{仮定する否定} \ (\lnot P) & \sqrt{2} + \sqrt{3} = r \ \text{が有理数である。} \\ \text{導かれる矛盾} & \text{両辺を2乗して } 5 + 2\sqrt{6} = r^2 \ \text{、よって } \sqrt{6} = \dfrac{r^2 - 5}{2} \ \text{は有理数。これは } \sqrt{6} \ \text{が無理数であることに矛盾。} \end{array}

注意 仮定したのは「√2 + √3 が有理数」。矛盾したのは既知の事実「√6 は無理数」。2乗して既知の無理数を単離するのが手筋。 対偶証明との違い: 「P⇒\RightarrowQ」を示すとき、対偶法は¬Q\neg Qだけを仮定して¬P\neg Pを直接導く。背理法は P と¬Q\neg Qの両方を仮定して矛盾を導く（使える材料が1つ多い代わりに、最後に「何と矛盾したか」を明示する必要がある）。

例 4.7.

a が有理数、b が無理数ならば a+b は無理数であるa \ \text{が有理数、} b \ \text{が無理数ならば } a + b \ \text{は無理数である}

答

仮定する否定 (¬P)a+b=r が有理数である。導かれる矛盾b=r−a は有理数どうしの差なので有理数。これは b が無理数であることに矛盾。\begin{array}{ll} \text{仮定する否定} \ (\lnot P) & a + b = r \ \text{が有理数である。} \\ \text{導かれる矛盾} & b = r - a \ \text{は有理数どうしの差なので有理数。これは } b \ \text{が無理数であることに矛盾。} \end{array}

注意 仮定したのは「和が有理数」。矛盾したのは前提「b は無理数」。有理数全体が引き算で閉じていることが矛盾を生む。 対偶証明との違い: 「P⇒\RightarrowQ」を示すとき、対偶法は¬Q\neg Qだけを仮定して¬P\neg Pを直接導く。背理法は P と¬Q\neg Qの両方を仮定して矛盾を導く（使える材料が1つ多い代わりに、最後に「何と矛盾したか」を明示する必要がある）。

例 4.8.

a+b≥2 ならば a≥1 または b≥1(a,b は実数)a + b \ge 2 \ \text{ならば } a \ge 1 \ \text{または } b \ge 1 \quad (a, b \ \text{は実数})

答

仮定する否定 (¬P)a+b≥2 かつ a<1 かつ b<1導かれる矛盾a<1 と b<1 を足すと a+b<2 となり、仮定 a+b≥2 に矛盾。\begin{array}{ll} \text{仮定する否定} \ (\lnot P) & a + b \ge 2 \ \text{かつ } a < 1 \ \text{かつ } b < 1 \\ \text{導かれる矛盾} & a < 1 \ \text{と } b < 1 \ \text{を足すと } a + b < 2 \ \text{となり、仮定 } a + b \ge 2 \ \text{に矛盾。} \end{array}

注意 仮定したのは結論の否定、すなわち a < 1 かつ b < 1（「A または B」の否定はド・モルガン則で「A でない かつ B でない」）。矛盾したのは前提 a + b≥\ge2。 対偶証明との違い: 「P⇒\RightarrowQ」を示すとき、対偶法は¬Q\neg Qだけを仮定して¬P\neg Pを直接導く。背理法は P と¬Q\neg Qの両方を仮定して矛盾を導く（使える材料が1つ多い代わりに、最後に「何と矛盾したか」を明示する必要がある）。

例 4.9.

2 は無理数である\sqrt{2} \ \text{は無理数である}

答

仮定する否定 (¬P)2=pq(p,q は整数、q≠0、この分数は既約)導かれる矛盾p2=2q2 より p は偶数。p=2r とおくと q2=2r2 より q も偶数。ともに偶数となり、既約であることに矛盾。\begin{array}{ll} \text{仮定する否定} \ (\lnot P) & \sqrt{2} = \dfrac{p}{q} \quad (p, q \ \text{は整数、} q \ne 0 \text{、この分数は既約}) \\ \text{導かれる矛盾} & p^2 = 2q^2 \ \text{より } p \ \text{は偶数。} p = 2r \ \text{とおくと } q^2 = 2r^2 \ \text{より } q \ \text{も偶数。ともに偶数となり、既約であることに矛盾。} \end{array}

注意 仮定したのは「√2 は有理数（既約分数で書ける）」。矛盾したのは、その既約性である（p と q がともに 2 で割れてしまう）。有理数だと仮定したことで「==p/q と書ける」という計算の足場が手に入るのが背理法の効能。 対偶証明との違い: 「P⇒\RightarrowQ」を示すとき、対偶法は¬Q\neg Qだけを仮定して¬P\neg Pを直接導く。背理法は P と¬Q\neg Qの両方を仮定して矛盾を導く（使える材料が1つ多い代わりに、最後に「何と矛盾したか」を明示する必要がある）。

例 4.10.

n2 が偶数ならば n は偶数である(n は整数)n^2 \ \text{が偶数ならば } n \ \text{は偶数である} \quad (n \ \text{は整数})

答

仮定する否定 (¬P)n2 は偶数、かつ n は奇数。導かれる矛盾n=2k+1 とおくと n2=2(2k2+2k)+1 で奇数。n2 が偶数かつ奇数となり矛盾。\begin{array}{ll} \text{仮定する否定} \ (\lnot P) & n^2 \ \text{は偶数、かつ } n \ \text{は奇数。} \\ \text{導かれる矛盾} & n = 2k + 1 \ \text{とおくと } n^2 = 2(2k^2 + 2k) + 1 \ \text{で奇数。} n^2 \ \text{が偶数かつ奇数となり矛盾。} \end{array}

注意 仮定したのは「n² は偶数」かつ「n は奇数」。矛盾したのは n² の偶奇。対偶法（n が奇数⇒\Rightarrown² が奇数 を直接示す）とほぼ同じ計算だが、背理法では前提「n² は偶数」も同時に手元に置いている点が違う。 対偶証明との違い: 「P⇒\RightarrowQ」を示すとき、対偶法は¬Q\neg Qだけを仮定して¬P\neg Pを直接導く。背理法は P と¬Q\neg Qの両方を仮定して矛盾を導く（使える材料が1つ多い代わりに、最後に「何と矛盾したか」を明示する必要がある）。

5 演習

レベル2 — 背理法の構造

次の主張を背理法で証明する。(1) 何を仮定するか（主張の否定）、(2) その仮定からどんな矛盾が導かれるか、を書け。

解法の型手順は固定: 示したい主張 P の否定¬P\neg Pを仮定する→\to計算を進める→\to矛盾（Q かつ¬Q\neg Q）に到達する→\to¬P\neg Pが誤りなので P が正しい

次の主張を背理法で示すとき、何を仮定し、どんな矛盾が導かれるかを書け。

問題 5.1.

素数は無限に存在する\text{素数は無限に存在する}
解答.

答

仮定する否定 (¬P)素数は有限個で、その全部が p1,p2,…,pn である。導かれる矛盾N=p1p2⋯pn+1 はどの pi で割っても余りが 1 なので、N の素因数は p1,…,pn のどれでもない。「これで全部」に矛盾。\begin{array}{ll} \text{仮定する否定} \ (\lnot P) & \text{素数は有限個で、その全部が } p_1, p_2, \ldots, p_n \ \text{である。} \\ \text{導かれる矛盾} & N = p_1 p_2 \cdots p_n + 1 \ \text{はどの } p_i \ \text{で割っても余りが } 1 \ \text{なので、} N \ \text{の素因数は } p_1, \ldots, p_n \ \text{のどれでもない。「これで全部」に矛盾。} \end{array}

注意 仮定したのは「素数が有限個で、そのリストが全部である」。矛盾したのは、その「全部である」という部分（リストにない素因数が作れてしまう）。N 自身が素数かどうかは問題ではない。 対偶証明との違い: 「P⇒\RightarrowQ」を示すとき、対偶法は¬Q\neg Qだけを仮定して¬P\neg Pを直接導く。背理法は P と¬Q\neg Qの両方を仮定して矛盾を導く（使える材料が1つ多い代わりに、最後に「何と矛盾したか」を明示する必要がある）。▨

問題 5.2.

2+3 は無理数である（6 が無理数であることは既知とする）\sqrt{2} + \sqrt{3} \ \text{は無理数である（} \sqrt{6} \ \text{が無理数であることは既知とする）}
解答.

答

仮定する否定 (¬P)2+3=r が有理数である。導かれる矛盾両辺を2乗して 5+26=r2 、よって 6=r2−52 は有理数。これは 6 が無理数であることに矛盾。\begin{array}{ll} \text{仮定する否定} \ (\lnot P) & \sqrt{2} + \sqrt{3} = r \ \text{が有理数である。} \\ \text{導かれる矛盾} & \text{両辺を2乗して } 5 + 2\sqrt{6} = r^2 \ \text{、よって } \sqrt{6} = \dfrac{r^2 - 5}{2} \ \text{は有理数。これは } \sqrt{6} \ \text{が無理数であることに矛盾。} \end{array}

注意 仮定したのは「√2 + √3 が有理数」。矛盾したのは既知の事実「√6 は無理数」。2乗して既知の無理数を単離するのが手筋。 対偶証明との違い: 「P⇒\RightarrowQ」を示すとき、対偶法は¬Q\neg Qだけを仮定して¬P\neg Pを直接導く。背理法は P と¬Q\neg Qの両方を仮定して矛盾を導く（使える材料が1つ多い代わりに、最後に「何と矛盾したか」を明示する必要がある）。▨

問題 5.3.

n2 が偶数ならば n は偶数である(n は整数)n^2 \ \text{が偶数ならば } n \ \text{は偶数である} \quad (n \ \text{は整数})
解答.

答

仮定する否定 (¬P)n2 は偶数、かつ n は奇数。導かれる矛盾n=2k+1 とおくと n2=2(2k2+2k)+1 で奇数。n2 が偶数かつ奇数となり矛盾。\begin{array}{ll} \text{仮定する否定} \ (\lnot P) & n^2 \ \text{は偶数、かつ } n \ \text{は奇数。} \\ \text{導かれる矛盾} & n = 2k + 1 \ \text{とおくと } n^2 = 2(2k^2 + 2k) + 1 \ \text{で奇数。} n^2 \ \text{が偶数かつ奇数となり矛盾。} \end{array}

注意 仮定したのは「n² は偶数」かつ「n は奇数」。矛盾したのは n² の偶奇。対偶法（n が奇数⇒\Rightarrown² が奇数 を直接示す）とほぼ同じ計算だが、背理法では前提「n² は偶数」も同時に手元に置いている点が違う。 対偶証明との違い: 「P⇒\RightarrowQ」を示すとき、対偶法は¬Q\neg Qだけを仮定して¬P\neg Pを直接導く。背理法は P と¬Q\neg Qの両方を仮定して矛盾を導く（使える材料が1つ多い代わりに、最後に「何と矛盾したか」を明示する必要がある）。▨

問題 5.4.

a が有理数、b が無理数ならば a+b は無理数であるa \ \text{が有理数、} b \ \text{が無理数ならば } a + b \ \text{は無理数である}
解答.

答

仮定する否定 (¬P)a+b=r が有理数である。導かれる矛盾b=r−a は有理数どうしの差なので有理数。これは b が無理数であることに矛盾。\begin{array}{ll} \text{仮定する否定} \ (\lnot P) & a + b = r \ \text{が有理数である。} \\ \text{導かれる矛盾} & b = r - a \ \text{は有理数どうしの差なので有理数。これは } b \ \text{が無理数であることに矛盾。} \end{array}

注意 仮定したのは「和が有理数」。矛盾したのは前提「b は無理数」。有理数全体が引き算で閉じていることが矛盾を生む。 対偶証明との違い: 「P⇒\RightarrowQ」を示すとき、対偶法は¬Q\neg Qだけを仮定して¬P\neg Pを直接導く。背理法は P と¬Q\neg Qの両方を仮定して矛盾を導く（使える材料が1つ多い代わりに、最後に「何と矛盾したか」を明示する必要がある）。▨

問題 5.5.

2 は無理数である\sqrt{2} \ \text{は無理数である}
解答.

答

仮定する否定 (¬P)2=pq(p,q は整数、q≠0、この分数は既約)導かれる矛盾p2=2q2 より p は偶数。p=2r とおくと q2=2r2 より q も偶数。ともに偶数となり、既約であることに矛盾。\begin{array}{ll} \text{仮定する否定} \ (\lnot P) & \sqrt{2} = \dfrac{p}{q} \quad (p, q \ \text{は整数、} q \ne 0 \text{、この分数は既約}) \\ \text{導かれる矛盾} & p^2 = 2q^2 \ \text{より } p \ \text{は偶数。} p = 2r \ \text{とおくと } q^2 = 2r^2 \ \text{より } q \ \text{も偶数。ともに偶数となり、既約であることに矛盾。} \end{array}

注意 仮定したのは「√2 は有理数（既約分数で書ける）」。矛盾したのは、その既約性である（p と q がともに 2 で割れてしまう）。有理数だと仮定したことで「==p/q と書ける」という計算の足場が手に入るのが背理法の効能。 対偶証明との違い: 「P⇒\RightarrowQ」を示すとき、対偶法は¬Q\neg Qだけを仮定して¬P\neg Pを直接導く。背理法は P と¬Q\neg Qの両方を仮定して矛盾を導く（使える材料が1つ多い代わりに、最後に「何と矛盾したか」を明示する必要がある）。▨

問題 5.6.

合成数 n は n 以下の素因数をもつ\text{合成数 } n \ \text{は } \sqrt{n} \ \text{以下の素因数をもつ}
解答.

答

仮定する否定 (¬P)n の素因数はすべて n より大きい。導かれる矛盾n は合成数なので n=ab (1<a≤b<n) と書ける。a,b の素因数もすべて n より大きいから a>n, b>n 。よって ab>n となり ab=n に矛盾。\begin{array}{ll} \text{仮定する否定} \ (\lnot P) & n \ \text{の素因数はすべて } \sqrt{n} \ \text{より大きい。} \\ \text{導かれる矛盾} & n \ \text{は合成数なので } n = ab \ (1 < a \le b < n) \ \text{と書ける。} a, b \ \text{の素因数もすべて } \sqrt{n} \ \text{より大きいから } a > \sqrt{n}, \ b > \sqrt{n} \ \text{。よって } ab > n \ \text{となり } ab = n \ \text{に矛盾。} \end{array}

注意 仮定したのは「素因数がすべて √n より大きい」。矛盾したのは n==ab（積が n を超えてしまう）。素数判定で √n までの試し割りで済ませてよい根拠がこれ。 対偶証明との違い: 「P⇒\RightarrowQ」を示すとき、対偶法は¬Q\neg Qだけを仮定して¬P\neg Pを直接導く。背理法は P と¬Q\neg Qの両方を仮定して矛盾を導く（使える材料が1つ多い代わりに、最後に「何と矛盾したか」を明示する必要がある）。▨

問題 5.7.

a が 0 でない有理数、b が無理数ならば ab は無理数であるa \ \text{が 0 でない有理数、} b \ \text{が無理数ならば } ab \ \text{は無理数である}
解答.

答

仮定する否定 (¬P)ab=r が有理数である。導かれる矛盾a≠0 より b=ra は有理数どうしの商で有理数。これは b が無理数であることに矛盾。\begin{array}{ll} \text{仮定する否定} \ (\lnot P) & ab = r \ \text{が有理数である。} \\ \text{導かれる矛盾} & a \ne 0 \ \text{より } b = \dfrac{r}{a} \ \text{は有理数どうしの商で有理数。これは } b \ \text{が無理数であることに矛盾。} \end{array}

注意 仮定したのは「積が有理数」。矛盾したのは前提「b は無理数」。a≠\ne0 がないと r/a を作れないので、この条件がどこで効くかを必ず確認すること。 対偶証明との違い: 「P⇒\RightarrowQ」を示すとき、対偶法は¬Q\neg Qだけを仮定して¬P\neg Pを直接導く。背理法は P と¬Q\neg Qの両方を仮定して矛盾を導く（使える材料が1つ多い代わりに、最後に「何と矛盾したか」を明示する必要がある）。▨

問題 5.8.

最大の自然数は存在しない\text{最大の自然数は存在しない}
解答.

答

仮定する否定 (¬P)最大の自然数 N が存在する。導かれる矛盾N+1 も自然数で N+1>N 。これは N が最大であることに矛盾。\begin{array}{ll} \text{仮定する否定} \ (\lnot P) & \text{最大の自然数 } N \ \text{が存在する。} \\ \text{導かれる矛盾} & N + 1 \ \text{も自然数で } N + 1 > N \ \text{。これは } N \ \text{が最大であることに矛盾。} \end{array}

注意 仮定したのは「最大元が存在する」。矛盾したのは、その最大性（もっと大きい自然数が作れる）。「存在しない」を示すときは、存在を仮定して壊すのが最短。 対偶証明との違い: 「P⇒\RightarrowQ」を示すとき、対偶法は¬Q\neg Qだけを仮定して¬P\neg Pを直接導く。背理法は P と¬Q\neg Qの両方を仮定して矛盾を導く（使える材料が1つ多い代わりに、最後に「何と矛盾したか」を明示する必要がある）。▨

問題 5.9.

a+b≥2 ならば a≥1 または b≥1(a,b は実数)a + b \ge 2 \ \text{ならば } a \ge 1 \ \text{または } b \ge 1 \quad (a, b \ \text{は実数})
解答.

答

仮定する否定 (¬P)a+b≥2 かつ a<1 かつ b<1導かれる矛盾a<1 と b<1 を足すと a+b<2 となり、仮定 a+b≥2 に矛盾。\begin{array}{ll} \text{仮定する否定} \ (\lnot P) & a + b \ge 2 \ \text{かつ } a < 1 \ \text{かつ } b < 1 \\ \text{導かれる矛盾} & a < 1 \ \text{と } b < 1 \ \text{を足すと } a + b < 2 \ \text{となり、仮定 } a + b \ge 2 \ \text{に矛盾。} \end{array}

注意 仮定したのは結論の否定、すなわち a < 1 かつ b < 1（「A または B」の否定はド・モルガン則で「A でない かつ B でない」）。矛盾したのは前提 a + b≥\ge2。 対偶証明との違い: 「P⇒\RightarrowQ」を示すとき、対偶法は¬Q\neg Qだけを仮定して¬P\neg Pを直接導く。背理法は P と¬Q\neg Qの両方を仮定して矛盾を導く（使える材料が1つ多い代わりに、最後に「何と矛盾したか」を明示する必要がある）。▨

問題 5.10.

log⁡23 は無理数である\log_2 3 \ \text{は無理数である}
解答.

答

仮定する否定 (¬P)log⁡23=pq(p,q は正の整数)導かれる矛盾2p/q=3 の両辺を q 乗して 2p=3q。左辺は偶数、右辺は奇数で矛盾。\begin{array}{ll} \text{仮定する否定} \ (\lnot P) & \log_2 3 = \dfrac{p}{q} \quad (p, q \ \text{は正の整数}) \\ \text{導かれる矛盾} & 2^{p/q} = 3 \ \text{の両辺を } q \ \text{乗して } 2^p = 3^q \text{。左辺は偶数、右辺は奇数で矛盾。} \end{array}

注意 仮定したのは「log2log_{2}3 が有理数」。矛盾したのは偶奇である（2 の正べきは偶数、3 のべきは奇数）。指数を払って整数の等式に持ち込むのが手筋。 対偶証明との違い: 「P⇒\RightarrowQ」を示すとき、対偶法は¬Q\neg Qだけを仮定して¬P\neg Pを直接導く。背理法は P と¬Q\neg Qの両方を仮定して矛盾を導く（使える材料が1つ多い代わりに、最後に「何と矛盾したか」を明示する必要がある）。▨

問題 5.11.

n2 が 3 の倍数ならば n は 3 の倍数である(n は整数)n^2 \ \text{が 3 の倍数ならば } n \ \text{は 3 の倍数である} \quad (n \ \text{は整数})
解答.

答

仮定する否定 (¬P)n2 は 3 の倍数、かつ n は 3 の倍数でない。導かれる矛盾n=3k±1 とおくと n2=3(3k2±2k)+1 で、3 で割った余りは 1 。これは n2 が 3 の倍数であることに矛盾。\begin{array}{ll} \text{仮定する否定} \ (\lnot P) & n^2 \ \text{は 3 の倍数、かつ } n \ \text{は 3 の倍数でない。} \\ \text{導かれる矛盾} & n = 3k \pm 1 \ \text{とおくと } n^2 = 3(3k^2 \pm 2k) + 1 \ \text{で、3 で割った余りは } 1 \ \text{。これは } n^2 \ \text{が 3 の倍数であることに矛盾。} \end{array}

注意 仮定したのは「n² は 3 の倍数」かつ「n は 3 の倍数でない」。矛盾したのは n² を 3 で割った余り。余りで場合分けして（n==3k ± 1）計算するのが手順。 対偶証明との違い: 「P⇒\RightarrowQ」を示すとき、対偶法は¬Q\neg Qだけを仮定して¬P\neg Pを直接導く。背理法は P と¬Q\neg Qの両方を仮定して矛盾を導く（使える材料が1つ多い代わりに、最後に「何と矛盾したか」を明示する必要がある）。▨

問題 5.12.

x≥0 で、すべての ε>0 に対し x<ε ならば x=0x \ge 0 \ \text{で、すべての } \varepsilon > 0 \ \text{に対し } x < \varepsilon \ \text{ならば } x = 0
解答.

答

仮定する否定 (¬P)x≠0 、すなわち x>0 である。導かれる矛盾ε=x2>0 と取れる。仮定より x<x2 、整理して x<0 。これは x>0 に矛盾。\begin{array}{ll} \text{仮定する否定} \ (\lnot P) & x \ne 0 \ \text{、すなわち } x > 0 \ \text{である。} \\ \text{導かれる矛盾} & \varepsilon = \dfrac{x}{2} > 0 \ \text{と取れる。仮定より } x < \dfrac{x}{2} \ \text{、整理して } x < 0 \ \text{。これは } x > 0 \ \text{に矛盾。} \end{array}

注意 仮定したのは x > 0（結論 x==0 の否定を x≥\ge0 と合わせたもの）。矛盾したのは x の符号。「すべてのε\varepsilonで成り立つ」という全称の仮定には、都合のよいε=\varepsilon =x/2 を代入するのが定石。 対偶証明との違い: 「P⇒\RightarrowQ」を示すとき、対偶法は¬Q\neg Qだけを仮定して¬P\neg Pを直接導く。背理法は P と¬Q\neg Qの両方を仮定して矛盾を導く（使える材料が1つ多い代わりに、最後に「何と矛盾したか」を明示する必要がある）。▨

問題 5.13.

n+1 個のものを n 個の箱に入れると、2 個以上入る箱がある（鳩の巣原理）n + 1 \ \text{個のものを } n \ \text{個の箱に入れると、2 個以上入る箱がある（鳩の巣原理）}
解答.

答

仮定する否定 (¬P)どの箱にも高々 1 個しか入っていない。導かれる矛盾入っているものの総数は高々 n 個。実際には n+1 個入れたので矛盾。\begin{array}{ll} \text{仮定する否定} \ (\lnot P) & \text{どの箱にも高々 1 個しか入っていない。} \\ \text{導かれる矛盾} & \text{入っているものの総数は高々 } n \ \text{個。実際には } n + 1 \ \text{個入れたので矛盾。} \end{array}

注意 仮定したのは「どの箱も高々1個」（結論「2個以上入る箱がある」の否定）。矛盾したのは総数の勘定。個数を数え上げて矛盾を作る典型例。 対偶証明との違い: 「P⇒\RightarrowQ」を示すとき、対偶法は¬Q\neg Qだけを仮定して¬P\neg Pを直接導く。背理法は P と¬Q\neg Qの両方を仮定して矛盾を導く（使える材料が1つ多い代わりに、最後に「何と矛盾したか」を明示する必要がある）。▨

前提記事