今、シリーズでオートマトンと言語に関する話を書いている。
初回は以下だ。
さて、ここで集合だったり論理だったりをガンガン使っている。
しかし、そのあたりが不安な方もいらっしゃるのではないだろうか。
特に、文系の方だとこのあたりはそもそも習ったかどうか、という感じだと思う。
ということで、今回はまず集合について、改めて解説をしていこう。
分かってしまえばそんな複雑なことはないので、一個一個確実に理解しながら進めていこう。
今回の解説のために、やはり押し入れから参考書を引っ張り出してきた。
以下の本だ。
今回は第一章の「離散集合」という部分を解説していくことになる。
なお、この本は今回の集合や次回の論理、次々回の写像以外にも色々な内容が掲載されている。
完全に余談ではあるが、この本の10章以降に載っているグラフ構造は非常に面白いので、気になる人は是非勉強してみて欲しい。
先にお断り
さて、いきなりではあるが、これまで本シリーズで扱っていた集合は、全て離散集合というものだ。
ということは、離散でない集合も存在する、ということになる…が、このあたりはオートマトンや形式言語の理解には不要な知識なので、今回は省略させてもらう。
ここからは、単に集合といったら、全てこの離散集合を表していると思っていただきたい。
もう一つ、今書いた通りだが、本記事の目的は、本編であるオートマトンや形式言語の内容を理解できるだけの知識を身に付けてもらうこと。
そのため、本編で使っていない内容は省くこともあるので、そこはご了承願いたい。
もし、個別で集合に関して勉強したい場合は、上の参考書か、あるいはネット検索で知識を補いながら進めてもらいたい。
ということで、内容に入っていこう。
集合の定義
さて、そもそも集合とは何だろうか。
こう改めて聞かれると非常に説明が難しいが…非常に大雑把に、誤解を恐れずに言うと、モノの集まりのことだ。
このモノのことを元や要素などと呼ぶが、本シリーズでは基本的に全て要素という呼び方をしている。
先にイメージを掴んでもらいたいので、書き方や具体例を説明してから厳密な定義を紹介しよう。
書き方は、まず要素をコンマ区切りで並べる。
そして、それを中括弧で囲めば完成だ。
例えば、数字の1から5を要素に持つ集合は…
$$\{1, 2, 3, 4, 5\}$$
という書き方になる。
この要素には、数字以外にも記号や、他の集合を含めることもできる。
そのため…
$$\{+, -, \times, /\}$$
$$\{\{1, 2\}, \{2, 5\}\}$$
これらも立派な集合だ。
さて、このような記法にも実は名前がついている。
要素をコンマ区切りで列挙するような書き方を外延的定義という。
この外延的定義は要素が明確に示されるので、何を要素として持つかが非常に分かりやすい。
しかし、例えばこれが100個とか、あるいは無限になってしまったら、どうすればいいのだろうか。
法則性が明らかであれば、その法則が分かるまで明示し、その後は点3つで省略することもできる。
しかし、それだと誤解を生んでしまう可能性もある。
そこで、もう一つ、内包的定義という書き方が用意されている。
これは、要素の条件を明記する書き方で、その条件を満たすもの全てがその集合に含まれることになる。
集合の中括弧内を縦棒で区切り、左側に要素を、右側にその要素が集合に属するための条件を書く。
例えば、上の例で出した集合\(\{1, 2, 3, 4, 5\}\)を内包的定義で書き直すと…
$$\{n | n \mbox{は自然数、かつ} 1 \leq n \leq 5\}$$
といった書き方になる。
あるいは、この「かつ」というように、複数の条件を列挙して、それら全てを満たすものを集合に含める場合は、コンマでその条件を書き並べることも多い。
$$\{n | n \mbox{は自然数}, 1 \leq n \leq 5\}$$
こちらはどんな要素数だろうと条件が明確なので、誤解を生むことなく集合を定義できるのがメリットだろう。
しかし、今回出した例のように、外延的定義の方が分かりやすい場合もある。
これらは状況によってどちらが適しているかがコロコロ変わるので、両方使えるようにしておきたい。
では、集合を厳密に定義していこう。
現在関心がある全体を、ドメインや関心領域と呼ぶ。
その中で、以下の2条件を満たす一部分のことを集合と呼ぶ。
- ある対象(=要素)が、その集合に属するかどうかが明確に判断できる
- 集合に属する2つの対象(=要素)が、同一のものか明確に判断できる
こう書くと難しそうだが、要するに条件1は、集合に含まれるor含まれないが明確に分かること、条件2は同じ要素がただ一つしか含まれないことを表している。
そして、条件1は暗に、集合内の順番は無視できることも表現している。
同じ要素がただ一つしか含まれない、というのはちょっと拡張して、同じ要素が複数個入っていても一つと見なすとしよう。
例えば…
$$\{n | n \mbox{は100以下の自然数}\}$$
これは、明確にどんな要素が入るか分かるので、集合だ。
それに対し…
$$\{n | n \mbox{は小さい自然数}\}$$
これは、小さいというのが具体的にいくつ以下なのかがわからないので、集合ではない。
そして、以下の集合は両方とも\(\{1, 2, 3, 4, 5\}\)と同じ集合を表している。
$$\{1, 1, 2, 3, 4, 5, 5\}$$
$$\{5, 4, 3, 2, 1\}$$
これが、集合の定義だ。
この集合も、通常の数と同じように変数で表すことができるが、通常は大文字を使うことが多い。
その中に含まれる要素は小文字の場合が多いので、それも覚えておこう。
集合と要素の関係
しばらく定義が続く。
ある要素\(a\)が、集合\(A\)に含まれることを、以下のように表記する。
$$a \in A$$
逆に含まれないときは、この記号に斜線を一本引いて…
$$a \not \in A$$
と書く。
そして、この集合\(A\)に含まれる要素の数を要素数といい、縦棒でその集合を挟むことで表現する。
これらを、幾つか具体例で見てみよう。
$$1 \in \{1, 2, 3, 4, 5\}$$
$$6 \not \in \{1, 2, 3, 4, 5\}$$
$$|\{1, 2, 3, 4, 5\}| = 5$$
こんな感じだ。
この要素数が有限であるような集合を有限集合と呼び、逆に要素数が無限の集合のことを無限集合と呼ぶ。
ここまで具体例を出した集合は、全て有限集合だ。
無限集合の例は、まず自然数や整数全体がそうだ。
他にも…
$$\{2n | n \mbox{は自然数}\}$$
これは正の2の倍数を集めた集合だが、これも無限集合になる。
…無限集合も首を突っ込むと非常に奥が深いが、今回は横道に逸れることになるので名前の紹介だけにしておこう。
ここからの話は、基本的に有限、無限に関わらない話になる。
もし区別する必要がある場合は、そのことを明記することにしよう。
空集合
要素数に関して、特別な集合がある。
要素数が0であるような集合を、空集合と呼ぶ。
これは要素を持たない集合で、表記は色々あるが、本シリーズでは\(\phi\)で統一している。
$$\phi = \{\}, |\phi| = 0$$
これも有限集合の一つだ。
集合同士の関係
ここからは、集合同士の関係について見ていこう。
まずは、部分集合というやつだ。
今、二つの集合\(A, B\)があったとする。
このとき、集合\(A\)の全ての要素\(a\)について、それが\(B\)の要素になっているとき、\(A\)を\(B\)の部分集合といい、以下のように書く。
$$A \subset B$$
このとき、\(B\)に\(b \not \in A\)となる要素が含まれているとき、それを強調して真部分集合と呼ぶ場合もある。
例を挙げると、以下のような感じ。
$$\{1, 3, 5\} \subset \{1, 2, 3, 4, 5\}$$
一つ補足で、空集合\(\phi\)は任意の集合の部分集合だ。
もう一つ、\(A\)を有限集合に限定すると、常に以下の式が成り立つ。
$$|A| \leq |B|$$
無限集合の場合は、これが成り立つとは限らないので注意しておこう。
次に、集合が等しいという関係。
二つの集合\(A, B\)について、\(A\)が\(B\)の部分集合、かつ\(B\)が\(A\)の部分集合であるとき、またその時に限って、\(A\)と\(B\)は等しいといい、単にイコールで表記する。
$$A = B$$
言葉で説明すると、両方に属する要素が完全に一致するとき、等しいと呼ぶのだ。
こちらは、その集合が有限であるか無限であるかに関わらず、以下が成立する。
$$|A| = |B|$$
集合がイコールなら、それらの要素数が等しいのだ。
しかし、要素数が等しいからといって、イコールであるとは限らないので、そこは気を付けよう。
ここで注意。
以下の二つの集合は、イコールではない。
$$\{1, 2, 3, 4, 5\}$$
$$\{\{1, 2, 3, 4, 5\}\}$$
上は、数字の1から5を要素に持つ集合だ。
それに対し、下は一つの集合を要素に持つ集合であり、その要素が1から5の数字、という意味だ。
なお、上の集合は下の集合の要素ではある。
つまり、関係を書くなら以下のようになる。
$$\{1, 2, 3, 4, 5\} \in \{\{1, 2, 3, 4, 5\}\}$$
ここは最初間違えやすいと思うので、気を付けておいて欲しい。
べき集合
本編でも出していた、べき集合を解説していこう。
集合\(A\)の全ての部分集合を要素とする集合のことを\(A\)のべき集合といい、本シリーズでは\(2^A\)と表記している。
例えば、\(A = \{1, 2, 3\}\)の時は…
$$\begin{eqnarray}
2^A = & \{ & \\
& & \phi, \{1\}, \{2\}, \{3\}, \\
& & \{1, 2\}, \{1, 3\}, \{2, 3\}, \\
& & \{1, 2, 3\} \\
& \} &
\end{eqnarray}$$
といった感じだ。
ちなみに、任意の有限集合\(A\)のべき集合\(2^A\)の要素数について、以下の式が成り立つ。
$$|2^A| = 2^{|A|}$$
これは簡単に証明できるが、ここではやらないので是非チャレンジしてみよう。
ちなみに、これまで使っていなかったが、集合を要素に持つ集合のことを、集合族と呼んだりする。
べき集合も、集合族の一種だ。
集合の演算
集合同士にも、演算を幾つか考えることができる。
ここでは5つほど紹介しよう。
和集合
二つの集合\(A\)、\(B\)のいずれか、もしくは両方に含まれる要素を集めて作られる新しい集合を、\(A\)と\(B\)の和集合と呼ぶ。
記号は、\(\cup\)というやつを使う。
$$A \cup B = \{x | x \in A \mbox{または} x \in B\}$$
共通部分
二つの集合\(A\)、\(B\)の両方に含まれる要素を集めて作られる新しい集合を、\(A\)と\(B\)の共通部分と呼ぶ。
こちらは、上の和集合の記号を上下ひっくり返して、\(\cap\)という記号だ。
$$A \cap B = \{x | x \in A, x \in B\}$$
補集合
集合を考えるとき、よく全体集合\(U\)を決めておいて、その部分集合として注目する集合\(A\)といった考え方をする。
このとき、全体集合のうち、\(A\)に含まれない要素を集めたものを、\(A\)の補集合と呼び、\(A\)の上に横棒を書いて表記する。
$$\overline{A} = \{x | x \in U, x \not \in A\}$$
差集合
二つの集合\(A\)、\(B\)について、\(A\)には含まれるが\(B\)には含まれないような要素を集めた集合を、差集合と呼ぶ。
これには書き方が複数ある。
$$A – B = \{x | x \in A, x \not \in B\}$$
$$A \setminus B = \{x | x \in A, x \not \in B\}$$
本シリーズでは両方使っているが、どちらも表しているものは同じだ。
順序対と直積
ちょっと補足で、ここは参考書と順番を変えている。
二つの要素\(a, b\)を小括弧で括ったもの\((a, b)\)を、順序対や2項組と呼ぶ。
本シリーズでは、単に組と呼ぶ場合が多い。
これは集合ではないので、同じ要素の組を考えることができるし、これらの順番を入れ替えたものもそれぞれ別の組として考えることができる。
イメージは、平面座標が適しているだろう。
平面座標上では、同じ数字の組でももちろん点をプロットすることができるし、順番を入れ替えると異なる点をプロットすることになる。
さて、直積とは、二つの集合からこの組を作り出し、それを要素とする新しい集合を作り出す演算、あるいはそれによってできた集合のことだ。
書き方は、通常の数の掛け算の記号を使う。
$$A \times B = \{(a, b) | a \in A, b \in B\}$$
これも具体例を出しておこう。
\(A = \{1, 2, 3\}\)、\(B = \{1, 3, 5\}\)として、\(A \times B\)を具体的に書くと以下の通りだ。
$$\begin{eqnarray}
A \times B = & \{ & \\
& & (1, 1), (1, 3), (1, 5), \\
& & (2, 1), (2, 3), (2, 5), \\
& & (3, 1), (3, 3), (3, 5) \\
& \} &
\end{eqnarray}$$
これについても、有限集合の場合は要素数について以下が成り立つ。
$$|A \times B| = |A| \times |B|$$
また、\(A\)自身との直積は、\(A^2\)と表記するので、これも覚えておこう。
なお、今回は2つで考えたが、三つ以上になっても同じ考え方だ。
集合の性質
参考書には幾つか集合や集合演算に関する性質が記載されているが、本編にはあまり関わりがない。
そのため、ざっと出して終わりにさせてもらおう。
まず、部分集合に関する性質。
集合\(A\)について、\(A \subset A\)。
三つの集合\(A, B, C\)に対して、\(A \subset B\)かつ\(B \subset C\)なら\(A \subset C\)が成り立つ。
これらが成り立つことは明らかだろう。
ちなみに、三つの関係については、推移律という名前がついている。
次に、集合演算の性質。
\(U\)を全体集合、\(A \subset U\)を集合、\(\phi\)を空集合とする。
このとき、以下三つが成り立つ。
- \(A \cup \phi = A, A \cap \phi = \phi\)
- \(A \cup U = U, A \cap U = A\)
- \(\overline{U} = \phi, \overline{\phi} = U\)
また、三つの集合\(A, B, C\)について、以下の分配法則が成り立つ。
- \(A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\)
- \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\)
そして、有名なド・モルガン律。
- \(\overline{A \cup B} = \overline{A} \cap \overline{B}\)
- \(\overline{A \cap B} = \overline{A} \cup \overline{B}\)
最後、5つほど。
- \(A \cup B = B \cup A, A \cap B = B \cap A\)
- \(A \cup (B \cup C) = (A \cup B) \cup C\)
\(A \cap (B \cap C) = (A \cap B) \cap C\) - \(A \cup (A \cap B) = A, A \cap (A \cup B) = A\)
- \(A \cup A = A, A \cap A = A\)
- \(\overline{\overline{A}} = A\)
上から順に交換律、結合律、吸収律、べき等律、対合律(二重否定)だ。
おわりに
今回は、ちょっと基礎に立ち戻って集合を解説した。
一部省略した部分や順番を変えた部分があるが、冒頭にも書いた通り、今回の目的は本編の内容が理解できる程度の知識をつけてもらうこと。
がっつりやろうとすると、それだけで1シリーズできてしまうほどの内容なので、そこはご了承いただきたい。
さて、次回はちょっと話が変わって、命題と論理に入ろう。
ここは、主に証明と関わりが深い部分だ。
そもそも証明って何？という方は、是非次回・次々回の内容を理解していってほしい。
2020/12/18追記
次回の内容である命題と論理の解説を投稿した。
証明の解説の基礎になるので、是非読んでみて欲しい。
コメント