nLab
Galois connection

Galois connections

Definition

In order theory the term Galois connection 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”.

More explicitly, given posets AA and BB, a Galois connection between AA and BB is a pair of order-reversing maps f:ABf:A\to B and g:BAg: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).

Examples

  • Frequently Galois connections between collections of subsets 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.” See orthogonality for one example.

  • 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.

Properties

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 the first example: 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

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

  • 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)

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

Revised on October 26, 2014 20:55:11 by Thomas Holder (89.204.138.28)