In order theory the term Galois connection (due to Ore 44, who spelled it “connexion”) can mean both: “adjunction between posets” and “dual adjunction between posets”; the former notion is sometimes called “monotone Galois connection” and the latter “antitone Galois connection”. In this article the term “Galois connection” shall mean “dual adjunction between posets”.
The term Galois correspondence is also in use. For some authors it is synonymous to “Galois connection”, others reserve it for its restriction to its fixed points, where it becomes an adjoint equivalence.
The example that gives the concept its name is the relation between subgroups and subfields in Galois theory (see below), but adjunctions between posets, hence Galois connections, appear also in many other and entirely different contexts, see further below.
Given posets $A$ and $B$, a Galois connection between $A$ and $B$ is a pair of order-reversing functions $f \colon A\to B$ and $g \colon B\to A$ such that $a\le g(f(a))$ and $b\le f(g(b))$ for all $a\in A$, $b\in B$.
A Galois correspondence is a Galois connection which is an adjoint equivalence (so $a = g(f(a))$ and $b = f(g(b))$ for all $a \in A$, $b \in B$).
Any Galois connection $f: A \to B$, $g: B \to A$ induces a Galois correspondence between $f(A)$ and $g(B)$, given by the composites $g(B) \hookrightarrow A \stackrel{f}{\to} f(A)$ and $f(A) \hookrightarrow B \stackrel{g}{\to} g(B)$.
For any $a \in A$ of the form $a = g(b)$, we have $a \leq (g \circ f)(a)$ and also $(g \circ f)(a) = g(f(g(b))) \leq g(b) = a$ where the inequality follows from $b \leq f(g(b))$ and antitonicity of $g$. Hence $(g \circ f)(a) = a$ for all $a \in g(B)$. Similarly $(f \circ g)(b) = b$ for all $b \in f(A)$.
The Galois theory normally taught in graduate-level algebra courses (and based on the work of Évariste Galois) involves a Galois connection between the intermediate fields of a Galois extension and the subgroups of the corresponding Galois group.
Frequently Galois connections between collections of subsets (power sets) arise where $f(a)$ is “the set of all $y$ standing in some relation to every $x\in a$” and dually $g(b)$ is “the set of all $x$ standing in some relation to every $y\in b$.”
Examples of this class of Galois connections include the following
In fact all Galois connections between power sets arise this way, see below.
We now spell out in detail the Galois connections induced from a relation:
(Galois connection induced from a relation)
Consider two sets $X,Y \in Set$ and a relation
Define two functions between their power sets $P(X), P(Y)$, as follows. (In the following we write $E(x, y)$ to abbreviate the formula $(x, y) \in E$.)
Define
by
Define
by
The construction in def. has the following properties:
$V_E$ and $I_E$ are contravariant order-preserving in that
if $S \subset S'$, then $V_E(S') \subset V_E(S)$;
if $T \subset T'$, then $I_E(T') \subset I_E(T)$
The adjunction law holds: $\left( T \subset V_E(S) \right) \,\Rightarrow\, \left( S \subset I_E(T) \right)$
which we denote by writing
both $V_E$ as well as $I_E$ take unions to intersections.
Regarding the first point: the larger $S$ is, the more conditions that are placed on $y$ in order to belong to $V_E(S)$, and so the smaller $V_E(S)$ will be.
Regarding the second point: This is because both these conditions are equivalent to the condition $S \times T \subset E$.
Regarding the third point: Observe that in a poset such as $P(Y)$, we have that $A = B$ iff for all $C$, $C \leq A$ iff $C \leq B$ (this is the Yoneda lemma applied to posets). It follows that
and we conclude $V_E(\bigcup_{i: I} S_i) = \bigcap_{i: I} V_E(S_i)$ by the Yoneda lemma.
(closure operators from Galois connection)
Given a Galois connection as in def. , consider the composites
and
These satisfy:
For all $S \in P(X)$ then $S \subset I_E \circ V_E(S)$.
For all $S \in P(X)$ then $V_E \circ I_E \circ V_E (S) = V_E(S)$.
$I_E \circ V_E$ is idempotent and covariant.
and
For all $T \in P(Y)$ then $T \subset V_E \circ I_E(T)$.
For all $T \in P(Y)$ then $I_E \circ V_E \circ I_E (T) = I_E(T)$.
$V_E \circ I_E$ is idempotent and covariant.
This is summarized by saying that $I_E \circ V_E$ and $V_E \circ I_E$ are closure operators (idempotent monads).
The first statement is immediate from the adjunction law (prop. ).
Regarding the second statement: This holds because applied to sets $S$ of the form $I_E(T)$, we see $I_E(T) \subset I_E \circ V_E \circ I_E(T)$. But applying the contravariant map $I_E$ to the inclusion $T \subset V_E \circ I_E(T)$, we also have $I_E \circ V_E \circ I_E(T) \subset I_E(T)$.
This directly implies that the function $I_E \circ V_E$. is idempotent, hence the third statement.
The argument for $V_E \circ I_E$ is directly analogous.
(closed elements)
Given a Galois connection induced from a relation as in def. , then
$S \in P(X)$ is called closed if $I_E \circ V_E(S) = S$;
the closure of $S \in P(X)$ is $Cl(S) \coloneqq I_E \circ V_E(S)$
and similarly
$T \in P(Y)$ is called closed if $V_E \circ I_E(T) = T$;
the closure of $T \in P(Y)$ is $Cl(T) \coloneqq V_E \circ I_E(T)$.
It follows from the properties of closure operators, hence form prop. :
(fixed points of a Galois connection)
Given a Galois connection induced from a relation as in def. , then
the closed elements of $P(X)$ are precisely those in the image $im(I_E)$ of $I_E$;
the closed elements of $P(Y)$ are precisely those in the image $im(V_E)$ of $V_E$.
We says these are the fixed points of the Galois connection. Therefore the restriction of the Galois connection
to these fixed points yields an equivalence
now called a Galois correspondence.
Given a Galois connection induced from a relation as in def. , then the sets of closed elements according to def. are closed under forming intersections.
If $\{T_i \in P(Y)\}_{i: I}$ is a collection of elements closed under the operator $K = V_E \circ I_E$, then by the first item in prop. it is automatic that $\bigcap_{i: I} T_i \subset K(\bigcap_{i: I} T_i)$, so it suffices to prove the reverse inclusion. But since $\bigcap_{i: I} T_i \subset T_i$ for all $i$ and $K$ is covariant and $T_i$ is closed, we have $K(\bigcap_{i: I} T_i) \subset K(T_i) \subset T_i$ for all $i$, and $K(\bigcap_{i: I} T_i) \subset \bigcap_{i: I} T_i$ follows.
Every Galois connection between full power sets,
is of the form in def. above: there is some binary relation $r$ from $X$ to $Y$ such that
Indeed, define $r: X \times Y \to \mathbf{2}$ by stipulating that $r(x, y)$ is true if and only if $y \in f(\{x\})$. Because $f$ is a left adjoint, it takes colimits in $P(X)$ (in this case, unions) to colimits in $P(Y)^{op}$, which are intersections in $P(Y)$. Since every $S$ in $P(X)$ is a union of singletons $\{x\}$, this gives
which is another way of writing the formula for $f$ given above. We observe that
if and only if
(now viewing $r$ extensionally in terms of subsets). This last symmetrical expression in $S$ and $T$ means
which means we have a Galois connection between $f$ and $g$ under this definition; since $g$ is uniquely determined by the presence of a Galois connection with $f$, we conclude that all Galois connections between power sets arise in this way, via a relation $r$ between $X$ and $Y$.
The concent is due to
Introduction is in
See also
Last revised on April 28, 2017 at 04:43:20. See the history of this page for a list of all contributions to it.