反例による反証
変数\(x\in X\)の自由な現れを持つ開論理式\(A\left( x\right) \)に関する主張\begin{equation}\lnot \left( \forall x\in x:A\left( x\right) \right) \quad \cdots (1)
\end{equation}が成り立つことを証明しようとしている状況を想定します。つまり、「任意の\(x\in X\)について\(A\left( x\right) \)が成り立つ」という主張が成り立たないことを証明しようとしているということです。全称命題の否定より、\begin{equation*}\lnot \left( \forall x\in x:A\left( x\right) \right) \Leftrightarrow \exists
x\in X:\lnot A\left( x\right)
\end{equation*}という関係が成り立つため、\(\left( 1\right) \)が成り立つことを示す代わりに、\begin{equation}\exists x\in X:\lnot A\left( x\right) \quad \cdots (2)
\end{equation}が成り立つことを示しても構いません。
さて、存在導入のもとでは、\begin{equation*}
\lnot A\left( c\right) \ \models \ \exists x\in X:\lnot A\left( x\right)
\end{equation*}が成り立ちます。ただし、上の主張中の\(c\)は論理式\(A\left( x\right) \)の変数\(x\)に代入すると真の命題になるような「何らかの値」を代表的な形で表す記号です。したがって、変数\(x\)がとり得る「具体的な」値\(x_{i}\in X\)についても、存在導入のもとでは、\begin{equation*}\lnot A\left( x_{i}\right) \ \models \ \exists x\in X:\lnot A\left(
x_{i}\right)
\end{equation*}が成り立ちます。したがって、\begin{equation*}
\lnot A\left( x_{i}\right)
\end{equation*}が真になるような値\(x_{i}\in X\)を具体的に提示すれば\(\left( 2\right) \)が成り立つことを示したことになり、したがって\(\left(1\right) \)を示したことにもなります。
結論を整理すると、変数\(x\in X\)の自由な現れを持つ開論理式\(A\left( x\right) \)に関する主張\begin{equation*}\lnot \left( \forall x\in x:A\left( x\right) \right)
\end{equation*}が成り立つことを示す代わりに、以下の命題\begin{equation*}
\lnot A\left( x_{i}\right)
\end{equation*}が真になるような値\(x_{i}\in X\)を具体的に提示しても構いません。言い換えると、以下の命題\begin{equation*}A\left( x_{i}\right)
\end{equation*}が偽になるような値\(x_{i}\in X\)を具体的に提示しても構いません。このような証明法法を反例による反証（disproof by counterexample）と呼びます。
\end{equation*}が成り立つことを示す代わりに、反例による反証より、\begin{equation*}
\lnot P\left( x_{i}\right)
\end{equation*}が真になるような値\(x_{i}\in X\)を具体的に提示しても構いません。
\end{equation*}を導入します。以下の主張\begin{equation*}
\lnot \left( \forall x\in X:P\left( x\right) \right)
\end{equation*}が成り立つことを示すことが目標であるため、反例による反証より、\begin{equation*}
\lnot P\left( x_{i}\right)
\end{equation*}が真になるような値\(x_{i}\in X\)を具体的に提示しても構いません。つまり、寿司が好きではない人を発見すれば証明が完了します。
\end{equation*}が成り立つことを示すことが目標ですが、反例による反証より、\begin{equation*}
\left( x+1\right) ^{2}\not=x^{2}+1
\end{equation*}が真になるような実数\(x\in \mathbb{R} \)を具体的に提示しても構いません。実際、以下の値\begin{equation*}x=2
\end{equation*}に注目したとき、\begin{eqnarray*}
\left( 2+1\right) ^{2} &=&9 \\
2^{2}+1 &=&5
\end{eqnarray*}であるため、\begin{equation*}
\left( 2+1\right) ^{2}\not=2^{2}+1
\end{equation*}が成り立ちます。したがって証明が完了しました。
\end{equation*}が成り立つことを示すことが目標ですが、反例による反証より、\begin{equation*}
z^{2}-z+5\text{は素数ではない}
\end{equation*}が真になるような整数\(z\in \mathbb{Z} \)を具体的に提示しても構いません。実際、以下の値\begin{equation*}z=5
\end{equation*}に注目したとき、\begin{equation*}
5^{2}-5+5=25
\end{equation*}となりますが、これは素数ではないため証明が完了しました。
\end{equation*}が成り立つことを示す代わりに、反例による反証より、\begin{equation*}
\lnot P\left( x_{i},y_{i}\right)
\end{equation*}が真になるような値\(x_{i}\in X\)および\(y_{i}\in Y\)を具体的に提示しても構いません。
\end{equation*}が成り立つことを示すことが目標ですが、反例による反証より、\begin{equation*}
\lnot \left( x>y\Rightarrow x^{2}>y^{2}\right)
\end{equation*}すなわち、\begin{equation*}
x>y\wedge x^{2}\leq y^{2}
\end{equation*}が真になるような整数\(x,y\in \mathbb{Z} \)を具体的に提示しても構いません。実際、\begin{eqnarray*}x &=&2 \\
y &=&-5
\end{eqnarray*}に注目したとき、\(2,-5\in \mathbb{Z} \)であるとともに、\begin{eqnarray*}2 &>&-5 \\
\left( 2\right) ^{2} &\leq &\left( -5\right) ^{2}
\end{eqnarray*}がともに成り立つため証明が完了しました。
例による証明
変数\(x\in X\)の自由な現れを持つ開論理式\(A\left( x\right) \)に関する主張\begin{equation*}\lnot \left( \forall x\in x:A\left( x\right) \right)
\end{equation*}が成り立つことを示す代わりに、以下の命題\begin{equation*}
A\left( x_{i}\right)
\end{equation*}が偽になるような値\(x_{i}\in X\)を具体的に提示しても構わないことが明らかになりました（反例による反証）。その一方で、以下の主張\begin{equation*}\forall x\in X:A\left( x\right)
\end{equation*}が成り立つことを示す代わりに、以下の命題\begin{equation*}
A\left( x_{i}\right)
\end{equation*}が真になるような値\(x_{i}\in X\)を具体的に提示しても不十分です。なぜなら、何らかの具体的な値\(x_{i}\)について\(A\left( x_{i}\right) \)が成り立つ場合でも、任意の値\(x\in X\)について\(A\left( x\right) \)が成り立つとは限らないからです。このような証明法法を例による証明（proof by example）と呼びます。反例による反証とは異なり、例による証明は証明方法として有効ではありません。
\end{equation*}を導入します。以下の主張\begin{equation}
\forall x\in X:P\left( x\right) \quad \cdots (1)
\end{equation}が成り立つことを示すことが目標です。寿司が好きな人を発見すれば、その人\(x_{i}\in X\)について、以下の命題\begin{equation*}P\left( x_{i}\right)
\end{equation*}が真であることを示したことになります。ただし、以上の事実によって\(\left( 1\right) \)が成り立つことを示したことにはなりません。\(x_{i}\)以外の人は寿司が好きであるとは限らないからです。
変数\(x\)の定義域\(X\)が1点集合である場合には、例外的に、例による証明は証明方法として有効です。なぜなら、変数\(x\)の定義域が1点集合\begin{equation*}X=\left\{ x_{i}\right\}
\end{equation*}である場合には、全称命題\begin{equation*}
\forall x\in X:P\left( x\right)
\end{equation*}と命題\begin{equation*}
P\left( x_{i}\right)
\end{equation*}は必要十分だからです。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】