うさぎでもわかる離散数学　第1羽　集合のいろは

こんにちは！
離散数学が難しすぎてわからないと言っている人が多かったので簡単にまとめたものを書いてみたいと思います！

初回である第1羽は「集合」についてまとめてみました。ぜひ見てください！

※注意

簡単にまとめているので、厳密的な定義とは若干違うことを書いているかもしれません。ご了承ください。

スポンサードリンク

1. 動画での解説はこちら！

本記事の内容は、動画でも解説しております。動画でご覧いただきたい方は、以下の動画をご覧ください。

★ 動画編第0羽　高校数学範囲の復習

★ 動画編第1羽　集合のいろは（大学数学範囲メイン）

スポンサードリンク

2. 集合の要素に集合!?

高校数学と(大学の)離散数学の変化点の1つ目は、集合の要素が数字でなくてもOKということです。

(1) 数字以外を要素にした集合とは？

例えば、下の集合のように、Perfumeのメンバーを要素とした集合なんかも作ることもできます。

A = {のっち, かしゆか, あ～ちゃん}

ただし、当てはまる／当てはまらないかが明確に識別できる必要があります。

例えば、"SixTONESのうち、背が高いメンバーを集めた集合" は、「背が高い」というのが抽象的（当てはまる／当てはまらないかが明確ではない）ので、このような集合は作れません^[1]身長が180cm以上のメンバーを集めた集合、のように基準を明確にすれば、集合を作れます。。

(2) 集合の要素に集合

離散数学では、集合の要素に集合を入れることができるようになります。

例えば、以下の集合 \(A \) は、1と集合 \( \{2,3 \} \) を要素に持つ集合です。\[
A = \{ 1, \{ 2,3 \} \}
\]もちろん、\[
A = \{ \{ \{ 2,3 \} \} \}
\]のように、集合を要素にもつ集合を要素にもつ集合なんかも作れます。マトリョシカみたいですね。

(3) 空集合も要素にすることができます！

集合の要素に集合を入れることができるので、集合の要素に空集合を入れることもできます。

例えば、\[
A = \{ 1, \phi , \{ \phi \} \}
\]とすることで、"1"と "空集合" と "空集合を要素にもつ集合" の3つを要素としてもつ集合 \( A \) が作れます。

(4) 例題を解いてみよう

集合の中に集合が出てくると、ゲシュタルト崩壊を起こし、混乱しますよね。

なので、ここで1問例題を解くことで、集合の中に集合が出てくることに慣れましょう。

[解説]

このような問題が出た場合、まずは与えられた集合 \( A \) の要素を全て書き出しましょう。

すると、\( A \) の要素は \( \{ 1,2 \} \) と 3 となりましたね。

(1) \( \in \) の確認の仕方

\( \in \) の関係式の場合、左辺の要素が \( A \) に属するか確認します。

今回は、左辺が \( \{ \{ 1,2 \} \} \) ですが、書き出した \( A \) の要素に \( \{ \{ 1,2 \} \} \) はありませんね。
※ \( \{ 1,2 \} \) と \( \{ \{ 1,2 \} \} \) は別物!!

なので、1の関係式 \( \{ \{ 1,2 \} \}, 3 \in A \) は誤りなことが分かります。

(2) \( \subseteq \) の確認の仕方

残った(2)が正解だと分かりましたが、こちらも確認していきましょう。

\( \subseteq \) の関係式の場合、まず左辺の集合の要素を追加で書き出します。

今回は、左辺の集合は \( \{ \{ 1,2 \} \} \) なので、この集合の要素は \( \{1,2 \} \) となります。

あとは、書き出した左辺の集合の要素がすべて \( A \) に含まれているかを確認します。

今回は \( \{ 1,2 \} \) が \( A \) に含まれているので、2の関係式 \( \{ \{ 1,2 \} \}, 3 \subseteq A \) は正しいことが分かりますね。

スポンサードリンク

3. 集合の演算記号紹介

離散数学では、高校数学では出てこなかった集合の演算記号が出てきます。

せっかくなので、高校数学の復習も兼ねながら、離散数学で出てくる記号を見ていきましょう。

★ 高校数学にも出てきた記号

01: 全体集合  \( U \)

考える対象の全体を表す集合を表す。定義域痛い

英語で Universal Set と呼ばれるため、 \( U \) という記号で表されることが多い。

02: 空集合  \( \phi \)   \( \emptyset \) 

要素（集合の中身）を1つももたない集合のことである。

厳密な空集合の記号は \( \emptyset \)  だが、参考書によっては \( \phi \) が使われることも多い。

私も \( \phi \) の記号のほうが好きなため、本記事では空集合は \( \phi \) で表すことにする。

03: 部分集合

\( x\in X \) ならば常に \( x\in Y \) が成り立つとき、つまり\( X \) の要素全てが \( Y \) の中に含まれているとき、\( X \) は \( Y \) の部分集合といえ、 \( X\subseteq Y \) のように表せる
→ この場合、集合 \( X \) は集合 \( Y \) の部分集合であるという意味を持つ。

例えば、\[\begin{align*}
A = \{ 1,2,3 \}, \ \ B = \{ 2,3 \}
\end{align*}\]とすると、\( \{1 \} \subseteq A, B \subseteq A \) などと表記できる。

※ 高校数学では、部分集合の記号は \( \subset \) でしたが、大学の離散数学では、部分集合の記号を \( \subseteq \), \( \subseteqq \) などと表記する人がいるため、注意。
(講義をする先生によって書き方が変わります。 高校数学の場合は \( \subset \) が部分集合と習うはず。)

04: 補集合 \( \overline{X} \) , \( X^{c} \)

全体集合 \( U \) のうち、\( \overline{X} \) に属さない要素全体を表す。

例えば、\[
U = \{ 1,2,3,4,5 \}, X = \{ 1,2,3 \}
\]とすると、\( \overline{X} = \{ 4,5 \} \) となる。

※ 高校数学では \( \overline{X} \) と表記されたが、離散数学では \( X^{c} \) と表記する先生もいるため注意。

05: \( a \in X \)

\( a \) は集合 \( X \) に属する。

例えば \( A = \{ 1,2,3 \} \) の場合、\( 1 \in A, 2 \in A \) などと書ける。

06: \( a \notin X \)

\( a \) は集合 \( X \) に属さない。

例えば \( A = \{ 1,2,3 \} \) の場合、\( 4 \notin A, 4 \notin B \) などが挙げられる。

07: 等しい \( X = Y \)

集合 \( X \) に属する全ての要素が、集合 \( Y \) に属するとき、集合 \( X \), 集合 \( Y \) は等しい、つまり \( X = Y \) と言える。

もう少し厳密な定義を見ると、 \( X \subseteq Y \) かつ \( Y \subseteq X \) が成り立つとき、 \( X = Y \) ということができる。

[例] \[\begin{align*}
\{ 1,2,3 \} & = \{ 1,2,3 \}
\\ \{ 1,2,3 \} & \not = \{ 1,2 \}
\\ \{ 1,2,3 \} & \not = \{ \{ 1,2,3 \} \}
\end{align*}\]※ 離散数学では \( \{ \{ 1,2,3 \} \} \) のように、集合の要素に集合を入れることができる。詳しくは、この記事の3章をご覧ください。

08: 和集合 \( X \cup Y \)

集合 \( X \) と集合 \( Y \) の和集合、つまり \( X,Y \) のうち少なくともどちらか一方に属する要素全体の集合である。記号の読み方としては、「和集合」、「かっぷ」、「ゆにおん」、「または」などがあります。（厳密な先生だと「または」って呼ぶと怒る先生もいるので注意）

[例] \( A = \{ 1,2,3 \} \), \( B = \{ 3,4,5 \} \) のとき、\[
A \cup B = \{ 1,2,3,4,5 \}
\]

 09: 積集合（共通部分） \( X \cap Y \)

集合 \( X \) と集合 \( Y \) の積集合、つまり \( X,Y \) の両方に属する要素全体の集合である。読み方としては、「積集合」、「共通部分」、「ぎゃっぷ」、「いんたーせくしょん」、「かつ」などがあります。（「かつ」と読むと「または」のように怒る先生もいるので注意）

※ 高校数学では共通部分と呼ばれることが多いですが、離散数学では積集合と呼ぶ人の方が多い気がします。

[例] \( A = \{ 1,2,3 \} \), \( B = \{ 3,4,5 \} \) のとき、\[
A \cap B = \{ 3 \}
\]

（修正：10月17日　積集合の説明の一部分が和集合になっていたミスを修正しました。）

★ 離散数学から出てくる記号

10: 差集合 \( X - Y \)

集合 \( X \) に含まれているが、集合 \( Y \) には含まれていない要素を除いた集合である。\( X \cap \overline{Y} \) と同じである。

[例] \( A = \{ 1,2,3 \} \), \( B = \{ 3,4,5 \} \) のとき、\[\begin{align*}
A - B & = \{ 1,2 \} \\
B - A & = \{ 4,5 \}
\end{align*}\]

11: \( X \oplus Y \) , \( X \Delta Y \)

集合 \( X \) と集合 \( Y \) のうち、片方の集合のみにある要素を集めた集合である。
\( X \oplus Y = (X - Y) \cup (Y - X) = (X \cap \overline{Y}) \cup (Y \cap \overline{X}) \) と変形できる。 

[例] \( A = \{ 1,2,3 \} \), \( B = \{ 3,4,5 \} \) のとき、\[\begin{align*}
A \oplus B = \{ 1,2,4,5 \}
\end{align*}\]

12: 要素数(濃度) \( |X| \)

集合 \( X \) に含まれている要素の個数を表す。濃度と呼ぶ人もいる。

[例] \( A = \{ 1,2,3,4,5 \} \), \( B = \{ 3,4, \{ 5,6 \} \} \) のとき、\[\begin{align*}
|A| = 5 , \ \ \ |B| = 3
\end{align*}\]※ \( B \) の要素は、3と4と \( \{5,6 \} \) の3つ。

13: べき（冪）集合　\( 2^{X} \)

集合 \( X \) の部分集合から作られる集合をすべて集めた集合です。

Step1. \( X \) から作られる部分集合を全て列挙する

例えば、\( S = \{1,2,3\} \) とする。まず、\( S \) から作成できる部分集合を要素数ごとに場合分けしてすべて列挙していく。

(1) 要素数が0のとき：\( \phi \) の1個 （個数計算式：\( {}_3 C _0  = 1 \) ）
(2) 要素数が1のとき：\( \{1\},\{2\},\{3\} \) の3個 （個数計算式：\( {}_3 C _1  = 3 \) ）
(3) 要素数が2のとき：\( \{1,2\},\{1,3\},\{2,3\} \) の3個 （個数計算式：\( {}_3 C _2  = 3 \) ）
(4) 要素数が3のとき：\( \{1,2,3\} \) の1個 （個数計算式：\( {}_3 C _3  = 1 \) ）

の合計8個となる。

Step2. 列挙した部分集合をすべて要素とした集合がべき集合

あとは、列挙した部分集合を、すべて要素とした集合を作ればべき集合の完成です。

今回の場合、べき集合 \( 2^S \) は以下のように求まります。\[ 2^{S} = \{\phi,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\} \]

べき集合の要素数は？

要素数が \( n \) 個の集合のべき集合の要素数は、\( 2^{n} \) 個と求めることができる。その理由を以下に示していく。

まず、べき集合は、元の集合の部分集合をすべて要素とした集合でしたね。ここで、部分集合を列挙していく際に、それぞれの要素に対して、選ぶか選ばないかの2つの可能性を考えることができます。

ここで、元の集合の要素数が \( n \) 個の場合、「選ぶか選ばないの2通り」が \( n \) 回分考える必要があるため、部分集合の総数（＝べき集合の要素数）は \( 2^{n} \) になりますね。

※ 本当か？って人は \( n = 3,4 \) くらいで試して実験してみてください。

14: 直積集合 \( X \times Y \)

集合 \( X \) と集合 \( Y \) に対して、それぞれの集合から1つずつ要素を取り出してペアにしたものを表す。

例えば、\( \textcolor{magenta}{X = \{ 1,2,3 \}} \), \( \textcolor{deepskyblue}{Y = \{ x,y \}} \) とする。このときの直積集合 \( \textcolor{magenta}{X} \times \textcolor{deepskyblue}{Y} \) は、つぎの通りになる。\[
\textcolor{magenta}{X} \times \textcolor{deepskyblue}{Y} = \{ ( \textcolor{magenta}{1}, \textcolor{deepskyblue}{x} ), ( \textcolor{magenta}{1}, \textcolor{deepskyblue}{y} ), (\textcolor{magenta}{2}, \textcolor{deepskyblue}{x} ), ( \textcolor{magenta}{2}, \textcolor{deepskyblue}{y} ), (\textcolor{magenta}{3}, \textcolor{deepskyblue}{x} ), (\textcolor{magenta}{3}, \textcolor{deepskyblue}{y} ) \}
\]

※ ペアの順番に注意。「\( \times \) の左側にある要素は , の左側」に、「\( \times \) の右側にある要素は , の右側」になるようにすること。

ここで、列挙漏れが心配な人は、下のような表を書きながら要素を列挙していくと、列挙漏れが防げるのでおすすめです。

	\( \textcolor{deepskyblue}{x}\)	\( \textcolor{deepskyblue}{y}\)
\( \textcolor{magenta}{1} \)	\( (\textcolor{magenta}{1},\textcolor{deepskyblue}{x}) \)	\( (\textcolor{magenta}{1}, \textcolor{deepskyblue}{y}) \)
\( \textcolor{magenta}{2} \)	\( (\textcolor{magenta}{2},\textcolor{deepskyblue}{x}) \)	\( (\textcolor{magenta}{2},\textcolor{deepskyblue}{y}) \)
\( \textcolor{magenta}{3} \)	\( (\textcolor{magenta}{3},\textcolor{deepskyblue}{x}) \)	\( (\textcolor{magenta}{3},\textcolor{deepskyblue}{y}) \)

この表を見ると、直積集合 \( X \times Y \) の要素数が「\( X \) の要素数（行部分）」と「\( Y \) の要素数（列部分）」の積で表されることが分かりますね。

例えば、上の例でみると、\( X = \{ 1,2,3 \} \) の要素数が3、\( Y = \{ x, y \} \) の要素数が2、直積集合 \( X \times Y \) の要素数が3×2 = 6になっていますね。

そのため、集合 \( X \) の要素数を \( n \) 個、集合 \( Y \) の要素数を \( m \) 個とすると、直積集合 \( X \times Y \) の要素数は \( nm \) 個となります。

15: 商集合（分割） \( A/{\equiv} \)

商集合 \( A / \equiv \) は、あらかじめ決めた同値関係 \( \equiv \) によりグループ分けした集合です。

実際にどのようにグループ分けされるかを見ていきましょう。

Step1. 同値関係ごとにグループ分けする

例えば、1～9の自然数からなる集合\[
A = \{ 1,2,3,4,5,6,7,8,9 \}
\]を、「3で割った余りが等しい関係 \( \equiv \)」によりグループ分けした場合、

• 余りが1のグループ: 1,4,7
• 余りが2のグループ: 2,5,8
• 余りが0のグループ: 3,6,9

の3つのグループに分けることができますね。

Step2. 同じグループに属する要素を、グループ化して集合にする

ここで、同じグループに属する要素を、グループ化して集合にします。

• 余りが1のグループ: \( \{1,4,7 \} \)
• 余りが2のグループ: \( \{2,5,8 \} \)
• 余りが0のグループ: \( \{3,6,9 \} \)

とします。ここで、グループ化されたそれぞれの集合 \( \{1,4,7 \} \), \( \{2,5,8 \} \), \( \{3,6,9 \} \) のことを同値類と呼ぶので、覚えておきましょう。

Step3. グループ化した各集合を要素とした集合 = 商集合

あとは、Step2で作った集合をすべて要素とする集合を作れば、商集合の完成です。\[
A = \{ \{ 1,4,7 \}, \{ 2,5,8 \}, \{ 3,6,9 \} \}
\]

※ 類別するときには、もとのすべての集合の要素が、必ず小さな集合のどこかに入るようにしてください（２つ以上の小さな集合に入るのもだめ）。

4. べき集合に慣れるための練習問題

べき集合は、少し難しいのに加えて、試験にもよく出てきます。

なので、練習問題で手を動かすことで慣れましょう。

[解説]

まずは、集合 \( A \) の部分集合をすべて列挙します。\[
\phi, \{ 1 \}, \{ \{ 2,3 \} \}, \{ 1, \{ 2,3 \} \}
\]Tips) \( A \) の要素数は2なので、べき集合 \( 2^A \) の要素数は \( 2^2 = 4 \) となることを頭に入れておけば、列挙漏れが防げます。

よって、この4つがべき集合 \( 2^A \) の要素となります。

あとは、「∈と⊆が出てくる問題の解き方」に従って、関係式が正しいか判定すればOK。

(1) \( \in \) の確認の仕方

\( \in \) の関係式の場合、左辺の要素がべき集合 \( 2^A \) に属するか確認します。

今回は、左辺 \( \{ \{ 2,3 \} \} \) が書き出したべき集合 \( 2^A \) の要素に属していることが分かりますね。 

なので、1の関係式 \( \{ \{ 2,3 \} \} \in 2^A \) は正しいことが分かります。

(2) \( \subseteq \) の確認の仕方

残った(2)は誤りだと分かりましたが、こちらも確認していきましょう。

\( \subseteq \) の関係式の場合、まず左辺の集合の要素を追加で書き出します。

今回は、左辺の集合は \( \{ \{ 2,3 \} \} \) なので、この集合の要素は \( \{ 2,3 \} \) となります。

あとは、書き出した左辺の集合の要素がすべてべき集合 \( 2^A \) に含まれているかを確認します。

今回は \( \{ 2,3 \} \) はべき集合 \( 2^A \) に含まれていないので、2の関係式 \( \{ \{ 2,3 \} \} \subseteq 2^A \) は誤りなことが分かりますね。

このタイプの問題をさらに演習したい人は、フォームを作成しておりますので、是非チャレンジしてみてください！

forms.gle

5. 動画のQuizの答えと解説

[解答] 4

[解説]

\( A \)の要素を列挙すると、1 と \( \{ \phi, \{ \phi \} \} \) となり、要素を2つ持つ集合であることが分かりますね。

ここで、べき集合は \( A \) の部分集合を全て集め、要素とした集合でしたね。

ここで、\( A \) の部分集合を列挙の総数としては、2つの要素に対して選ぶ/選ばないの2通りを考える必要があるので、2×2 = 4通りと求まります。

6. その他の練習問題

ここからは、例題を交えて解説をしていきたいとおもいます。

例題1（レベル1）

\( \phi \in \phi \) と \( \phi \subseteq \phi \) 、成り立つのはどっち？

解答1（レベル1）

\(  \phi \) は空集合なので要素を1つも持たない。よって \(  \phi \) も要素に持たず、\( \phi \in \phi \) は誤りであることがわかる。
また、空集合はすべての要素の部分集合なので、\( \phi \subseteq \phi \) は成立する。
よって答えは \( \phi \subseteq \phi \) となる。

例題2（レベル2）

\( \{1,\phi\} \in \{1,\{1,\phi\}\} \) と \( \{1,\phi\} \subseteq \{1,\{1,\phi\}\} \) 、成り立つのはどっち？

解答2（レベル2）

このように複雑になるとわけが分からなくなってくるので左辺と右辺の集合の中身、つまり箱の中身はなにかを1つずつしらべていく。

\( \{1,\phi\} \) の箱の中には1と空の箱が入っている。
\(  \{1,\{1,\phi\}\} \) の箱の中には1と1と空の箱が入った箱が入っている。

\( \{1,\phi\} \in \{1,\{1,\phi\}\} \) は、「1と1の空の箱が入った箱 \(  \{1,\{1,\phi\}\} \)  に1のと空の箱が入った箱 \( \{1,\phi\} \) はありますか？」という問題に変わる。実際見てみると1と空の箱が入った箱があるのでこれは正しいことがわかる。

一方 \( \{1,\phi\} \subseteq \{1,\{1,\phi\}\} \) というのは、左辺に入っている要素が右辺に全て入っていないと正しいと言えない。つまり、「1と1の空の箱が入った箱 \(  \{1,\{1,\phi\}\} \) の中には1と空の箱 \(  \{1,\{1,\phi\}\} \) はありますか？」という問題に変わる。この場合、右辺に1はあるが、空の箱は入っていない。よってこれは誤りだということがわかる。

よって答えは \( \{1,\phi\} \in \{1,\{1,\phi\}\} \) となる。

例題3（レベル2）

\( \phi \cup \{\phi\} \) と \( \{\phi\} \cap \{1,\phi,\{\phi\}\} \) を求めなさい。

解答3（レベル2）

\( \phi \) には要素は存在しない。（箱の中身：空）
\(   \{\phi\} \) の要素は空集合である。（箱の中身：空の箱）

よって、\( \phi \cup \{\phi\} = \{\phi\} \) となる。（中身：空の箱）

また、\(   \{1,\phi,\{\phi\}\} \) の要素は1と空集合と空集合からなる集合である。
（中身：1、空の箱、空の箱が入っている箱の3つ）

「空の箱」と「1、空の箱、空の箱が入っている箱」の共通している箱の中身は「空の箱」となる。

よって、 \( \{\phi\} \cap \{1,\phi,\{\phi\}\} = \{\phi\} \) となる。

例題4（レベル3）

集合 \( S \) を \( S = \{1,\{2,3\}\} \) とする。次の(1)～(3)の問いに答えなさい。
(1) 集合 \( S \) の部分集合を全て求めなさい。
(2) 集合 \( S \) のべき集合 \( 2^{S} \) を求めなさい。
(3) \( \{1\} \in 2^{S} \)、\( \{\{2,3\}\}\subseteq 2^{S} \) のうち、正しい関係はどちらか？

解答4

(1) 集合の要素数ごとに場合分けをすればよい。
(i) 要素数が0の部分集合：\( \phi \) の1つ
(ii) 要素数が1の部分集合：\( \{1\},\{\{2,3\}\} \) の2つ 
(iii) 要素数が2の部分集合：\( \{1,\{2,3\}\} \) の1つ
よって答えは \( \phi,\{1\},\{\{2,3\}\},\{1,\{2,3\}\} \) の4つとなる。
（箱に言い換えると空の箱、1が入った箱、2と3が入った箱に入った箱、1と2と3が入った箱に入った箱）

(2) \( S \) のべき集合は、\( S \) の部分集合から作られる集合をすべて集めたものである。(1)より、\( 2^{S} = \{\phi,\{1\},\{\{2,3\}\},\{1,\{2,3\}\}\} \) と求めることができる。

(3) 例題1のように要素（箱）を全部書いてから比較したほうがいいかも。
\( S \) のべき集合の中に \( \{1\} \) （1が入った箱）は入っているため、\( \{1\} \in 2^{S} \) は正しいといえる。

また、2と3が入った箱のべき集合 は\( S \) のべき集合の中には含まれていない（べき集合の中にあるのは2と3が入った箱 \( \{2,3\} \) ではなく、2と3がが入った箱が入っている箱 \( \{\{2,3\}\} \) なので微妙に違う）ので、\( \{\{2,3\}\}\subseteq 2^{S} \) は誤りなことがわかる。

よって \( \{1\} \in 2^{S} \) が正しい。

7. 確認テスト

本記事の内容が理解できたかどうかを確認するための小テストを作りました！

理解度確認に是非チャレンジしてみてください！

※ 回答フォームに入力後、自動採点 & 自動解説表示が行われます。

8. 最後に

今回は離散数学では避けて通れないであろう集合分野について少しまとめてみました。

第2羽では、命題と真理値表（場合分けみたいなもん）について少し説明したいとおもいます。ではまた次回！

第2羽はこちらから！

www.momoyama-usagi.com