集合

定義

集合とは、明確に定まる対象の集まりで、対象を要素という。例えば

$A=\{2,4,6\}$A={2,4,6}

と書き、$4\in A$4∈Aは4が$A$Aに属することを表す。反対に$5\notin A$5∈/Aである。

順序や重複は集合を変えない。$\{2,4,6\}${2,4,6}、$\{6,4,2\}${6,4,2}、$\{2,2,4,6\}${2,2,4,6}は同じ集合である。重要なのは、どの要素が属するかだけである。

集合の記述

要素を列挙できる：

$B=\{a,e,i,o,u\}$B={a,e,i,o,u}

または性質で定められる：

$C=\{n\in\mathbb{N}\mid n<5\}=\{0,1,2,3,4\}$C={n∈N∣n<5}={0,1,2,3,4}

ここでは$0\in\mathbb{N}$0∈Nという約束を用いる。縦線は「…を満たす」と読む。性質は対象が集合に属するかを曖昧なく決めなければならない。

空集合、等しさ、濃度

空集合$\varnothing$∅は要素を持たない。$\{\varnothing\}${∅}は空集合そのものを一要素として持つので別物である。

二つの集合は要素が完全に同じなら等しい。有限集合$A$Aの濃度$|A|$∣A∣は要素数である。$A=\{2,4,6\}$A={2,4,6}なら$|A|=3$∣A∣=3。

包含と部分集合

$A$Aの全要素が$B$Bにも属するとき$A\subseteq B$A⊆Bと書く。例えば

$\{2,4\}\subseteq\{1,2,3,4\}${2,4}⊆{1,2,3,4}

所属と包含は異なる。$2\in A$2∈Aは対象と集合を、$A\subseteq B$A⊆Bは二集合を比較する。どの集合も自分自身の部分集合であり、空集合はすべての集合の部分集合である。

三つの基本演算

$A=\{1,2,3\}$A={1,2,3}、$B=\{3,4\}$B={3,4}とする。

和集合の「または」は両方を含む。両方にある要素も和集合に属するが、一度だけ現れる。全体集合$U$Uを定めたとき、$U$Uにおける$A$Aの補集合は$U\setminus A$U∖Aである。全体集合なしでは「$A$Aの補集合」は不完全である。

図は助けるが定義ではない

ベン図は集合を領域で表し、重なりが共通部分、領域の結合が和集合を示す。図は思考補助であり定義ではない。証明は所属条件に戻る。

$A\cap B\subseteq A$A∩B⊆Aを示すには$x\in A\cap B$x∈A∩Bを取る。定義から$x\in A$x∈Aかつ$x\in B$x∈Bなので$x\in A$x∈Aである。

この抽象化が役立つ理由

集合は数学と計算機科学に共通の語彙を与える。値の領域、問い合わせ結果、グラフの頂点、規則が受理する場合を集合として扱える。関係は順序対の集合となり、関数は定義域と終域を使う。集合は関係、関数、データベース、確率、グラフの直接の前提である。

まとめ

集合は要素で決まり、所属は対象と集合を結び、包含は集合を比較し、和集合・共通部分・差集合が新しい集合を作る。

教育参考資料

• ACM/IEEE-CS/AAAI — Computer Science Curricula 2023, Mathematical and Statistical Foundations
• National University of Singapore — CS1231S, Discrete Structures
• Australian National University — MATH1005, Discrete Mathematical Models