集合と写像の話をします。集合圏のごく基本的な用語・記法は使います(最初の節に説明あり)。写像のセクションと集合族のタプルを定義して、その関係を述べます。$`\newcommand{\In}{\text{ in }}
\newcommand{\id}{\mathrm{id}}
\newcommand{\Iff}{\Leftrightarrow}
\require{color}
\newcommand{\Keyword}[1]{ \textcolor{green}{\text{#1}} }%
\newcommand{\For}{\Keyword{For } }%
%\newcommand{\Let}{\Keyword{Let } }%
\newcommand{\Declare}{\Keyword{Declare } }%
\newcommand{\Define}{\Keyword{Define } }%
%`$
内容:
集合圏
$`{\bf Set}`$ は集合圏で、$`f:A \to B \In {\bf Set}`$ と書いたら次の意味です。
- $`A, B`$ は集合圏の対象、つまり集合である。
- $`f`$ は集合圏の射、つまり写像である。
- 写像 $`f`$ の域〈始域〉は集合 $`A`$ で、余域〈終域〉は集合 $`B`$ である。
$`|{\bf Set}|`$ はすべての集合の集まり〈大きな集合〉です。$`|{\bf Set}|`$ は、公理的集合論のホントの宇宙ではなくて、実用上十分に大きいが集合論から見たら小さい宇宙です。$`|{\bf Set}|`$ の扱いは公理的ではなくて、素朴集合論に基づきます。
$`f:A \to B, g:B\to C \In {\bf Set}`$ に対して、$`f;g`$ と $`g\circ f`$ は同じ意味で、写像の結合〈composition | 合成〉を表します。
$`\quad f;g = g\circ f\; : A \to C \In {\bf Set}`$
$`\id_A`$ は集合 $`A`$ の恒等写像です。
$`\quad \id_A : A \to A \In {\bf Set}`$
写像のセクション
$`f:A \to B \In {\bf Set}`$ に対して、次のような写像 $`s`$ が存在すれば、$`s`$ を $`f`$ のセクション〈section | 断面〉と呼びます。([追記]以下で、$`f;s = \id_A`$ と間違えていたので修正しました。[/追記])
$`\quad s:B \to A\\
\quad s;f = \id_B`$
若干形式的〈formal〉に書けば:
$`\For f:A \to B \In {\bf Set}\\
\Define \text{IsSectionOf}(s, f) :\Iff (s: B \to A) \land (s;f = \id_B)
%`$
任意の写像にセクションが在るとは言えません。例えば、$`f`$ が全射ではないとしましょう。全射ではないので、次のような $`b\in B`$ が在ります。
$`\quad f^\dashv(b) = \emptyset`$
ここで、$`f^\dashv(b)`$ は、一点〈単一の要素〉に対する逆像集合だとします。この状況でもしセクション $`s`$ が在れば:
$`\quad f(s(b)) = b \:\text{ i.e. }\: s(b)\in f^\dashv(b)`$
これは矛盾するので、セクションは無いことが分かります。
では、$`f`$ が全射ならセクションが存在するでしょうか? これを証明しようとしても、どう証明していいか分かりません。通常は、天下りに次を仮定します。
- $`f`$ が全射ならセクションが存在する。
集合族とその合併
次のような写像を集合族〈family of sets〉と呼びます。詳しく言えば、インデックス付けられた集合の族〈indexed family of sets〉です。
$`\quad I\in |{\bf Set}|\\
\quad F:I \to |{\bf Set}|
%`$
$`F`$ は集合圏 $`{\bf Set}`$ のなかの写像ではありませんが、域 $`I`$ は集合なので、一種の写像として取り扱います。$`F`$ の居場所〈生息地〉をハッキリさせたいなら、$`{\bf Set}`$
より大きな集合圏 $`{\bf SET}`$ を取ります(あまり気にしなくていいですが)。
$`\quad I\in |{\bf Set}|\\
\quad |{\bf Set}| \in |{\bf SET}|, |{\bf Set}| \subseteq |{\bf SET}|\\
\quad F:I \to |{\bf Set}| \In {\bf SET}
%`$
集合族 $`F`$ に対して、その合併〈union | ユニオン〉を次のように定義します。
$`\quad x\in \bigcup_{i\in I}F(i) \Iff \exists a\in I. x\in F(a)`$
右辺の論理式はハッキリとした意味を持ち、これによって要素の所属が確定するので、集合 $`\bigcup_{i\in I}F(i)`$ はちゃんと定義されています*1。
$`I`$ が有限集合、例えば $`I = \{1, 2, 3\}`$ のとき、3つの集合の合併に一致します。
$`\quad \bigcup_{i\in \{1, 2, 3\}}F(i) = F(1)\cup F(2) \cup F(3)`$
集合族の直和
集合族 $`F`$ に対して、その直和〈direct sum〉を次のように定義します。
$`\quad \sum_{i\in I}F(i) := \bigcup_{i\in I}(\{i\}\times F(i))`$
右辺の合併は既に定義済みなので、直和もハッキリと定義されます。
圏論に馴染みがある方は、直和の定義が必ずしもコレじゃなくてもいい事はご存知でしょう。しかし、具体的な計算をするとき、直和の構成法が決まってないと計算が出来ないので、この構成法を標準に採用します。
集合 $`\sum_{i\in I}F(i)`$ の要素は、$`(a, b), b\in F(a)`$ というペアです(標準的直和の定義から)。ペアの第一成分を取る写像を $`\pi`$ とすると:
$`\quad \pi : \sum_{i\in I}F(i) \to I \In {\bf Set}`$
$`\pi`$ を射影〈projection〉と呼ぶことがありますが、全射であることは保証できません。$`F(a) = \emptyset`$ のときは、$`\{a\}\times F(a)`$ が空集合になるので、ペアの第一成分を取りようがなくて、射影の値(第一成分)も在りません。
射影 $`\pi`$ は、集合族 $`F`$ に依存して決まるので、正確には $`\pi_F`$ と書きます。が、$`F`$ が文脈から明らかなら下付きの $`F`$ を省略してかまいません。
集合族のタプル
前節で、集合族 $`F`$ に対して直和 $`\sum_{i\in I}F(i)`$ と射影 $`\pi_F`$ を定義しました。射影 $`\pi_F`$ が全射だとは限りませんが、次の2つの命題が同値なことは言えます。
- 射影 $`\pi_F: \sum_{i\in I}F(i) \to I \In {\bf Set}`$ が全射である。
- $`\forall i\in I.\, F(i) \ne \emptyset`$
集合族 $`F`$ に対して、射影のセクションを(その集合族の)タプル〈tuple〉と呼びます。半形式的〈semi-formal〉に定義すれば:
$`\For F:I \to |{\bf Set}|\\
\Define \text{IsTupleOf}(t, F) :\Iff \text{IsSectionOf}(t, \pi_F)
`$
セクションの定義を展開すれば:
$`\For F:I \to |{\bf Set}|\\
\Define \text{IsTupleOf}(t, F) :\Iff
(t:I \to \sum_{i\in I}F(i)) \land (t;\pi_F = \id_I)
`$
$`(t;\pi_F = \id_I)`$ であることから、値 $`t(a)`$ の第一成分は $`a`$ であり、第ニ成分だけ考えればよいことになります。$`t(a) \in \sum_{i\in I}F(i)`$ の第二成分を $`t_2(a)`$ と書くと、
$`\quad t(a) = (t_1(a), t_2(a)) = (a, t_2(a)) \in \{a\}\times F(a)`$
つまり、タプルである条件は次のように書けます。
$`\quad t:I \to \sum_{i\in I}F(i)\\
\quad \forall i\in I.(\, t(i) = (i, t_2(i)) \land t_2(i) \in F(i) \,)
`$
タプル $`t`$ の第一成分 $`t_1`$ は恒等写像ですが、第二成分 $`t_2`$ に関する条件は次のように書けます。
$`\quad t_2:I \to \bigcup_{i\in I}F(i)\\
\quad \forall i\in I.\, t_2(i) \in F(i)
`$
「俺の知ってるタプルと違う」と思うかもしれませんが、$`I = \{1, 2, 3\}`$ のときに、$`t_2`$ を改めて $`t`$ と置いて(今、記法を変えたので注意)条件を書き下してみます。
$`\quad t:\{1, 2, 3\} \to F(1)\cup F(2)\cup F(3)\\
\quad t(1)\in F(1) \land t(2)\in F(2) \land t(3)\in F(3)
`$
集合族 $`F`$ をデータベース・テーブルのスキーマと考えましょう。すると、タプル $`t:\{1, 2, 3\} \to F(1)\cup F(2)\cup F(3)`$ は、データベースの意味で「テーブル・スキーマを満たすタプル」です。
一般的なタプルの定義は、テーブルのカラム番号/カラム名の集合である $`I`$ を無限集合も許したケースになっています。特に変わった概念が登場したわけではありません。
この節の冒頭で述べた「2つの命題の同値性」と「写像のセクション」の節で天下りに仮定した「全射にはセクションが在る」*2を使うと、次のことが言えます。
- $`\forall i\in I.\, F(i) \ne \emptyset`$ ならば、射影 $`\pi_F: \sum_{i\in I}F(i) \to I`$ は全射である。
- 射影 $`\pi_F: \sum_{i\in I}F(i) \to I`$ が全射ならば、セクション $`t: I \to \sum_{i\in I}F(i)`$ が存在する。
- セクションをタプルと呼ぶので、集合族 $`F:I \to |{\bf Set}|`$ のタプルが存在する。
データベースの言葉で言えば、テーブル・スキーマにおいて、「型が空集合」と指定されたカラムがないならば、そのテーブル・スキーマを満たすタプルは存在する。当たり前ですよね。
集合族の直積
集合族 $`F`$ に対して、その集合族のすべてのタプルの集合を(その集合族の)直積〈direct product〉と呼びます。$`F`$ の直積は、$`\prod_{i\in I}F(i)`$ と書きます。直積はタプルを使って定義されているので次のように書けます。
$`\quad t\in \prod_{i\in I}F(i) :\Iff \text{IsTupleOf}(t, F)`$
タプルの条件を展開すれば:
$`\quad t\in \prod_{i\in I}F(i) :\Iff (t:I \to \sum_{i\in I}F(i)) \land (t;\pi_F = \id_I)`$
しかし前述したように、タプルの第一成分は自明なので、上の意味のタプルの第二成分だけを取り出してタプルと呼ぶ場合が多いです。そうなると、直積の定義は次のようになります。
$`\quad t\in \prod_{i\in I}F(i) :\Iff
(t:I \to \bigcup_{i\in I}F(i)) \land
(\forall i\in I.\, t(i) \in F(i))
`$
いずれにしてもタプル $`t`$ は集合 $`I`$ からの写像です。$`I`$ は有限集合とは限らないので、「値を順番に並べたデータ」のような定義は使えません。そもそも「順番に並べる」という概念はタプルの定義に($`I`$ が有限集合の場合でも)登場しません。
さて、$`F(a) = \emptyset`$ となる $`a\in I`$ があるとタプルが作れないので、集合族 $`F`$ の直積は空集合になってしまいます。では、$`\forall i\in I.F(i) \ne \emptyset`$ なら $`F`$ の直積は非空〈non-empty〉でしょうか?
前節の議論を思い出せば、「全射にはセクションが在る」を仮定すれば次が言えます。
$`\For F:I \to |{\bf Set}|\\
\quad (\forall i\in I.F(i) \ne \emptyset) \Rightarrow
(\prod_{i\in I}F(i) \ne \emptyset)
`$
当たり前のことを回りくどく言っている印象を持つかも知れませんが、当たり前をホントに当たり前だと確認するにはこのテの回りくどさが必要です。