理論計算機科学を読むための数学・証明・アルゴリズム基礎

第2章 関数と関係

章間ナビゲーション

この章で使う記号

記号 意味
f: A → B 集合 A から集合 B への関数
f(x) x に対する関数値
f ∘ g 関数合成
R ⊆ A × B A と B の間の二項関係
a R b a と b が関係 R にある
[a] a の同値類
≤ 順序関係の代表記号
R* 反射推移閉包を表すことが多い記号

この章で解消する詰まりどころ

理論計算機科学では、遷移関数、符号化関数、還元、順序、同値類、到達可能性などが頻繁に出ます。これらはすべて「関数」または「関係」として定義されます。

この章では、次を扱います。

  • 関数
  • 定義域、終域、像
  • 単射、全射、全単射
  • 関数合成、逆関数
  • 二項関係
  • 同値関係
  • 半順序、全順序
  • 閉包の直観

本体教科書のどこで使うか

  • 有限オートマトンの遷移関数
  • 計算可能関数
  • 多対一還元、チューリング還元
  • 同値類としての状態最小化
  • グラフの到達可能性
  • 並行計算における順序関係

1. 関数

関数 f: A → B とは、集合 A の各要素に対して、集合 B の要素をちょうど1つ対応させる規則です。

  • A: 定義域
  • B: 終域
  • f(a): a の像
  • Im(f) = { f(a) | a∈A }: 像

注意: 像は終域の部分集合です。常に Im(f) ⊆ B です。

2. 単射・全射・全単射

単射

f: A → B が単射であるとは、異なる入力が同じ出力に潰れないことです。

∀x,y∈A, f(x)=f(y) → x=y

同値に、

x≠y → f(x)≠f(y)

です。

全射

f: A → B が全射であるとは、終域 B の全ての要素が、何らかの入力の出力として現れることです。

∀b∈B, ∃a∈A, f(a)=b

全単射

単射かつ全射である関数を全単射と呼びます。全単射は、2つの集合の要素が1対1に対応することを表します。

有限集合では、A と B の間に全単射が存在することは、|A| = |B| と同値です。

3. 関数合成と逆関数

f: A → B, g: B → C のとき、合成関数 g∘f: A → C は次で定義されます。

(g∘f)(a) = g(f(a))

f: A → B が全単射なら、逆関数 f^{-1}: B → A が存在します。

4. 二項関係

集合 A 上の二項関係 R とは、A × A の部分集合です。

R ⊆ A × A

(a,b) ∈ R を a R b と書くことがあります。

例:

整数上の関係 a R b ⇔ a ≤ b
整数上の関係 a R b ⇔ a と b は同じ偶奇である

5. 関係の性質

性質 定義
反射律 ∀a∈A, a R a
対称律 ∀a,b∈A, a R b → b R a
反対称律 ∀a,b∈A, (a R b ∧ b R a) → a=b
推移律 ∀a,b,c∈A, (a R b ∧ b R c) → a R c

6. 同値関係

関係 R が次の3つを満たすとき、同値関係です。

  1. 反射律
  2. 対称律
  3. 推移律

同値関係は、集合を互いに交わらない部分集合へ分割します。この部分集合を同値類と呼びます。

例:

整数 a,b について、a R b ⇔ a ≡ b (mod 3)

このとき同値類は、余り0、余り1、余り2の3種類です。

7. 順序関係

半順序

関係 R が次の3つを満たすとき、半順序です。

  1. 反射律
  2. 反対称律
  3. 推移律

例:

  • ≤ は整数上の全順序
  • ⊆ は集合族上の半順序

全順序

半順序に加えて、任意の2要素が比較可能であるとき、全順序です。

∀a,b∈A, a R b または b R a

8. 閉包の直観

関係 R に性質を強制的に追加した最小の関係を閉包と呼びます。

例:

  • 反射閉包: 全ての (a,a) を追加する
  • 推移閉包: 到達可能な関係を全て追加する

グラフの到達可能性は、辺関係の推移閉包として見られます。

9. 非例・誤解しやすい例

誤解1: 単射と全射を混同する

単射は「入力側が潰れない」性質、全射は「出力側を覆い尽くす」性質です。

誤解2: 同値関係と順序関係を混同する

同値関係は分類を作ります。順序関係は並びや包含関係を作ります。

誤解3: 反対称律と非対称を混同する

反対称律は a R b かつ b R a なら a=b という性質です。a R b なら b R a でない、という意味ではありません。

10. 接続問題

有限オートマトンの遷移関数は次の形で書かれます。

δ: Q × Σ → Q

これは、状態 q∈Q と入力記号 a∈Σ の組に対して、次状態 δ(q,a)∈Q を返す関数です。

一方、非決定性オートマトンでは次のような形になります。

δ: Q × Σ → P(Q)

ここで P(Q) は Q の冪集合です。つまり、次状態が1つではなく、状態集合として返ります。

演習

Level 1

  1. 関数 f: A → B における A と B の名前を答えよ。
  2. 単射、全射、全単射の定義を書け。
  3. 関係が同値関係であるための3条件を書け。
  4. 関係が半順序であるための3条件を書け。

Level 2

  1. f: ℤ → ℤ, f(n)=2n は単射か。全射か。
  2. g: ℤ → ℤ, g(n)=n+1 は全単射か。
  3. A={1,2,3} 上の関係 a R b ⇔ a=b は同値関係か。
  4. 集合族上の ⊆ が半順序であることを示せ。

Level 3

  1. a R b ⇔ a-b が偶数、で定義される整数上の関係が同値関係であることを示せ。
  2. 同値関係が集合を分割する理由を説明せよ。
  3. 有向グラフの到達可能性関係が推移的であることを示せ。

自己診断

次を説明できれば、この章は通過です。

  • 関数と一般の関係を区別できる。
  • 単射・全射・全単射の定義を量化記号で書ける。
  • 同値関係と半順序を区別できる。
  • 到達可能性を関係として説明できる。

次に読む章

Edit this page on GitHub