始対象と終対象
圏論の学習で、始対象と終対象の理解でつまづかせるのは、書籍等でのその例に挙げられる圏Setでの対象である空集合に対する射の説明がないからだとわかった。
始対象、終対象ともに定義なのでそれ自体は特に難しくないのだが、例が無説明で挙げられるのみなので、そこにひっかかってしまうのです。
定義は以下のとおり
この最初にあげられる例として「圏Set(小さな集合。集合を要素に含まない集合)では、始対象は空集合、終対象は任意の1点集合(要素が一つだけの集合)」であると書かれてたりします。
Setでの射
圏Setでの射A->Bとは、集合Aの要素を集合Bの要素に変換する関数になります。外延的に表現すると、集合Aの要素と、集合Bの要素bへのペアの集合になるでしょう。また関数なので、このペア集合のペアの左にはAの要素それぞれがひとつづつ存在します(部分関数ではない)。
たとえば、A={a,b,c}, B={x,y}なら、f:A->B = {(a,x), (b,y), (c,x)}やg:A->B={(a,y),(b,y),(c,y)}などのようになります。
一点集合が終対象であるというのは、たとえば、集合A={a,b,c}, 一点集合B={x}とすると、A->Bとなる関数は、{(a, x), (b, x), (c, x)}のひとつだけしか存在しないから、ということです。これが任意のAについて言えて、それぞれひとつのA->B集合しかできないため終対象である、という意味になります。
一点集合は始対象ではないです。上記AとBで、B->Aは、{(x, a)}、{(x, b)}、{(x, c)}のように複数存在するからです。
空集合と射
空集合(empty set)は要素が存在しないので、集合上での関数は特別扱いされています(これが重要)。つまり、ペア集合として表現はできない関数として扱われます。
空集合から任意のA(空集合0も含めて)への関数0->Aは、各Aについて一つづつ存在すると定義されています(つまり、始対象の定義そのもの)。
集合の関数B->Aを命題論理として、しかも空集合0はFalseとみると、つまり、0->Aは左辺がFalseなのでこの関数は必ずTrueになるという扱いになります。
逆にして、空集合以外の集合Aから空集合への関数A->0は、命題論理的には必ずFalseであるので、存在しない、ということなのでしょう。それなら空集合0は終対象ではないというのも、納得できなくもありません。
もしこれ(空集合以外の集合から空集合への関数)が存在するとすると仮定したら、A={a,b,c}、B={x}なとき、ユニークなg:B->0が存在することになり、するとユニークであるf:0->Aとの合成、f.gがユニークになってしまうため、前出のB->Aの複数存在するのと矛盾します。ということで、空集合以外の集合から空集合への関数は存在しないといえそうです。
CPO⊥
完備半順序集合CPOのうち、射をストリクト関数(引数が⊥なら、戻り値は必ず⊥)のみに制限した圏CPO⊥では、{⊥}が始対象でも、終対象でもある。
例として、Bool⊥={⊥、false、true}(そして⊥⊆false, ⊥⊆true)を使います。ストリクト関数に限定している以上、そのcodomainとなる対象には必ず⊥が含まれることになります。
{⊥}->Bool⊥は、射はすべてストリクト関数なので、{(⊥:{⊥}, ⊥:Bool⊥)}だけです。Bool⊥->{⊥}は、{(⊥、⊥), (false, ⊥), (true, ⊥)}の一つだけになります。
これが任意のCPO⊥上の対象についても言えるので、{⊥}は始対象であり、終対象でもある、ことが理解できます。
