Galois Connection & Galois Embedding

黄前久美子：“不嫉妒比自己优秀的人，到底是优点还是缺点呢，我应该说些什么吗。这种小事让我不自觉地思考，有种令人害怕却无法否认的要钻进牛角尖里的感觉，它将我的不成熟摆在眼前，我也因此竭尽全力。”

# Lattice

Let $(S,\sqsubseteq)$ be a partial order.

$(S,\sqsubseteq)$ is a lattice if the meet and join of any pair of elements of $S$ always exists.

$(S,\sqsubseteq)$ is a complete lattice if the meet and join of any subset of elements of $S$ always exists.

# Galois connection

Let $(C,\subseteq)$ and $(A,\sqsubseteq)$ be complete lattice, and let $\alpha:C\rightarrow A,\gamma:A\rightarrow C$.

We say $(C,A,\alpha,\gamma)$ is a (monotone) Galois connection if for all $c\in C,a\in A$:

$$\alpha(c)\sqsubseteq a\iff c\subseteq \gamma(a)$$

---

Lemma: In Galois connection, $\alpha,\gamma$ are monotonic.

Proof:

$$\begin{aligned} & \because \forall c\in C.\;\alpha(c)\sqsubseteq\alpha(c)\\ & \therefore\forall c\in C.\;c\subseteq\gamma(\alpha(c))\\ & \therefore \forall c'\subseteq c.\;c'\subseteq\gamma(\alpha(c))\\ & \therefore \forall c'\subseteq c.\;\alpha(c')\sqsubseteq\alpha(c) \end{aligned}$$

Similarly we can prove that $\gamma$ is monotonic.

$\square$.

Equivalent Definition: $(C,A,\alpha,\gamma)$ is a (monotone) Galois connection if for all $c\in C,a\in A$:

$$c\subseteq \gamma(\alpha(c))\text{ and }\alpha(\gamma(a))\sqsubseteq a$$

Proof:

• (=>) Assume $\alpha(c)\sqsubseteq a\iff c\subseteq\gamma(a)$.

  Because $\alpha(c)\sqsubseteq\alpha(c)$, therefore $c\subseteq\gamma(\alpha(c))$. Similarly it ca be proved that $\alpha(\gamma(a))\sqsubseteq a$ because $\gamma(a)\subseteq\gamma(a)$.

• (<=) Assume $c\subseteq\gamma(\alpha(c))$ and $\alpha(\gamma(a))\sqsubseteq a$.

  If $\alpha(c)\sqsubseteq a$, then since $\gamma$ is monotonic:

  $$c\subseteq\gamma(\alpha(c))\sqsubseteq \gamma(a)$$

  Similarly, we can prove that if $c\subseteq\gamma(a)$, then $\alpha(c)\sqsubseteq a$…

$\square$.

Lemma: $\text{id}_C\leq \gamma\circ \alpha$, $\text{id}_A\geq \alpha\circ\gamma$.

Proof: By equivalent definition.

$\square$.

Lemma: $\alpha$ preserves suprema and $\gamma$ preserves infima. i.e., given a subset $X\subseteq C,Y\subseteq A$:

$$\alpha(\bigcup_{x\in X} x)=\bigvee_{x\in X}\alpha(x)\qquad \gamma(\bigwedge_{y\in Y}y)=\bigcap_{y\in Y}\gamma(y)$$

Proof: 我们只需要证明，$\alpha(\bigcup x)$ 是$\{\alpha(x)\mid x\in X\}$ 的最小公共上界。

因为$\forall x\in X.\;x\subseteq\bigcup x$，那么根据单调性有$\forall x\in X.\;\alpha(x)\sqsubseteq \alpha(\bigcup x)$. 下面我们证明它是最小的公共上界。

假设还有一个公共上界$y$ : $\forall x\in X.\;\alpha(x)\sqsubseteq y$, 根据 Galois connection 就有$\forall x\in X.\;x\subseteq\gamma(y)$. 因此$\bigcup_{x\in X}x\subseteq\gamma(y)$ ($\gamma(y)$ 是$X$ 的一个公共上界，故大于其最小公共上界)。 那么就有$\alpha(\bigcup x)\sqsubseteq\alpha(\gamma(y))\sqsubseteq y$。因此，$\alpha(\bigcup x)$ 是所有公共上界中最小的一个。下界同理。

$\square$.

Lemma: $\alpha\circ\gamma\circ\alpha=\alpha$ and $\gamma\circ\alpha\circ\gamma=\gamma$.

Proof: Since $\gamma\circ\alpha\geq\text{id}_C$ and $\alpha\circ\gamma\leq\text{id}_A$:

$$\alpha\circ\gamma\circ\alpha(c)=\alpha\circ(\gamma\circ\alpha)(c)\sqsupseteq \alpha(c)\\ \alpha\circ\gamma\circ\alpha(c)=(\alpha\circ\gamma)\circ\alpha(c)\sqsubseteq \alpha(c)$$

thus $\alpha\circ\gamma\circ\alpha=\alpha$. And the other cas e is similar.

$\square$.

# Galois Embedding

Let $(C,A,\alpha,\gamma)$ a Galois connection.

It forms a Galois embedding if $\alpha\circ\gamma=\text{id}_A$.

Lemma: Given a Galois connection $(C,A,\alpha,\gamma)$, the following conditions are equivalent:

1. It forms a Galois embedding.

2. $\alpha$ is a surjective function.

3. $\gamma$ is an injective function.

Proof:

• (1 => 2) 若$\alpha\circ\gamma=\text{id}_A$，那么显然，$\forall a\in A.\;\exists y=\gamma(a)$ 使得$\alpha(y)=a$。故$\alpha$ 是满射。

• (2 => 3) 若$\alpha$ 是满射，反设存在$a_1\neq a_2\in A$ 使得$\gamma(a_1)=\gamma(a_2)\triangleq c$。因为$\alpha$ 是满射，所以存在$c_1,c_2\in C$ 使得$\alpha(c_1)=a_1,\alpha(c_2)=a_2$。所以有：

$$\alpha(c)=\alpha(\gamma(a_1))\sqsubseteq a_1\\ \alpha(c)=\alpha(\gamma(a_2))\sqsubseteq a_2$$

​ 又因为$c_1\subseteq \gamma(\alpha(c_1))=\gamma(a_1)=c$，同理也有$c_2\subseteq c$，所以有：

$$a_1=\alpha(c_1)\sqsubseteq\alpha(c)\sqsubseteq a_1\\ a_2=\alpha(c_2)\sqsubseteq\alpha(c)\sqsubseteq a_2$$

​ 因此可以夹逼出$a_1=\alpha(c)=a_2$，矛盾。

• (3 => 1) 若$\gamma$ 是单射，反设存在$a\in A$ 使得$\alpha(\gamma(a))=a'\neq a$。同时套上$\gamma$，有：

  $$\gamma(a')=\gamma(\alpha(\gamma(a)))=\gamma(a)$$

  这和$\gamma$ 是单射矛盾。

$\square$ 证毕。

upd：实际上 Galois connection 可以看作两个 poset category 间的 adjunction