オートマトン/第一類/数学的準備/集合

集合に関した基礎的な事項を簡単にまとめておく.
集合(set)とは,要素(element)の集まりである.対象となる要素はなんであってもいいし,特に集合を要素とする集合も通常は許容される. ある集合 A {\displaystyle A} があるとき,どんな要素が A {\displaystyle A} に属するかは明瞭に記述されなければならない. 例えば「0 と 1 からなる文字列」の集まりは集合である. 一つの集合には,同じ要素が重複して含まれることはない. 有限個の要素よりなる集合を有限集合(finite set),無限個の要素より成る集合を無限集合(infinite set)という.
要素 0, 1 の二つからなる集合は { 0 , 1 } {\displaystyle \{0,1\}} と表す. n {\displaystyle n} 個の要素 a 1 , a 2 , a 3 , ⋯ , a n {\displaystyle a_{1},a_{2},a_{3},\cdots ,a_{n}} ( i ≠ j {\displaystyle i\neq j} ならば a i ≠ a j {\displaystyle a_{i}\neq a_{j}} )からなる集合は, { a 1 , a 2 , ⋯ , a n } {\displaystyle \{a_{1},a_{2},\cdots ,a_{n}\}} と表す. 要素の順序は任意であり, { 0 , 1 } {\displaystyle \{0,1\}} と { 1 , 0 } {\displaystyle \{1,0\}} は同じ集合である.
集合を表す記法として次のような方法もある. D = { x | x {\displaystyle D=\{x\ |\ x} は実数の集合 R {\displaystyle {\mathit {R}}} に属し,かつ x 6 = 1 } {\displaystyle x^{6}=1\}} は, “ x {\displaystyle x} は実数の集合の集合 R {\displaystyle {\mathit {R}}} に属し,かつ x 6 = 1 {\displaystyle x^{6}=1} ” という性質を満足するような x {\displaystyle x} をすべて集めた集合であり, 要素を列挙する記法で表せば, D = { − 1 , 1 } {\displaystyle D=\{-1,1\}} である.
一般に, x {\displaystyle x} に関する性質を P ( x ) {\displaystyle P(x)} としたとき,性質 P ( x ) {\displaystyle P(x)} を満足するような x {\displaystyle x} をすべて集めた集合を
と表す.さらに性質 P ( y ) {\displaystyle P(y)} と性質 Q ( x ) {\displaystyle Q(x)} をともに満足するような y {\displaystyle y} をすべて集めた集合を
と表す.
特に要素を一つも持たない集合は空集合(empty set) という.空集合は記号 ∅ {\displaystyle \varnothing } で表す.
集合 A {\displaystyle A} が要素として a {\displaystyle a} を持つとき, a {\displaystyle a} は A {\displaystyle A} に属する,あるいは A {\displaystyle A} は a {\displaystyle a} を含むといい,
と表す. a {\displaystyle a} が A {\displaystyle A} の要素ではないときは,
と表す.前提としてのすでに明らかな集合 S {\displaystyle S} があって,今は性質 P ( x ) {\displaystyle P(x)} に論述の力点があるときに
は
のように表示されることもある.例えば実数の集合を R {\displaystyle {\mathit {R}}} としたとき,先にあげた集合 D {\displaystyle D} を
とも表すことができる.
集合 A , B {\displaystyle A,B} において,集合 A {\displaystyle A} の要素は必ず集合 B {\displaystyle B} であるとき, A {\displaystyle A} は B {\displaystyle B} の部分集合(subset) であるという.またこのとき, A {\displaystyle A} は B {\displaystyle B} に含まれる, あるいは, B {\displaystyle B} は A {\displaystyle A} を含むといい,
と表す.例えば { 0 } ⊆ { 0 , 1 } {\displaystyle \{0\}\subseteq \{0,1\}} . 定義より A {\displaystyle A} 自身は A {\displaystyle A} の部分集合である.
また,空集合 ∅ {\displaystyle \varnothing } はすべての集合の部分集合である,と定義する.
集合 A , B {\displaystyle A,B} において A ⊆ B {\displaystyle A\subseteq B} かつ B ⊆ A {\displaystyle B\subseteq A} であるとき,集合 A {\displaystyle A} と B {\displaystyle B} は等しいといい,
と表す.

集合 A , B {\displaystyle A,B} に対し,そのいずれかに属する要素をすべて集めた集合 C = { c | c ∈ A {\displaystyle C=\{c\ |\ c\in A} または c ∈ B } {\displaystyle c\in B\}} を, A {\displaystyle A} と B {\displaystyle B} を A {\displaystyle A} と B {\displaystyle B} の和集合 (union) という.これを
と表す.一般に集合 S 1 , S 2 , ⋯ , S n ( n ≧ 2 ) {\displaystyle S_{1},S_{2},\cdots ,S_{n}(n\geqq 2)} に対して S = { a | a ∈ S 1 {\displaystyle S=\{a\ |\ a\in S_{1}} あるいは a ∈ S 2 , ⋯ , {\displaystyle a\in S_{2},\cdots ,} あるいは a ∈ S n } {\displaystyle a\in S_{n}\}} を S 1 , S 2 , ⋯ , S n {\displaystyle S_{1},S_{2},\cdots ,S_{n}} の和集合といい,
と表す.
集合 A {\displaystyle A} と B {\displaystyle B} とに共通して含まれる要素を集めた集合 C = { c | c ∈ A {\displaystyle C=\{c\ |\ c\in A} かつ c ∈ B } {\displaystyle c\in B\}} を A {\displaystyle A} と B {\displaystyle B} の積集合 (intersection, product) という.これを
と表す.一般に集合 S 1 , S 2 , ⋯ , S n ( n ≧ 2 ) {\displaystyle S_{1},S_{2},\cdots ,S_{n}(n\geqq 2)} に対して S = { a | a ∈ S 1 {\displaystyle S=\{a\ |\ a\in S_{1}} かつ a ∈ S 2 , ⋯ , {\displaystyle a\in S_{2},\cdots ,} かつ a ∈ S n } {\displaystyle a\in S_{n}\}} を S 1 , S 2 , ⋯ , S n {\displaystyle S_{1},S_{2},\cdots ,S_{n}} の積集合といい,
と表す.
集合 A {\displaystyle A} の要素の中から,集合 B {\displaystyle B} にも属する共通要素をすべて除いて得られる集合 C = { c | c ∈ A , {\displaystyle C=\{c\ |\ c\in A,} かつ c ∉ B } {\displaystyle c\not \in B\}} を, A {\displaystyle A} から B {\displaystyle B} を引いた差集合 (difference) という.これを
と表す.考察の前提または対象となる全要素が先に提示されていて,これを集合 Ω {\displaystyle \Omega } (omega; これを全体集合あるいは普遍集合(universal set)という)とし, Ω {\displaystyle \Omega } の部分集合 A {\displaystyle A} が与えられたときの Ω {\displaystyle \Omega } と A {\displaystyle A} の差集合
を A {\displaystyle A} の( Ω {\displaystyle \Omega } に関する)補集合 (complement) という.これを A ̄ {\displaystyle {\overline {A}}} または A C {\displaystyle A^{C}} と表す. 定義より A ̄ ̄ = A {\displaystyle {\overline {\overline {A}}}=A} が成り立つ.
次の公式はド・モルガン則と呼ばれている.
集合を要素とする集合を,特に集合族 (family),あるいは集合のクラス (class) という.
集合 A {\displaystyle A} のすべての部分集合全体を考えたとき,これは集合の集合すなわち集合族である.すなわち { B | B ⊆ A } {\displaystyle \{B\ |\ B\subseteq A\}} は集合族をなす. この集合を A {\displaystyle A} のべき集合 (power set) といい, 2 A {\displaystyle 2^{A}} あるいは ℘ ( A ) {\displaystyle \wp (A)} と記す.
例: A = { a , b , c } {\displaystyle A=\{a,b,c\}} のとき,
℘ ( A ) = { ∅ , { a } , { b } , { c } , { a , b } , { a , c } , { b , c } , { a , b , c } } {\displaystyle \wp (A)=\{\varnothing ,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}} である.