数学の国語：集合と論理を正確に読み書きする

0. この記事の要点

• 数学の文章は、集合と論理という 2 つの語彙だけで書かれています。この 2 つは別々の話題ではなく、$\cap$ と「かつ」、$\cup$ と「または」、$\subseteq$ と「ならば」がそれぞれ正確に対応します。
• 集合の等式 $A = B$ の証明は、例外なく $A \subseteq B$ と $B \subseteq A$ の 2 本に分解できます（命題 3.4）。証明の方針で迷ったら、まずここに戻ってください。
• 「$P$ ならば $Q$」は因果関係ではありません。$P$ が偽ならこの命題は真です。この規約のおかげで「空集合のすべての元は $\sqrt{2}$ より大きい」のような文が矛盾なく扱えます（命題 3.6）。
• ド・モルガンの法則は、命題論理の版・集合の版・量化子の版という 3 つの顔を持ちますが、中身は 1 つです（補題 4.3、定理 4.4、系 5.6）。
• $\forall$ と $\exists$ の否定は「否定記号を内側へ押し込みながら $\forall$ と $\exists$ を入れ替える」という機械的な操作です（定理 5.3）。$\varepsilon$-$\delta$ 論法の否定もこの手順だけで作れます。
• 「十分条件」「必要条件」は矢印の向きの言い換えにすぎず、真理集合の包含関係と同じことです（命題 6.3）。

1. 動機 — 直感が壊れたときに何を頼るか

数学の言葉づかいを「作法」として教わると、なぜそこまで細かく書く必要があるのかが見えません。この節では、その必要が実際に生じた場面を 1 つ挙げます。

19 世紀の前半まで、関数はグラフとして思い描くものでした。「連続な関数は、ところどころの例外を除けば接線を引ける」というのは、当時の数学者にとって疑う余地のない直感でした。ところが 1872 年、ワイエルシュトラスは

$$W(x) = \sum_{n=0}^{\infty} a^{n} \cos(b^{n} \pi x)$$

という形の関数（$0 < a < 1$、$b$ は奇数の自然数で、$ab > 1 + \tfrac{3}{2}\pi$）が、すべての実数 $x$ で連続でありながら、どの点でも微分可能でないことを示しました。絵に描けないものが、式としては目の前にある。ここで、「連続」や「微分可能」が何を意味するかを、絵ではなく文で確定させる必要が生じました。

同じころ、カントールは無限集合の大小を比較しはじめ、「集合」という語そのものが精密化を要求されるようになります。こうして 19 世紀末には、数学の主張を有限個の記号の並びとして書き、その真偽を書かれた形だけから判定する、という様式が確立しました。その様式で使われる語彙が、集合と論理です。

この記事を読み終えると、たとえば次の素朴な疑問に、はっきり答えられるようになります。

1. 「クラスの生徒全員が 3 メートル以上の身長を持つ」は、生徒が 1 人もいないクラスでは真か偽か。
2. 「$x = 2$ ならば $x^2 = 4$」は真なのに、その逆が偽なのはなぜか。$x^2 = 4$ は $x = 2$ の何なのか。
3. 「どんな実数にも、それより大きい実数がある」と「どんな実数よりも大きい実数がある」は、記号で書くとどこが違うのか。

ノート

この記事は全 6 章の第 1 章です。ここで整えた言葉づかいは、以降のすべての章で使います。証明の型（背理法・数学的帰納法・対偶論法）そのものは 証明の技術（数学的帰納法の原理（定理 3.2）［証明の技術］、背理法の正当性（命題 6.2）［証明の技術］）で、無限集合の大小は 濃度と無限 で扱います。

2. 命題と論理結合子

2.1. 命題

定義 2.1（命題）

真か偽かのいずれか一方に定まる主張を命題といいます。命題 $P$ が真であることを $P$ の真理値が $\mathrm{T}$ である、偽であることを $\mathrm{F}$ であると言います。

「いずれか一方に定まる」という部分が効いています。「この文は偽である」は真としても偽としても矛盾するので命題ではありません。「$x + 1 = 3$」も、$x$ が何かを言わないかぎり真偽が定まらないので、それ自体は命題ではありません（このような、変数を含む主張は 定義 5.1 で述語として扱います）。

注意 2.2

厳密には、「真か偽かに定まる主張」という説明は「主張」の意味を説明していないので、定義として完結していません。数理論理学では、まず記号列としての論理式を有限個の規則で定義し、そこに真理値を割り当てる手続きを別に定めます。この記事では、その手前の実用的な水準で扱います。形式化そのものに踏み込む話は 不完全性定理 にあります。

2.2. 4 つの結合子と真理値表

定義 2.3（論理結合子）

命題 $P$、$Q$ から新しい命題 $\lnot P$（$P$ でない）、$P \land Q$（$P$ かつ $Q$）、$P \lor Q$（$P$ または $Q$）、$P \implies Q$（$P$ ならば $Q$）、$P \iff Q$（$P$ と $Q$ は同値）を、次の表のとおりに定めます。

$P$	$Q$	$\lnot P$	$P \land Q$	$P \lor Q$	$P \implies Q$	$P \iff Q$
T	T	F	T	T	T	T
T	F	F	F	T	F	F
F	T	T	F	T	T	F
F	F	T	F	F	T	T

この表が定義そのものです。つまり結合子の意味は「日常語のニュアンス」ではなく、この 4 行だけで決まります。とくに次の 2 点は日常語とずれます。

• 「または」は排他的でない。 $P$ と $Q$ が両方とも真のとき $P \lor Q$ は真です。「コーヒーまたは紅茶」のような日常の選択とは違います。両方は成り立たない、と言いたいときは $(P \lor Q) \land \lnot(P \land Q)$ と書きます。
• 「ならば」は因果でない。 $P$ が偽であれば、$Q$ が何であれ $P \implies Q$ は真です。「$2 < 1$ ならば富士山は海抜 0 メートルである」は、数学の意味では真の命題です。

2 点目に違和感を持つのは自然です。ここでの $\implies$ は、$P$ と $Q$ のあいだの関連を主張するものではなく、「$P$ が成り立っているのに $Q$ が成り立たない、という事態は起きない」ことだけを主張する記号だと読んでください。実際 命題 2.4 が示すとおり、$P \implies Q$ は $\lnot(P \land \lnot Q)$ と同じ意味です。この読み方を採用すると、「該当するものが 1 つもないとき、その全員についての主張は真」という便利な規約が自動的に手に入ります（命題 3.6）。

命題 2.4（含意の言い換え）

任意の命題 $P$、$Q$ に対し、次の 3 つの命題はつねに同じ真理値をとります。

$$P \implies Q, \qquad \lnot P \lor Q, \qquad \lnot Q \implies \lnot P .$$

3 番目を $P \implies Q$ の対偶といいます。さらに、$\lnot(P \implies Q)$ と $P \land \lnot Q$ もつねに同じ真理値をとります。

証明（命題 2.4）

定義 2.3 の表に従って、$P$、$Q$ の真理値の 4 通りをすべて書き出します。

$P$	$Q$	$P \implies Q$	$\lnot P \lor Q$	$\lnot Q \implies \lnot P$	$P \land \lnot Q$	$\lnot(P \implies Q)$
T	T	T	T	T	F	F
T	F	F	F	F	T	T
F	T	T	T	T	F	F
F	F	T	T	T	F	F

各行を確認します。1 行目は $P$ が真、$Q$ が真なので、$P \implies Q$ は表の 1 行目より T、$\lnot P$ は F で $\lnot P \lor Q$ は $\mathrm{F} \lor \mathrm{T} = \mathrm{T}$、$\lnot Q$ は F、$\lnot P$ は F なので $\lnot Q \implies \lnot P$ は $\mathrm{F} \implies \mathrm{F} = \mathrm{T}$ です。2 行目は $P$ が真、$Q$ が偽なので $P \implies Q$ は F、$\lnot P \lor Q = \mathrm{F} \lor \mathrm{F} = \mathrm{F}$、$\lnot Q \implies \lnot P$ は $\mathrm{T} \implies \mathrm{F} = \mathrm{F}$ です。3 行目と 4 行目では $P$ が偽なので $P \implies Q$ は T、$\lnot P$ が真なので $\lnot P \lor Q$ も T、そして $\lnot Q \implies \lnot P$ は結論 $\lnot P$ が真なので T です。

こうして 3 列 $P \implies Q$、$\lnot P \lor Q$、$\lnot Q \implies \lnot P$ が 4 行すべてで一致しました。また $P \land \lnot Q$ の列は $\lnot(P \implies Q)$ の列と 4 行すべてで一致しています。

∎

対偶が使えることは、証明の実務でそのまま効きます。「$n^2$ が偶数ならば $n$ は偶数」を直接示すのは面倒ですが、対偶「$n$ が奇数ならば $n^2$ は奇数」なら $n = 2k+1$ と置いて $n^2 = 4k^2 + 4k + 1 = 2(2k^2+2k)+1$ と計算するだけで済みます（この補題が $\sqrt{2}$ の無理性の証明でどう使われるかは 平方が偶数なら元も偶数（補題 7.4）［証明の技術］ を参照）。

例 2.5（逆・裏・対偶）

$x$ を実数とし、$P$ を「$x = 2$」、$Q$ を「$x^2 = 4$」とします。

• $P \implies Q$ は真です。$x = 2$ なら $x^2 = 2^2 = 4$ だからです。
• 逆 $Q \implies P$ は偽です。$x = -2$ とすると $x^2 = 4$ は真ですが $x = 2$ は偽なので、定義 2.3 の表の 2 行目にあたり、$Q \implies P$ は F になります。
• 裏 $\lnot P \implies \lnot Q$ も偽です。$x = -2$ のとき $\lnot P$ は真、$\lnot Q$ は偽だからです。
• 対偶 $\lnot Q \implies \lnot P$ は真です。$x^2 \ne 4$ なら $x = 2$ ではありえません。これは 命題 2.4 が保証するとおり、$P \implies Q$ が真であることと同じです。

逆と裏は互いに対偶の関係にあるので、いま見たように真偽が一致します。

3. 集合の基本概念

3.1. 元と外延性

定義 3.1（集合と元）

集合とは、ある対象 $x$ を持ってきたときに「$x$ がそれに属するか属さないか」が一意に定まるような、ものの集まりです。$x$ が集合 $A$ に属することを $x \in A$ と書き、$x$ を $A$ の元（または要素）といいます。属さないことは $x \notin A$ と書きます。

集合を指定する方法は 2 つあります。元をすべて並べる外延的記法 $A = \{1, 2, 3\}$ と、条件で切り出す内包的記法 $A = \{x \in \mathbb{N} \mid x \le 3\}$ です。ここで $\mathbb{N} = \{1, 2, 3, \ldots\}$ とし、$0$ は含めないことにします。

公理 3.2（外延性の原理）

集合 $A$、$B$ に対し、

$$A = B \iff \forall x\,(x \in A \iff x \in B)$$

と定めます。すなわち、集合は「どの元を持つか」だけで決まります。

これは定理ではなく取り決めです。この取り決めから、集合には順序も重複もないことが従います。実際 $\{1, 2\}$ と $\{2, 1, 1\}$ は、どちらも「$x$ が $1$ または $2$ であるとき、そのときに限り属する」ので、公理 3.2 により等しい集合です。

定義 3.3（部分集合）

集合 $A$、$B$ に対し、

$$A \subseteq B \quad :\Longleftrightarrow \quad \forall x\,(x \in A \implies x \in B)$$

と定め、$A$ は $B$ の部分集合であるといいます。さらに $A \subseteq B$ かつ $A \ne B$ のとき、$A$ は $B$ の真部分集合であるといい、$A \subsetneq B$ と書きます。

$\in$ と $\subseteq$ は別物です。$\in$ は「元であること」、$\subseteq$ は「部分集合であること」を表します。$A = \{1, 2\}$ について $1 \in A$ は真ですが $1 \subseteq A$ は意味をなさず（$1$ は集合ではない）、$\{1\} \subseteq A$ は真ですが $\{1\} \in A$ は偽です。$A$ の元は $1$ と $2$ であって $\{1\}$ ではないからです。

命題 3.4（集合の相等は二重包含）

集合 $A$、$B$ に対し

$$A = B \iff (A \subseteq B \ \text{かつ}\ B \subseteq A)$$

が成り立ちます。

証明（命題 3.4）

公理 3.2 により、$A = B$ は「すべての $x$ について $x \in A \iff x \in B$」と同値です。そこで、各 $x$ について

$$(x \in A \iff x \in B) \quad\text{と}\quad \bigl((x \in A \implies x \in B) \ \text{かつ}\ (x \in B \implies x \in A)\bigr)$$

が同じ真理値をとることを見れば十分です。$P$ を $x \in A$、$Q$ を $x \in B$ とおいて 定義 2.3 の表を見ると、$P \iff Q$ が T になるのは 1 行目（両方 T）と 4 行目（両方 F）です。一方 $(P \implies Q) \land (Q \implies P)$ は、2 行目では $P \implies Q$ が F、3 行目では $Q \implies P$ が F なので F になり、1 行目と 4 行目では両方の含意が T なので T になります。したがって 4 行すべてで一致します。

以上より、「すべての $x$ について $x \in A \iff x \in B$」は「すべての $x$ について $x \in A \implies x \in B$」かつ「すべての $x$ について $x \in B \implies x \in A$」と同値です。定義 3.3 によりこれは $A \subseteq B$ かつ $B \subseteq A$ に他なりません。

∎

この命題は、この記事だけでなく数学全体でもっともよく使う証明の型を与えます。集合の等式を見たら、まず 2 本の包含関係に割り、それぞれを「$x \in$ 左辺 と仮定して $x \in$ 右辺 を導く」形で書く。これを元の追跡（element chasing）といいます。

3.2. 空集合とべき集合

定義 3.5（空集合・べき集合）

元を 1 つも持たない集合を空集合といい、$\emptyset$ と書きます。すなわち、すべての $x$ について $x \notin \emptyset$ です。

集合 $A$ に対し、$A$ の部分集合全体からなる集合

$$\mathcal{P}(A) = \{X \mid X \subseteq A\}$$

を $A$ のべき集合といいます。

命題 3.6（空集合の基本性質）

(1) 任意の集合 $A$ に対し $\emptyset \subseteq A$ が成り立ちます。
(2) 空集合はただ 1 つです。すなわち、元を持たない集合 $E$、$E'$ があれば $E = E'$ です。

証明（命題 3.6）

(1) 定義 3.3 により、示すべきは「すべての $x$ について $x \in \emptyset \implies x \in A$」です。$x$ を任意にとると、定義 3.5 により $x \in \emptyset$ は偽です。定義 2.3 の表を見ると、前件が F の行（3 行目と 4 行目）では $\implies$ の値は T です。よって $x \in \emptyset \implies x \in A$ は $x$ によらず真であり、$\emptyset \subseteq A$ が成り立ちます。

(2) $E$、$E'$ がともに元を持たないとします。(1) と同じ議論で $E \subseteq E'$ と $E' \subseteq E$ が言えます。$x \in E$ はつねに偽なので $x \in E \implies x \in E'$ はつねに真、同様に $x \in E' \implies x \in E$ もつねに真だからです。命題 3.4 により $E = E'$ です。

∎

(1) の証明のように、前件が決して成り立たないために自動的に真になる主張を空虚に真（vacuously true）といいます。冒頭に挙げた「生徒が 1 人もいないクラスの全員が身長 3 メートル以上」も同じ構造で、真です。反例となる生徒を 1 人も出せない以上、この主張を偽にする方法がありません。

例 3.7（べき集合を書き下す）

$A = \{1, 2, 3\}$ とします。部分集合を、元の個数ごとに漏れなく列挙します。

• 元が 0 個: $\emptyset$
• 元が 1 個: $\{1\}, \{2\}, \{3\}$
• 元が 2 個: $\{1,2\}, \{1,3\}, \{2,3\}$
• 元が 3 個: $\{1,2,3\}$

したがって

$$\mathcal{P}(A) = \bigl\{\, \emptyset,\ \{1\},\ \{2\},\ \{3\},\ \{1,2\},\ \{1,3\},\ \{2,3\},\ \{1,2,3\} \,\bigr\}$$

であり、$\mathcal{P}(A)$ の元の個数は $1 + 3 + 3 + 1 = 8 = 2^{3}$ 個です。$\emptyset$ が含まれるのは 命題 3.6 の (1) による、$A$ 自身が含まれるのは $A \subseteq A$ による、という点に注意してください。

定理 3.8（べき集合の元の個数）

$A$ を元の個数が $n$ 個の有限集合とすると、$\mathcal{P}(A)$ の元の個数は $2^{n}$ 個です。

証明（定理 3.8）

$A$ の元を $a_1, a_2, \ldots, a_n$ と番号づけます（$i \ne j$ なら $a_i \ne a_j$）。長さ $n$ の $0$-$1$ 列全体の集合を

$$S = \{(\varepsilon_1, \ldots, \varepsilon_n) \mid \text{各 } \varepsilon_i \text{ は } 0 \text{ または } 1\}$$

とします。$\mathcal{P}(A)$ から $S$ への対応 $\chi$ を、$X \subseteq A$ に対し

$$\chi(X) = (\varepsilon_1, \ldots, \varepsilon_n), \qquad \varepsilon_i = \begin{cases} 1 & (a_i \in X) \\ 0 & (a_i \notin X) \end{cases}$$

で定めます。各 $i$ について $a_i \in X$ か $a_i \notin X$ のいずれか一方が成り立つので（定義 3.1）、$\chi(X)$ は一意に定まります。

$\chi$ が単射であることを示します。$X, Y \subseteq A$ が $\chi(X) = \chi(Y)$ を満たすとします。任意の $x \in A$ は $x = a_i$ となる $i$ を持ちますが、第 $i$ 成分が等しいことから「$a_i \in X$」と「$a_i \in Y$」は同時に成り立つか同時に成り立たないかのいずれかです。また $x \notin A$ である $x$ については、$X \subseteq A$、$Y \subseteq A$ より $x \notin X$ かつ $x \notin Y$ です。よってすべての $x$ について $x \in X \iff x \in Y$ が成り立ち、公理 3.2 から $X = Y$ を得ます。

$\chi$ が全射であることを示します。$(\varepsilon_1, \ldots, \varepsilon_n) \in S$ が与えられたとき、$X = \{a_i \mid \varepsilon_i = 1\}$ とおけば $X \subseteq A$ であり、定義から $a_i \in X$ となるのはちょうど $\varepsilon_i = 1$ のときなので $\chi(X) = (\varepsilon_1, \ldots, \varepsilon_n)$ です。

したがって $\mathcal{P}(A)$ と $S$ の元の個数は等しくなります。$S$ の元は各成分を独立に $2$ 通りから選んで作られるので $2 \times 2 \times \cdots \times 2 = 2^{n}$ 個です。よって $\mathcal{P}(A)$ の元の個数は $2^{n}$ 個です。

∎

注意 3.9

$A$ が無限集合のときも $\mathcal{P}(A)$ は $A$ より「真に大きい」ことが証明できます（カントールの定理（定理 7.1）［濃度と無限］）。有限の場合の $2^n > n$ に対応する主張ですが、証明は数え上げではなく対角線論法によります。詳しくは 濃度と無限 を参照してください。また、$n$ についての数学的帰納法による 定理 3.8 の別証明は 証明の技術 の例として扱います。

4. 集合の演算

4.1. 定義と論理結合子との対応

以下、考える対象をすべて含む集合 $U$ を固定し、これを全体集合と呼びます。扱う集合はすべて $U$ の部分集合とします。

定義 4.1（和集合・共通部分・差集合・補集合）

$A, B \subseteq U$ に対し、

$$\begin{aligned} A \cup B &= \{x \in U \mid x \in A \ \text{または}\ x \in B\} &&(\text{和集合}) \\ A \cap B &= \{x \in U \mid x \in A \ \text{かつ}\ x \in B\} &&(\text{共通部分}) \\ A \setminus B &= \{x \in U \mid x \in A \ \text{かつ}\ x \notin B\} &&(\text{差集合}) \\ A^{c} &= \{x \in U \mid x \notin A\} &&(\text{補集合}) \end{aligned}$$

と定めます。$A \cap B = \emptyset$ のとき $A$ と $B$ は互いに素であるといいます。

定義を見ればわかるとおり、集合の演算は論理結合子の言い換えです。この対応表が、この記事全体の背骨です。

集合の側	$x$ についての条件	論理の側
$A \cap B$	$x \in A$ かつ $x \in B$	$\land$
$A \cup B$	$x \in A$ または $x \in B$	$\lor$
$A \setminus B$	$x \in A$ かつ $x \notin B$	$\land$ と $\lnot$
$A^{c}$	$x \notin A$	$\lnot$
$A \subseteq B$	$x \in A$ ならば $x \in B$	$\implies$
$A = B$	$x \in A$ と $x \in B$ が同値	$\iff$

この対応があるので、論理の等式を 1 つ証明すれば、集合の等式が 1 つ手に入ります。以下ではその手順を実際に踏みます。

全体集合 U の中の 2 つの集合 A, B。境界で区切られる 4 つの領域に番号を振った。

図の 4 領域は、それぞれ ① が $A \setminus B$、② が $A \cap B$、③ が $B \setminus A$、④ が $A^{c} \cap B^{c}$ です。任意の $x \in U$ は、$x \in A$ かどうかと $x \in B$ かどうかの組み合わせで、この 4 つのちょうど 1 つに属します。

注意

ベン図は発見の道具であって証明ではありません。3 つ以上の集合になると、すべての交わり方を平面上の円で描き分けることができなくなります（4 つの集合を円 4 個で描くと、$2^4 = 16$ 個あるべき領域のうちいくつかが現れません）。図で見当をつけ、証明は元の追跡で書く、という使い分けをしてください。

4.2. 分配法則

定理 4.2（分配法則）

$A, B, C \subseteq U$ に対し

$$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$$

が成り立ちます。

証明（定理 4.2）

命題 3.4 により、2 つの包含を示します。

（$\subseteq$）$x \in A \cap (B \cup C)$ とします。定義 4.1 より $x \in A$ かつ $x \in B \cup C$ です。後半から、$x \in B$ または $x \in C$ が成り立ちます。

• $x \in B$ の場合: $x \in A$ と合わせて $x \in A \cap B$。よって $x \in (A \cap B) \cup (A \cap C)$。
• $x \in C$ の場合: $x \in A$ と合わせて $x \in A \cap C$。よって $x \in (A \cap B) \cup (A \cap C)$。

いずれの場合も $x \in (A \cap B) \cup (A \cap C)$ なので、$A \cap (B \cup C) \subseteq (A \cap B) \cup (A \cap C)$ です。

（$\supseteq$）$x \in (A \cap B) \cup (A \cap C)$ とします。$x \in A \cap B$ または $x \in A \cap C$ です。

• $x \in A \cap B$ の場合: $x \in A$ かつ $x \in B$。$x \in B$ から $x \in B \cup C$ なので、$x \in A \cap (B \cup C)$。
• $x \in A \cap C$ の場合: $x \in A$ かつ $x \in C$。$x \in C$ から $x \in B \cup C$ なので、$x \in A \cap (B \cup C)$。

いずれの場合も $x \in A \cap (B \cup C)$ なので、$(A \cap B) \cup (A \cap C) \subseteq A \cap (B \cup C)$ です。

2 つの包含が示されたので、命題 3.4 により等号が成り立ちます。

∎

もう一方の分配法則 $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ も同じ型で示せます。手を動かして確かめるために、演習 7.2 に回しました。

4.3. ド・モルガンの法則

補題 4.3（ド・モルガンの法則（命題論理版））

任意の命題 $P$、$Q$ に対し、$\lnot(P \lor Q)$ と $\lnot P \land \lnot Q$ はつねに同じ真理値をとります。また $\lnot(P \land Q)$ と $\lnot P \lor \lnot Q$ もつねに同じ真理値をとります。

証明（補題 4.3）

定義 2.3 の表に従って 4 通りを書き出します。

$P$	$Q$	$P \lor Q$	$\lnot(P \lor Q)$	$\lnot P \land \lnot Q$	$P \land Q$	$\lnot(P \land Q)$	$\lnot P \lor \lnot Q$
T	T	T	F	F	T	F	F
T	F	T	F	F	F	T	T
F	T	T	F	F	F	T	T
F	F	F	T	T	F	T	T

たとえば 2 行目は、$P$ が T、$Q$ が F なので $P \lor Q$ は T、その否定は F です。一方 $\lnot P$ は F なので $\lnot P \land \lnot Q$ は F であり、両者は一致します。同じ行で $P \land Q$ は F、その否定は T、$\lnot P \lor \lnot Q = \mathrm{F} \lor \mathrm{T} = \mathrm{T}$ でこちらも一致します。残りの 3 行も表のとおりです。

$\lnot(P \lor Q)$ の列と $\lnot P \land \lnot Q$ の列、$\lnot(P \land Q)$ の列と $\lnot P \lor \lnot Q$ の列が、それぞれ 4 行すべてで一致しました。

∎

定理 4.4（ド・モルガンの法則（集合版））

$A, B \subseteq U$ に対し

$$(A \cup B)^{c} = A^{c} \cap B^{c}, \qquad (A \cap B)^{c} = A^{c} \cup B^{c}$$

が成り立ちます。

証明（定理 4.4）

前半を示します。$x \in U$ を任意にとり、$P$ を命題「$x \in A$」、$Q$ を命題「$x \in B$」とおきます。定義 4.1 の各定義と、4 行目で 補題 4.3 を使うと、次の同値が順に成り立ちます。

$$\begin{aligned} x \in (A \cup B)^{c} &\iff x \notin A \cup B && (\text{補集合の定義}) \\ &\iff \lnot(x \in A \ \text{または}\ x \in B) && (\text{和集合の定義}) \\ &\iff \lnot(P \lor Q) \\ &\iff \lnot P \land \lnot Q && (\text{ド・モルガンの法則の命題論理版}) \\ &\iff x \notin A \ \text{かつ}\ x \notin B \\ &\iff x \in A^{c} \ \text{かつ}\ x \in B^{c} && (\text{補集合の定義}) \\ &\iff x \in A^{c} \cap B^{c} && (\text{共通部分の定義}). \end{aligned}$$

すべての $x \in U$ について $x \in (A \cup B)^{c} \iff x \in A^{c} \cap B^{c}$ が成り立つので、公理 3.2 により $(A \cup B)^{c} = A^{c} \cap B^{c}$ です。

後半も同様の鎖で示せます。$x \in (A \cap B)^{c} \iff \lnot(P \land Q)$ であり、補題 4.3 の後半より $\lnot(P \land Q) \iff \lnot P \lor \lnot Q$、これは $x \in A^{c}$ または $x \in B^{c}$、すなわち $x \in A^{c} \cup B^{c}$ です。よって 公理 3.2 から $(A \cap B)^{c} = A^{c} \cup B^{c}$ を得ます。

∎

定理 4.4 の前半は、定義 4.1 のあとの図の 4 領域を使っても確認できます。各領域について両辺に属するかどうかを表にすると、次のようになります（○ が「属する」、× が「属さない」）。

領域	$x \in A$	$x \in B$	$A \cup B$	$(A \cup B)^{c}$	$A^{c}$	$B^{c}$	$A^{c} \cap B^{c}$
①	○	×	○	×	×	○	×
②	○	○	○	×	×	×	×
③	×	○	○	×	○	×	×
④	×	×	×	○	○	○	○

$(A \cup B)^{c}$ の列と $A^{c} \cap B^{c}$ の列が 4 行とも一致しています。4 つの領域が $U$ を覆い尽くしていることが、この確認が証明になるための条件です。

例 4.5（具体的な集合で確かめる）

$U = \{1,2,3,4,5,6,7,8,9,10\}$、$A$ を $U$ の偶数全体、$B$ を $U$ の $3$ の倍数全体とします。すなわち

$$A = \{2,4,6,8,10\}, \qquad B = \{3,6,9\}.$$

まず左辺を計算します。$A \cup B = \{2,3,4,6,8,9,10\}$ なので、

$$(A \cup B)^{c} = \{1,5,7\}.$$

次に右辺を計算します。$A^{c} = \{1,3,5,7,9\}$、$B^{c} = \{1,2,4,5,7,8,10\}$ なので、共通の元を拾って

$$A^{c} \cap B^{c} = \{1,5,7\}.$$

一致しました。意味を読み取ると、「偶数でも $3$ の倍数でもない数」は「$6$ 以下の素数と $1$ と $7$」ではなく、正しくは「$2$ でも $3$ でも割り切れない $10$ 以下の自然数」、つまり $1, 5, 7$ です。

注意 4.6

すべての演算が数の四則と同じ性質を持つわけではありません。差集合は結合法則を満たしません。$A = B = C = \{1\}$ とすると、

$$(A \setminus B) \setminus C = \emptyset \setminus \{1\} = \emptyset, \qquad A \setminus (B \setminus C) = \{1\} \setminus \emptyset = \{1\}$$

となり、両者は異なります。したがって $A \setminus B \setminus C$ という括弧なしの表記は使えません。「$\cup$ と $\cap$ は結合的だから $\setminus$ もそうだろう」という類推は、ここで壊れます。

5. 述語と量化子

5.1. 述語

定義 5.1（述語）

集合 $X$ を固定します。各 $a \in X$ に対して命題 $P(a)$ が定まっているとき、$P$ を $X$ 上の述語（または条件）といい、$X$ を $P$ の変域といいます。

「$x + 1 = 3$」は、変域を $\mathbb{N}$ と決めれば $\mathbb{N}$ 上の述語です。$P(2)$ は真、$P(5)$ は偽、というように、$x$ に値を代入してはじめて真偽が決まります。変域を明示しないと真偽が変わることに注意してください。「$x^2 = 2$ を満たす $x$ が存在する」は変域が $\mathbb{Q}$ なら偽（平方根 2 の無理性（定理 7.5）［証明の技術］）、$\mathbb{R}$ なら真です（√2 の存在（定理 5.6）［数とは何か］）。

定義 5.2（全称記号と存在記号）

$X$ 上の述語 $P$ に対し、次の 2 つの命題を定めます。

• $\forall x \in X,\ P(x)$：$X$ のすべての元 $a$ に対して $P(a)$ が真であるとき、そのときに限り真。
• $\exists x \in X,\ P(x)$：$P(a)$ が真となる $a \in X$ が少なくとも 1 つ存在するとき、そのときに限り真。

$\forall$ を全称記号、$\exists$ を存在記号といい、まとめて量化子といいます。

変域が空のときの値を確認しておきます。$X = \emptyset$ なら、$\forall x \in \emptyset,\ P(x)$ は真です。偽だとすると $P(a)$ が偽になる $a \in \emptyset$ が必要ですが、$\emptyset$ には元がないからです。一方 $\exists x \in \emptyset,\ P(x)$ は偽です。$P(a)$ を真にする $a$ 以前に、$a \in \emptyset$ となる $a$ が存在しません。これが 命題 3.6 で見た「空虚に真」の言い換えです。

5.2. 否定の作り方

定理 5.3（量化子の否定）

$X$ を集合、$P$ を $X$ 上の述語とします。このとき

$$\lnot\bigl(\forall x \in X,\ P(x)\bigr) \iff \exists x \in X,\ \lnot P(x),$$$$\lnot\bigl(\exists x \in X,\ P(x)\bigr) \iff \forall x \in X,\ \lnot P(x)$$

が成り立ちます。

証明（定理 5.3）

前半を示します。

（$\Longrightarrow$）$\lnot(\forall x \in X, P(x))$ が真であるとします。ここで、結論 $\exists x \in X,\ \lnot P(x)$ が偽であると仮定して矛盾を導きます。$\exists x \in X,\ \lnot P(x)$ が偽であるとは、定義 5.2 により、$\lnot P(a)$ を真にする $a \in X$ が 1 つも存在しないということです。すると、どの $a \in X$ についても $\lnot P(a)$ は偽、すなわち $P(a)$ は真です。これは 定義 5.2 により $\forall x \in X, P(x)$ が真であることを意味し、仮定 $\lnot(\forall x \in X, P(x))$ に反します。よって $\exists x \in X,\ \lnot P(x)$ は真です。

（$\Longleftarrow$）$\exists x \in X,\ \lnot P(x)$ が真であるとし、$\lnot P(a)$ が真となる元 $a \in X$ を 1 つとります。もし $\forall x \in X, P(x)$ が真なら、$a \in X$ なので $P(a)$ が真となり、$\lnot P(a)$ が真であることに矛盾します。よって $\forall x \in X, P(x)$ は偽、すなわち $\lnot(\forall x \in X, P(x))$ は真です。

後半は、前半を述語 $\lnot P$ に適用して得られます。実際、前半より $\lnot(\forall x \in X, \lnot P(x)) \iff \exists x \in X, \lnot\lnot P(x)$ であり、$\lnot \lnot P(x)$ と $P(x)$ は同じ真理値をとるので（定義 2.3 の表で $\lnot$ を 2 回適用すれば元に戻ります）、$\lnot(\forall x \in X, \lnot P(x)) \iff \exists x \in X, P(x)$ を得ます。両辺の否定をとり、再び二重否定を外せば $\forall x \in X, \lnot P(x) \iff \lnot(\exists x \in X, P(x))$ となります。

∎

この定理と 命題 2.4 の最後の主張（$\lnot(P \implies Q)$ は $P \land \lnot Q$）を組み合わせると、どんなに長い論理式でも、否定を機械的に内側へ押し込めます。手順は 3 つだけです。

1. 先頭の $\forall$ は $\exists$ に、$\exists$ は $\forall$ に入れ替え、$\lnot$ を 1 つ内側へ移す。
2. $\lnot(P \land Q)$ は $\lnot P \lor \lnot Q$ に、$\lnot(P \lor Q)$ は $\lnot P \land \lnot Q$ に置き換える（補題 4.3）。
3. $\lnot(P \implies Q)$ は $P \land \lnot Q$ に置き換える（命題 2.4）。

flowchart TB
S0["¬ ∀ε ∃δ ∀x ( P ⟹ Q )"] --> S1["∃ε ¬ ∃δ ∀x ( P ⟹ Q )"]
S1 --> S2["∃ε ∀δ ¬ ∀x ( P ⟹ Q )"]
S2 --> S3["∃ε ∀δ ∃x ¬( P ⟹ Q )"]
S3 --> S4["∃ε ∀δ ∃x ( P ∧ ¬Q )"]

ε-δ 論法の否定を作る手順。各段で否定記号が 1 つ内側へ移り、そのたびに量化子が入れ替わる。

例 5.4（連続性の定義を否定する）

実数値関数 $f$ が点 $a$ で連続であるとは、

$$\forall \varepsilon > 0,\ \exists \delta > 0,\ \forall x \in \mathbb{R},\ \bigl(|x - a| < \delta \implies |f(x) - f(a)| < \varepsilon\bigr)$$

が成り立つことです。この否定を、上の 3 手順で作ります。最初の 3 段では 定理 5.3 を、最後の 1 段では 命題 2.4 を使います。

$$\begin{aligned} &\lnot\Bigl(\forall \varepsilon > 0,\ \exists \delta > 0,\ \forall x,\ (|x-a| < \delta \implies |f(x)-f(a)| < \varepsilon)\Bigr) \\ &\iff \exists \varepsilon > 0,\ \lnot\Bigl(\exists \delta > 0,\ \forall x,\ (\cdots)\Bigr) && (\text{量化子の否定}) \\ &\iff \exists \varepsilon > 0,\ \forall \delta > 0,\ \lnot\Bigl(\forall x,\ (\cdots)\Bigr) && (\text{量化子の否定}) \\ &\iff \exists \varepsilon > 0,\ \forall \delta > 0,\ \exists x,\ \lnot\bigl(|x-a| < \delta \implies |f(x)-f(a)| < \varepsilon\bigr) && (\text{量化子の否定}) \\ &\iff \exists \varepsilon > 0,\ \forall \delta > 0,\ \exists x,\ \bigl(|x-a| < \delta \ \land\ |f(x)-f(a)| \ge \varepsilon\bigr) && (\text{含意の否定}). \end{aligned}$$

日本語に直すと、「ある $\varepsilon > 0$ が存在して、どんなに $\delta > 0$ を小さくとっても、$a$ から $\delta$ 未満の距離にありながら値が $\varepsilon$ 以上ずれる点 $x$ が見つかる」となります。

実際に使ってみます。

$$f(x) = \begin{cases} 0 & (x \le 0) \\ 1 & (x > 0) \end{cases}$$

が $a = 0$ で連続でないことを示します。$\varepsilon = \tfrac{1}{2}$ とします。$\delta > 0$ を任意にとり、$x = \delta/2$ と選びます。すると $|x - 0| = \delta/2 < \delta$ であり、$x > 0$ より $f(x) = 1$、$f(0) = 0$ なので

$$|f(x) - f(0)| = |1 - 0| = 1 \ge \tfrac{1}{2} = \varepsilon$$

です。$\delta$ は任意だったので、上の否定形が成り立ちます。よって $f$ は $0$ で連続ではありません。

5.3. 量化子の順序

注意 5.5（順序を入れ替えてはいけない）

$\forall$ と $\exists$ が続くとき、その順序は意味を変えます。変域を $\mathbb{R}$ として、

• $\forall x \in \mathbb{R},\ \exists y \in \mathbb{R},\ y > x$ は真です。$x$ が与えられてから $y$ を選べるので、$y = x + 1$ とすればよいからです。
• $\exists y \in \mathbb{R},\ \forall x \in \mathbb{R},\ y > x$ は偽です。$y$ を先に固定しなければならず、その後で $x = y$ と選べば $y > x$ は成り立ちません。定理 5.3 を使えば、この否定が $\forall y,\ \exists x,\ y \le x$ であり、$x = y$ が実際に条件を満たすことで確認できます。

例 5.4 の連続性でも同じことが起きています。連続性では $\delta$ を $\varepsilon$ と点 $a$ の両方に応じて選べますが、$\forall a$ を $\exists \delta$ の内側に移して

$$\forall \varepsilon > 0,\ \exists \delta > 0,\ \forall a,\ \forall x,\ \bigl(|x-a| < \delta \implies |f(x)-f(a)| < \varepsilon\bigr)$$

とすると、$\delta$ が $a$ に依存できなくなります。これが一様連続の定義で、各点での連続性より強い条件です。記号の並び順という 1 か所の違いが、まったく別の概念を生みます。

5.4. 集合族への一般化

系 5.6（ド・モルガンの法則（集合族版））

$\Lambda$ を空でない集合とし、各 $\lambda \in \Lambda$ に対し $A_{\lambda} \subseteq U$ が与えられているとします。

$$\bigcup_{\lambda \in \Lambda} A_{\lambda} = \{x \in U \mid \exists \lambda \in \Lambda,\ x \in A_{\lambda}\}, \qquad \bigcap_{\lambda \in \Lambda} A_{\lambda} = \{x \in U \mid \forall \lambda \in \Lambda,\ x \in A_{\lambda}\}$$

と定めると、

$$\Bigl(\bigcup_{\lambda \in \Lambda} A_{\lambda}\Bigr)^{c} = \bigcap_{\lambda \in \Lambda} A_{\lambda}^{c}, \qquad \Bigl(\bigcap_{\lambda \in \Lambda} A_{\lambda}\Bigr)^{c} = \bigcup_{\lambda \in \Lambda} A_{\lambda}^{c}$$

が成り立ちます。

証明（系 5.6）

前半を示します。$x \in U$ を任意にとります。2 行目で 定理 5.3 の後半（$\lnot \exists$ が $\forall \lnot$ になる方）を使います。

$$\begin{aligned} x \in \Bigl(\bigcup_{\lambda} A_{\lambda}\Bigr)^{c} &\iff \lnot\bigl(\exists \lambda \in \Lambda,\ x \in A_{\lambda}\bigr) && (\text{和集合と補集合の定義}) \\ &\iff \forall \lambda \in \Lambda,\ \lnot(x \in A_{\lambda}) && (\text{量化子の否定}) \\ &\iff \forall \lambda \in \Lambda,\ x \in A_{\lambda}^{c} && (\text{補集合の定義}) \\ &\iff x \in \bigcap_{\lambda \in \Lambda} A_{\lambda}^{c} && (\text{共通部分の定義}). \end{aligned}$$

すべての $x \in U$ で同値なので、公理 3.2 により両辺は等しくなります。後半は、同じ鎖の 2 行目で 定理 5.3 の前半（$\lnot \forall$ が $\exists \lnot$ になる方）を使えば得られます。

∎

$\Lambda$ が 2 元集合のときが 定理 4.4 です。つまり 補題 4.3、定理 4.4、系 5.6 は同じ規則の 3 つの現れ方で、「否定は $\land$ と $\lor$ を、$\forall$ と $\exists$ を、$\cap$ と $\cup$ を入れ替える」という 1 文にまとまります。

6. 必要条件・十分条件・同値

定義 6.1（必要条件と十分条件）

命題 $P$、$Q$ について $P \implies Q$ が真であるとき、

• $P$ は $Q$ であるための十分条件、
• $Q$ は $P$ であるための必要条件

であるといいます。$P \implies Q$ と $Q \implies P$ がともに真であるとき、すなわち $P \iff Q$ が真であるとき、$P$ は $Q$ であるための必要十分条件であるといい、$P$ と $Q$ は同値であるといいます。

覚え方は「矢印の出る側が十分、入る側が必要」です。$P$ さえ言えれば $Q$ が言えるので $P$ は「十分」、$Q$ が成り立たなければ $P$ もありえない（対偶、命題 2.4）ので $Q$ は「必要」、と読みます。

例 6.2（2 乗して 4 になる数）

実数 $x$ についての条件を 3 つ考えます。$P$：$x = 2$、$Q$：$x^2 = 4$、$R$：$|x| = 2$。

• $P$ は $Q$ の十分条件です。$x = 2$ なら $x^2 = 4$ だからです。しかし必要条件ではありません。$x = -2$ は $Q$ を満たすが $P$ を満たさないので、$Q \implies P$ が偽だからです。
• $Q$ は $P$ の必要条件です。これは $P \implies Q$ が真であることの言い換えにすぎません。$x = 2$ であるためには、少なくとも $x^2 = 4$ でなければならない、と読みます。
• $R$ は $Q$ の必要十分条件です。$|x| = 2$ なら $x^2 = |x|^2 = 4$。逆に $x^2 = 4$ なら $x^2 - 4 = (x-2)(x+2) = 0$ より $x = 2$ または $x = -2$ で、どちらの場合も $|x| = 2$ です。

「$x = 2$ は $x^2 = 4$ であるための十分条件である」という文が、$x = 2$ という条件を強いものとして扱っていることに注意してください。強い条件（満たす数が少ない条件）が十分条件、弱い条件（満たす数が多い条件）が必要条件です。次の命題がこの直感を正確にします。

命題 6.3（真理集合と論理の対応）

$X$ を集合、$P$、$Q$ を $X$ 上の述語とし、真理集合を

$$[P] = \{x \in X \mid P(x) \ \text{が真}\}$$

で定めます（全体集合は $X$ とします）。このとき次が成り立ちます。

$$\begin{aligned} &\text{(1)}\quad \bigl(\forall x \in X,\ (P(x) \implies Q(x))\bigr) \iff [P] \subseteq [Q], \\ &\text{(2)}\quad [P \land Q] = [P] \cap [Q], \quad [P \lor Q] = [P] \cup [Q], \quad [\lnot P] = [P]^{c}. \end{aligned}$$

証明（命題 6.3）

(1) 定義 3.3 により、$[P] \subseteq [Q]$ とは「すべての $x$ について $x \in [P] \implies x \in [Q]$」ということです。真理集合の定義から、$x \in [P]$ は「$x \in X$ かつ $P(x)$ が真」と同値、$x \in [Q]$ は「$x \in X$ かつ $Q(x)$ が真」と同値です。変域を $X$ に限れば $x \in X$ は自動的に成り立つので、条件は「すべての $x \in X$ について $P(x) \implies Q(x)$」に一致します。

(2) $x \in X$ を任意にとります。$x \in [P \land Q]$ は定義により「$P(x) \land Q(x)$ が真」、すなわち「$P(x)$ が真かつ $Q(x)$ が真」であり（定義 2.3）、これは $x \in [P]$ かつ $x \in [Q]$、すなわち $x \in [P] \cap [Q]$ と同値です（定義 4.1）。すべての $x \in X$ で同値なので、公理 3.2 により $[P \land Q] = [P] \cap [Q]$ です。$\lor$ と $\lnot$ についても、$\lor$ が $\cup$ の、$\lnot$ が補集合の定義そのものであることから、まったく同じ手順で示せます。

∎

(1) により、「$P$ は $Q$ の十分条件」は「$[P] \subseteq [Q]$」と同じです。例 6.2 では $[P] = \{2\}$、$[Q] = \{2, -2\}$ なので $[P] \subsetneq [Q]$ であり、十分条件だが必要条件ではない、という結論が包含関係として一目でわかります。「十分条件は小さい集合、必要条件は大きい集合」というのは、この包含関係のことです。

ヒント

定義を書くときには、それがきちんと定まっているか（well-defined か）を確かめる必要があります。たとえば「有理数 $p/q$ に対し $f(p/q) = p + q$ と定める」は、$1/2 = 2/4$ なのに $f$ の値が $3$ と $6$ で食い違うため、定義になっていません。代表元の取り方によらないことを確認する、というこの手続きは、関係と同値関係 で正面から扱います（この例そのものは well-defined でない「定義」（例 5.6）［関係と同値関係］ で検討されます）。

注意 6.4（素朴集合論の限界）

定義 3.1 のように「条件を書けば集合が作れる」と考えると、破綻します。条件「$x \notin x$」で集合

$$R = \{x \mid x \notin x\}$$

を作ったとしましょう。$R \in R$ とすると、$R$ が条件を満たすので $R \notin R$。逆に $R \notin R$ とすると、$R$ は条件を満たすので $R \in R$。どちらの場合も矛盾します（ラッセル、1901 年）。

現代の公理的集合論（ZFC）は、「任意の条件から集合を作ってよい」という原則を捨て、すでにある集合 $A$ の中から条件で切り出すことだけを許します（分出公理図式）。この記事で内包的記法をつねに $\{x \in U \mid \cdots\}$ の形で書き、変域 $U$ を明示してきたのはそのためです。公理系そのものが何を保証し何を保証しないかという問いは、不完全性定理（第一不完全性定理（定理 5.1）［ゲーデルの不完全性定理］）につながります。また「$0.999\ldots = 1$」のような等式が、記号の意味をどこまで遡って定義すれば決着するのかは、数とは何か で扱います。

7. 演習

演習 7.1易

$A = \{\emptyset, \{\emptyset\}\}$ とします。

(1) $\mathcal{P}(A)$ を書き下し、元の個数が 定理 3.8 と合うことを確かめてください。
(2) 次の 4 つの主張の真偽を、理由を付けて答えてください。$\emptyset \in A$、$\emptyset \subseteq A$、$\{\emptyset\} \in A$、$\{\emptyset\} \subseteq A$。

解答

(1) $A$ の元は $\emptyset$ と $\{\emptyset\}$ の 2 個です。部分集合を元の個数ごとに列挙すると、$0$ 個のものが $\emptyset$、$1$ 個のものが $\{\emptyset\}$ と $\{\{\emptyset\}\}$、$2$ 個のものが $\{\emptyset, \{\emptyset\}\} = A$ です。よって

$$\mathcal{P}(A) = \bigl\{\, \emptyset,\ \{\emptyset\},\ \{\{\emptyset\}\},\ \{\emptyset, \{\emptyset\}\} \,\bigr\}$$

であり、元の個数は $4 = 2^{2}$ 個で 定理 3.8 と合致します。

(2)

• $\emptyset \in A$ は真です。$A$ の元として $\emptyset$ が挙げられているからです。
• $\emptyset \subseteq A$ は真です。命題 3.6 の (1) により、空集合は任意の集合の部分集合です。
• $\{\emptyset\} \in A$ は真です。$A$ の 2 つ目の元が $\{\emptyset\}$ だからです。
• $\{\emptyset\} \subseteq A$ は真です。$\{\emptyset\}$ の元は $\emptyset$ だけであり、$\emptyset \in A$ が成り立つので、定義 3.3 の条件が満たされます。

この例では 4 つとも真になりますが、それは $\emptyset$ が「$A$ の元」でも「$A$ の元だけからなる集合の中身」でもあるという特殊事情によります。一般には $\in$ と $\subseteq$ は無関係だと考えてください。

演習 7.2標準

$A, B, C \subseteq U$ に対し

$$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$$

を、元の追跡によって証明してください。

解答

命題 3.4 に従い、2 つの包含を示します。

（$\subseteq$）$x \in A \cup (B \cap C)$ とします。定義 4.1 より、$x \in A$ または $x \in B \cap C$ です。

• $x \in A$ の場合：$x \in A$ から $x \in A \cup B$ かつ $x \in A \cup C$ なので、$x \in (A \cup B) \cap (A \cup C)$ です。
• $x \in B \cap C$ の場合：$x \in B$ かつ $x \in C$ です。$x \in B$ より $x \in A \cup B$、$x \in C$ より $x \in A \cup C$。よって $x \in (A \cup B) \cap (A \cup C)$ です。

いずれの場合も右辺に属するので、$A \cup (B \cap C) \subseteq (A \cup B) \cap (A \cup C)$ です。

（$\supseteq$）$x \in (A \cup B) \cap (A \cup C)$ とします。すなわち $x \in A \cup B$ かつ $x \in A \cup C$ です。ここで $x \in A$ かどうかで場合分けします。

• $x \in A$ の場合：ただちに $x \in A \cup (B \cap C)$ です。
• $x \notin A$ の場合：$x \in A \cup B$ と $x \notin A$ から、$x \in B$ でなければなりません（$\lor$ の定義により、$x \in A$ が偽なら $x \in B$ が真）。同様に $x \in A \cup C$ と $x \notin A$ から $x \in C$ です。よって $x \in B \cap C$ となり、$x \in A \cup (B \cap C)$ です。

いずれの場合も左辺に属するので、$(A \cup B) \cap (A \cup C) \subseteq A \cup (B \cap C)$ です。

2 つの包含から、命題 3.4 により等号が成り立ちます。

演習 7.3標準

実数列 $(a_n)_{n \in \mathbb{N}}$ が実数 $\alpha$ に収束するとは

$$\forall \varepsilon > 0,\ \exists N \in \mathbb{N},\ \forall n \in \mathbb{N},\ \bigl(n \ge N \implies |a_n - \alpha| < \varepsilon\bigr)$$

が成り立つことです。

(1) この主張の否定を、量化子を先頭にそろえた形で書いてください。
(2) $a_n = (-1)^{n}$ で定まる数列が、どんな実数 $\alpha$ にも収束しないことを示してください。

解答

(1) 定理 5.3 を 3 回、続いて 命題 2.4 を 1 回使います。

$$\begin{aligned} &\lnot\bigl(\forall \varepsilon > 0,\ \exists N,\ \forall n,\ (n \ge N \implies |a_n - \alpha| < \varepsilon)\bigr) \\ &\iff \exists \varepsilon > 0,\ \forall N \in \mathbb{N},\ \exists n \in \mathbb{N},\ \lnot\bigl(n \ge N \implies |a_n - \alpha| < \varepsilon\bigr) \\ &\iff \exists \varepsilon > 0,\ \forall N \in \mathbb{N},\ \exists n \in \mathbb{N},\ \bigl(n \ge N \ \land\ |a_n - \alpha| \ge \varepsilon\bigr). \end{aligned}$$

(2) $\alpha$ を任意の実数とし、$\varepsilon = 1$ とします。$N \in \mathbb{N}$ を任意にとります。ここで、$n \ge N$ を満たすすべての $n$ について $|a_n - \alpha| < 1$ が成り立つと仮定して、矛盾を導きます。

$n_0$ を $N$ 以上の偶数、$m_0$ を $N$ 以上の奇数とします（$N, N+1$ の一方は偶数、他方は奇数なので、どちらも存在します）。仮定より $|a_{n_0} - \alpha| < 1$ かつ $|a_{m_0} - \alpha| < 1$ です。三角不等式から

$$|a_{n_0} - a_{m_0}| \le |a_{n_0} - \alpha| + |\alpha - a_{m_0}| < 1 + 1 = 2$$

となります。しかし $a_{n_0} = (-1)^{n_0} = 1$、$a_{m_0} = (-1)^{m_0} = -1$ なので $|a_{n_0} - a_{m_0}| = |1 - (-1)| = 2$ であり、$2 < 2$ という矛盾が生じます。

したがって仮定は誤りで、$n \ge N$ かつ $|a_n - \alpha| \ge 1$ を満たす $n$ が存在します。$N$ は任意だったので (1) の否定形が成り立ち、$(a_n)$ は $\alpha$ に収束しません。$\alpha$ も任意だったので、この数列はどんな実数にも収束しません。

演習 7.4難

$A, B \subseteq U$ に対し対称差を $A \bigtriangleup B = (A \setminus B) \cup (B \setminus A)$ で定めます。$A, B, C \subseteq U$ に対し

$$(A \bigtriangleup B) \bigtriangleup C = A \bigtriangleup (B \bigtriangleup C)$$

が成り立つことを示してください。

解答

まず補題として、$x \in U$ に対し

$$x \in A \bigtriangleup B \iff \text{「$x \in A$」と「$x \in B$」のちょうど一方が成り立つ}$$

を示します。定義 4.1 により $x \in A \setminus B$ は「$x \in A$ かつ $x \notin B$」、$x \in B \setminus A$ は「$x \in B$ かつ $x \notin A$」です。和集合の定義より $x \in A \bigtriangleup B$ はこの 2 つの一方が成り立つこと、すなわち $x$ が $A$ だけに属するか $B$ だけに属するかであり、これは「ちょうど一方」と同じです。

次に、$x$ が $A$、$B$、$C$ のうち属するものの個数を $k(x) \in \{0,1,2,3\}$ と書き、次の主張を示します。

$$x \in (A \bigtriangleup B) \bigtriangleup C \iff k(x) \ \text{が奇数}.$$

補題を $A \bigtriangleup B$ と $C$ に適用すると、$x \in (A \bigtriangleup B) \bigtriangleup C$ は「$x \in A \bigtriangleup B$」と「$x \in C$」のちょうど一方が成り立つことです。$x \in C$ かどうかで場合分けします。

• $x \in C$ の場合：条件は $x \notin A \bigtriangleup B$、すなわち補題より「$x \in A$ と $x \in B$ がともに成り立つか、ともに成り立たない」ことです。このとき $x$ が $A$、$B$ に属する個数は $2$ か $0$ で偶数、これに $C$ の分の $1$ を足して $k(x)$ は奇数です。逆に $k(x)$ が奇数で $x \in C$ なら、$A$、$B$ に属する個数は偶数なので条件が成り立ちます。
• $x \notin C$ の場合：条件は $x \in A \bigtriangleup B$、すなわち $A$、$B$ に属する個数が $1$ です。$C$ の分は $0$ なので $k(x) = 1$ で奇数です。逆に $k(x)$ が奇数で $x \notin C$ なら、$A$、$B$ に属する個数は $k(x)$ 自身で奇数、しかも $2$ 以下なので $1$、よって条件が成り立ちます。

どちらの場合も同値が成り立つので、主張が示されました。

同じ議論を $A \bigtriangleup (B \bigtriangleup C)$ に適用します。補題を $A$ と $B \bigtriangleup C$ に適用すると、$x \in A \bigtriangleup (B \bigtriangleup C)$ は「$x \in A$」と「$x \in B \bigtriangleup C$」のちょうど一方が成り立つことです。$x \in A$ かどうかで場合分けします。

• $x \in A$ の場合：条件は $x \notin B \bigtriangleup C$、すなわち $B$、$C$ に属する個数が $2$ か $0$ で偶数。$A$ の分の $1$ を足して $k(x)$ は奇数です。逆も同様に成り立ちます。
• $x \notin A$ の場合：条件は $x \in B \bigtriangleup C$、すなわち $B$、$C$ に属する個数が $1$。$A$ の分は $0$ なので $k(x) = 1$ で奇数です。逆も同様です。

よって $x \in A \bigtriangleup (B \bigtriangleup C) \iff k(x)$ が奇数、も成り立ちます。

以上より、すべての $x \in U$ について

$$x \in (A \bigtriangleup B) \bigtriangleup C \iff k(x) \ \text{が奇数} \iff x \in A \bigtriangleup (B \bigtriangleup C)$$

が成り立つので、公理 3.2 により 2 つの集合は等しくなります。

参考文献

• 松坂和夫『集合・位相入門』岩波書店、1968 — 第 1 章「集合と写像」。日本語で書かれた入門書の定番で、集合演算の証明が丁寧です。
• 齋藤正彦『数学の基礎 — 集合・数・位相』東京大学出版会、2002 — 第 1 章。集合論から実数の構成へ進む流れが見通せます。
• 中島匠一『集合・写像・論理 — 数学の基本を学ぶ』共立出版、2012 — 論理式の読み書きと量化子の扱いに紙数を割いています。
• 前原昭二『記号論理入門』日本評論社、1967（新装版 2005）— 命題論理と述語論理を形式的に扱う標準的な入門書です。
• P. R. Halmos, Naive Set Theory, Van Nostrand, 1960 — 第 1 章から第 5 章。素朴集合論を公理的集合論へ橋渡しする短い古典です。

Appendix: よく使う同値変形の一覧

証明中に手が止まったときに参照してください。$P$、$Q$、$R$ は命題、$A$、$B$、$C$ は $U$ の部分集合とします。ただし最後の 2 行（量化子の否定）でのみ、$P$ は変域 $X$ 上の述語とします。左右はつねに同じ真理値をとる（集合の場合は等しい集合を表す）ことが、真理値表または元の追跡で確かめられます。

名前	論理の形	集合の形
二重否定	$\lnot \lnot P$ と $P$	$(A^{c})^{c} = A$
ド・モルガン	$\lnot(P \land Q)$ と $\lnot P \lor \lnot Q$	$(A \cap B)^{c} = A^{c} \cup B^{c}$
ド・モルガン	$\lnot(P \lor Q)$ と $\lnot P \land \lnot Q$	$(A \cup B)^{c} = A^{c} \cap B^{c}$
分配	$P \land (Q \lor R)$ と $(P \land Q) \lor (P \land R)$	$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
分配	$P \lor (Q \land R)$ と $(P \lor Q) \land (P \lor R)$	$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
吸収	$P \land (P \lor Q)$ と $P$	$A \cap (A \cup B) = A$
含意の展開	$P \implies Q$ と $\lnot P \lor Q$	$A \subseteq B$ と $A^{c} \cup B = U$
対偶	$P \implies Q$ と $\lnot Q \implies \lnot P$	$A \subseteq B$ と $B^{c} \subseteq A^{c}$
含意の否定	$\lnot(P \implies Q)$ と $P \land \lnot Q$	$A \nsubseteq B$ と $A \cap B^{c} \ne \emptyset$
量化子の否定	$\lnot \forall x\, P(x)$ と $\exists x\, \lnot P(x)$	—
量化子の否定	$\lnot \exists x\, P(x)$ と $\forall x\, \lnot P(x)$	—

このうち「吸収」だけは本文で扱っていないので、確かめ方を書いておきます。$x \in A \cap (A \cup B)$ なら $x \in A$ です（共通部分の定義の前半）。逆に $x \in A$ なら $x \in A \cup B$ でもあるので $x \in A \cap (A \cup B)$ です。よって 命題 3.4 により両者は等しくなります。