Category Theory for scientists(David spivak) メモ ... グラフとPre順序

圏論

前回に続いて、圏の例としてグラフとPre順序を簡単に説明する。

まずグラフとは、有向グラフのことである。

Definition 3.3.1.1.

グラフ $G$は、次の $ (V , A , src , tgt ) $ 4つ組で、以下の条件が成り立つものである。

  • $V$は集合で、$G$の頂点の集合とよぶ。
  • $A$は集合で、$G$の矢印の集合である。
  • $src$は$ A \to V $の関数で、$G$のソース関数と呼ぶ。
  • $tgt$は$ A \to V $の関数で、$G$のターゲット関数と呼ぶ。

ある矢印$a \in A$ を与えると、$src(a)$は$a$のソースの頂点と呼び、$tgt(a)$は$a$のターゲットの頂点と呼ぶ。要するに、有向グラフの矢印の元が$src(a)$で、先が$tgt(a)$でよろしい。
これによって定義されるグラフにはいろいろなものがあるが、わかりやすいものとして自然数$n$で定義されているものである。

$n \in \textrm{N} $で $[n]$とは、\[ 0  \to  1  \to  2  \to  \dots  \to  n \]と書けるグラフで、"長さnのチェーングラフ"と呼ぶ。

※このあたり、$[n]$の表現はものの本によってことなるっぽい。

グラフにはPathというものが定義できて、これが今後の圏論を検討するうえで重要となる。

Definition 3.3.2.1.

グラフを $G = (V,A,src,tgt)$とする。グラフの長さnのパスとは、$ p \in {\textrm{Path}}^{(n)}_G $ と書き、G上の矢印の次のようなシーケンスである。

\[ p= ( v_0 \xrightarrow{a_1}  v_1 \xrightarrow{a_2}  v_2  \xrightarrow{a_3}  \dots  \xrightarrow{a_n}  v_n) \]

特に、標準的な同型として、$ {\textrm{Path}}^{(0)}_G \simeq A $ と、$ {\textrm{Path}}^{(0)}_G \simeq V $ がある。$G$上のPathをすべて集めた集合を ${\textrm{Path}}_G$とすると、

\[ {\textrm{Path}}_g := \bigcup_{n \in \textrm{N}} {\textrm{Path}}^{(n)}_G  \]

と書ける。

グラフとグラフを比較すると、そこに準同型写像(homomorphism)が見出せる。これは、monoidの場合と同じように、構造を保存した状態で、それぞれの要素の写像を考えたものである。

 

 Definition 3.3.3.1

$G=(V,A<src,tgt) , G'=(V',A',src',tgt')$がグラフとする。グラフのGからG'への準同型写像(homomorphism)は、$f:G \to G'$とかき、次の２つの可換図を満足する2つの関数、$f_0:V \to V' $ と、$f_1:A \to A' $である。

$$ \begin{array}{cccccc} A & \xrightarrow{f_1} & A' & \qquad & A & \xrightarrow{f_1} & A' \\ {\scriptsize src} \downarrow \quad & & \quad \downarrow {\scriptsize src'} & \qquad & {\scriptsize tgt} \downarrow & & \downarrow {\scriptsize tgt'} \\ V & \xrightarrow{f_0} & V & \qquad & V & \xrightarrow{f_0} & V \end{array}' $$

 

それぞれの矢印のソース関数、ターゲット関数が、準同型写像に関して一致していればよいことになる。

 

次に、順序集合について整理しておく。

 

順序集合は、Pre順序(preorder) 、半順序(partial order) , 全順序(linear order) の3種類が存在してそれぞれの定義は以下のとおり。※この日本語訳も結構いろいろある。

Definition 3.4.1.1.

$S$が集合で $ R \subseteq S \times S $ は、Sの二項関係とする。$(s,s') \in R$ であれば、$s \le s' $ と書けるとして、 $R$がPre順序(preorder)とは、すべての$s,s',s'' \in S$ において、次の2つが満たされることである。

Reflexivity: $ s \le s $

Transitivity: もし、$ s \le s' $ で、$ s' \le s'' $ なら、$ s \le s'' $

 $R$が半順序(partial order) であるとは、上記のPre順序(preorder)の条件に加えて、すべての$s,s' \in S $ で次が成り立つことである。

Antisymmetry: もし、$ s \le s' $ かつ $ s' \le s $ なら、$ s=s' $

 $R$が全順序(linear order) であるとは、上記の半順序(partial order)の条件に加えて、すべての$s,s' \in S $ で次が成り立つことである。

Comparability: s,s'について、$ s \le s' $ か、$ s' \le s$どちらか一方(もしくは両方)が成り立つ。

いずれの場合も、部分集合を $ (S , \le)$ と記述する。

 

Pre順序はたとえば、集合と集合の二項関係を、$ X \subseteq Y $ を $ X \le Y $とすれば、これは、Pre順序となる。

で、先に説明したグラフから、Pre順序の構造を見出すことができる。$\textrm{Path}$関数を使って、$ v,v' \in G $においてPathが存在すれば、$ v \le v' $ とおくことで、$(V , \le) $ は、Pre順序となる。

※あと、meet(最大下限=and)とjoin(最小上限=or)という概念を説明している。ちなみに、meetとjoinが唯一存在して演算として定義できれば、束構造(lattice)ということになる。

 

最後に、順序集合についても、準同型写像(homomorphism)が定義できる。

Definition 3.4.4.1

$S:=(S , \le)$と$S':=(S',\le')$ がPre順序(preorder)とする。preorderの準同型写像とは、$S$から、$S'$への関数 $f$で、$f:S \to S' $ と表し、すべてのペア要素 $ s_1,s_2 \in S $ で、もし、 $ s_1 \le s_2 $なら、$f(s_1) \le' f(s_2) $が成り立つ関数である。

 

グラフやモノイドのときと同じように、Pre順序も構造を保存しながらの写像が準同型写像(homomorphism)であるとわかる。

 

さて、Monoidのときと同じように、グラフやPre順序も、それぞれをobjectとした、圏が構成できる。

 

グラフは、いろいろなグラフを圏のobjectとしてとり、グラフの準同型写像を圏の射とした圏を、$\textrm{Grph} $ とかく。

Pre順序は、いろいろなPre順序集合を圏のobjectとしてとり、Pre順序の準同型写像を圏の射とした圏を、$\textrm{PrO} $ とかく。