場合分けによる証明
概要
場合分けによる証明（proof by cases）とは、示したい状況をいくつかの場合 $P_1,\dots,P_n$ に分け、場合が網羅的であること（$P_1\lor\dots\lor P_n$）と各場合から結論 $Q$ が従うことを示して $Q$ を得る証明の方法である。論理の上では選言の除去にあたり、$(P_1\lor\dots\lor P_n)\to Q$ は各 $P_i\to Q$ の連言と同値で、網羅性はこの推論が正しいための必要十分条件である。整数の剰余による全数検査、対称性で場合を減らす「一般性を失わずに」の議論、どちらの場合かを決めずに結論を得る非構成的な証明などに使われ、排中律による場合分けは直観主義論理では一般には使えない。
整数 $n$ について $n^3-n$ が $6$ の倍数であることを示すには、$n$ を $6$ で割った余りが $0,1,2,3,4,5$ のどれであるかで分け、それぞれの場合に確かめればよい。実数 $a,b$ についての主張なら、$a\le b$ の場合と $b< a$ の場合に分ければよい。このように、考えている状況をいくつかの場合に分け、どの場合にも漏れがないこと と 各場合に結論が成り立つこと を示して結論を得る証明の方法を 場合分けによる証明 という。
場合分けは、論理の上では「または」を前提に使う推論（選言の除去）であり、もっとも基本的な証明の型の 1 つである。その正しさは真理値の計算で確かめられるが、実際に使うときには、場合に漏れがないかどうか、対称性で場合を減らしてよいかどうか、場合分けの条件そのものが確かめられるかどうか、という 3 つの点で注意が要る。この記事では、場合分けの正しさとその必要条件（thm-cases-valid）、集合を覆う形と剰余で分ける形（prop-cases-cover、cor-cases-residues）、対称性で場合を減らす議論の根拠（thm-cases-symmetry）を証明し、どちらの場合が起きているか分からないまま結論だけが得られる場合分けの例（prop-cases-irrational-power）を扱う。
定義
真理値は $\mathrm{T}$（真）と $\mathrm{F}$（偽）で書く。$P\lor Q$ は $P,Q$ の少なくとも一方が真のとき真であり、$P\to Q$ は $P$ が真で $Q$ が偽のときだけ偽である（論理と命題 の記事の定義「論理結合子と真理値表」）。
命題 $Q$ を、仮定 $H$ のもとで示したいとする。命題 $P_1,\dots,P_n$（$n\ge1$）について、
- （網羅性）$H$ のもとで $P_1\lor P_2\lor\dots\lor P_n$ が成り立つ、
- （各場合の証明）各 $i=1,\dots,n$ について、$H$ と $P_i$ のもとで $Q$ が成り立つ、
の 2 つを示して、$H$ のもとで $Q$ を結論することを 場合分けによる証明（proof by cases）といい、$P_i$ を 場合（case）という。場合が有限集合の元を 1 つずつ調べる形のとき（「$x\in\{a_1,\dots,a_n\}$ なので $x=a_1$ または … または $x=a_n$」）は 全数検査（proof by exhaustion）ともいう。
場合どうしが重なっていてもよい（$P_i$ と $P_j$ が同時に成り立ってもよい）。重なった部分では結論が 2 回示されるだけである。一方、網羅性は省けない（thm-cases-valid の 3）。
命題論理 の論理式の言葉では、場合分けは次の推論にあたる。
$$
\frac{\varphi_1\lor\dots\lor\varphi_n\qquad\varphi_1\to\psi\qquad\cdots\qquad\varphi_n\to\psi}{\psi}
$$
この形の推論規則は 選言の除去（disjunction elimination）と呼ばれる。命題論理 の記事の定義「シーケント計算」の左の $\lor$ の規則
$$
\frac{\Gamma,A\Rightarrow\Delta\qquad\Gamma,B\Rightarrow\Delta}{\Gamma,A\lor B\Rightarrow\Delta}
$$
は、$n=2$ の場合分けを「仮定に $A\lor B$ があるなら、$A$ を仮定した場合と $B$ を仮定した場合の両方で同じ結論を導けばよい」という形で述べたものである。
量化を含む主張では、場合分けは集合を部分集合で覆う形になる。
集合 $X$ の各元 $x$ について真偽が定まる条件 $Q(x)$ に対し、$X$ の部分集合の族 $(X_i)_{i\in I}$ で $X=\bigcup_{i\in I}X_i$ となるものをとり、各 $i\in I$ について「すべての $x\in X_i$ で $Q(x)$」を示して「すべての $x\in X$ で $Q(x)$」を結論することも、場合分けによる証明という。$I$ は無限集合でもよい。
$I$ が有限集合 $\{1,\dots,n\}$ なら、これは $P_i$ を「$x\in X_i$」とした def-cases-main と同じである。
直感
場合分けは「起こりうることを全部並べて、どれが起きても困らないことを確かめる」証明である。どの場合が実際に起きているかを知る必要はない。必要なのは、並べた場合で起こりうることが尽きていることだけである。そのため、場合分けの証明で誤りがもっとも起きやすいのは、各場合の計算よりも網羅性のほうである。「$x>0$ の場合と $x< 0$ の場合」と書いて $x=0$ を忘れる、「整数 $n$」を「正の整数」のつもりで扱う、といった漏れは、各場合の議論がすべて正しくても証明全体を誤りにする。
例
自然数 $n\ge1$ について、$1+(-1)^n(2n-1)$ は $4$ の倍数である（Ham18 §4.4、p. 124 の例）。整数は偶数か奇数のどちらかなので、2 つの場合で網羅される（除法の原理 の記事の例「偶数と奇数」）。
- $n$ が偶数の場合：$n=2k$ と書けて $(-1)^n=1$ なので、$1+(2\cdot2k-1)=4k$ である。
- $n$ が奇数の場合：$n=2k+1$ と書けて $(-1)^n=-1$ なので、$1-(2(2k+1)-1)=-4k$ である。
どちらの場合も $4$ の倍数である。$(-1)^n$ の値が $n$ の偶奇で変わるので、場合を分けると式が 1 つの形に定まる。場合分けは、場合ごとに使える等式が違う式を扱うときの標準的な手段である。
実数 $a,b$ について
$$
\max\{a,b\}=\frac{a+b+\lvert a-b\rvert}2,\qquad\min\{a,b\}=\frac{a+b-\lvert a-b\rvert}2
$$
である。実数の大小は全順序なので、$a\le b$ か $b\le a$ のどちらかが成り立つ（$a=b$ のときは両方が成り立つ。場合は重なってよい）。$a\le b$ なら $\lvert a-b\rvert=b-a$ なので右辺はそれぞれ $b$ と $a$ になり、左辺に一致する。$b\le a$ なら $\lvert a-b\rvert=a-b$ なので右辺はそれぞれ $a$ と $b$ になり、やはり一致する。2 つの場合は $a$ と $b$ を入れ替えただけの同じ計算であり、thm-cases-symmetry を使えば 1 つにまとめられる。
すべての整数 $n$ について $n^3-n$ は $6$ の倍数である。cor-cases-residues により、$n$ を $6$ で割った余り $r=0,1,\dots,5$ の 6 つの場合を調べれば足りる。
| $r$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ |
|---|---|---|---|---|---|---|
| $r^3-r$ | $0$ | $0$ | $6$ | $24$ | $60$ | $120$ |
どれも $6$ の倍数である。$n^3-n=(n-1)n(n+1)$ と因数分解して「連続する 3 整数の中には偶数と $3$ の倍数がある」と論じることもでき、これは $2$ で割った余りと $3$ で割った余りによる、より少ない場合への分け方になっている。
性質
場合分けの正しさと網羅性
論理式の間の 論理的帰結 $\Gamma\vDash\psi$（$\Gamma$ のすべての論理式を真にするどの付値でも $\psi$ が真）と 論理的同値 $\varphi\equiv\psi$（どの付値でも同じ真理値）は、命題論理 の記事の定義「恒真式・充足可能性・論理的帰結」のとおりに使う。$\varphi_1\lor\dots\lor\varphi_n$ は、付値 $v$ のもとで「ある $i$ について $v(\varphi_i)=\mathrm{T}$」のとき、かつそのときに限り真である（$n$ についての帰納法で、$\lor$ の真理値表から分かる）。
$n\ge1$ とし、$\varphi_1,\dots,\varphi_n,\psi$ を論理式とする。
- $\{\varphi_1\lor\dots\lor\varphi_n,\ \varphi_1\to\psi,\ \dots,\ \varphi_n\to\psi\}\vDash\psi$ である。
- $(\varphi_1\lor\dots\lor\varphi_n)\to\psi\equiv(\varphi_1\to\psi)\land\dots\land(\varphi_n\to\psi)$ である。
- 次の 2 条件は同値である。
- (a) $\varphi_1\lor\dots\lor\varphi_n$ は恒真式である。
- (b) どの論理式 $\psi$ についても、$\{\varphi_1\to\psi,\ \dots,\ \varphi_n\to\psi\}\vDash\psi$ である。
1：付値 $v$ が左辺の論理式をすべて真にするとする。$v(\varphi_1\lor\dots\lor\varphi_n)=\mathrm{T}$ なので、$v(\varphi_i)=\mathrm{T}$ となる $i$ がある。$v(\varphi_i\to\psi)=\mathrm{T}$ で前件が真なので、含意の真理値表により $v(\psi)=\mathrm{T}$ である。
2：付値 $v$ を固定する。左辺が偽であるのは、$v(\varphi_1\lor\dots\lor\varphi_n)=\mathrm{T}$ かつ $v(\psi)=\mathrm{F}$ のとき、すなわち「ある $i$ について $v(\varphi_i)=\mathrm{T}$ で、$v(\psi)=\mathrm{F}$」のときである。右辺が偽であるのは、ある $i$ について $v(\varphi_i\to\psi)=\mathrm{F}$、すなわち「ある $i$ について $v(\varphi_i)=\mathrm{T}$ かつ $v(\psi)=\mathrm{F}$」のときである。2 つの条件は同じなので、両辺はどの付値でも同じ真理値をとる。
3：(a) ⇒ (b)：$v$ が $\varphi_i\to\psi$（$i=1,\dots,n$）をすべて真にするとする。(a) により $v(\varphi_1\lor\dots\lor\varphi_n)=\mathrm{T}$ なので、1 により $v(\psi)=\mathrm{T}$ である。
(b) ⇒ (a)：$\psi:=\varphi_1\lor\dots\lor\varphi_n$ とおく。各 $i$ について $\varphi_i\to\psi$ は恒真式である。$v(\varphi_i)=\mathrm{T}$ なら $v(\psi)=\mathrm{T}$ だからである。よってどの付値も $\{\varphi_1\to\psi,\dots,\varphi_n\to\psi\}$ を真にし、(b) によりどの付値でも $v(\psi)=\mathrm{T}$、すなわち $\psi$ は恒真式である。$\square$
1 は場合分けが正しい推論であること、2 は「場合を合わせた仮定から $\psi$ を示すこと」と「各場合から $\psi$ を示すこと」が同じ強さの主張であることを述べている。2 の $n=2$ の場合は、$(P\lor Q)\to R$ を示すには $P\to R$ と $Q\to R$ を別々に示せばよく、逆に $(P\lor Q)\to R$ からはどちらも従う、という使い方をする。
3 は網羅性の役割を述べている。各場合から結論が出ることだけからは、一般には結論は出ない。網羅性がない場合分けでも「結論か、またはどの場合でもない」までは言えるが、結論そのものを言うには、場合が尽きていることが必要十分である。(b) ⇒ (a) の証明で使った $\psi$ は「どれかの場合である」という主張そのもので、これは各場合からは自明に出るのに、それ自身は成り立たないかもしれない。
集合を覆う場合分けと剰余による場合分け
集合 $X$ の部分集合の族 $(X_i)_{i\in I}$ と、$X$ 上の条件 $Q(x)$ について次が成り立つ。
- $X=\bigcup_{i\in I}X_i$ ならば、「すべての $x\in X$ で $Q(x)$」と「すべての $i\in I$ とすべての $x\in X_i$ で $Q(x)$」は同値である。
- $X\ne\bigcup_{i\in I}X_i$ ならば、「すべての $i\in I$ とすべての $x\in X_i$ で $Q(x)$」が成り立つのに「すべての $x\in X$ で $Q(x)$」が成り立たない条件 $Q$ がある。
1：「すべての $x\in X$ で $Q(x)$」なら、$X_i\subset X$ なので各 $X_i$ の元でも $Q$ が成り立つ。逆に各 $X_i$ の元で $Q$ が成り立つとし、$x\in X$ をとる。$X=\bigcup_iX_i$ なので $x\in X_i$ となる $i$ があり、$Q(x)$ が成り立つ。
2：$x_0\in X\setminus\bigcup_iX_i$ をとり、$Q(x)$ を「$x\ne x_0$」とする。$x_0$ はどの $X_i$ にも属さないので、各 $X_i$ の元はすべて $Q$ を満たすが、$Q(x_0)$ は偽である。$\square$
整数についての主張では、$m$ で割った余りによる場合分けがよく使われる。整数全体は、余りが $r$（$0\le r< m$）である整数の集合 $X_r$ の $m$ 個で覆われる（除法の原理）。主張が余りだけで決まるなら、各 $X_r$ からは代表の $r$ を 1 つ調べれば足りる。
$m\ge1$ を整数とし、整数 $n$ についての条件 $Q(n)$ が、すべての整数 $n$ について「$Q(n)\iff Q(n+m)$」を満たすとする。このとき、「すべての整数 $n$ で $Q(n)$」と「$Q(0),Q(1),\dots,Q(m-1)$ がすべて成り立つ」は同値である。とくに、整数係数の多項式 $f$ について $Q(n)$ が「$f(n)\equiv0\pmod m$」であるとき、この仮定が成り立つ。
前者から後者は明らかである。後者を仮定し、$n$ を整数とする。除法の原理 により $n=qm+r$（$q$ は整数、$0\le r< m$）と書ける。仮定 $Q(k)\iff Q(k+m)$ を $k=r,r+m,\dots$ や $k=r-m,r-2m,\dots$ に順に当てると、$\lvert q\rvert$ についての帰納法により、すべての整数 $q$ について $Q(r)\iff Q(r+qm)$ である。$Q(r)$ が成り立つので $Q(n)$ も成り立つ。これは prop-cases-cover の 1 を、$X_r$ の元 $n$ について $Q(n)\iff Q(r)$ を使って当てたものである。
最後の主張：$n+m\equiv n\pmod m$ なので、合同式 の記事の命題「合同式の和・差・積・冪」の 4 により $f(n+m)\equiv f(n)\pmod m$ であり、$f(n)\equiv0$ と $f(n+m)\equiv0$ は同値である。$\square$
ex-cases-residues はこの系の $m=6$、$f(n)=n^3-n$ の場合である。平方数を $4$ や $8$ で割った余りについての主張も同じ形の場合分けで示される（平方数 の記事の命題「平方数の法 4・法 8 での剰余」）。周期性の仮定は外せない（rem-cases-counterexamples の 3 行目）。
対称性で場合を減らす
ex-cases-max-min の 2 つの場合は、$a$ と $b$ の名前を入れ替えただけの同じ計算だった。このようなとき、「一般性を失わずに（without loss of generality）$a\le b$ としてよい」と書いて 1 つの場合だけを示すことが多い（Ham18 §4.5、pp. 125–126）。この省略が正しいのは、次の条件が満たされているときである。
$X$ を集合、$S\subset X$ をその部分集合、$G$ を $X$ から $X$ への写像の集合、$Q(x)$ を $X$ 上の条件とし、次の 2 つを仮定する。
- (a) どの $x\in X$ についても、$g(x)\in S$ となる $g\in G$ がある。
- (b) どの $x\in X$ と $g\in G$ についても、$Q(g(x))$ ならば $Q(x)$ である。
このとき、すべての $x\in S$ で $Q(x)$ が成り立てば、すべての $x\in X$ で $Q(x)$ が成り立つ。
$x\in X$ をとる。(a) により $g(x)\in S$ となる $g\in G$ があり、仮定により $Q(g(x))$ が成り立つ。(b) により $Q(x)$ が成り立つ。$\square$
典型的な使い方は次のとおりである。
- 2 変数で対称な主張。$X=\mathbb{R}^2$、$S=\{(a,b)\mid a\le b\}$、$G=\{\mathrm{id},\tau\}$（$\tau(a,b)=(b,a)$）とする。実数の大小は全順序なので (a) が成り立つ。$Q(a,b)$ と $Q(b,a)$ が同値な主張（対称な主張）なら (b) が成り立つ。
- 3 変数で対称な主張。$X=\mathbb{R}^3$、$S=\{(a,b,c)\mid a\le b\le c\}$、$G$ を 3 つの成分の 6 通りの並べ替えとする。3 つの実数は小さい順に並べ替えられるので (a) が成り立つ。$Q$ が成分の並べ替えで変わらない主張なら (b) が成り立つ。
例。実数 $a,b,c$ について $\lvert a-b\rvert+\lvert b-c\rvert+\lvert c-a\rvert=2(\max\{a,b,c\}-\min\{a,b,c\})$ である。両辺とも $a,b,c$ の並べ替えで変わらないので、$a\le b\le c$ の場合だけを示せばよい。このとき左辺は $(b-a)+(c-b)+(c-a)=2(c-a)$、右辺も $2(c-a)$ である。大小の並び方は 6 通りあるが、確かめる場合は 1 つで済む。
(b) が成り立たないのに「一般性を失わずに」と書くと誤りになる。たとえば $Q(a,b)$ を「$a\le b$」とすると、$S$ の上では $Q$ は真なのに全体では偽である（rem-cases-counterexamples の 4 行目）。「$a$ と $b$ の役割は同じなので」と書く前に、示す主張が本当に入れ替えで変わらないかを確かめる必要がある。仮定の側だけが対称で、結論の側が対称でない場合には、(b) が成り立つとは限らない。
どちらの場合かは分からなくてよい
場合分けでは、どの場合が実際に起きているかを決める必要はない。次の命題はそれをよく示す例である（Ham18 §7.4、p. 154）。
無理数 $a,b$ で、$a^b$ が有理数となるものが存在する。
$\sqrt2$ は無理数である（背理法 の記事の例「2 の平方根は無理数」）。$x:=\sqrt2^{\sqrt2}$ とおき、$x$ が有理数か無理数かで場合を分ける。これはどの実数についても成り立つ「有理数であるか、そうでないか」という場合分けであり、網羅性は論理と命題 の記事の定理「排中の法則」による。
- $x$ が有理数の場合：$a=b=\sqrt2$ とすれば、$a,b$ は無理数で $a^b=x$ は有理数である。
- $x$ が無理数の場合：$a=x$、$b=\sqrt2$ とすれば、$a,b$ は無理数で、指数法則により
$$ a^b=\bigl(\sqrt2^{\sqrt2}\bigr)^{\sqrt2}=\sqrt2^{\sqrt2\cdot\sqrt2}=\sqrt2^{\,2}=2 $$
は有理数である。
どちらの場合も求める $a,b$ が存在する。$\square$
この証明は、$\sqrt2^{\sqrt2}$ が有理数かどうかを決めずに結論を得ている。実際には $\sqrt2^{\sqrt2}$ は無理数であり、さらに超越数である（超越数 の記事の定理「Gelfond–Schneiderの定理」を $\sqrt2$ と $\sqrt2$ に当てる。この記事では証明しない）。したがって正しい例は 2 番目の場合の組であるが、それを知るには場合分けの証明よりはるかに深い定理が要る。
場合分けを使わずに例を直接与えることもできる。$a=\sqrt2$、$b=\log_29$ とすると $a^b=2^{\frac12\log_29}=2^{\log_23}=3$ である（Ham18 §7.4、p. 154）。$b=2\log_23$ が無理数であることは、$\log_23$ が無理数であること（背理法 の記事の例「2 を底とする 3 の対数は無理数」）から従う。$2\log_23=p/q$ なら $\log_23=p/(2q)$ が有理数になるからである。
選言の除去（def-cases-main の推論）は 直観主義論理 でも正しい推論である。直観主義論理で使えないのは、任意の命題 $P$ について「$P$ の場合と $\lnot P$ の場合」に分けること、すなわち網羅性を排中律 $P\lor\lnot P$（論理と命題 の記事の定理「排中の法則」）から得ることである。直観主義論理では $p\lor\lnot p$ は一般には証明できない（直観主義論理 の記事の例「反例：3 元の鎖と排中律」）。直観主義論理には、$\varphi\lor\psi$ が証明できるなら $\varphi$ か $\psi$ のどちらかが証明できるという性質があり（同じ記事の定理「選言特性」）、そこでの場合分けは、どちらの場合かを（原理的には）決められるときにだけ使える。prop-cases-irrational-power の最初の証明は、この意味で直観主義論理の証明になっていない。2 番目の直接の例は、どちらの立場でも証明になっている。
場合分けによる定義
関数や値を場合分けで定めることも多い。たとえば $\lvert x\rvert$ は「$x\ge0$ なら $x$、$x< 0$ なら $-x$」と定める。場合分けによる定義が 1 つの値を決めるには、場合が網羅的であることに加えて、場合が重なる部分で値が一致すること が必要である。「$x\ge0$ なら $x$、$x\le0$ なら $-x$」と書いても、重なる $x=0$ で $0=-0$ なので同じ関数が定まる。重なりで値が食い違うと値は定まらない（well-definedness の語が表すのはこの種の条件である）。場合分けによる証明では重なりが許されるのに対し、場合分けによる定義では重なりに条件がつく。
条件を外した反例
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| def-cases-main の網羅性 | 実数 $x$ を「$x>0$」「$x< 0$」の 2 つの場合に分けて $x^2>0$ を示す | すべての実数 $x$ で $x^2>0$ |
| prop-cases-cover の $X=\bigcup X_i$ | $X=\mathbb{Z}$、$X_1=\{n\ge2\}$、$X_2=\{n\le-1\}$、$Q(n)$：$n^2>n$ | すべての整数 $n$ で $Q(n)$ |
| cor-cases-residues の周期性 | $m=6$、$Q(n)$：$n< 6$ | $Q(0),\dots,Q(5)$ からすべての $n$ で $Q(n)$ |
| thm-cases-symmetry の (b) | $S=\{(a,b)\mid a\le b\}$、$Q(a,b)$：$a\le b$ | $S$ 上で $Q$ ならすべての $(a,b)$ で $Q$ |
| 古典論理（排中律） | 3 元の鎖を真理値とする Heyting 代数 | $p\lor\lnot p$ を網羅的な場合分けとして使える |
表の各行は次のように確かめられる。
詳細
1 行目：各場合の議論（正の数の 2 乗は正、負の数の 2 乗は正）は正しいが、$x=0$ がどちらの場合にも入らず、$0^2>0$ は偽である。thm-cases-valid の 3 の (a) が破れている。
2 行目：$n\ge2$ なら $n^2-n=n(n-1)>0$、$n\le-1$ なら $n^2>0>n$ なので、各 $X_i$ の上で $Q$ は成り立つ。しかし $n=0,1$ では $n^2=n$ で $Q$ は偽である。$0,1$ は $X_1\cup X_2$ に入らない。
3 行目：$Q(0),\dots,Q(5)$ はすべて真だが $Q(6)$ は偽である。$Q(5)$ は真で $Q(5+6)$ は偽なので、周期性 $Q(n)\iff Q(n+6)$ が破れている。
4 行目：(a) は成り立ち、$S$ の上で $Q$ は真だが、$(1,0)$ では $Q$ は偽である。$Q(\tau(1,0))=Q(0,1)$ は真で $Q(1,0)$ は偽なので、(b) が破れている。
5 行目：直観主義論理 の記事の例「反例：3 元の鎖と排中律」により、$p\lor\lnot p$ の値は $1$ でなく、直観主義論理では証明できない。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
