nLab
Galois connection

Galois connections

Idea

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.

Definition

Given posets AA and BB, a Galois connection between AA and BB is a pair of order-reversing functions f:ABf \colon A\to B and g:BAg \colon B\to A such that ag(f(a))a\le g(f(a)) and bf(g(b))b\le f(g(b)) for all aAa\in A, bBb\in B.

A Galois correspondence is a Galois connection which is an adjoint equivalence (so a=g(f(a))a = g(f(a)) and b=f(g(b))b = f(g(b)) for all aAa \in A, bBb \in B).

Proposition

Any Galois connection f:ABf: A \to B, g:BAg: B \to A induces a Galois correspondence between f(A)f(A) and g(B)g(B), given by the composites g(B)Aff(A)g(B) \hookrightarrow A \stackrel{f}{\to} f(A) and f(A)Bgg(B)f(A) \hookrightarrow B \stackrel{g}{\to} g(B).

Proof

For any aAa \in A of the form a=g(b)a = g(b), we have a(gf)(a)a \leq (g \circ f)(a) and also (gf)(a)=g(f(g(b)))g(b)=a(g \circ f)(a) = g(f(g(b))) \leq g(b) = a where the inequality follows from bf(g(b))b \leq f(g(b)) and antitonicity of gg. Hence (gf)(a)=a(g \circ f)(a) = a for all ag(B)a \in g(B). Similarly (fg)(b)=b(f \circ g)(b) = b for all bf(A)b \in f(A).

Examples

Galois theory

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.

Galois connections induced from a relation

Frequently Galois connections between collections of subsets (power sets) arise where f(a)f(a) is “the set of all yy standing in some relation to every xax\in a” and dually g(b)g(b) is “the set of all xx standing in some relation to every yby\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:

Definition

(Galois connection induced from a relation)

Consider two sets X,YSetX,Y \in Set and a relation

EX×Y. E \hookrightarrow X \times Y \,.

Define two functions between their power sets P(X),P(Y)P(X), P(Y), as follows. (In the following we write E(x,y)E(x, y) to abbreviate the formula (x,y)E(x, y) \in E.)

  1. Define

    V E:P(X)P(Y) V_E \;\colon\; P(X) \longrightarrow P(Y)

    by

    V E(S){yY|xX((xS)E(x,y))} V_E(S) \coloneqq \left\{ y \in Y \vert \underset{x \in X}{\forall} \left( \left(x \in S\right) \Rightarrow E(x, y) \right) \right\}
  2. Define

    I E:P(Y)P(X) I_E \;\colon\; P(Y) \longrightarrow P(X)

    by

    I E(T){xX|yY((yT)E(x,y))} I_E(T) \coloneqq \left\{x \in X \vert \underset{y \in Y}{\forall} \left( \left(y \in T \right) \Rightarrow E(x, y) \right)\right\}
Proposition

The construction in def. 1 has the following properties:

  1. V EV_E and I EI_E are contravariant order-preserving in that

    1. if SSS \subset S', then V E(S)V E(S)V_E(S') \subset V_E(S);

    2. if TTT \subset T', then I E(T)I E(T)I_E(T') \subset I_E(T)

  2. The adjunction law holds: (TV E(S))(SI E(T)) \left( T \subset V_E(S) \right) \,\Rightarrow\, \left( S \subset I_E(T) \right)

    which we denote by writing

    P(X)V EI EP(Y) op P(X) \underoverset{\underset{V_E}{\longrightarrow}}{\overset{I_E}{\longleftarrow}}{\bot} P(Y)^{op}
  3. both V EV_E as well as I EI_E take unions to intersections.

Proof

Regarding the first point: the larger SS is, the more conditions that are placed on yy in order to belong to V E(S)V_E(S), and so the smaller V E(S)V_E(S) will be.

Regarding the second point: This is because both these conditions are equivalent to the condition S×TES \times T \subset E.

Regarding the third point: Observe that in a poset such as P(Y)P(Y), we have that A=BA = B iff for all CC, CAC \leq A iff CBC \leq B (this is the Yoneda lemma applied to posets). It follows that

TV E( iIS i) iff i:IS iI E(T) iff i:IS iI E(T) iff i:ITV E(S i) iff T i:IV E(S i) \array{ T \subset V_E(\bigcup_{i \in I} S_i) & iff & \bigcup_{i: I} S_i \subset I_E(T) \\ & iff & \forall_{i: I} S_i \subset I_E(T) \\ & iff & \forall_{i: I} T \subset V_E(S_i) \\ & iff & T \subset \bigcap_{i: I} V_E(S_i) }

and we conclude V E( i:IS i)= i:IV E(S i)V_E(\bigcup_{i: I} S_i) = \bigcap_{i: I} V_E(S_i) by the Yoneda lemma.

Proposition

(closure operators from Galois connection)

Given a Galois connection as in def. 1, consider the composites

I EV E:P(X)P(X) I_E \circ V_E \;\colon\; P(X) \longrightarrow P(X)

and

V EI E:P(Y)P(Y). V_E \circ I_E \;\colon\; P(Y) \longrightarrow P(Y) \,.

These satisfy:

  1. For all SP(X)S \in P(X) then SI EV E(S)S \subset I_E \circ V_E(S).

  2. For all SP(X)S \in P(X) then V EI EV E(S)=V E(S)V_E \circ I_E \circ V_E (S) = V_E(S).

  3. I EV EI_E \circ V_E is idempotent and covariant.

and

  1. For all TP(Y)T \in P(Y) then TV EI E(T)T \subset V_E \circ I_E(T).

  2. For all TP(Y)T \in P(Y) then I EV EI E(T)=I E(T)I_E \circ V_E \circ I_E (T) = I_E(T).

  3. V EI EV_E \circ I_E is idempotent and covariant.

This is summarized by saying that I EV EI_E \circ V_E and V EI EV_E \circ I_E are closure operators (idempotent monads).

Proof

The first statement is immediate from the adjunction law (prop. 2).

Regarding the second statement: This holds because applied to sets SS of the form I E(T)I_E(T), we see I E(T)I EV EI E(T)I_E(T) \subset I_E \circ V_E \circ I_E(T). But applying the contravariant map I EI_E to the inclusion TV EI E(T)T \subset V_E \circ I_E(T), we also have I EV EI E(T)I E(T)I_E \circ V_E \circ I_E(T) \subset I_E(T).

This directly implies that the function I EV EI_E \circ V_E. is idempotent, hence the third statement.

The argument for V EI EV_E \circ I_E is directly analogous.

In view of prop. 3 we say that:

Definition

(closed elements)

Given a Galois connection induced from a relation as in def. 1, then

  1. SP(X)S \in P(X) is called closed if I EV E(S)=SI_E \circ V_E(S) = S;

  2. the closure of SP(X)S \in P(X) is Cl(S)I EV E(S)Cl(S) \coloneqq I_E \circ V_E(S)

and similarly

  1. TP(Y)T \in P(Y) is called closed if V EI E(T)=TV_E \circ I_E(T) = T;

  2. the closure of TP(Y)T \in P(Y) is Cl(T)V EI E(T)Cl(T) \coloneqq V_E \circ I_E(T).

It follows from the properties of closure operators, hence form prop. 3:

Proposition

(fixed points of a Galois connection)

Given a Galois connection induced from a relation as in def. 1, then

  1. the closed elements of P(X)P(X) are precisely those in the image im(I E)im(I_E) of I EI_E;

  2. the closed elements of P(Y)P(Y) are precisely those in the image im(V E)im(V_E) of V EV_E.

We says these are the fixed points of the Galois connection. Therefore the restriction of the Galois connection

P(X)V EI EP(Y) op P(X) \underoverset{\underset{V_E}{\longrightarrow}}{\overset{I_E}{\longleftarrow}}{\bot} P(Y)^{op}

to these fixed points yields an equivalence

im(I E)V EI Eim(V E) op im(I_E) \underoverset{\underset{V_E}{\longrightarrow}}{\overset{I_E}{\longleftarrow}}{\simeq} im(V_E)^{op}

now called a Galois correspondence.

Proposition

Given a Galois connection induced from a relation as in def. 1, then the sets of closed elements according to def. 2 are closed under forming intersections.

Proof

If {T iP(Y)} i:I\{T_i \in P(Y)\}_{i: I} is a collection of elements closed under the operator K=V EI EK = V_E \circ I_E, then by the first item in prop. 3 it is automatic that i:IT iK( i:IT i)\bigcap_{i: I} T_i \subset K(\bigcap_{i: I} T_i), so it suffices to prove the reverse inclusion. But since i:IT iT i\bigcap_{i: I} T_i \subset T_i for all ii and KK is covariant and T iT_i is closed, we have K( i:IT i)K(T i)T iK(\bigcap_{i: I} T_i) \subset K(T_i) \subset T_i for all ii, and K( i:IT i) i:IT iK(\bigcap_{i: I} T_i) \subset \bigcap_{i: I} T_i follows.

Properties

Galois connections between power sets

Every Galois connection between full power sets,

(f:P(X)P(Y) op)(g:P(Y) opP(X))(f: P(X) \to P(Y)^{op}) \dashv (g: P(Y)^{op} \to P(X))

is of the form in def. 1 above: there is some binary relation rr from XX to YY such that

f(S)={y: xXxSr(x,y)},g(T)={x: yYyTr(x,y)}f(S) = \{y: \forall_{x \in X} x \in S \Rightarrow r(x, y)\}, \qquad g(T) = \{x: \forall_{y \in Y} y \in T \Rightarrow r(x, y)\}

Indeed, define r:X×Y2r: X \times Y \to \mathbf{2} by stipulating that r(x,y)r(x, y) is true if and only if yf({x})y \in f(\{x\}). Because ff is a left adjoint, it takes colimits in P(X)P(X) (in this case, unions) to colimits in P(Y) opP(Y)^{op}, which are intersections in P(Y)P(Y). Since every SS in P(X)P(X) is a union of singletons {x}\{x\}, this gives

f(S)= xSf({x})={y: xSr(x,y)}f(S) = \bigcap_{x \in S} f(\{x\}) = \{y: \forall_{x \in S} r(x, y)\}

which is another way of writing the formula for ff given above. We observe that

Tf(S)={y: xSr(x,y)}T \subseteq f(S) = \{y: \forall_{x \in S} r(x, y)\}

if and only if

S×TrS \times T \subseteq r

(now viewing rr extensionally in terms of subsets). This last symmetrical expression in SS and TT means

Sg(T):={x: yTr(x,y)}S \subseteq g(T) := \{x: \forall_{y \in T} r(x, y)\}

which means we have a Galois connection between ff and gg under this definition; since gg is uniquely determined by the presence of a Galois connection with ff, we conclude that all Galois connections between power sets arise in this way, via a relation rr between XX and YY.

References

The concent is due to

  • Øystein Ore, Galois connexions , Trans. AMS 55 (1944) pp.493-513. (pdf)

Introduction is in

  • M. Erné, E. Klossoswki, A. Melton, G. E. Strecker, A primer in Galois connections , Annals New York Academy of Sciences 704 (1993) pp.103-125. (draft)

See also

  • Wojciech Dzik, Jouni Järvinen, Michiro Kondo, Characterising intermediate tense logics in terms of Galois connections (arXiv:1401.7646).

Revised on April 28, 2017 04:43:20 by David Corfield (51.9.254.136)