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

> 集合の元・部分集合・べき集合、和集合と共通部分と補集合を定義から厳密に扱い、真理値表による命題論理、全称記号と存在記号の否定規則、必要条件と十分条件までを、ド・モルガンの法則の証明を軸に整理する。
> https://rikai.mugen-giken.com/mathematics/foundations/sets-and-logic

## 0. この記事の要点

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

## 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. 「どんな実数にも、それより大きい実数がある」と「どんな実数よりも大きい実数がある」は、記号で書くとどこが違うのか。

<Aside type="note">
この記事は全 6 章の第 1 章です。ここで整えた言葉づかいは、以降のすべての章で使います。証明の型（背理法・数学的帰納法・対偶論法）そのものは [証明の技術](/mathematics/foundations/proof-techniques)（<Ref to="mathematics/foundations/proof-techniques#thm-induction" text="数学的帰納法の原理" />、<Ref to="mathematics/foundations/proof-techniques#prop-contradiction" text="背理法の正当性" />）で、無限集合の大小は [濃度と無限](/mathematics/foundations/cardinality-and-infinity) で扱います。
</Aside>

## 2. 命題と論理結合子

### 2.1. 命題

<Definition id="def-proposition" title="命題">

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

</Definition>

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

<Remark id="rem-proposition-informal">

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

</Remark>

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

<Definition id="def-connectives" title="論理結合子">

命題 $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 |

</Definition>

この表が定義そのものです。つまり結合子の意味は「日常語のニュアンス」ではなく、この 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$ が成り立たない、という事態は起きない」ことだけを主張する記号だと読んでください。実際 <Ref to="prop-implication-forms" /> が示すとおり、$P \implies Q$ は $\lnot(P \land \lnot Q)$ と同じ意味です。この読み方を採用すると、「該当するものが 1 つもないとき、その全員についての主張は真」という便利な規約が自動的に手に入ります（<Ref to="prop-empty-subset" />）。

<Proposition id="prop-implication-forms" title="含意の言い換え">

任意の命題 $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$ もつねに同じ真理値をとります。

</Proposition>

<Proof of="prop-implication-forms">

<Ref to="def-connectives" /> の表に従って、$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 行すべてで一致しています。

</Proof>

対偶が使えることは、証明の実務でそのまま効きます。「$n^2$ が偶数ならば $n$ は偶数」を直接示すのは面倒ですが、対偶「$n$ が奇数ならば $n^2$ は奇数」なら $n = 2k+1$ と置いて $n^2 = 4k^2 + 4k + 1 = 2(2k^2+2k)+1$ と計算するだけで済みます（この補題が $\sqrt{2}$ の無理性の証明でどう使われるかは <Ref to="mathematics/foundations/proof-techniques#lem-even-square" text="平方が偶数なら元も偶数" /> を参照）。

<Example id="ex-converse" title="逆・裏・対偶">

$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$ は偽なので、<Ref to="def-connectives" /> の表の 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$ ではありえません。これは <Ref to="prop-implication-forms" /> が保証するとおり、$P \implies Q$ が真であることと同じです。

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

</Example>

## 3. 集合の基本概念

### 3.1. 元と外延性

<Definition id="def-set" title="集合と元">

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

</Definition>

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

<Axiom id="ax-extensionality" title="外延性の原理">

集合 $A$、$B$ に対し、
$$
A = B \iff \forall x\,(x \in A \iff x \in B)
$$
と定めます。すなわち、集合は「どの元を持つか」だけで決まります。

</Axiom>

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

<Definition id="def-subset" title="部分集合">

集合 $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$ と書きます。

</Definition>

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

<Proposition id="prop-double-inclusion" title="集合の相等は二重包含">

集合 $A$、$B$ に対し
$$
A = B \iff (A \subseteq B \ \text{かつ}\ B \subseteq A)
$$
が成り立ちます。

</Proposition>

<Proof of="prop-double-inclusion">

<Ref to="ax-extensionality" /> により、$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$ とおいて <Ref to="def-connectives" /> の表を見ると、$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$」と同値です。<Ref to="def-subset" /> によりこれは $A \subseteq B$ かつ $B \subseteq A$ に他なりません。

</Proof>

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

### 3.2. 空集合とべき集合

<Definition id="def-empty-powerset" title="空集合・べき集合">

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

集合 $A$ に対し、$A$ の部分集合全体からなる集合
$$
\mathcal{P}(A) = \{X \mid X \subseteq A\}
$$
を $A$ の**べき集合**といいます。

</Definition>

<Proposition id="prop-empty-subset" title="空集合の基本性質">

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

</Proposition>

<Proof of="prop-empty-subset">

(1) <Ref to="def-subset" /> により、示すべきは「すべての $x$ について $x \in \emptyset \implies x \in A$」です。$x$ を任意にとると、<Ref to="def-empty-powerset" /> により $x \in \emptyset$ は偽です。<Ref to="def-connectives" /> の表を見ると、前件が 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$ もつねに真だからです。<Ref to="prop-double-inclusion" /> により $E = E'$ です。

</Proof>

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

<Example id="ex-powerset" title="べき集合を書き下す">

$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$ が含まれるのは <Ref to="prop-empty-subset" /> の (1) による、$A$ 自身が含まれるのは $A \subseteq A$ による、という点に注意してください。

</Example>

<Theorem id="thm-powerset-card" title="べき集合の元の個数">

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

</Theorem>

<Proof of="thm-powerset-card">

$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$ のいずれか一方が成り立つので（<Ref to="def-set" />）、$\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$ が成り立ち、<Ref to="ax-extensionality" /> から $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}$ 個です。

</Proof>

<Remark id="rem-powerset-infinite">

$A$ が無限集合のときも $\mathcal{P}(A)$ は $A$ より「真に大きい」ことが証明できます（<Ref to="mathematics/foundations/cardinality-and-infinity#thm-cantor-power" text="カントールの定理" />）。有限の場合の $2^n > n$ に対応する主張ですが、証明は数え上げではなく対角線論法によります。詳しくは [濃度と無限](/mathematics/foundations/cardinality-and-infinity) を参照してください。また、$n$ についての数学的帰納法による <Ref to="thm-powerset-card" /> の別証明は [証明の技術](/mathematics/foundations/proof-techniques) の例として扱います。

</Remark>

## 4. 集合の演算

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

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

<Definition id="def-operations" title="和集合・共通部分・差集合・補集合">

$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$ は**互いに素**であるといいます。

</Definition>

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

| 集合の側 | $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 つ手に入ります。以下ではその手順を実際に踏みます。

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

<svg viewBox="0 0 480 270" width="100%" role="img" aria-label="全体集合の長方形の中に 2 つの円 A と B が重なって描かれ、4 つの領域に番号が振られたベン図">
  <rect x="10" y="10" width="460" height="250" rx="10" fill="none" stroke="currentColor" stroke-width="1.5" />
  <text x="26" y="34" fill="currentColor" font-size="17" font-style="italic">U</text>
  <circle cx="190" cy="140" r="95" fill="var(--sl-color-accent)" fill-opacity="0.10" stroke="currentColor" stroke-width="1.5" />
  <circle cx="290" cy="140" r="95" fill="var(--sl-color-accent)" fill-opacity="0.10" stroke="currentColor" stroke-width="1.5" />
  <text x="135" y="78" fill="currentColor" font-size="18" font-style="italic" text-anchor="middle">A</text>
  <text x="345" y="78" fill="currentColor" font-size="18" font-style="italic" text-anchor="middle">B</text>
  <text x="152" y="148" fill="currentColor" font-size="19" text-anchor="middle">①</text>
  <text x="240" y="148" fill="currentColor" font-size="19" text-anchor="middle">②</text>
  <text x="328" y="148" fill="currentColor" font-size="19" text-anchor="middle">③</text>
  <text x="58" y="60" fill="currentColor" font-size="19" text-anchor="middle">④</text>
</svg>

</Figure>

図の 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 つに属します。

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

### 4.2. 分配法則

<Theorem id="thm-distributive" title="分配法則">

$A, B, C \subseteq U$ に対し
$$
A \cap (B \cup C) = (A \cap B) \cup (A \cap C)
$$
が成り立ちます。

</Theorem>

<Proof of="thm-distributive">

<Ref to="prop-double-inclusion" /> により、2 つの包含を示します。

（$\subseteq$）$x \in A \cap (B \cup C)$ とします。<Ref to="def-operations" /> より $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 つの包含が示されたので、<Ref to="prop-double-inclusion" /> により等号が成り立ちます。

</Proof>

もう一方の分配法則 $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ も同じ型で示せます。手を動かして確かめるために、<Ref to="exr-distributive" /> に回しました。

### 4.3. ド・モルガンの法則

<Lemma id="lem-demorgan-logic" title="ド・モルガンの法則（命題論理版）">

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

</Lemma>

<Proof of="lem-demorgan-logic">

<Ref to="def-connectives" /> の表に従って 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 行すべてで一致しました。

</Proof>

<Theorem id="thm-demorgan" title="ド・モルガンの法則（集合版）">

$A, B \subseteq U$ に対し
$$
(A \cup B)^{c} = A^{c} \cap B^{c}, \qquad (A \cap B)^{c} = A^{c} \cup B^{c}
$$
が成り立ちます。

</Theorem>

<Proof of="thm-demorgan">

前半を示します。$x \in U$ を任意にとり、$P$ を命題「$x \in A$」、$Q$ を命題「$x \in B$」とおきます。<Ref to="def-operations" /> の各定義と、4 行目で <Ref to="lem-demorgan-logic" /> を使うと、次の同値が順に成り立ちます。

$$
\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}$ が成り立つので、<Ref to="ax-extensionality" /> により $(A \cup B)^{c} = A^{c} \cap B^{c}$ です。

後半も同様の鎖で示せます。$x \in (A \cap B)^{c} \iff \lnot(P \land Q)$ であり、<Ref to="lem-demorgan-logic" /> の後半より $\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}$ です。よって <Ref to="ax-extensionality" /> から $(A \cap B)^{c} = A^{c} \cup B^{c}$ を得ます。

</Proof>

<Ref to="thm-demorgan" /> の前半は、<Ref to="def-operations" /> のあとの図の 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$ を覆い尽くしていることが、この確認が証明になるための条件です。

<Example id="ex-demorgan-concrete" title="具体的な集合で確かめる">

$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$ です。

</Example>

<Remark id="rem-difference-not-associative">

すべての演算が数の四則と同じ性質を持つわけではありません。差集合は結合法則を満たしません。$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$ もそうだろう」という類推は、ここで壊れます。

</Remark>

## 5. 述語と量化子

### 5.1. 述語

<Definition id="def-predicate" title="述語">

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

</Definition>

「$x + 1 = 3$」は、変域を $\mathbb{N}$ と決めれば $\mathbb{N}$ 上の述語です。$P(2)$ は真、$P(5)$ は偽、というように、$x$ に値を代入してはじめて真偽が決まります。変域を明示しないと真偽が変わることに注意してください。「$x^2 = 2$ を満たす $x$ が存在する」は変域が $\mathbb{Q}$ なら偽（<Ref to="mathematics/foundations/proof-techniques#thm-sqrt2" text="平方根 2 の無理性" />）、$\mathbb{R}$ なら真です（<Ref to="mathematics/foundations/what-is-a-number#thm-sqrt2-exists" text="√2 の存在" />）。

<Definition id="def-quantifiers" title="全称記号と存在記号">

$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$ を**存在記号**といい、まとめて**量化子**といいます。

</Definition>

変域が空のときの値を確認しておきます。$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$ が存在しません。これが <Ref to="prop-empty-subset" /> で見た「空虚に真」の言い換えです。

### 5.2. 否定の作り方

<Theorem id="thm-quantifier-negation" title="量化子の否定">

$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)
$$
が成り立ちます。

</Theorem>

<Proof of="thm-quantifier-negation">

前半を示します。

（$\Longrightarrow$）$\lnot(\forall x \in X, P(x))$ が真であるとします。ここで、結論 $\exists x \in X,\ \lnot P(x)$ が偽であると仮定して矛盾を導きます。$\exists x \in X,\ \lnot P(x)$ が偽であるとは、<Ref to="def-quantifiers" /> により、$\lnot P(a)$ を真にする $a \in X$ が 1 つも存在しないということです。すると、どの $a \in X$ についても $\lnot P(a)$ は偽、すなわち $P(a)$ は真です。これは <Ref to="def-quantifiers" /> により $\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)$ は同じ真理値をとるので（<Ref to="def-connectives" /> の表で $\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))$ となります。

</Proof>

この定理と <Ref to="prop-implication-forms" /> の最後の主張（$\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$ に置き換える（<Ref to="lem-demorgan-logic" />）。
3. $\lnot(P \implies Q)$ は $P \land \lnot Q$ に置き換える（<Ref to="prop-implication-forms" />）。

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

<Mermaid code={`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 )"]`} />

</Figure>

<Example id="ex-negate-continuity" title="連続性の定義を否定する">

実数値関数 $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 段では <Ref to="thm-quantifier-negation" /> を、最後の 1 段では <Ref to="prop-implication-forms" /> を使います。

$$
\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$ で連続ではありません。

</Example>

### 5.3. 量化子の順序

<Remark id="rem-quantifier-order" title="順序を入れ替えてはいけない">

$\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$ は成り立ちません。<Ref to="thm-quantifier-negation" /> を使えば、この否定が $\forall y,\ \exists x,\ y \le x$ であり、$x = y$ が実際に条件を満たすことで確認できます。

<Ref to="ex-negate-continuity" /> の連続性でも同じことが起きています。連続性では $\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 か所の違いが、まったく別の概念を生みます。

</Remark>

### 5.4. 集合族への一般化

<Corollary id="cor-demorgan-family" title="ド・モルガンの法則（集合族版）">

$\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}
$$
が成り立ちます。

</Corollary>

<Proof of="cor-demorgan-family">

前半を示します。$x \in U$ を任意にとります。2 行目で <Ref to="thm-quantifier-negation" /> の後半（$\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$ で同値なので、<Ref to="ax-extensionality" /> により両辺は等しくなります。後半は、同じ鎖の 2 行目で <Ref to="thm-quantifier-negation" /> の前半（$\lnot \forall$ が $\exists \lnot$ になる方）を使えば得られます。

</Proof>

$\Lambda$ が 2 元集合のときが <Ref to="thm-demorgan" /> です。つまり <Ref to="lem-demorgan-logic" />、<Ref to="thm-demorgan" />、<Ref to="cor-demorgan-family" /> は同じ規則の 3 つの現れ方で、「否定は $\land$ と $\lor$ を、$\forall$ と $\exists$ を、$\cap$ と $\cup$ を入れ替える」という 1 文にまとまります。

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

<Definition id="def-necessary-sufficient" title="必要条件と十分条件">

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

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

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

</Definition>

覚え方は「矢印の出る側が十分、入る側が必要」です。$P$ さえ言えれば $Q$ が言えるので $P$ は「十分」、$Q$ が成り立たなければ $P$ もありえない（対偶、<Ref to="prop-implication-forms" />）ので $Q$ は「必要」、と読みます。

<Example id="ex-necessary-sufficient" title="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$ という条件を**強い**ものとして扱っていることに注意してください。強い条件（満たす数が少ない条件）が十分条件、弱い条件（満たす数が多い条件）が必要条件です。次の命題がこの直感を正確にします。

</Example>

<Proposition id="prop-truth-set" title="真理集合と論理の対応">

$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}
$$

</Proposition>

<Proof of="prop-truth-set">

(1) <Ref to="def-subset" /> により、$[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)$ が真」であり（<Ref to="def-connectives" />）、これは $x \in [P]$ かつ $x \in [Q]$、すなわち $x \in [P] \cap [Q]$ と同値です（<Ref to="def-operations" />）。すべての $x \in X$ で同値なので、<Ref to="ax-extensionality" /> により $[P \land Q] = [P] \cap [Q]$ です。$\lor$ と $\lnot$ についても、$\lor$ が $\cup$ の、$\lnot$ が補集合の定義そのものであることから、まったく同じ手順で示せます。

</Proof>

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

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

<Remark id="rem-russell" title="素朴集合論の限界">

<Ref to="def-set" /> のように「条件を書けば集合が作れる」と考えると、破綻します。条件「$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$ を明示してきたのはそのためです。公理系そのものが何を保証し何を保証しないかという問いは、[不完全性定理](/mathematics/foundations/incompleteness-theorems)（<Ref to="mathematics/foundations/incompleteness-theorems#thm-first" text="第一不完全性定理" />）につながります。また「$0.999\ldots = 1$」のような等式が、記号の意味をどこまで遡って定義すれば決着するのかは、[数とは何か](/mathematics/foundations/what-is-a-number) で扱います。

</Remark>

## 7. 演習

<Exercise id="exr-powerset-empty" difficulty="易">

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

(1) $\mathcal{P}(A)$ を書き下し、元の個数が <Ref to="thm-powerset-card" /> と合うことを確かめてください。<br />
(2) 次の 4 つの主張の真偽を、理由を付けて答えてください。$\emptyset \in A$、$\emptyset \subseteq A$、$\{\emptyset\} \in A$、$\{\emptyset\} \subseteq A$。

<Solution>

(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}$ 個で <Ref to="thm-powerset-card" /> と合致します。

(2)

- $\emptyset \in A$ は**真**です。$A$ の元として $\emptyset$ が挙げられているからです。
- $\emptyset \subseteq A$ は**真**です。<Ref to="prop-empty-subset" /> の (1) により、空集合は任意の集合の部分集合です。
- $\{\emptyset\} \in A$ は**真**です。$A$ の 2 つ目の元が $\{\emptyset\}$ だからです。
- $\{\emptyset\} \subseteq A$ は**真**です。$\{\emptyset\}$ の元は $\emptyset$ だけであり、$\emptyset \in A$ が成り立つので、<Ref to="def-subset" /> の条件が満たされます。

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

</Solution>

</Exercise>

<Exercise id="exr-distributive" difficulty="標準">

$A, B, C \subseteq U$ に対し
$$
A \cup (B \cap C) = (A \cup B) \cap (A \cup C)
$$
を、元の追跡によって証明してください。

<Solution>

<Ref to="prop-double-inclusion" /> に従い、2 つの包含を示します。

（$\subseteq$）$x \in A \cup (B \cap C)$ とします。<Ref to="def-operations" /> より、$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 つの包含から、<Ref to="prop-double-inclusion" /> により等号が成り立ちます。

</Solution>

</Exercise>

<Exercise id="exr-negate-convergence" difficulty="標準">

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

<Solution>

(1) <Ref to="thm-quantifier-negation" /> を 3 回、続いて <Ref to="prop-implication-forms" /> を 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$ も任意だったので、この数列はどんな実数にも収束しません。

</Solution>

</Exercise>

<Exercise id="exr-symmetric-difference" difficulty="難">

$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)
$$
が成り立つことを示してください。

<Solution>

まず補題として、$x \in U$ に対し
$$
x \in A \bigtriangleup B \iff \text{「$x \in A$」と「$x \in B$」のちょうど一方が成り立つ}
$$
を示します。<Ref to="def-operations" /> により $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)
$$
が成り立つので、<Ref to="ax-extensionality" /> により 2 つの集合は等しくなります。

</Solution>

</Exercise>

## 参考文献

- 松坂和夫『集合・位相入門』岩波書店、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)$ です。よって <Ref to="prop-double-inclusion" /> により両者は等しくなります。