### # 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\}$ 的最小公共上界。

$\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