Differences
This shows you the differences between two versions of the page.
Next revision | Previous revision Next revision Both sides next revision | ||
sav08:galois_connection_on_lattices [2008/05/07 08:52] vkuncak created |
sav08:galois_connection_on_lattices [2008/05/07 10:03] vkuncak |
||
---|---|---|---|
Line 1: | Line 1: | ||
==== Galois Connection ==== | ==== Galois Connection ==== | ||
- | Galois connection is defined by two monotonic functions $\alpha : C \to A$ and $\gamma : A \to C$ between [[partial order]]s $\leq$ on $C$ and $\sqsubseteq$ on $A$, such that | + | Galois connection is defined by two monotonic functions $\alpha : C \to A$ and $\gamma : A \to C$ between [[:partial order]]s $\leq$ on $C$ and $\sqsubseteq$ on $A$, such that |
\begin{equation*} | \begin{equation*} | ||
\alpha(c) \sqsubseteq a\ \iff\ c \leq \gamma(a) \qquad (*) | \alpha(c) \sqsubseteq a\ \iff\ c \leq \gamma(a) \qquad (*) | ||
Line 7: | Line 7: | ||
for all $c$ and $a$ (intuitively, the condition means that $c$ is approximated by $a$). | for all $c$ and $a$ (intuitively, the condition means that $c$ is approximated by $a$). | ||
- | **Lemma:** The condition $(*)$ is equivalent to the conjunction of these two conditions: | + | **Lemma:** The condition $(*)$ holds iff the conjunction of these two conditions: |
\begin{eqnarray*} | \begin{eqnarray*} | ||
c &\leq& \gamma(\alpha(c)) \\ | c &\leq& \gamma(\alpha(c)) \\ | ||
\alpha(\gamma(a)) &\sqsubseteq& a | \alpha(\gamma(a)) &\sqsubseteq& a | ||
\end{eqnarray*} | \end{eqnarray*} | ||
- | hold for all $c$ and $a$. | + | holds for all $c$ and $a$. |
**Lemma:** Let $\alpha$ and $\gamma$ satisfy the condition of Galois connection. Then the following three conditions are equivalent: | **Lemma:** Let $\alpha$ and $\gamma$ satisfy the condition of Galois connection. Then the following three conditions are equivalent: | ||
- | |||
* $\alpha(\gamma(a)) = a$ for all $a$ | * $\alpha(\gamma(a)) = a$ for all $a$ | ||
* $\alpha$ is a [[wk>surjective function]] | * $\alpha$ is a [[wk>surjective function]] | ||
* $\gamma$ is an [[wk>injective function]] | * $\gamma$ is an [[wk>injective function]] | ||