集合と写像

写像

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

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

写像の合成

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

を与える．

$𝑓$ と $𝑔$ の合成（写像）(composition)とは，以下の写像のこと： $$𝑔\circ 𝑓:𝐴\to 𝐶,𝑎\mapsto 𝑔\left(𝑓\left(𝑎\right)\right)$$

恒等写像

集合$𝐴$を与える．

$𝐴$ 上の恒等写像(identity mapping)とは，以下の写像のこと： $$1_{𝐴}:𝐴\to 𝐴,𝑎\mapsto 𝑎$$

集合の圏

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

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

濃度

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

冪集合上の写像

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

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

像

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

を与える．

• $𝑎\in 𝐴$ の $𝑓$ による像(image)とは， $𝑓\left(𝑎\right)$ のこと．
• $𝑋\subset 𝐴$ の $𝑓$ による像(image)とは， $𝑓\left(𝑋\right)$ のこと．
• $𝑓\left(𝐴\right)$ のことを単に$𝑓$の像(image)，または値域と呼ぶ．

原像

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

を与える．

$𝑓$ に対し，写像 $${𝑓}^{-1}:𝐵\to 2^{𝐴},𝑏\mapsto \left\{𝑎\in 𝐴|𝑓\left(𝑎\right)=𝑏\right\}$$ および自然に誘導される写像 $𝑓:2^{𝐵}\to 2^{𝐴}$ が定まる．

• $𝑏\in 𝐵$ の $𝑓$ による原像(preimage)や逆像(inverse image)とは， ${𝑓}^{-1}\left(𝑏\right)$ のこと．
• $𝑌\subset 𝐵$ の $𝑓$ による原像(preimage)や逆像(inverse image)とは， ${𝑓}^{-1}\left(𝑌\right)$ のこと．
• ${𝑓}^{-1}\left(𝑌\right)$ のことを単に $𝑓$ の原像(preimage)や逆像(inverse image)と呼ぶ．

特性函数

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

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

直積

• 集合$𝛬$
• 集合の集合 ${\left\{{𝐴}_{𝜆}\right\}}_{𝜆\in 𝛬}$

を与える．

• ${\left\{{𝐴}_{𝜆}\right\}}_{𝜆\in 𝛬}$ の直積(direct product)とは，以下のデータのこと：
  • 集合 $\prod _{𝜆\in 𝛬}{𝐴}_{𝜆}≔\left\{{\left({𝑎}_{𝜆}\right)}_{𝜆\in 𝛬}|{𝑎}_{𝜆}\in {𝐴}_{𝜆}\right\}$
  • 自然な全射の集合 ${\left\{{𝜋}_{𝜆}:\prod _{𝜆\in 𝛬}{𝐴}_{𝜆}\to {𝐴}_{𝜆},{\left({𝑎}_{𝜆}\right)}_{𝜆\in 𝛬}\mapsto {𝑎}_{𝜆}\right\}}_{𝜆\in 𝛬}$
• 集合$𝐵$を始域とする写像の集合 ${\left\{{𝑓}_{𝜆}:𝐵\to {𝐴}_{𝜆}\right\}}_{𝜆\in 𝛬}$ の直積(direct product)とは，以下の写像のこと： $$\prod _{𝜆\in 𝛬}{𝑓}_{𝜆}:𝐵\to \prod _{𝜆\in 𝛬}{𝐴}_{𝜆},𝑥\mapsto {\left({𝑓}_{𝜆}\left(𝑥\right)\right)}_{𝜆\in 𝛬}$$

直和

• 集合$𝛬$
• 集合の集合 ${\left\{{𝐴}_{𝜆}\right\}}_{𝜆\in 𝛬}$

を与える．

• ${\left\{{𝐴}_{𝜆}\right\}}_{𝜆\in 𝛬}$ の直和(direct product)とは，以下のデータのこと：
  • 集合 $\coprod _{𝜆\in 𝛬}{𝐴}_{𝜆}≔\bigcup _{𝜆\in 𝛬}\left({𝐴}_{𝜆}\Pi \left\{𝜆\right\}\right)$
  • 自然な単射の集合 ${\left\{{𝜄}_{𝜆}:{𝐴}_{𝜆}\to \coprod _{𝜆\in 𝛬}{𝐴}_{𝜆},𝑎\mapsto \left(𝑎,𝜆\right)\right\}}_{𝜆\in 𝛬}$
• 集合$𝐵$を終域とする写像の集合 ${\left\{{𝑓}_{𝜆}:{𝐴}_{𝜆}\to 𝐵\right\}}_{𝜆\in 𝛬}$ の直和(direct product)とは，以下の写像のこと： $${𝑓}_{𝜆}:\coprod _{𝜆\in 𝛬}{𝐴}_{𝜆}\to 𝐵,\left(𝑎,𝜆\right)\mapsto {𝑓}_{𝜆}\left(𝑎\right)$$

等化子

• 集合$𝛬,𝐴,𝐵$
• 写像の集合 ${\left\{{𝑓}_{𝜆}:𝐴\to 𝐵\right\}}_{𝜆\in 𝛬}$

を与える．

${\left\{{𝑓}_{𝜆}\right\}}_{𝜆\in 𝛬}$ の等化子(equalizer)とは，以下のデータのこと：

• $𝐴$の部分集合 $\mathrm{eq}\left({\left\{{𝑓}_{𝜆}\right\}}_{𝜆\in 𝛬}\right)≔\left\{𝑎\in 𝐴|\forall 𝜆,{𝜆}^{\prime }\in 𝛬,{𝑓}_{𝜆}\left(𝑎\right)={𝑓}_{{𝜆}^{\prime }}\left(𝑎\right)\right\}$
• 自然な包含写像 $𝜄:\mathrm{eq}\left({\left\{{𝑓}_{𝜆}\right\}}_{𝜆\in 𝛬}\right)\hookrightarrow 𝐴$

引き戻し

• 集合$𝛬,𝐵$
• 集合の集合 ${\left\{{𝐴}_{𝜆}\right\}}_{𝜆\in 𝛬}$ とその直積 $\left(\prod _{𝜆\in 𝛬}{𝐴}_{𝜆},{𝜋}_{𝜆}\right)$
• 写像の集合 ${\left\{{𝑓}_{𝜆}:{𝐴}_{𝜆}\to 𝐵\right\}}_{𝜆\in 𝛬}$

を与える．

${\left\{{𝑓}_{𝜆}\right\}}_{𝜆\in 𝛬}$ の引き戻し(pullback)とは，写像の集合 ${\left\{{𝑓}_{𝜆}\circ {𝜋}_{𝜆}:\prod _{𝜆\in 𝛬}{𝐴}_{𝜆}\to 𝐵\right\}}_{𝜆\in 𝛬}$ の等化子のこと．明示的には以下のデータのこと：

• 集合 $\mathrm{pull}\left({\left\{{𝑓}_{𝜆}\right\}}_{𝜆\in 𝛬}\right)≔\left\{{\left({𝑥}_{𝜆}\right)}_{𝜆\in 𝛬}\in \prod _{𝜆\in 𝛬}{𝐴}_{𝜆}|\forall 𝜆,{𝜆}^{\prime }\in 𝛬,{𝑓}_{𝜆}\left({𝑥}_{𝜆}\right)={𝑓}_{{𝜆}^{\prime }}\left({𝑥}_{{𝜆}^{\prime }}\right)\right\}$
• 写像の集合 ${{𝜋}_{𝜆}|}_{\mathrm{pull}\left({\left\{{𝑓}_{𝜆}\right\}}_{𝜆\in 𝛬}\right)}:\mathrm{pull}\left({\left\{{𝑓}_{𝜆}\right\}}_{𝜆\in 𝛬}\right)\to {𝐴}_{𝜆},{\left({𝑎}_{𝜆}\right)}_{𝜆\in 𝛬}\mapsto {𝑎}_{𝜆}$

単射

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

写像 $𝑓:𝐴\to 𝐵$ が単射(injective)であるとは，以下の同値な条件のいずれか（ゆえに全て）を満たすことを言う：

• $\forall 𝑥,𝑦\in 𝐴,𝑓\left(𝑥\right)=𝑓\left(𝑦\right)\Rightarrow 𝑥=𝑦$
• 集合の圏のモノ射．つまり，
  • 任意の集合 $𝐶$
  • 任意の写像 $𝑔,ℎ:𝐶\to 𝐴$
  に対し，以下を満たす： $$𝑓\circ 𝑔=𝑓\circ ℎ\Rightarrow 𝑔=ℎ$$
• 集合の圏の有効モノ射．つまり，余核対の等化子は $\left(𝐴,𝑓\right)$．
• 集合の圏の分裂モノ射．つまり，写像 ${𝑓}^{\prime }:𝐵\to 𝐴$ が存在し，以下を満たす： $${𝑓}^{\prime }\circ 𝑓={\mathrm{id}}_{𝐴}$$

全射

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

写像 $𝑓:𝐴\to 𝐵$ が全射(surjective)であるとは，以下の同値な条件のいずれか（ゆえに全て）を満たすことを言う：

• $𝑓$ の像は終域に等しい： $𝑓\left(𝐴\right)=𝐵$
• 集合の圏のエピ射．つまり，
  • 任意の集合 $𝐶$
  • 任意の写像 $𝑔,ℎ:𝐵\to 𝐶$
  に対し，以下を満たす： $$𝑔\circ 𝑓=ℎ\circ 𝑓\Rightarrow 𝑔=ℎ$$
• 集合の圏の有効エピ射．つまり，核対の余等化子は $𝐵$で，その余射影は $𝑓$．

分裂エピ射

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

写像 $𝑓:𝐴\to 𝐵$ が（集合の圏の）分裂エピ射(split epimorphism)であるとは，切断(section)と呼ばれる写像 ${𝑓}^{\prime }:𝐵\to 𝐴$ が存在し，以下を満たすことを言う： $$𝑓\circ {𝑓}^{\prime }={\mathrm{id}}_{𝐵}$$

全単射

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

写像 $𝑓:𝐴\to 𝐵$ 全単射（または双射(bijection)，可逆(invertible)）とは，以下の同値な条件のいずれか（ゆえに全て）を満たすことを言う：

• 全射かつ単射
• 集合の圏の同型射．つまり，写像 ${𝑓}^{\prime }:𝐵\to 𝐴$ が一意的に存在し，以下を満たす： $${𝑓}^{\prime }\circ 𝑓={\mathrm{id}}_{𝐴},𝑓\circ {𝑓}^{\prime }={\mathrm{id}}_{𝐵}$$

関係

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

• 直積集合の部分集合 $𝑅\in 2^{𝐴\times 𝐵}$ に対し，記号$\in$の代わりに$\sim$を用いて， $$\begin{array}{ccc}\left(𝑥,𝑦\right)\in 𝑅& \iff & 𝑥\sim 𝑦\\ \left(𝑥,𝑦\right)\notin 𝑅& \iff & 𝑥\nsim 𝑦\end{array}$$ と表す．$\sim$を（$𝑅$が誘導する）$𝐴$と$𝐵$の間の（二項）関係((binary) relation)と呼ぶ．
• また，$𝑅$を関係$\sim$のグラフ(graph)と呼ぶ．
• 特に，$𝐵=𝐴$のとき，$𝐴$上の関係と呼ぶ．
• • 集合 $𝐴$
  • $𝐴$ 上の関係 $\sim$
  の組のことを関係付き集合と呼ぶ．

関係の合成

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

を与える．

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

関係の圏

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

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

関係の誘導する写像

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

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

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

関係を保つ写像

関係付き集合 $\left(𝐴,\sim \right),\left({𝐴}^{\prime },{\sim }^{\prime }\right)$ を与える．

• $\left(𝐴,\sim \right)$ から $\left({𝐴}^{\prime },{\sim }^{\prime }\right)$ への関係を保つ写像(relation-preserving map)とは，写像 $𝑓:𝐴\to {𝐴}^{\prime }$ であって，以下を満たすものを言う： $$\forall 𝑎,𝑏\in 𝐴,\left(𝑎\sim 𝑏\Rightarrow 𝑓\left(𝑎\right){\sim }^{\prime }𝑓\left(𝑏\right)\right)$$
• $\left(𝐴,\sim \right)$ から $\left({𝐴}^{\prime },{\sim }^{\prime }\right)$ への関係を逆にする写像(relation-reversing map)とは，写像 $𝑓:𝐴\to {𝐴}^{\prime }$ であって，以下を満たすものを言う： $$\forall 𝑎,𝑏\in 𝐴,\left(𝑎\sim 𝑏\Rightarrow 𝑓\left(𝑏\right){\sim }^{\prime }𝑓\left(𝑎\right)\right)$$
• $\left(𝐴,\sim \right)$ から $\left({𝐴}^{\prime },{\sim }^{\prime }\right)$ への関係を反映する(relation-reflecting)とは，写像 $𝑓:𝐴\to {𝐴}^{\prime }$ であって，以下を満たすものを言う： $$\forall 𝑎,𝑏\in 𝐴,\left(𝑓\left(𝑎\right){\sim }^{\prime }𝑓\left(𝑏\right)\Rightarrow 𝑎\sim 𝑏\right)$$
• $\left(𝐴,\sim \right)$ から $\left({𝐴}^{\prime },{\sim }^{\prime }\right)$ への関係埋め込み(order embedding)とは，写像 $𝑓:𝐴\to {𝐴}^{\prime }$ であって，以下を満たすものを言う： $$\forall 𝑎,𝑏\in 𝐴,\left(𝑎\sim 𝑏\iff 𝑓\left(𝑎\right){\sim }^{\prime }𝑓\left(𝑏\right)\right)$$
• $\left(𝐴,\sim \right)$ から $\left({𝐴}^{\prime },{\sim }^{\prime }\right)$ への関係同型(order isomorphism)とは，全射な関係埋め込み $𝑓:𝐴\to {𝐴}^{\prime }$ のこと．

関係と写像の圏

関係と関係を保つ写像の圏()とは，以下で定義される圏のこと：

• 対象を任意の関係付き集合
• 射を任意の関係を保つ写像
• 合成を写像の合成

関係の制限

• 集合 $𝐴,𝐵$
• それぞれの部分集合 $𝑆\subset 𝐴,𝑇\subset 𝐵$

を与える．

• $𝐴$ と $𝐵$ の関係 $\sim$ の $𝑆\Pi 𝑇$ への制限()とは，$\sim$ のグラフ $𝑅$ に対する $𝑅\cap 𝑆\Pi 𝑇\subset 𝑆\Pi 𝑇$ が誘導する $𝑆$ と $𝑇$ の関係のこと．
• $𝐴$ 上の関係 $\sim$ の $𝑆$ への制限()とは，$\sim$ のグラフ $𝑅$ に対する $𝑅\cap 𝑆\Pi 𝑆\subset 𝑆\Pi 𝑆$ が誘導する $𝑆$ 上の関係のこと．

反対関係

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

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

左右一意的・一対一

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

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

左右全域的・対応

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

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

左右可逆関係

集合$𝐴,𝐵\in \mathrm{ob}\left(\mathrm{𝐑𝐞𝐥}\right)$を与える．

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

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

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

を与える．

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

一対一対応・可逆関係

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

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

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

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

双積

• 集合$𝛬$
• 集合の集合 ${\left\{{𝐴}_{𝜆}\right\}}_{𝜆\in 𝛬}$

を与える．

• ${\left\{{𝐴}_{𝜆}\right\}}_{𝜆\in 𝛬}$ の双積(biproduct)（または（関係に関する）直和(direct sum)）とは，以下のデータのこと：
  • 集合の直和 $\coprod _{𝜆\in 𝛬}{𝐴}_{𝜆}$
  • 自然な$\coprod _{𝜆\in 𝛬}{𝐴}_{𝜆}$ と ${𝐴}_{𝜆}$ の間の右可逆関係の集合 ${\left\{\left({𝑎}^{\prime },{𝜆}^{\prime }\right){\sim }_{𝜆}^{\mathrm{R}}𝑎\iff {𝑎}^{\prime }=𝑎\cap {𝜆}^{\prime }=𝜆\right\}}_{𝜆\in 𝛬}$
  • ${\sim }_{𝜆}^{\mathrm{L}}$ の反対関係（つまり${𝐴}_{𝜆}$ と $\coprod _{𝜆\in 𝛬}{𝐴}_{𝜆}$ の間の左可逆関係）の集合 ${\left\{𝑎{\sim }_{𝜆}^{\mathrm{L}}\left({𝑎}^{\prime },{𝜆}^{\prime }\right)\iff 𝑎={𝑎}^{\prime }\cap 𝜆={𝜆}^{\prime }\right\}}_{𝜆\in 𝛬}$
• 集合$𝐵$に対し，$𝐵$ と ${𝐴}_{𝜆}$ の間の関係の集合 ${\left\{{\sim }_{𝜆}\in \mathrm{𝐑𝐞𝐥}\left(𝐵,{𝐴}_{𝜆}\right)\right\}}_{𝜆\in 𝛬}$ の双積(biproduct)（または直和(direct sum)とは，以下で定義される $𝐵$ と $\coprod _{𝜆\in 𝛬}{𝐴}_{𝜆}$ の間の関係のこと： $$𝑏\sim \left(𝑎,𝜆\right)\iff 𝑏{\sim }_{𝜆}𝑎$$
• 集合$𝐵$に対し，${𝐴}_{𝜆}$ と $𝐵$ の間の関係の集合 ${\left\{{\sim }_{𝜆}\in \mathrm{𝐑𝐞𝐥}\left({𝐴}_{𝜆},𝐵\right)\right\}}_{𝜆\in 𝛬}$ の双積(biproduct)（または直和(direct sum)とは，以下で定義される $\coprod _{𝜆\in 𝛬}{𝐴}_{𝜆}$ と $𝐵$ の間の関係のこと： $$\left(𝑎,𝜆\right)\sim 𝑏\iff 𝑎{\sim }_{𝜆}𝑏$$

関係の合併

• 集合 $𝐴,𝐵$
• $𝐴$ と $𝐵$ の関係 $\sim ,{\sim }^{\prime }$
• $\sim ,{\sim }^{\prime }$ それぞれのグラフ $𝑅,{𝑅}^{\prime }$

を与える．

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

関係の交叉

• 集合 $𝐴,𝐵$
• $𝐴$ と $𝐵$ の関係 $\sim ,{\sim }^{\prime }$
• $\sim ,{\sim }^{\prime }$ それぞれのグラフ $𝑅,{𝑅}^{\prime }$

を与える．

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

関係の差

• 集合 $𝐴,𝐵$
• $𝐴$ と $𝐵$ の関係 $\sim ,{\sim }^{\prime }$
• $\sim ,{\sim }^{\prime }$ それぞれのグラフ $𝑅,{𝑅}^{\prime }$

を与える．

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

関係の包含関係

• 集合 $𝐴,𝐵$
• $𝐴$ と $𝐵$ の関係 $\sim ,{\sim }^{\prime }$
• $\sim ,{\sim }^{\prime }$ それぞれのグラフ $𝑅,{𝑅}^{\prime }$

を与える．

関係の包含関係()とは，それぞれのグラフの包含関係のこと： $\sim \subset {\sim }^{\prime }\stackrel{\mathrm{def}}{\iff }𝑅\subset {𝑅}^{\prime }\subset 𝐴\Pi 𝐵$

直積関係

• 集合$𝛬$
• 関係付き集合の集合 ${\left\{\left({𝐴}_{𝜆},{\sim }_{𝜆}\right)\right\}}_{𝜆\in 𝛬}$

を与える．

${\left\{\left({𝐴}_{𝜆},{\sim }_{𝜆}\right)\right\}}_{𝜆\in 𝛬}$ の直積関係(prodcut relation)とは，以下のデータのこと：

• 直積集合 $\prod _{𝜆\in 𝛬}{𝐴}_{𝜆}$ 上に以下で定義される関係を付けた関係付き集合： $${\left({𝑎}_{𝜆}\right)}_{𝜆\in 𝛬}\sim {\left({𝑎}_{𝜆}^{\prime }\right)}_{𝜆\in 𝛬}\stackrel{\mathrm{def}}{\iff }\forall 𝜆\in 𝛬,{𝑎}_{𝜆}{\sim }_{𝜆}{𝑎}_{𝜆}^{\prime }$$
• 集合の直積の射影（の集合） ${𝜋}_{𝜆}:$ \prod _{{𝜆}^{\prime }\in 𝛬}{𝐴}_{{𝜆}^{\prime }}$\to {𝐴}_{𝜆}$

空関係

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

$𝐴$ と $𝐵$ の間の空関係(empty relation)とは，空集合 $\varnothing \subset 𝐴\Pi 𝐵$ が誘導する $𝐴$ と $𝐵$ の関係のこと．

反鎖

関係付き集合 $\left(𝐴,\sim \right)$ を与える．

• $\left(𝐴,\sim \right)$ の反鎖(antichain)とは，$𝐴$ の部分集合 $𝑆$ であって，$\sim$ の $𝑆$ への制限が空関係となるものを言う．
• $𝑆$ の濃度を幅(width)と呼ぶ．
• 幅が有限のとき有限幅(finite width)，そうでないとき無限幅(infinite width)と呼ぶ．
• $𝐴$ の全ての反鎖の幅の最大値を，単に $𝐴$ の幅(width)と呼ぶ．

反射関係

集合$𝐴$を与える．

• $𝐴$ 上の関係 $\sim$ で，以下の同値な条件のいずれか（ゆえに全て）を満たすものを反射関係(reflexive relation)と呼ぶ：
  • $=\subset \sim$
  • $\left(\sim \cup =\right)=\sim$
  • $\forall 𝑎\in 𝐴,𝑎\sim 𝑎$
• $𝐴$上の関係 $\sim$ で，以下の同値な条件のいずれか（ゆえに全て）を満たすものを非反射関係(irreflexive relation)と呼ぶ．
  • $\left(\sim \setminus =\right)=\sim$
  • $\forall 𝑎\in 𝐴,𝑎\nsim 𝑎$

対称関係

集合$𝐴$を与える．

• $𝐴$ 上の関係$\sim$で，以下の同値な条件のいずれか（ゆえに全て）を満たすものを対称関係(symmetric relation)と呼ぶ．
  • $\sim ={\sim }^{\mathrm{op}}$
  • $\sim \cup {\sim }^{\mathrm{op}}=\sim$
  • $\forall 𝑎,𝑏\in 𝐴,𝑎\sim 𝑏\Rightarrow 𝑏\sim 𝑎$
• $𝐴$ 上の関係$\sim$で，以下の同値な条件のいずれか（ゆえに全て）を満たすものを反対称関係(antisymmetric relation)と呼ぶ：
  • $\sim \cap {\sim }^{\mathrm{op}}\subset =$
  • $\left(\sim \setminus {\sim }^{\mathrm{op}}\right)\cup \left(\sim \cap =\right)=\sim$
  • $\forall 𝑎,𝑏\in 𝐴,𝑎\sim 𝑏\cap 𝑏\sim 𝑎\Rightarrow 𝑎=𝑏$
• $𝐴$ 上の関係$\sim$で，以下の同値な条件のいずれか（ゆえに全て）を満たすものを非対称関係(asymmetric relation)と呼ぶ：
  • $\sim \cap {\sim }^{\mathrm{op}}$ は空関係
  • $\sim \setminus {\sim }^{\mathrm{op}}=\sim$
  • $\forall 𝑎,𝑏\in 𝐴,𝑎\sim 𝑏\Rightarrow 𝑏\nsim 𝑎$

推移関係

集合$𝐴$を与える．

• $𝐴$上の関係 $\sim$ で，以下の同値な条件のいずれか（ゆえに全て）を満たすものを推移関係(transitive relation)と呼ぶ：
  • $\sim \circ \sim \subset \sim$
  • $\forall 𝑎,𝑏,𝑐\in 𝐴,𝑎\sim 𝑏,𝑏\sim 𝑐\Rightarrow 𝑎\sim 𝑐$
  • $\forall 𝑛\in \mathbb{N},{\sim }^{\circ 𝑛}\subset \sim$
  • $\forall 𝑛\in \mathbb{N},\forall {𝑎}_0,\dots ,{𝑎}_{𝑛}\in 𝐴,{𝑎}_0\sim {𝑎}_1,\dots ,{𝑎}_{𝑛-1}\sim {𝑎}_{𝑛}\Rightarrow {𝑎}_0\sim {𝑎}_{𝑛}$
• $𝐴$上の関係 $\sim$ で，以下の同値な条件のいずれか（ゆえに全て）を満たすものを満たすものを非推移関係(intransitive relation)と呼ぶ：
  • $\forall 𝑛\in {\mathbb{N}}_{\ge 2},\sim \setminus {\left(\sim \setminus =\right)}^{\circ 𝑛}=\sim$
  • $\forall 𝑛\in {\mathbb{N}}_{\ge 2},\forall {𝑎}_0\ne \dots \ne {𝑎}_{𝑛}\in 𝐴,{𝑎}_0\sim {𝑎}_1,\dots ,{𝑎}_{𝑛-1}\sim {𝑎}_{𝑛}\Rightarrow {𝑎}_0\nsim {𝑎}_{𝑛}$
• $𝐴$上の関係 $⋖$ で，以下の同値な条件のいずれか（ゆえに全て）を満たすものを満たすものを厳密非推移関係(strict intransitive relation)（または被覆関係(covering relation)）と呼ぶ：
  • $\forall 𝑛\in {\mathbb{N}}_{\ge 2},⋖\setminus {⋖}^{\circ 𝑛}=\sim$
  • $\forall 𝑛\in {\mathbb{N}}_{\ge 2},\forall {𝑎}_0,\dots ,{𝑎}_{𝑛}\in 𝐴,{𝑎}_0⋖{𝑎}_1,\dots ,{𝑎}_{𝑛-1}⋖{𝑎}_{𝑛}\Rightarrow \neg {𝑎}_0⋖{𝑎}_{𝑛}$