4.1 集合

形式的でない言い方をすれば、集合とは「モノ」の集まりである。集合を構成する「モノ」を、集合の要素 (element) と呼ぶ。集合の要素は何でも構わない: 数や空間内の点はもちろん、他の集合さえも集合の要素になれる。集合を表記するときは、要素をコンマで区切って並べて波括弧で囲う記法が慣習とされている。集合の例を示す:

この記法が使えるのは小さな有限集合だけである。それ以外の集合は、例えば要素を生成する規則を示す方法で表記される:

集合を表記するとき、要素の順序は意味を持たない。例えば \(\left\{x, y\right\}\) と \(\left\{y, x\right\}\) は同じ集合を表す異なる表記である。また、任意の「モノ」は集合に一度だけ含まれるか、全く含まれないかのどちらかである ── 集合に複数回含まれる要素という概念は存在しない¹。例えば \(\left\{x, x\right\}\) は \(x\) が集合の要素であると二回宣言しているだけで、\(\left\{x, x\right\} = \left\{x\right\}\) が成り立つ。

\(x \in S\) という表記は「\(x\) が集合 \(S\) の要素である」を意味する。例えば \(32 \in D\) と \(\text{青} \in B\) が成り立ち、さらに \(\text{Tailspin} \notin A\) が成り立つ ── 今のところは。

集合は単純かつ柔軟であり、あらゆるところで使われている。本書のほぼ全ての節で集合を見つけられるだろう。

4.1.1 頻繁に使われる集合

数学者は頻繁に使われる集合に対する特別な記号を考案している:

上付き添え字 \(+\) は集合を正の要素だけに制限する。例えば \(\mathbb{R}^{+}\) は正の実数全体の集合を表し、\(\mathbb{Z}^{+}\) は正の整数全体の集合を表す。同様に上付き添え字 \(-\) は集合を負の要素だけに制限する。

4.1.2 集合の比較と合成

記法 \(S \subseteq T\) は \(S\) が \(T\) の部分集合 (subset) である、つまり \(S\) の任意の要素が \(T\) の要素でもあることを表す。例えば任意の非負整数は整数なので \(\mathbb{N} \subseteq \mathbb{Z}\) が成り立ち、任意の有理数は実数なので \(\mathbb{Q} \subseteq \mathbb{R}\) が成り立つ。一方で実数でない複素数が存在する事実から \(\mathbb{C} \nsubseteq \mathbb{R}\) が分かる。

\(\subseteq\) の意味が覚えられない場合は、\(\subseteq\) を \(\leq\) だと思って、\(\subseteq\) が成り立つとき集合の要素数に関して \(\leq\) が成り立つと考えるとよい。なお、任意の整数 \(n\) で \(n \leq n\) が成り立つのと同様に、任意の集合 \(S\) で \(S \subseteq S\) が成り立つ。

「未満」を表す記号 \(<\) に対応する記号 \(\subset\) も存在する。\(S \subset T\) は \(S\) が \(T\) の部分集合であり、かつ \(S\) と \(T\) が等しくないことを意味する。任意の実数 \(n\) で \(n \nless n\) が成り立つのと同様に、任意の集合 \(S\) で \(S \not \subset S\) が成り立つ。\(S \subset T\) のとき \(S\) は \(T\) の狭義部分集合 (strict subset)と言う。狭義部分集合は真部分集合 (proper subset) とも呼ぶ。

集合を合成して新しい集合を作成する標準的な方法がいくつかある。例で使う集合 \(A\), \(B\) を最初に定めておく:

議論に登場する全ての集合が既知の議論領域 \(D\) の部分集合と暗黙に仮定される場合がよくある。このとき、\(D\) の部分集合 \(A\) に対して \(\overline{\mathstrut A}\) で \(D\) から \(A\) を除いた集合を表す。つまり、次のように定義される:

この集合 \(\overline{\mathstrut A}\) を \(A\) の補集合 (complement) と呼ぶ。次の関係が成り立つ:

例えば、議論領域が \(\mathbb{Z}\) のとき、\(\mathbb{N}\) の補集合は負の整数全体の集合である:

補集合を使うと \(A \subseteq B\) を等号だけで言い換えられる:

4.1.3 冪集合

集合 \(A\) の部分集合全体の集合を \(A\) の冪集合 (power set) と呼び、\(\operatorname{pow}(A)\) と表記する。つまり、次の関係が成り立つ:

例えば \(\operatorname{pow}(\left\{1, 2\right\})\) の要素は \(\varnothing\), \(\left\{1\right\}\), \(\left\{2\right\}\), \(\left\{1, 2\right\}\) である。

一般に、集合 \(A\) が \(n\) 個の要素を持つとき \(\operatorname{pow}(A)\) は \(2^{n}\) 個の要素を持つ (定理 4.5.5)。このため、\(\operatorname{pow}(A)\) を \(2^{A}\) と表記する著者もいる。

4.1.4 集合の内包表記

述語の重要な用途の一つに集合の内包表記 (set builder notation) がある。明示的な要素の列挙や和集合・共通部分などで表現するのが難しい集合を扱うとき、集合の内包表記が役に立つ。「要素が満たす述語で集合を定義する」が基本的なアイデアであり、述語が真になる全ての値全体の集合が表現される。集合の内包表記の例を示す:

例えば、集合 \(A\) は次の述語が真になる非負整数 \(n\) 全体の集合である:

\(A\) の要素を小さいものから並べると

となる。\(A\) の要素を並べることで \(A\) を定義しようとしても上手く行かない: 最初の \(10\) 項を並べたとしても、そのパターンは正確に記述されない。同様に、集合 \(B\) は次の述語が真になる実数 \(x\) 全体の集合である:

\(B\) の要素は三次方程式を解かないと明示的に列挙できない。集合 \(C\) は次の述語が真になる複素数 \(a + bi\) 全体の集合である:

これは複素数平面において原点中心の楕円の内側を表す。最後に、集合 \(D\) の要素は巻末の参考文献リストから論文を取り除くと得られる。

4.1.5 集合の等価性の証明

二つの集合が等しいとは、ちょうど同じ要素を持つことを言う。つまり、\(X = Y\) は \(z \in X \ \ \longleftrightarrow \ \ z \in Y\) が任意の \(z\) で成り立つことを意味する²。このため、集合の等価性は同値性の証明と同じように証明できる。例を示す:

証明 等式 \(\text{(4.1)}\) は全ての \(z\) で次の関係が成り立つという命題と同値である:

これから関係 \(\text{(4.2)}\) を同値変形で示す。

■

集合の等価性を示す方法は当然ながら多くある。ただ、ここでは同値変形を使う上記のアプローチを強調しておく。なぜなら、これは一般的な手法の特殊ケースと言えるからである: \(\,\cup\) (和集合)、\(\cap\) (共通部分)、\(-\) (差集合)、そして補集合が絡む集合の等価性は命題論理式の恒真性に変換でき、その証明は自動化できる。命題論理式の恒真性は例えば真理値表や代数的手法で機械的に検証できることを思い出してほしい。

もう一つ例を示す。命題論理式に対する Deド Morganモルガン の法則 \(\text{(3.14)}\) は次の関係だった:

問題 4.5 で見るように、集合の等価性に関しても同様の関係を導ける:

実は、集合の等価性が恒真でないとき、同値変形のアプローチを使うと単純な反例を作成できる (問題 4.10)。

命題論理式と集合にはこういった対応関係があるものの、両者に対する演算を混同しないように注意する必要がある。例えば \(X\) と \(Y\) が集合のとき「\(X \ \operatorname{\text{\footnotesize AND}} \ Y\)」は意味を持たず、「\(X \cap Y\)」と書かなければならない。\(\operatorname{\text{\footnotesize AND}}\) の引数は真理値であって集合ではないので、\(\operatorname{\text{\footnotesize AND}}\) に集合を渡すとコンパイラ ── そして答案の採点者 ── が型エラーを送出する。同様に、\(P\) と \(Q\) が命題論理式のとき「\(P \cup Q\)」は型エラーであり、「\(P \ \operatorname{\text{\footnotesize OR}}\ Q\)」と書かなければならない。