付録 B — 集合

B.1 集合の定義

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

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

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

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

B.1.1 帰属関係

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

x \in S

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

x \notin S

と書く．

例 B.1 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

練習 B.1 A = \{1, 2, 3\} を Python で定義し，2 が A の元であることを確認せよ．

B.1.2 記法

B.1.2.1 外延的記法

外延的記法（roster notation）では，集合のすべての要素を列挙する．

例 B.2 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}

B.1.2.2 内包的記法

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

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

Python でも，集合内包表記（set comprehension）を用いて同様に集合を定義できる．

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

練習 B.2 1 から 100 までのすべての奇数の集合を Python で定義せよ．

B.1.3 特別な集合

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

B.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 と表す．

例 B.4 A = \{1, 2\}，B = \{1, 2, 3\} とする．A \subseteq B かつ A \neq B であるから，A \subset B である．一方，B \subseteq B は成り立つが，B \subset B は成り立たない．

Python では，<= で部分集合，< で真部分集合，== で相等を判定できる．

A = {1, 2}
B = {1, 2, 3}
print(A <= B)  # True
print(A < B)  # True
print(A == B)  # False
print(B <= B)  # True
print(B < B)  # False
True
True
False
True
False

B.2 順序組

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

二つの n 組 (a_1, a_2, \ldots, a_n) と (b_1, b_2, \ldots, b_n) が等しいための必要十分条件は，すべての i = 1, 2, \ldots, n に対して a_i = b_i が成り立つことである．

例 B.5 順序組では (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) で表される．

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

B.3 リスト

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

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

例 B.6  

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  # エラー

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

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

B.4 集合の演算

B.4.1 和集合（Union）

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

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

を A と B の和集合という．

B.4.2 共通部分（Intersection）

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

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

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

B.4.3 差集合（Difference）

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

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

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

例 B.7 A = \{1, 2, 3, 4\}，B = \{3, 4, 5\} とするとき，

A \cup B = \{1, 2, 3, 4, 5\}, \qquad A \cap B = \{3, 4\}, \qquad A \setminus B = \{1, 2\}

である．

共通部分と差集合は，集合内包表記を使えば，定義をそのまま Python で書くことができる．

A = {1, 2, 3, 4}
B = {3, 4, 5}

intersection_AB = {x for x in A if x in B}  # x ∈ A かつ x ∈ B
difference_AB = {x for x in A if x not in B}  # x ∈ A かつ x ∉ B
print(intersection_AB)
print(difference_AB)
{3, 4}
{1, 2}

同じ計算は，for 文を使って書くこともできる．set() は空集合を作り，add() は集合に元を追加する．

intersection_AB = set()

for x in A:
    if x in B:
        intersection_AB.add(x)

difference_AB = set()

for x in A:
    if x not in B:
        difference_AB.add(x)
print(intersection_AB)
print(difference_AB)
{3, 4}
{1, 2}

また，Python には集合の演算を行う演算子が用意されている．

print(A | B)  # 和集合
print(A & B)  # 共通部分
print(A - B)  # 差集合
{1, 2, 3, 4, 5}
{3, 4}
{1, 2}

B.4.4 補集合（Complement）

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

例 B.8 全体集合 \Omega = \{1, 2, \ldots, 10\} の部分集合 A = \{1, 2, 3, 4\} について，A^c = \{5, 6, 7, 8, 9, 10\} である．

Python には補集合を求める演算子がないため，全体集合を定義したうえで，差集合 \Omega \setminus A として計算する．

Omega = set(range(1, 11))
A = {1, 2, 3, 4}
print(Omega - A)
{5, 6, 7, 8, 9, 10}

B.4.5 直積（Cartesian product）

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

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

である．

例 B.9 A = \{1, 2\}，B = \{3, 4, 5\} とするとき，

A \times B = \{(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)\}

である．

直積の元は順序対であるから，Python ではタプルで表す．二重の for 文を用いると，直積を次のように計算できる．

A = {1, 2}
B = {3, 4, 5}
product_AB = set()  # 空集合
for a in A:
    for b in B:
        product_AB.add((a, b))
print(product_AB)
{(2, 4), (1, 5), (1, 4), (2, 3), (2, 5), (1, 3)}

集合には順序がないため，表示される順序は上の式と異なることがある．

B.4.6 冪集合（Power set）

A を集合とするとき，A のすべての部分集合からなる集合を A の冪集合といい，記号 \mathcal{P}(A) や 2^A で表す．

例 B.10 A = \{1, 2\} のとき，\mathcal{P}(A) = 2^A = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\} である．

B.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

で表される．

有限個の数からなる集合についても，その元の総和と総乗を定義できる．

例 B.11 集合 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

練習 B.6 A = \{1, \dots, 10\} を Python で定義し，A の元の総和と総乗を計算せよ．

B.6 総合演習

練習 B.7 全体集合を \Omega = \{1, 2, \ldots, 12\} とする．\Omega の元のうち，2 の倍数からなる集合を A，3 の倍数からなる集合を B とする．

  1. A と B をそれぞれ外延的記法で表せ．
  2. A \cup B，A \cap B，A \setminus B，A^c をそれぞれ外延的記法で表せ．ただし，補集合は \Omega に対して考えるものとする．
  3. C = A \cap B とする．C \times \{0, 1\} と \mathcal{P}(C) をそれぞれ求めよ．
  4. Python の集合内包表記を使って A，B，C を定義し，表示せよ．ヒント：C は，A の元のうち x in B を満たすものを集めればよい．
  5. for 文を使って C の元の総和と総乗を計算し，その結果をこの順に格納したタプルを作成して表示せよ．