集合と論理：必要条件・十分条件

条件 $p$：「$x=1$」、$q$：「$x^2=1$」（$x$ は実数）について、「$p\Rightarrow q$」は真、「$q\Rightarrow p$」は偽である（$x=-1$ が反例）。このとき「$p$ は $q$ であるための十分条件」「$q$ は $p$ であるための必要条件」という。真理集合は $T_p=\{1\}$、$T_q=\{-1,1\}$ で、$T_p\subset T_q$ となっている（高校の教科書では真理集合を $P,Q$ と書くことが多いが、本記事では $P,Q$ を命題に使うので、条件 $p$ の真理集合を $T_p$ と書く）。

• 対偶：「整数 $n$ について、$n^2$ が偶数ならば $n$ は偶数」を示すには、対偶「$n$ が奇数ならば $n^2$ は奇数」を示せばよい。$n=2k+1$ なら $n^2=2(2k^2+2k)+1$ だからである。
• 背理法：「$\sqrt2$ は無理数」を示すには、有理数だと仮定して矛盾を導く。

$P$：「$2$ は偶数」（真）、$Q$：「$3$ は偶数」（偽）とすると、表の 2 行目により $P\land Q$ は偽、$P\lor Q$ は真、$P\Rightarrow Q$ は偽である。一方 $Q\Rightarrow P$ は、前件 $Q$ が偽で後件 $P$ が真なので（表の 3 行目の $P\Rightarrow Q$ と同じ型）真である。

$U=\mathbb{R}$ とする。

1. $p$：$x^2<1$、$q$：$x<1$。$T_p=(-1,1)\subset T_q=(-\infty,1)$ なので $p$ は $q$ の十分条件である。$x=-2$ は $T_q$ に属するが $T_p$ に属さないので、必要条件ではない。
2. $p$：$ab=0$、$q$：$a=0$ または $b=0$（$U=\mathbb{R}^2$、$x=(a,b)$）。実数の積が $0$ なら一方が $0$、逆も成り立つので $T_p=T_q$、$p\Leftrightarrow q$ である。
3. 整数全体を $U$ として、$p$：$6$ の倍数、$q$：$2$ の倍数。$T_p\subset T_q$ で $2\in T_q\setminus T_p$ なので、十分であるが必要でない。

$p$：$x^2=1$、$q$：$x=1$ とする（ex-slns-start-condition の $p,q$ を入れ替え、逆向きの含意を調べる）。$U=\mathbb{R}$ では $T_p=\{-1,1\}\not\subset T_q=\{1\}$ なので $p\Rightarrow q$ は成り立たない（$x=-1$ が反例）。$U=(0,\infty)$ では $T_p=\{1\}=T_q$ なので $p\Leftrightarrow q$ である。「$p\Rightarrow q$ が成り立つか」は $p,q$ だけでなく $U$ にもよる。変数の範囲を書かない主張は、真偽が定まらないことがある。

$p$：$6$ の倍数、$q$：$2$ の倍数（整数全体）では、$p\Rightarrow q$ とその対偶「$2$ の倍数でなければ $6$ の倍数でない」は真、逆「$2$ の倍数なら $6$ の倍数」と裏「$6$ の倍数でなければ $2$ の倍数でない」は偽である（$n=2$ が反例）。この例は「$p\Rightarrow q$ が成り立てば逆 $q\Rightarrow p$ も成り立つ」という主張を破る。

1. 対偶：整数 $n$ について「$n^2$ が偶数 $\Rightarrow$ $n$ が偶数」は、ex-slns-start-proofs で対偶を使って示した。次の 2 でこれを使う。
2. 背理法：「$\sqrt2$ は無理数」。有理数と仮定し、$\sqrt2=\frac ab$（$a,b$ は互いに素な正の整数）と書くと $a^2=2b^2$。$a^2$ が偶数なので 1 により $a$ は偶数、$a=2c$ とおくと $b^2=2c^2$ で $b$ も偶数となり、互いに素であることと矛盾する。含意の形をしていない命題なので、対偶による証明は直接には使えない。

「すべての実数 $x$ について、$x^2>1\Rightarrow x>1$」（$R$ とする）は偽である（$x=-2$）。正しい否定は、prop-slns-contradiction と次節の規則により「ある実数 $x$ で $x^2>1$ かつ $x\le1$」で、$x=-2$ により真である。一方「すべての実数 $x$ について $x^2>1\Rightarrow x\le1$」は $x=2$ で破れて偽であり、$R$ と同じく偽なので $R$ の否定ではない。「ならば」の否定は「ならば〜でない」ではなく「かつ〜でない」である。

$X=\{1,2,3\}$、$P(x)$：「$x^2>x$」とする。$P(1)$ は偽（$1>1$ でない）、$P(2)$、$P(3)$ は真なので、$\forall x\in X,\ P(x)$ は偽、$\exists x\in X,\ P(x)$ は真である。真理集合は $T=\{2,3\}$ で、$T\ne X$、$T\ne\emptyset$ である。

関数 $f\colon\mathbb{R}\to\mathbb{R}$ が $a$ で連続であるとは
$$ \forall\varepsilon>0,\ \exists\delta>0,\ \forall x\in\mathbb{R},\ \bigl(|x-a|<\delta\Rightarrow|f(x)-f(a)|<\varepsilon\bigr) $$
が成り立つことである。規則により、その否定（$a$ で不連続）は
$$ \exists\varepsilon>0,\ \forall\delta>0,\ \exists x\in\mathbb{R},\ \bigl(|x-a|<\delta\land|f(x)-f(a)|\ge\varepsilon\bigr) $$
である。$f(x)=0$（$x\le0$）、$f(x)=1$（$x>0$）、$a=0$ とする。$\varepsilon=\frac12$ をとり、任意の $\delta>0$ に対して $x=\frac\delta2$ とすると、$|x|<\delta$ かつ $|f(x)-f(0)|=1\ge\frac12$。よって $f$ は $0$ で不連続である。

$f(x)=x^2$（$x\in\mathbb{R}$）について、次の 2 つを比べる（$\varepsilon,\delta$ は正の実数、$a,x$ は実数を動く）。
$$ \text{(A)}\ \forall\varepsilon\ \forall a\ \exists\delta\ \forall x\ \bigl(|x-a|<\delta\Rightarrow|x^2-a^2|<\varepsilon\bigr),\qquad \text{(B)}\ \forall\varepsilon\ \exists\delta\ \forall a\ \forall x\ \bigl(|x-a|<\delta\Rightarrow|x^2-a^2|<\varepsilon\bigr). $$
(A) はすべての点で連続であること、(B) は一様連続であることである。違いは $\exists\delta$ と $\forall a$ の順序だけである。

• (A) は真：$\delta:=\min\{1,\varepsilon/(2|a|+1)\}$ とすると、$|x-a|<\delta$ なら $|x+a|\le|x-a|+2|a|<2|a|+1$ なので $|x^2-a^2|=|x-a||x+a|<\delta(2|a|+1)\le\varepsilon$。$\delta$ は $a$ によってよい。
• (B) は偽：否定 $\exists\varepsilon\ \forall\delta\ \exists a\ \exists x\ (|x-a|<\delta\land|x^2-a^2|\ge\varepsilon)$ を示す。$\varepsilon=1$、任意の $\delta$ に $a=\frac1\delta$、$x=a+\frac\delta2$ をとると、$|x-a|<\delta$ かつ $x^2-a^2=\frac\delta2\bigl(2a+\frac\delta2\bigr)=1+\frac{\delta^2}4\ge1$。

「$x\le-1$ または $x\ge1$」の否定は、thm-slns-de-morgan により「$x>-1$ かつ $x<1$」、すなわち $-1< x<1$ である。例えば $x=0$ では元の条件が偽で否定が真、$x=2$ では元の条件が真で否定が偽である。

「$x>-1$ かつ $x<1$」の否定を「$x\le-1$ かつ $x\ge1$」とするのは誤りである。後者を満たす実数はないので、この「否定」はつねに偽であるが、たとえば $x=2$ では元の条件も偽である。否定なら真偽が逆になるはずなので、これは否定ではない。正しい否定は「$x\le-1$ または $x\ge1$」で、$x=2$ で真になる。