計算理論の基礎(集合)

[計算理論]計算理論の導入(集合について)

計算理論を学ぶ為に、集合理論についてまとめておく

語句

・集合(set)：「もの」の集まり
・元(element)：集合に属するもの
・要素(member)：集合に属するもの(元と同意)

記法

\[
A \in a
\]
aはAの要素である。
\[
A \notin a
\]
aはAの要素でない。
\[
A \subseteq B
\]
AがBの部分集合(subset)である。
\[
A \subset B
\]
AはBの真部分集合(proper subset)である。

\[\emptyset\]
空集合(empty set)

・重複集合(multiset)：要素が重複している
・無限集合(infinite set)：要素が無限に多くある

\[ A \cup B \]
AとBの和集合(union)：AとBの要素を寄せ集めて一つにまとめた集合

\[A \cap B\]
AとBの積集合(intersection)：AとBに含まれる要素の集合

\[ \bar{A} \]
Aの補集合(complement) : Aに含まれていない要素の集合