4  集合

4.1 集合の定義

集合（Set）とは、「ものの集まり」のことである．集合は，普通 \(A\)，\(B\)，\(C\) などの大文字のアルファベットで表される．集合を構成している一つ一つのものを要素または元（element）という．

元を一つも持たない集合を空集合（empty set）といい，記号 \(\emptyset\) で表す．

無限の元を持つ集合は無限集合，有限の元を持つ集合は有限集合と呼ばれる．

議論するすべての元があるひとつの集合に属する場合，その集合を全体集合（universal set）という．

4.1.1 帰属関係

対象 \(x\) が集合 \(S\) の元であることを

\[ x \in S \]

と書き，「\(x\) が \(S\) に属する」，「\(x\) is an element of \(S\)」などと読む．\(x\) が \(S\) の元でないことを

\[ x \notin S \]

と書く．

例えば，\(A = \{1, 2, 3\}\) とするとき，\(1 \in A\)，\(4 \notin A\) である．Python では次のように確認できる．

A = {1, 2, 3}
print(1 in A)  # True
print(4 in A)  # False

True
False

4.1.2 記法

4.1.2.1 外延的記法

外延的記法（roster notation）では，集合のすべての要素を列挙する．例えば，\(10\)より小さい正の奇数全体の集合は\(\{1, 3, 5, 7, 9\}\)，四季の集合は\(\{\text{春}, \text{夏}, \text{秋}, \text{冬}\}\)と表される．

集合が多くの要素を持つ場合は，省略記号（\(\ldots\)）を使って表すことができる．例えば，\(1\)から\(100\)までの自然数全体の集合は\(\{1, 2, 3, \ldots, 100\}\)，自然数全体の集合\(\mathbb{N}\)は\(\{1, 2, 3, \ldots\}\)と表される．

Python では次のように集合を定義できる．

A = {1, 2, 3, 4, 5}
print(A)

B = {"春", "夏", "秋", "冬"}
print(B)

C = set(range(1, 11))  # 1から10までの自然数全体の集合
print(C)

{1, 2, 3, 4, 5}
{'秋', '夏', '春', '冬'}
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

4.1.2.2 内包的記法

内包的記法（set-builder notation）では，集合の要素が満たす条件を用いて集合を定義する．\(P(x)\)を条件とし，\(P(x)\)を満たす\(x\)全体の集合を\(\{x \mid P(x)\}\)と表す．

例えば，\([0, 1]\)の区間に含まれる実数全体の集合は\(\{x \mid 0 \leq x \leq 1\}\)，\(5\)以上\(10\)未満の整数全体の集合は\(\{x \in \mathbb{Z} \mid 5 \leq x < 10\}\)と表される．

Python でも同様に，内包的記法で集合を定義できる．

# 1から10までの偶数全体の集合
A = {x for x in range(1, 11) if x % 2 == 0}
print(A)

{2, 4, 6, 8, 10}

4.1.3 特別な集合

• \(\mathbb{Z}\)：整数全体の集合
• \(\mathbb{N}\)：自然数全体の集合
• \(\mathbb{Q}\)：有理数全体の集合
• \(\mathbb{R}\)：実数全体の集合
• \(\mathbb{R}^+\)：正の実数全体の集合

4.1.4 集合の包含関係

• 部分集合（Subset）：集合\(A\)のすべての元が集合\(B\)の元であるとき，\(A \subseteq B\)と表す．\(A\)は\(B\)の部分集合であるという．
• 相等（Equality）：集合\(A\)と\(B\)が同じ元から構成されているとき，\(A = B\)と表す．すなわち，\(A \subseteq B\)かつ\(B \subseteq A\)が成り立つ．
• 真部分集合（Proper subset）：\(A \subseteq B\)かつ\(A \neq B\)のとき，\(A \subset B\)と表す．

4.2 順序組

順序組（Tuple，タプル）は，複数の対象を順序を持って並べたものである．\(n\)個の対象を並べた順序組を\(n\)-組（\(n\)-tuple）という．

\((a_1, a_2, \ldots, a_n)\)，\((b_1, b_2, \ldots, b_n)\)を二つの\(n\)-組とするとき，

\[(a_1, a_2, \ldots, a_n) = (b_1, b_2, \ldots, b_n)\]

であるためには，\(a_1 = b_1\)，\(a_2 = b_2\)，\(\ldots\)，\(a_n = b_n\)でないといけない．

例えば，\((1, 2) \neq (2, 1)\)であるが，\(\{1, 2\} = \{2, 1\}\)である．

ordered_pair_1 = (1, 2)
ordered_pair_2 = (2, 1)
print(ordered_pair_1 == ordered_pair_2)  # False

False

set_1 = {1, 2}
set_2 = {2, 1}
print(set_1 == set_2)  # True

True

\(2\)-組を特に順序対（ordered pair）という．例えば，\(a\)，\(b\)を二つの対象とするとき，\(a\)，\(b\)の順序対（ordered pair）は\((a, b)\)で表される．

4.3 リスト

リスト（List）は，順序を持った対象の集まりである．

python では，リストとタプルは似ているが，リストは変更可能（mutable）であり，タプルは変更不可能（immutable）であるという違いがある．

my_list = [1, 2, 3]
print(my_list)

my_list[0] = 10  # 変更可能
print(my_list)

[1, 2, 3]
[10, 2, 3]

タプルは変更不可能であるため，次のように要素を変更しようとするとエラーになる．

my_tuple = (1, 2, 3)
my_tuple[0] = 10  # エラー  

4.4 集合算

4.4.1 和集合（Union）

\(A\)，\(B\)を二つの集合とするとき，

\[A \cup B = \{x \mid x \in A \text{ または } x \in B\}\]

を\(A\)と\(B\)の和集合という．

4.4.2 共通部分（Intersection）：

\(A\)，\(B\)を二つの集合とするとき，

\[A \cap B = \{x \mid x \in A \text{ かつ } x \in B\}\]

を\(A\)と\(B\)の共通部分という．

4.4.3 差集合（Difference）

\(A\)，\(B\)を二つの集合とするとき，

\[A \setminus B = \{x \mid x \in A \text{ かつ } x \notin B\}\]

を\(A\)と\(B\)の差集合という．\(A - B\)と書くこともある．

4.4.4 補集合（Complement）

\(\Omega\)を全体集合とするとき，集合\(A\)の補集合は\(\Omega \setminus A\)である．\(A^c\)または\(\bar{A}\)と書くこともある．

4.4.5 直積（Cartesian product）

\(A\)，\(B\)を二つの集合とするとき，\(A\)と\(B\)の直積は

\[A \times B = \{(a, b) \mid a \in A, b \in B\}\]

である．例えば，\(\{1, 2\} \times \{3, 4, 5\} = \{(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)\}\)である．

4.4.6 冪乗集合（Power set）

\(A\)を集合とするとき，\(A\)のすべての部分集合からなる集合を\(A\)の冪乗集合といい，記号\(\mathcal{P}(A)\)や\(2^A\)で表す．例えば，\(A = \{1, 2\}\)のとき，\(\mathcal{P}(A) = 2^A = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}\)である．

4.5 総和と総乗

\(x_1, x_2, \ldots, x_n\) の総和は

\[ \sum_{i=1}^{n} x_i = x_1 + x_2 + \cdots + x_n \]

で表される．総乗は

\[ \prod_{i=1}^{n} x_i = x_1 \times x_2 \times \cdots \times x_n \]

で表される．

集合の元に対しても総和と総乗を定義できる．例えば，集合 \(A = \{1, 3, 5\}\) の総和と総乗は次のように計算できる．

\[ \sum_{x \in A} x = 1 + 3 + 5 = 9 \]

\[ \prod_{x \in A} x = 1 \times 3 \times 5 = 15 \]

for 文を用いて，\(A\) の総和を次のように計算できる．

A = {1, 3, 5}
sum_A = 0
for x in A:
    sum_A = sum_A + x
print("Sum:", sum_A)

Sum: 9

同様に，\(A\) の総乗を次のように計算できる．

A = {1, 3, 5}
prod_A = 1
for x in A:
    prod_A = prod_A * x
print("Product:", prod_A)

Product: 15

4.6 練習問題

Exercise 4.1 \(A = \{1, 2, 3\}\) を Python で定義し，\(2\) が \(A\) の元であることを確認せよ．

Exercise 4.2 \(A = \{1, \dots, 100\}\) を Python で定義し，\(A\) の元の総和と総乗を計算せよ．

Exercise 4.3 1 から 100 までのすべての奇数の集合を Python で定義せよ．

Exercise 4.4 タプル \((1, 2, 3)\) を Python で定義し，2 番目の要素を print() 関数で表示せよ．

Exercise 4.5 リスト [1, 2, 3] を Python で定義し，3 番目の要素を print() 関数で表示せよ．

Exercise 4.6 Python では，リストは変更可能（mutable）であり，タプルは変更不可能（immutable）であるという違いがある．リストとタプルの違いを確認するコードを書け．