集合と写像

目的は，公理的集合論そのものではなく，そこで保証されている（気がする）道具を知ることだけなので，悪しからず．

集合

集まり

何かのもの（元(element)と呼ばれる）を集めたものを集まりと呼び，（自分の知る限り）以下の操作が許される．

集まりから，元をとってくる操作

集合

ZFC公理系を満たす集まりのことを集合(set)と呼ぶ．

空集合

元を持たない集合 $\exists \emptyset, \forall 𝑥, (𝑥 \notin \emptyset)$ が（一意的に）存在する．この $\emptyset$ を空集合(empty set)と呼ぶ．

冪集合

集合 $𝐴$ を与える．すべての部分集合の集合を冪集合(power set)と呼び， $2^{𝐴}$ と表す．

選択公理

集合の集合 $𝑋$ を与える．各元 $𝐴 \in 𝑋$ から元を一つずつとってきたものも集合になる，という公理のことを選択公理(axiom of choice)と言う．

写像

基本概念

写像

集合 $𝐴, 𝐵$ を与える．

$\forall 𝑎 \in 𝐴$ に対し， $𝑏 \in 𝐵$ を一つ対応させる．この対応規則を $𝑓 : 𝐴 \to 𝐵, 𝑎 \mapsto 𝑏$ のように表し，これを写像(mapping)と呼ぶ．
$\forall 𝑎 \in 𝐴$ に対して選んだ $𝑏 \in 𝐵$ のことを $𝑓 (𝑎) ≔ 𝑏$ と書く．
$𝐴$ を $𝑓$ の始域(domain)（または定義域）， $𝐵$ を $𝑓$ の終域(codomain)と呼ぶ．
特に $𝐴 = 𝐵$ のとき， $𝑓$ を $𝐴$ 上の写像，または変換(transformation)と呼ぶ．

写像の合成

集合 $𝐴, 𝐵, 𝐶$
写像 $𝑓 : 𝐴 \to 𝐵, 𝑔 : 𝐵 \to 𝐶$

を与える．

$𝑔 \circ 𝑓 : 𝐴 \to 𝐶, 𝑎 \mapsto 𝑔 (𝑓 (𝑎))$ $𝑓$ と $𝑔$ の合成（写像）(composition)と呼ぶ．

恒等写像

集合 $𝐴$ を与える．

$1_{𝐴} : 𝐴 \to 𝐴, 𝑎 \mapsto 𝑎$ を $𝐴$ 上の恒等写像(identity mapping)と呼ぶ．

集合の圏

対象を全ての集合
射を全ての写像
合成を写像の合成
恒等射を恒等写像

とする圏を集合の圏(category of sets)と呼び， $𝐒𝐞𝐭$ と表す．

濃度

集合の元の数を一般化した概念を濃度(cardinality)と呼ぶ．

冪集合上の写像

集合 $𝐴, 𝐵$
写像 $𝑓 : 𝐴 \to 𝐵$

を与える．

このとき $𝑓$ は，それぞれの冪集合に関する自然な写像 $2^{𝐴} \to 2^{𝐵}, 𝑋 \mapsto {𝑓 (𝑥) | 𝑥 \in 𝑋}$ を誘導する．この写像のことも（記号の濫用で） $𝑓$ と表す．

像

集合 $𝐴, 𝐵$ と写像 $𝑓 : 𝐴 \to 𝐵$ を与える．

$\forall 𝑎 \in 𝐴$ に対し， $𝑓 (𝑎)$ を $𝑎$ の $𝑓$ による像(image)と呼ぶ．

$\forall 𝑋 \in 2^{𝐴}$ に対し， $𝑓 (𝑋)$ を $𝑋$ の $𝑓$ による像(image)と呼ぶ．

$𝑓 (𝐴)$ のことを単に $𝑓$ の像(image)，または値域と呼ぶ．

特性函数

集合 $𝐴$ とその部分集合 $𝑋 \in 2^{𝐴}$ ，二元集合 ${0, 1}$ を与える．

このとき $𝑋$ は写像 $𝜒_{𝑋} : 𝐴 \to {0, 1}, 𝑥 \mapsto 𝜒_{𝑋} ≔ {\begin{matrix} 1 & 𝑥 \in 𝑋 \\ 0 & 𝑥 \notin 𝑋 \end{matrix}$ を誘導する．これを（ $𝐴$ 上の）特性函数(characteristic function)と呼ぶ．

逆に写像 $𝜒 : 𝐴 \to {0, 1}$ （これも特性函数と呼ばれる）を与えたとき， $𝑓^{- 1} (1) \in 2^{𝐴}$ であり， $𝜒 = 𝜒_{𝑓^{- 1} (1)}$ を満たす．つまり，特性函数と冪集合には一対一の関係がある．冪集合の2はこれが理由となる．

関係

関係，そして特に重要な同値関係を扱う．

定義

関係

集合 $𝐴, 𝐵$ を与える．

直積集合の部分集合 $𝑅 \in 2^{𝐴 \times 𝐵}$ に対し，記号 $\in$ の代わりに $\sim$ を用いて， $\begin{matrix} (𝑥, 𝑦) \in 𝑅 & \Leftrightarrow & 𝑥 \sim 𝑦 \\ (𝑥, 𝑦) \notin 𝑅 & \Leftrightarrow & 𝑥 ≁ 𝑦 \end{matrix}$ と表す． $\sim$ を（ $𝑅$ が誘導する） $𝐴$ と $𝐵$ の間の（二項）関係((binary) relation)と呼ぶ．

また， $𝑅$ を関係 $\sim$ のグラフ(graph)と呼ぶ．

特に， $𝐵 = 𝐴$ のとき， $𝐴$ 上の関係と呼ぶ．

関係の合成

集合 $𝐴, 𝐵, 𝐶$
$𝐴$ と $𝐵$ の関係 $\sim$
$𝐵$ と $𝐶$ の関係 $\sim^{'}$

を与える．

$\forall (𝑎, 𝑐) \in 𝐴 \times 𝐶, 𝑎 \sim^{'} \circ \sim 𝑐 \Leftrightarrow \exists 𝑏 \in 𝐵, 𝑎 \sim 𝑏 \sim^{'} 𝑐$ で定義される $𝐴$ と $𝐶$ の関係 $\sim \circ \sim^{'}$ を， $\sim$ と $\sim^{'}$ の合成(composition)と呼ぶ．

関係としての等号

集合 $𝐴, 𝐵$ を与える．

集合の元として等しいことを表す等号 $=_{𝐴, 𝐵}$ は，関係の合成に関する恒等射をなす．

つまり，任意の関係 $\sim$ に対し以下を満たす： $(\sim \circ =_{𝐴}) = \sim = (=_{𝐵} \circ \sim)$

関係の圏

対象を全ての集合
射を全ての関係
合成を関係の合成
恒等射を等号

とする圏を関係の圏(category of relations)と呼び， $𝐑𝐞𝐥$ と表す．

関係の誘導する写像

集合 $𝐴, 𝐵$
$𝐴, 𝐵$ の関係 $\sim$
$\sim$ のグラフ $𝑅$

を与えると，以下のような関係の誘導する写像()が定義できる．

$𝑅_{*} : 2^{𝐴} \to 2^{𝐵}, 𝑆 \mapsto {𝑏 \in 𝐵 | \exists 𝑠 \in 𝑆, 𝑠 \sim 𝑏}$
$𝑅^{*} : 2^{𝐴} \to 2^{𝐵}, 𝑆 \mapsto {𝑎 \in 𝐴 | \exists 𝑠 \in 𝑆, 𝑎 \sim 𝑠}$

関係の圏の分析(?)

空関係

集合 $𝐴$ を与える．

空集合 $\emptyset$ と $𝐴$ の関係， $𝐴$ と $\emptyset$ の関係は共に唯一．これを空関係(empty relation)と呼ぶ．

空関係は零対象

空関係は関係の圏の零対象

反対関係

集合 $𝐴, 𝐵$ を与える．

$𝐴$ と $𝐵$ の間の関係は，自然な $𝐵$ と $𝐴$ の間の関係 $𝑏 \sim^{op} 𝑎 \Leftrightarrow 𝑎 \sim 𝑏$ を誘導する．これを $\sim$ の反対関係(opposite/converse relation)と呼ぶ．

左右一意的・一対一

集合 $𝐴, 𝐵$ を与える．

𝐴と𝐵の間の関係 ∼ ∈ 𝐑𝐞𝐥 ⁡ ( 𝐴,𝐵 ) が左一意的(left-unique)であるとは，以下の同値な条件のいずれか（ゆえに全て）を満たすことを言う：
- $\forall 𝑎, 𝑎^{'} \in 𝐴, \forall 𝑏 \in 𝐵, (𝑎 \sim 𝑏 \cap 𝑎^{'} \sim 𝑏 \Rightarrow 𝑎 = 𝑎^{'})$
- $\sim$ の反対関係 $\sim^{op}$ に対し， $\forall 𝑎, 𝑎^{'} \in 𝐴, (𝑎 \sim^{op} \circ \sim 𝑎^{'} \Rightarrow 𝑎 = 𝑎^{'})$
- ∼op ∘ ∼ の誘導する写像 ( 𝑅op ∘ 𝑅 ) ∗ に対し，以下の同値な条件のいずれか（ゆえに全て）を満たす：
  - $\forall 𝑆 \in 2^{𝐴}, {(𝑅^{op} \circ 𝑅)}_{*} (𝑆) \subset 𝑆$
  - $\forall 𝑎 \in 𝐴, {(𝑅^{op} \circ 𝑅)}_{*} (𝑎) \subset {𝑎}$
  - $\forall 𝑎 \in 𝐴, {(𝑅^{op} \circ 𝑅)}_{*} (𝐴 ∖ {𝑎}) \subset 𝐴 ∖ {𝑎}$
𝐴と𝐵の間の関係 ∼ ∈ 𝐑𝐞𝐥 ⁡ ( 𝐴,𝐵 ) が右一意的(right-unique)であるとは，以下の同値な条件のいずれか（ゆえに全て）を満たすことを言う：
- $\forall 𝑏, 𝑏^{'} \in 𝐵, \forall 𝑎 \in 𝐴, (𝑎 \sim 𝑏 \cap 𝑎 \sim 𝑏^{'} \Rightarrow 𝑏 = 𝑏^{'})$
- $\sim$ の反対関係 $\sim^{op}$ に対し， $\forall 𝑏, 𝑏^{'} \in 𝐵, (𝑏 \sim \circ \sim^{op} 𝑏^{'} \Rightarrow 𝑏 = 𝑏^{'})$
- ∼ ∘ ∼op の誘導する写像 ( 𝑅 ∘ 𝑅op ) ∗ に対し，以下の同値な条件のいずれか（ゆえに全て）を満たす：
  - $\forall 𝑆 \in 2^{𝐵}, {(𝑅 \circ 𝑅^{op})}_{*} (𝑆) \subset 𝑆$
  - $\forall 𝑏 \in 𝐵, {(𝑅 \circ 𝑅^{op})}_{*} (𝑏) \subset {𝑏}$
  - $\forall 𝑏 \in 𝐵, {(𝑅 \circ 𝑅^{op})}_{*} (𝐵 ∖ {𝑏}) \subset 𝐵 ∖ {𝑏}$
左一意的かつ右一意的な関係を一対一(one-to-one)と呼ぶ．

ここでの一意的は，あくまで「存在すれば」一意である．

条件の同値性の証明

$\forall 𝑎 \in 𝐴, {(𝑅^{op} \circ 𝑅)}_{*} (𝐴 ∖ {𝑎}) \subset 𝐴 ∖ {𝑎}$ を満たすとする．このとき $𝑎 \sim^{op} \circ \sim 𝑎^{'}$ を仮定すると， $𝑎 \neq 𝑎^{'} \Rightarrow 𝑎^{'} \in {(𝑅^{op} \circ 𝑅)}_{*} (𝐴 ∖ {𝑎^{'}})$ となるから， $𝑎 = 𝑎^{'}$ ．

他の同値性は自明．

左右全域的・対応

集合 $𝐴, 𝐵$ を与える．

𝐴と𝐵の間の関係 ∼ ∈ 𝐑𝐞𝐥 ⁡ ( 𝐴,𝐵 ) が左全域的(left-entire, left-total)であるとは，以下の同値な条件のいずれか（ゆえに全て）を満たすことを言う：
- $\forall 𝑎 \in 𝐴, \exists 𝑏 \in 𝐵, 𝑎 \sim 𝑏$
- $\sim$ の反対関係 $\sim^{op}$ に対し， $\forall 𝑎 \in 𝐴, 𝑎 \sim^{op} \circ \sim 𝑎$
- ∼op ∘ ∼ の誘導する写像 ( 𝑅op ∘ 𝑅 ) ∗ に対し，以下の同値な条件のいずれか（ゆえに全て）を満たす：
  - $\forall 𝑆 \in 2^{𝐴}, 𝑆 \subset {(𝑅^{op} \circ 𝑅)}_{*} (𝑆)$
  - $\forall 𝑎 \in 𝐴, 𝑎 \in {(𝑅^{op} \circ 𝑅)}_{*} (𝑎)$
  - ${(𝑅^{op} \circ 𝑅)}_{*} (𝐴) = 𝐴$
𝐴と𝐵の間の関係 ∼ ∈ 𝐑𝐞𝐥 ⁡ ( 𝐴,𝐵 ) が右全域的(right-entire, right-total)であるとは，以下の同値な条件のいずれか（ゆえに全て）を満たすことを言う：
- $\forall 𝑏 \in 𝐵, \exists 𝑎 \in 𝐴, 𝑎 \sim 𝑏$
- $\sim$ の反対関係 $\sim^{op}$ に対し， $\forall 𝑏 \in 𝐵, 𝑏 \sim \circ \sim^{op} 𝑏$
- ∼ ∘ ∼op の誘導する写像 ( 𝑅 ∘ 𝑅op ) ∗ に対し，以下の同値な条件のいずれか（ゆえに全て）を満たす：
  - $\forall 𝑆 \in 2^{𝐵}, 𝑆 \subset {(𝑅 \circ 𝑅^{op})}_{*} (𝑆)$
  - $\forall 𝑏 \in 𝐵, 𝑏 \in {(𝑅 \circ 𝑅^{op})}_{*} (𝑏)$
  - ${(𝑅 \circ 𝑅^{op})}_{*} (𝐵) = 𝐵$
左全域的かつ右全域的な関係を対応(correspondence)と呼ぶ．

非一点集合との全域関係

関係 $\sim \in 𝐑𝐞𝐥 (𝐴, 𝐵)$ を与えると，以下が成り立つ：

𝐴 が一点集合でないとき，以下は同値：
- $\sim$ が左全域関係．
- $\forall 𝑎 \in 𝐴, {(𝑅^{op} \circ 𝑅)}_{*} (𝐴 ∖ {𝑎}) = 𝐴 ∖ {𝑎}, 𝐴$
𝐵 が一点集合でないとき，以下は同値：
- $\sim$ が右全域関係．
- $\forall 𝑏 \in 𝐵, {(𝑅 \circ 𝑅^{op})}_{*} (𝐵 ∖ {𝑏}) = 𝐵 ∖ {𝑏}, 𝐵$

条件の同値性の証明

一般に，左全域関係は，定義の一つより， $\forall 𝑎 \in 𝐴, {(𝑅^{op} \circ 𝑅)}_{*} (𝐴 ∖ {𝑎}) = 𝐴 ∖ {𝑎}, 𝐴$ を満たす．逆を示す．

$𝐴 = \emptyset$ のときの関係は空関係に限られるが，これは自明に左全域的．
$𝐴 \neq \emptyset$ かつ一点集合でもないとき， $\forall 𝑎 \in 𝐴, {(𝑅^{op} \circ 𝑅)}_{*} (𝐴 ∖ {𝑎}) = 𝐴 ∖ {𝑎}, 𝐴$ を満たすとする．このとき， $\forall 𝑎 \in 𝐴$ に対し， $(\forall 𝑏 \in 𝐵, 𝑎 ≁ 𝑏) \Rightarrow \forall 𝑎^{'} \in 𝐴 ∖ {𝑎}, 𝑎 \notin {(𝑅^{op} \circ 𝑅)}_{*} (𝐴 ∖ {𝑎^{'}})$ を満たすから， $\forall 𝑎 \in 𝐴, \exists 𝑏 \in 𝐵, 𝑎 \sim 𝑏$ ．

左右可逆関係

集合 $𝐴, 𝐵 \in ob (𝐑𝐞𝐥)$ を与える．

𝐴と𝐵の間の関係 ∼ ∈ 𝐑𝐞𝐥 ⁡ ( 𝐴,𝐵 ) で，以下の同値な条件のいずれか（ゆえに全て）を満たすものを左可逆(left-invertible)と呼ぶ．
- 左一意的かつ左全域的
- 反対関係 $\sim^{op}$ に対して以下を満たす： $\sim^{op} \circ \sim = =_{𝐴}$
- 関係の圏の分裂モノ射．つまり，以下を満たす： $\exists \sim^{'} \in 𝐑𝐞𝐥 (𝐵, 𝐴), \sim^{'} \circ \sim = =_{𝐴}$
- ∼op の誘導する写像 ( 𝑅op ∘ 𝑅 ) ∗ に対し，以下の同値な条件のいずれか（ゆえに全て）を満たす：
  - $\forall 𝑆 \in 2^{𝐴}, {(𝑅^{op} \circ 𝑅)}_{*} (𝑆) = 𝑆$
  - $\forall 𝑎 \in 𝐴, {(𝑅^{op} \circ 𝑅)}_{*} (𝑎) = {𝑎}$
𝐴と𝐵の間の関係 ∼ ∈ 𝐑𝐞𝐥 ⁡ ( 𝐴,𝐵 ) で，以下の同値な条件のいずれか（ゆえに全て）を満たすものを右可逆(right-invertible)と呼ぶ．
- 右一意的かつ右全域的
- 反対関係 $\sim^{op}$ に対して以下を満たす： $\sim \circ \sim^{op} = =_{𝐵}$
- 関係の圏の分裂エピ射．つまり，以下を満たす： $\exists \sim^{'} \in 𝐑𝐞𝐥 (𝐵, 𝐴), \sim \circ \sim^{'} = =_{𝐵}$
- ∼ ∘ ∼op の誘導する写像 ( 𝑅 ∘ 𝑅op ) ∗ に対し，以下の同値な条件のいずれか（ゆえに全て）を満たす：
  - $\forall 𝑆 \in 2^{𝐵}, {(𝑅 \circ 𝑅^{op})}_{*} (𝑆) = 𝑆$
  - $\forall 𝑏 \in 𝐵, {(𝑅 \circ 𝑅^{op})}_{*} (𝑏) = {𝑏}$

条件の同値性の証明

左可逆の方を示す．

$\sim$ の左一意性の左全域性を仮定する． $\sim^{op}$ が右全域的であることに注意すると， $\forall 𝑎 \in 𝐴$ に対し， $\forall 𝑎^{'} \in 𝐴, \exists 𝑏 \in 𝐵, 𝑎 \sim 𝑏 \sim^{op} 𝑎^{'} \Leftrightarrow 𝑎 = 𝑎^{'}$ が成り立つから， $\sim^{op} \circ \sim = =_{𝐴}$ を満たす．
$\sim^{op} \circ \sim = =_{𝐴}$ であれば，定義より自明に関係の圏の分裂モノ射．
関係の圏の分裂モノ射になるとすると，
- $𝑎 \sim 𝑏, 𝑎^{'} \sim 𝑏$ のとき， $𝑎 \sim^{op} \circ \sim 𝑎^{'}$ より， $𝑎 = 𝑎^{'}$ ．つまり左一意関係．
- $\sim$ が左全域的でないと， $\sim^{'} \circ \sim = =_{𝐴}$ に矛盾．
他は自明．

非一点集合との可逆関係

関係 $\sim \in 𝐑𝐞𝐥 (𝐴, 𝐵)$ を与えると，以下が成り立つ：

𝐴 が一点集合でないとき，以下は同値：
- $\sim$ が左可逆関係．
- $\forall 𝑎 \in 𝐴, {(𝑅^{op} \circ 𝑅)}_{*} (𝐴 ∖ {𝑎}) = 𝐴 ∖ {𝑎}$
𝐵 が一点集合でないとき，以下は同値：
- $\sim$ が右可逆関係．
- $\forall 𝑏 \in 𝐵, {(𝑅 \circ 𝑅^{op})}_{*} (𝐵 ∖ {𝑏}) = 𝐵 ∖ {𝑏}$

証明

左可逆関係の定義，左一意関係の定義，および非一点集合との左全域関係の別定義より自明．

関係の圏のモノ射・エピ射

集合 $𝐴, 𝐵$
$𝐴, 𝐵$ の関係 $\sim$
$\sim$ のグラフ $𝑅$

を与える．

以下の同値な条件のいずれか（ゆえに全て）を満たすとき，∼をモノ関係(monic relatoin)と呼ぶ．
- $\sim$ の誘導する写像 $𝑅_{*}$ が単射．
- 関係の圏のモノ射．つまり，以下を満たす． $\forall 𝐶 \in ob (𝐑𝐞𝐥), \forall \sim_{1}, \sim_{2} \in 𝐑𝐞𝐥 (𝐶, 𝐴), \sim \circ \sim_{1} = \sim \circ \sim_{2} \Rightarrow \sim_{1} = \sim_{2}$
以下の同値な条件のいずれか（ゆえに全て）を満たすとき，∼をエピ関係(epic relation)と呼ぶ．
- $\sim$ の誘導する写像 $𝑅^{*}$ が単射．
- 関係の圏のエピ射．つまり，以下を満たす． $\forall 𝐶 \in ob (𝐑𝐞𝐥), \forall \sim_{1}, \sim_{2} \in 𝐑𝐞𝐥 (𝐵, 𝐶), \sim_{1} \circ \sim = \sim_{2} \circ \sim \Rightarrow \sim_{1} = \sim_{2}$

条件の同値性の証明

$𝑅_{*}$ が単射のとき，
関係の圏のモノ射のとき，

証明

関係 $\sim \in 𝐑𝐞𝐥 (𝐴, 𝐵)$ が左全域関係でないと仮定すると， $\sim$ の誘導する写像 $𝑅_{*}$ に対し， $\exists 𝑎 \in 𝐴, 𝑅_{*} ({𝑎}) = \emptyset = 𝑅_{*} (\emptyset)$ を満たすから， $𝑅_{*}$ は単射でない．つまり $\sim$ はモノ関係でない．

一対一対応・可逆関係

集合 $𝐴, 𝐵$ を与える．

$𝐴$ と $𝐵$ の間の関係 $\sim \in 𝐑𝐞𝐥 (𝐴, 𝐵)$ で，以下の同値な条件のいずれか（ゆえに全て）を満たすものを一対一対応(one-to-one correspondence)，可逆関係(invertible relation)，同型関係(isomorphic relation)等と呼ぶ：

反対関係 $\sim^{op}$ に対し，以下を満たす： $\sim^{op} \circ \sim = =_{𝐴}, \sim \circ \sim^{op} = =_{𝐵}$
関係の圏の同型射．つまり以下を満たす： $\exists! \sim^{- 1} \in 𝐑𝐞𝐥 (𝐵, 𝐴), \sim^{- 1} \circ \sim = =_{𝐴}, \sim \circ \sim^{- 1} = =_{𝐴}$
一対一の対応．同じことだが左可逆かつ右可逆
関係の誘導する写像 $𝑅_{*}$ が全単射
関係の誘導する写像 $𝑅^{*}$ が全単射
モノ関係かつエピ関係

$\sim^{- 1} = \sim^{op}$ のことを $\sim$ の逆関係(inverse relation)と呼ぶ．

関係の圏は均衡圏

条件の同値性の証明

同値性が非自明なのは，モノ関係かつエピ関係のとき，他の条件を満たすことくらいだろう．それを示す．

モノ関係は左全域的なので，左全域関係の定義より， $\forall 𝑎 \in 𝐴$ に対し， ${(𝑅^{op} \circ 𝑅)}_{*} (𝐴 ∖ 𝑎) = 𝐴 ∖ 𝑎, 𝐴$ および ${(𝑅^{op} \circ 𝑅)}_{*} (𝐴) = 𝐴$ を満たす．ここで，関係 $\sim$ がエピ関係であることは，反対関係 $\sim^{op}$ がモノ関係であることと同値だから， ${𝑅^{op}}_{*} \circ 𝑅_{*} = {(𝑅^{op} \circ 𝑅)}_{*}$ は単射．よって， ${(𝑅^{op} \circ 𝑅)}_{*} (𝐴 ∖ {𝑎}) = 𝐴 ∖ {𝑎}$ となり， $\sim$ は左一意関係となる． $\sim$ が左全域関係となることと合わせて， $\sim$ は左可逆．同様にして右可逆となる．

関係の合併

集合 $𝐴, 𝐵$ ， $𝐴$ と $𝐵$ の関係 $\sim, \sim^{'}$ とそれぞれのグラフ $𝑅, 𝑅^{'}$ を与える．

$𝑅 \cup 𝑅^{'}$ が誘導する関係を， $\sim$ と $\sim^{'}$ の合併(union)と呼び， $\sim \cup \sim^{'}$ と表す．

関係の交叉

集合 $𝐴, 𝐵$ ， $𝐴$ と $𝐵$ の関係 $\sim, \sim^{'}$ とそれぞれのグラフ $𝑅, 𝑅^{'}$ を与える．

$𝑅 \cap 𝑅^{'}$ が誘導する関係を， $\sim$ と $\sim^{'}$ の交叉(intersection)と呼び， $\sim \cap \sim^{'}$ と表す．

関係の差

集合 $𝐴, 𝐵$ ， $𝐴$ と $𝐵$ の関係 $\sim, \sim^{'}$ とそれぞれのグラフ $𝑅, 𝑅^{'}$ を与える．

$𝑅 ∖ 𝑅^{'}$ が誘導する関係を， $\sim$ と $\sim^{'}$ の差()と呼び， $\sim ∖ \sim^{'}$ と表す．

集合上の関係

とりあえず名前のついた特別な関係を確認する．

反射関係

集合 $𝐴$ を与える．

$𝐴$ 上の関係 $\sim$ で，以下を満たすものを反射関係(reflexive relation)と呼ぶ．

$\forall 𝑎 \in 𝐴, 𝑎 \sim 𝑎$

$𝐴$ 上の関係 $\sim$ で，以下を満たすものを非反射関係(irreflexive relation)と呼ぶ．

$\forall 𝑎 \in 𝐴, 𝑎 ≁ 𝑎$

対称関係

集合 $𝐴$ を与える．

$𝐴$ 上の関係 $\sim$ で，以下を満たすものを対称関係(symmetric relation)と呼ぶ．

$\forall 𝑎, 𝑏 \in 𝐴, 𝑎 \sim 𝑏 \Rightarrow 𝑏 \sim 𝑎$

$𝐴$ 上の関係 $\sim$ で，以下を満たすものを反対称関係(antisymmetric relation)と呼ぶ．

$\forall 𝑎, 𝑏 \in 𝐴, 𝑎 \sim 𝑏 \cap 𝑏 \sim 𝑎 \Rightarrow 𝑎 = 𝑏$

$𝐴$ 上の関係 $\sim$ で，以下を満たすものを非対称関係(asymmetric relation)と呼ぶ．

$\forall 𝑎, 𝑏 \in 𝐴, 𝑎 \sim 𝑏 \Rightarrow 𝑏 ≁ 𝑎$

非対称関係の性質

非対称関係は，非反射関係かつ反対称関係

推移関係

集合 $𝐴$ を与える．

$𝐴$ 上の関係 $\sim$ で，以下を満たすものを推移関係(transitive relation)と呼ぶ．

$\forall 𝑎, 𝑏, 𝑐 \in 𝐴, 𝑎 \sim 𝑏, 𝑏 \sim 𝑐 \Rightarrow 𝑎 \sim 𝑐$

$𝐴$ 上の関係 $\sim$ で，以下を満たすものを非推移関係(intransitive relation)と呼ぶ．

$\forall 𝑎, 𝑏, 𝑐 \in 𝐴, 𝑎 \sim 𝑏, 𝑏 \sim 𝑐 \Rightarrow 𝑎 ≁ 𝑐$

完全関係

集合 $𝐴$ を与える．

$𝐴$ 上の関係 $\sim$ で，以下を満たすものを完全関係(total relation)と呼ぶ．

$\forall 𝑎, 𝑏 \in 𝐴, 𝑎 \sim 𝑏 または 𝑏 \sim 𝑎$

以上のうちいくつかを同時に満たすこともある．多くが関係の代わりに順序と呼ばれ，それらは順序理論で扱う（希望的観測）．もう一つ重要なのが同値関係で，あとで扱っている．

閉包と簡約

関係 $\sim$ に対し，適当な関係を合併することで，上に挙げたような性質を満たすようにできる．このうち最小のもの（そのような関係全ての交叉）を閉包(closure)と呼ぶ．

具体的には以下がある．

反射閉包

集合 $𝐴$ ， $𝐴$ 上の関係 $\sim$ を与える．

$\sim^{=} ≔ \sim \cup =$ と定義される関係を $\sim$ の反射閉包(reflexive closure)と呼ぶ．

対称閉包

集合 $𝐴$ ， $𝐴$ 上の関係 $\sim$ を与える．

$\sim$ とその反対関係の合併 $\sim \cup \sim^{op}$ で定義される関係を $\sim$ の対称閉包(symmetric closure)と呼ぶ．

推移閉包

集合 $𝐴$ ， $𝐴$ 上の関係 $\sim$ を与える．

$⋃_{𝑛 = 1}^{\infty} \sim^{\circ 𝑛}$ で定義される関係を $\sim$ の推移閉包(transitive closure)と呼ぶ．

逆に，関係 $\sim$ に，適当な関係との交叉または差をとることで，上に挙げたような性質を満たすようにできる．このうち最大のもの（そのような関係全ての合併）を簡約(reduction)と呼ぶ．

具体的には以下がある．

非反射簡約

集合 $𝐴$ ， $𝐴$ 上の関係 $\sim$ を与える．

$\sim^{\neq} ≔ \sim ∖ =$ と定義される関係を $\sim$ の非反射簡約(irreflexive reduction)と呼ぶ．

非推移簡約

集合 $𝐴$ ， $𝐴$ 上の関係 $\sim$ ， $\sim$ のグラフ $𝑅$ を与える．

閉包と簡約の関係

反射閉包は，非反射簡約の反射閉包に等しい．
推移閉包は，非推移簡約の推移閉包に等しい．

同値関係と商集合

分割

集合 $𝐴$ を与える．

部分集合の集合 $𝑃 \subset 2^{𝐴}$ が $𝐴$ の分割(partition)であるとは，以下を満たすことをいう．

$\emptyset \notin 𝑃$
$⋃_{𝑋 \in 𝑃} 𝑋 = 𝐴$
$\forall 𝑋, 𝑌 \in 𝐴, 𝑋 \neq 𝑌 \Rightarrow 𝑋 \cap 𝑌 = \emptyset$

分割の分割っぽさ

集合 $𝐴$ とその分割 $𝑃$ を与えると，以下が成り立つ．

$\forall 𝑎 \in 𝐴, \exists! 𝑋 \in 𝑃, 𝑎 \in 𝑋$

分割ないしは「類別」の定義としては妥当だろうが，分割になっているかの判定に使うには，抽象度が高い．応用上便利な方法は，関係を使う方法である．その準備をしよう．

同値関係

集合 $𝐴$ を与える．

$𝐴$ 上の関係 $\sim$ で，以下を満たすものを同値関係(equivalence relation)と呼ぶ．

反射律: $\forall 𝑎 \in 𝐴, 𝑎 ~ 𝑎$
対称律: $\forall 𝑎, 𝑏 \in 𝐴, 𝑎 \sim 𝑏 \Rightarrow 𝑏 \sim 𝑎$
推移律: $\forall 𝑎, 𝑏 \in 𝐴, 𝑎 \sim 𝑏 または 𝑏 \sim 𝑎$

同値類・商集合

集合 $𝐴$ と同値関係 $\sim$ を与える．

$𝑎 \in 𝐴$ に対し， $[𝑎] ≔ {𝑥 \in 𝑆 | 𝑎 \sim 𝑥}$ を $𝑎$ の $\sim$ による同値類と呼ぶ．

すべての同値類の集合を $𝑆 ∕ \sim ≔ {[𝑎] | 𝑎 \in 𝑆}$ と表し，商集合と呼ぶ．

∼が誘導する写像 $𝐴 \to 𝐴 ∕ \sim : 𝑎 \mapsto [𝑎]$ を標準射影canonical projection)と呼ぶ．

同値類と分割は本質的に等価

商集合は分割であり，これらは一対一に対応する．

同型定理

核対? 等化子?

定義より明らかだが，一応代数学的な同型定理は以下となる．

同型定理

集合 $𝐴, 𝐵$ とをの間の写像 $𝑓 : 𝐴 \to 𝐵$ を与えると，以下が成り立つ．

$𝑓$ の核対?は $𝐴$ の商集合．
$𝑓$ の像 $𝑓 (𝐴)$ は $𝐵$ の部分集合．
$𝑓$ の核対?と $𝑓$ の像 $𝑓 (𝐴)$ は自然な全単射をもつ．特に等濃．

最後に，時々使う同値閉包を明示しておく．

同値閉包

集合 $𝐴$ ， $𝐴$ 上の関係 $\sim$ を与える．

$\sim$ の反射閉包の推移閉包の対称閉包 $⋃_{𝑛 = 0}^{\infty} {(\sim \cup \sim^{op})}^{\circ 𝑛}$ を同値閉包(equivalence closure)と呼ぶ．