【圏論メモ】Set が完備であることの証明

# 命題
$\textbf{Set}$ は完備である。

# 定義
## 完備
圏 $\textbf{C}$ が完備であるとは、任意の小さい圏 $\textbf{J}$ に対して任意の図式

```math
\mathcal{D}: \textbf{J} \rightarrow \textbf{C}
```

が極限を持つことを言う。

## 小さい圏
圏 $\textbf{C}$ について $\textbf{Ob(C)}$ と $\textbf{Hom(C)}$ がともに集合である時、 $\textbf{C}$ を小さい圏と言う。

$\textbf{Set}$ は小さい圏ではない。
自然数を対象とし、順序を射とすると圏になるが、これは小さい圏である。

# 証明
小さい圏 $\textbf{J}$ を一つ任意に取る。[極限の存在定理](http://qiita.com/amoO_O/items/5d8fb067aaecea10041d) より、次の3つの存在が言えれば、完備であることが証明できる

- $\textbf{Ob(J)}$ で添字付けられられた積
- $\textbf{Hom(J)}$ で添字付けられた積
- 任意の平行射

はじめの2つは、任意の集合族 $\Lambda$ について直積 $\prod_{\lambda \in \Lambda} \lambda$ が定義でき、これが集合であることが言えれば良い。

## 任意の集合族の直積
ZFC 公理系を仮定することで直積の存在が証明できるが、厳密にやろうとするとかなり時間がかかるので、手短に、少しだけ丁寧に書いてみたい。


### 2 つの集合の直積
まず 2 つの集合 $A, B$ の直積 $\prod \\{A, B\\} = A \times B$ について考える。
[和集合の公理](https://ja.wikipedia.org/wiki/%E5%92%8C%E9%9B%86%E5%90%88%E3%81%AE%E5%85%AC%E7%90%86)から $\bigcup \\{A, B\\} = A \cup B$ が定義でき、[冪集合公理](https://ja.wikipedia.org/wiki/%E5%86%AA%E9%9B%86%E5%90%88%E5%85%AC%E7%90%86) によって冪集合や冪集合の冪集合

```math
\begin{eqnarray}
&\mathcal{P}(A \cup B)\\
&\mathcal{P}\bigl(\mathcal{P}(A \cup B)\bigr)\\
\end{eqnarray}
```

が定義できる。
また、[対の公理](https://ja.wikipedia.org/wiki/%E5%AF%BE%E3%81%AE%E5%85%AC%E7%90%86) によって $a \in A$ と $b \in B$ に対し対

```math
\{a, b\} \in \mathcal{P}(A \cup B)
```

や、順序対

```math
(a, b) = \bigl\{\{a\}, \{a, b\}\bigr\} \in \mathcal{P}\bigl(\mathcal{P}(A \cup B)\bigr)
```

が定義できる。直積 $A \times B$ は順序対の集まり

```math
A \times B = \bigl\{(a, b) \in \mathcal{P}\bigl(\mathcal{P}(A \cup B)\bigr) \mid a \in A, b \in B \bigr\}
```

として定義され、これは [分出公理](https://ja.wikipedia.org/wiki/%E5%85%AC%E7%90%86%E7%9A%84%E9%9B%86%E5%90%88%E8%AB%96#.E5.88.86.E5.87.BA.E5.85.AC.E7.90.86) によって集合であることが保証される。

### 写像集合
写像 $f: A \rightarrow B$ を次の集合と同一視する：

```math
\left\{\bigl(a, f(a)\bigr) \, \middle | \, a \in A \right\}
```

この同一視によって、 $f \in \mathcal{P}(A \times B)$ が言えるので、その全体

```math
\textrm{Map}(A, B) = \{f: A \rightarrow B\}
```

は分出公理によって集合であることが保証される。

### 無限直積
$\Lambda$ を（有限とは限らない）任意の集合族とする。和集合の公理によって和集合

```math
A = \bigcup_{\lambda \in \Lambda} \lambda
```

の存在が保証される。

$\Lambda$ から $A$ への写像の全体 $\textrm{Map}(\Lambda, A)$ はこれも集合であるから、直積 $\prod_{\lambda \in \Lambda} \lambda$ を その部分集合

```math
\prod_{\lambda \in \Lambda} \lambda = \{f: \Lambda \rightarrow A \mid \forall \lambda, f(\lambda) \in \lambda \subset A \}
```

で定義すると、これまた分出公理によって集合であることがわかる。

余談だが、

```math
\emptyset \in \Lambda \Longleftrightarrow \prod_{\lambda \in \Lambda} \lambda = \emptyset
```

である。 $\Rightarrow$ は [空集合の公理](https://ja.wikipedia.org/wiki/%E7%A9%BA%E9%9B%86%E5%90%88%E3%81%AE%E5%85%AC%E7%90%86) より $f(\emptyset) \in \emptyset$ を満たす $f$ が無いことから、 $\Leftarrow$ は[選択公理](https://ja.wikipedia.org/wiki/%E9%81%B8%E6%8A%9E%E5%85%AC%E7%90%86) から証明できる。

## 平行射
$A, B$ を集合とし、$f, g: A \rightrightarrows B$ を $A$ から $B$ への平行射とする。これに対しイコライザ $\bigl(\textrm{eq}(f, g), \phi\bigr)$ が次のように定義できる。

```math
\textrm{eq}(f, g) = \{a \in A \mid f(a) = g(a) \}\\

\begin{eqnarray}
\phi_A: & \textrm{eq}(f, g) & \rightarrow & A\\
& a & \mapsto & a\\
\phi_B: & \textrm{eq}(f, g) & \rightarrow & B\\
& a & \mapsto & f(a) = g(a)
\end{eqnarray}
```

これが平行射の極限になっていることを示すには、

- 組 $(\textrm{eq}(f, g), \phi)$ が図式 $A \rightrightarrows B$ の錐になっていること
- 他の錐 $(N, \psi)$ に対し $u: N \rightarrow \textrm{eq}(f, g)$ が唯一つ存在して、 $\phi_A \circ u = \psi_A, \phi_B \circ u = \psi_B$ を満たすこと
  - この射を普遍射と呼ぶ。

を示せば良い。

### 錐になっていること
定義から明らかに

```math
\phi_B = f \circ \phi_A\\
\phi_B = g \circ \phi_A
```

であるから、$(\textrm{eq}(f, g), \phi)$ は錐である。

### 他の錐からの普遍射が存在すること
$(N, \psi)$ を平行射の錐とする。つまり、次が成り立つ：

```math
f \circ \psi_A = \psi_B = g \circ \psi_A
```

すると、 $\forall x \in N$ について、$a = \psi_A(x) \in A$ は、

```math
f(a) = f\bigl(\psi_A(x)\bigr) = \bigl(f \circ \psi_A\bigr)(x) = \bigl(g \circ \psi_A\bigr)(x) = g\bigl(\psi_A(x)\bigr) = g(a)
```

であるから、 $a \in \textrm{eq}(f, g)$ である。そこで、$u: N \rightarrow \textrm{eq}(f, g)$ を

```math
\begin{eqnarray}
u: & N & \rightarrow & \textrm{eq}(f, g)\\
& x & \mapsto & \psi_A(x)
\end{eqnarray}
```

と定義すれば、$\forall x \in N$ について、

```math
\bigl(\phi_A \circ u \bigr)(x) = \phi_A \bigl(u(x) \bigr) = u(x) = \psi_A(x)\\
```

```math
\phi_B \circ u = (f \circ \phi_A) \circ u = f \circ (\phi_A \circ u) = f \circ (\psi_A) = \psi_B
```

最後に、$u$ が一意であることを見る。$v: N \rightarrow \textrm{eq}(f, g)$ が

```math
\phi_A \circ v = \psi_A\\
\phi_B \circ v = \psi_B
```

を満たすとする。$\forall x \in N$ について、 $v(x) \in \textrm{eq}(f, g) \subset A$ だから、

```math
v(x) = \phi_A\bigl(v(x)\bigr) = \bigl(\phi_A \circ v\bigr)(x) = \psi_A(x) = \bigl(\phi_A \circ u\bigr)(x) = u(x)
```

より $v = u$ である。

以上により u が普遍射であることが示された。したがって $\bigl(\textrm{eq}(f, g), \phi\bigr)$ は平行射の極限である。

以上により、 $\textbf{Set}$ が完備であることが示された。