Inmathematics, especially inorder theory, aGalois connection is a particular correspondence (typically) between twopartially ordered sets (posets). Galois connections find applications in various mathematical theories. They generalize thefundamental theorem of Galois theory about the correspondence betweensubgroups andsubfields, discovered by the French mathematicianÉvariste Galois.

A Galois connection can also be defined onpreordered sets orclasses; this article presents the common case of posets.The literature contains two closely related notions of "Galois connection". In this article, we will refer to them as(monotone) Galois connections andantitone Galois connections.

A Galois connection is rather weak compared to anorder isomorphism between the involved posets, but every Galois connection gives rise to an isomorphism of certain sub-posets, as will be explained below.The termGalois correspondence is sometimes used to mean abijectiveGalois connection; this is simply anorder isomorphism (or dual order isomorphism, depending on whether we take monotone or antitone Galois connections).

Let(A, ≤) and(B, ≤) be twopartially ordered sets. Amonotone Galois connection between these posets consists of twomonotone^[1]functions,F :A →B andG :B →A, such that for alla inA andb inB, we have

F(a) ≤bif and only ifa ≤G(b).

In this situation,F is called thelower adjoint ofG andG is called theupper adjoint ofF. Mnemonically, the upper/lower terminology refers to where the function application appears relative to ≤.^[2] The term "adjoint" refers to the fact that monotone Galois connections are special cases of pairs ofadjoint functors incategory theory as discussed further below. Other terminology encountered here isleft adjoint (respectivelyright adjoint) for the lower (respectively upper) adjoint.

An essential property of a Galois connection is that an upper/lower adjoint of a Galois connectionuniquely determines the other:

F(a) is the least element~b witha ≤G(~b), and

G(b) is the largest element~a withF(~a) ≤b.

A consequence of this is that ifF orG isbijective then each is theinverse of the other, i.e.F =G ⁻¹.

Given a Galois connection with lower adjointF and upper adjointG, we can consider thecompositionsGF :A →A, known as the associatedclosure operator, andFG :B →B, known as the associated kernel operator. Both are monotone andidempotent, and we havea ≤GF(a) for alla inA andFG(b) ≤b for allb inB.

AGalois insertion ofB intoA is a Galois connection in which the kernel operatorFG is theidentity onB, and henceG is an order isomorphism ofBonto the set of closed elementsGF [A] ofA.^[3]

The above definition is common in many applications today, and prominent inlattice anddomain theory. However the original notion in Galois theory is slightly different. In this alternative definition, a Galois connection is a pair ofantitone, i.e. order-reversing, functionsF :A →B andG :B →A between two posetsA andB, such that

b ≤F(a) if and only ifa ≤G(b).

The symmetry ofF andG in this version erases the distinction between upper and lower, and the two functions are then calledpolarities rather than adjoints.^[4] Each polarity uniquely determines the other, since

F(a) is the largest elementb witha ≤G(b), and

G(b) is the largest elementa withb ≤F(a).

The compositionsGF :A →A andFG :B →B are the associated closure operators; they are monotone idempotent maps with the propertya ≤GF(a) for alla inA andb ≤FG(b) for allb inB.

The implications of the two definitions of Galois connections are very similar, since an antitone Galois connection betweenA andB is just a monotone Galois connection betweenA and theorder dualB^op ofB. All of the below statements on Galois connections can thus easily be converted into statements about antitone Galois connections.

Thebijection of a pair of functions${\displaystyle f:X\to Y}$ and${\displaystyle g:Y\to X,}$ each other's inverse, forms a (trivial) Galois connection, as follows. Because theequality relation is reflexive, transitive and antisymmetric, it is, trivially, apartial order, making${\displaystyle (X,=)}$ and${\displaystyle (Y,=)}$ partially ordered sets. Since${\displaystyle f(x)=y}$ if and only if${\displaystyle x=g(y),}$ we have a Galois connection.

A monotone Galois connection between${\displaystyle \mathbb{Z},}$ the set ofintegers and${\displaystyle \mathbb{R},}$ the set ofreal numbers, each with its usual ordering, is given by the usualembedding function of the integers into the reals and thefloor function truncating a real number to the greatest integer less than or equal to it. The embedding of integers is customarily done implicitly, but to show the Galois connection we make it explicit. So let${\displaystyle F:\mathbb{Z}\to \mathbb{R}}$ denote the embedding function, with${\displaystyle F(n)=n\in \mathbb{R},}$ while${\displaystyle G:\mathbb{R}\to \mathbb{Z}}$ denotes the floor function, so${\displaystyle G(x)=\lfloor x\rfloor .}$ The equivalence${\displaystyle F(n)\le x\iff n\le G(x)}$ then translates to

${\displaystyle n\le x\iff n\le \lfloor x\rfloor .}$

This is valid because the variable${\displaystyle n}$ is restricted to the integers. The well-known properties of the floor function, such as${\displaystyle \lfloor x+n\rfloor =\lfloor x\rfloor +n,}$ can be derived by elementary reasoning from this Galois connection.

The dual orderings give another monotone Galois connection, now with theceiling function:

${\displaystyle x\le n\iff \lceil x\rceil \le n.}$

For an order-theoretic example, letU be someset, and letA andB both be thepower set ofU, ordered byinclusion. Pick a fixedsubsetL ofU. Then the mapsF andG, whereF(M ) =L ∩M, andG(N ) =N ∪ (U \ L), form a monotone Galois connection, withF being the lower adjoint. A similar Galois connection whose lower adjoint is given by the meet (infimum) operation can be found in anyHeyting algebra. Especially, it is present in anyBoolean algebra, where the two mappings can be described byF(x) = (a ∧x) andG( y) = ( y ∨ ¬a) = (a ⇒y). Inlogical terms: "implication froma" is the upper adjoint of "conjunction witha".

Further interesting examples for Galois connections are described in the article oncompleteness properties. Roughly speaking, the usual functions ∨ and ∧ are lower and upper adjoints to thediagonal mapX →X ×X. The least and greatest elements of a partial order are given by lower and upper adjoints to the unique functionX → {1}. Going further, evencomplete lattices can be characterized by the existence of suitable adjoints. These considerations give some impression of the ubiquity of Galois connections in order theory.

LetGacttransitively onX and pick some pointx inX. Consider

${\displaystyle \mathcal{B}=\{B\subseteq X:x\in B;\mathrm{\forall }g\in G,gB=B\mathrm{o}\mathrm{r}gB\cap B=\mathrm{\varnothing }\},}$

the set ofblocks containingx. Further, let${\displaystyle \mathcal{G}}$ consist of thesubgroups ofG containing thestabilizer ofx.

Then, the correspondence${\displaystyle \mathcal{B}\to \mathcal{G}}$:

${\displaystyle B\mapsto H_B=\{g\in G:gx\in B\}}$

is a monotone,one-to-one Galois connection.^[5] As acorollary, one can establish that doubly transitive actions have no blocks other than the trivial ones (singletons or the whole ofX): this follows from the stabilizers being maximal inG in that case. SeeDoubly transitive group for further discussion.

If f :X →Y is afunction, then for any subsetM ofX we can form theimageF(M ) =  f M = { f (m) |m ∈M} and for any subsetN ofY we can form theinverse imageG(N ) =  f ⁻¹N = {x ∈X |  f (x) ∈N}. ThenF andG form a monotone Galois connection between the power set ofX and the power set ofY, both ordered by inclusion ⊆. There is a further adjoint pair in this situation: for a subsetM ofX, defineH(M) = {y ∈Y |  f ⁻¹{y} ⊆M}. ThenG andH form a monotone Galois connection between the power set ofY and the power set ofX. In the first Galois connection,G is the upper adjoint, while in the second Galois connection it serves as the lower adjoint.

In the case of aquotient map between algebraic objects (such asgroups), this connection is called thelattice theorem: subgroups ofG connect to subgroups ofG/N, and the closure operator on subgroups ofG is given byH =HN.

Pick some mathematical objectX that has anunderlying set, for instance a group,ring,vector space, etc. For any subsetS ofX, letF(S ) be the smallestsubobject ofX that containsS, i.e. thesubgroup,subring orsubspace generated byS. For any subobjectU ofX, letG(U ) be the underlying set ofU. (We can even takeX to be atopological space, letF(S ) theclosure ofS, and take as "subobjects ofX" theclosed subsets ofX.) NowF andG form a monotone Galois connection between subsets ofX and subobjects ofX, if both are ordered by inclusion.F is the lower adjoint.

A very general comment ofWilliam Lawvere^[6] is thatsyntax and semantics are adjoint: takeA to be the set of alllogical theories (axiomatizations) reverse ordered by strength, andB the power set of the set of all mathematical structures. For a theoryT ∈A, letMod(T ) be the set of all structures that satisfy theaxiomsT ; for a set of mathematical structuresS ∈B, letTh(S ) be the minimum of the axiomatizations that approximateS (infirst-order logic, this is the set of sentences that are true in all structures inS). We can then say thatS is a subset ofMod(T ) if and only ifTh(S ) logically entailsT: the "semantics functor"Mod and the "syntax functor"Th form a monotone Galois connection, with semantics being the upper adjoint.

The motivating example comes from Galois theory: supposeL/K is afield extension. LetA be the set of all subfields ofL that containK, ordered by inclusion ⊆. IfE is such a subfield, writeGal(L/E) for the group offield automorphisms ofL that holdE fixed. LetB be the set of subgroups ofGal(L/K), ordered by inclusion ⊆. For such a subgroupG, defineFix(G) to be the field consisting of all elements ofL that are held fixed by all elements ofG. Then the mapsE ↦ Gal(L/E) andG ↦ Fix(G) form an antitone Galois connection.

Analogously, given apath-connectedtopological spaceX, there is an antitone Galois connection between subgroups of thefundamental groupπ₁(X) and path-connectedcovering spaces ofX. In particular, ifX issemi-locally simply connected, then for every subgroupG ofπ₁(X), there is a covering space withG as its fundamental group.

Given aninner product spaceV, we can form theorthogonal complementF(X ) of any subspaceX ofV. This yields an antitone Galois connection between the set of subspaces ofV and itself, ordered by inclusion; both polarities are equal toF.

Given avector spaceV and a subsetX ofV we can define its annihilatorF(X ), consisting of all elements of thedual spaceV ^∗ ofV that vanish onX. Similarly, given a subsetY ofV ^∗, we define its annihilatorG(Y ) = { x ∈V |φ(x) = 0 ∀φ ∈Y }. This gives an antitone Galois connection between the subsets ofV and the subsets ofV ^∗.

Inalgebraic geometry, the relation between sets ofpolynomials and their zero sets is an antitone Galois connection.

Fix anatural numbern and afieldK and letA be the set of all subsets of thepolynomial ringK[X₁, ...,X_n] ordered by inclusion ⊆, and letB be the set of all subsets ofKⁿ ordered by inclusion ⊆. IfS is a set of polynomials, define thevariety of zeros as

${\displaystyle V(S)=\{x\in K^n:f(x)=0\text{ for all }f\in S\},}$

the set of commonzeros of the polynomials inS. IfU is a subset ofKⁿ, defineI(U ) as theideal of polynomials vanishing onU, that is

${\displaystyle I(U)=\{f\in K[X_1,\dots ,X_n]:f(x)=0\text{ for all }x\in U\}.}$

ThenV andI form an antitone Galois connection.

The closure onKⁿ is the closure in theZariski topology, and if the fieldK isalgebraically closed, then the closure on the polynomial ring is theradical of ideal generated byS.

More generally, given acommutative ringR (not necessarily a polynomial ring), there is an antitone Galois connection between radical ideals in the ring and Zariski closed subsets of theaffine varietySpec(R).

More generally, there is an antitone Galois connection between ideals in the ring andsubschemes of the correspondingaffine variety.

SupposeX andY are arbitrary sets and abinary relationR overX andY is given. For any subsetM ofX, we defineF(M ) = { y ∈Y |mRy ∀m ∈M }. Similarly, for any subsetN ofY, defineG(N ) = { x ∈X |xRn ∀n ∈N }. ThenF andG yield an antitone Galois connection between the power sets ofX andY, both ordered by inclusion ⊆.^[7]

Up to isomorphismall antitone Galois connections between power sets arise in this way. This follows from the "Basic Theorem on Concept Lattices".^[8] Theory and applications of Galois connections arising from binary relations are studied informal concept analysis. That field uses Galois connections for mathematical data analysis. Many algorithms for Galois connections can be found in the respective literature, e.g., in.^[9]

Thegeneral concept lattice in its primitive version incorporates both the monotone and antitone Galois connections to furnish its upper and lower bounds of nodes for the concept lattice, respectively.^[10]

In the following, we consider a (monotone) Galois connection f = ( f ^∗,  f_∗), where f ^∗ :A →B is the lower adjoint as introduced above. Some helpful and instructive basic properties can be obtained immediately. By the defining property of Galois connections, f ^∗(x) ≤  f ^∗(x) is equivalent tox ≤  f_∗( f ^∗(x)), for allx inA. By a similar reasoning (or just by applying theduality principle for order theory), one finds that f ^∗( f_∗(y)) ≤y, for ally inB. These properties can be described by saying the composite f ^∗∘ f_∗ isdeflationary, while f_∗∘ f ^∗ isinflationary (orextensive).

Now considerx,y ∈A such thatx ≤y. Then using the above one obtainsx ≤  f_∗( f ^∗(y)). Applying the basic property of Galois connections, one can now conclude that f ^∗(x) ≤  f ^∗(y). But this just shows that f ^∗ preserves the order of any two elements, i.e. it is monotone. Again, a similar reasoning yields monotonicity of f_∗. Thus monotonicity does not have to be included in the definition explicitly. However, mentioning monotonicity helps to avoid confusion about the two alternative notions of Galois connections.

Another basic property of Galois connections is the fact that f_∗( f ^∗( f_∗(x))) =  f_∗(x), for allx inB. Clearly we find that

 f_∗( f ^∗( f_∗(x))) ≥  f_∗(x).

because f_∗∘ f ^∗ is inflationary as shown above. On the other hand, since f ^∗∘ f_∗ is deflationary, while f_∗ is monotonic, one finds that

 f_∗( f ^∗( f_∗(x))) ≤  f_∗(x).

This shows the desired equality. Furthermore, we can use this property to conclude that

 f ^∗( f_∗( f ^∗( f_∗(x)))) =  f ^∗( f_∗(x))

and

 f_∗( f ^∗( f_∗( f ^∗(x)))) =  f_∗( f ^∗(x))

i.e., f ^∗∘ f_∗ and f_∗∘ f ^∗ areidempotent.

It can be shown (see Blyth or Erné for proofs) that a function f  is a lower (respectively upper) adjoint if and only if f  is aresiduated mapping (respectively residual mapping). Therefore, the notion of residuated mapping and monotone Galois connection are essentially the same.

The above findings can be summarized as follows: for a Galois connection, the composite f_∗∘ f ^∗ is monotone (being the composite of monotone functions), inflationary, and idempotent. This states that f_∗∘ f ^∗ is in fact aclosure operator onA. Dually, f ^∗∘ f_∗ is monotone, deflationary, and idempotent. Such mappings are sometimes calledkernel operators. In the context offrames and locales, the composite f_∗∘ f ^∗ is called thenucleus induced by f . Nuclei induce frame homomorphisms; a subset of a locale is called a sublocale if it is given by a nucleus.

Conversely, any closure operatorc on some posetA gives rise to the Galois connection with lower adjoint f ^∗ being just the corestriction ofc to the image ofc (i.e. as asurjective mapping the closure systemc(A)). The upper adjoint f_∗ is then given by theinclusion ofc(A) intoA, that maps each closed element to itself, considered as an element ofA. In this way, closure operators and Galois connections are seen to be closely related, each specifying an instance of the other. Similar conclusions hold true for kernel operators.

The above considerations also show that closed elements ofA (elementsx with f_∗( f ^∗(x)) =x) are mapped to elements within the range of the kernel operator f ^∗∘ f_∗, and vice versa.

Another important property of Galois connections is that lower adjoints preserve allsuprema that exist within theirdomain. Dually, upper adjoints preserve all existinginfima. From these properties, one can also conclude monotonicity of the adjoints immediately. Theadjoint functor theorem for order theory states that the converse implication is also valid in certain cases: especially, any mapping betweencomplete lattices that preserves all suprema is the lower adjoint of a Galois connection.

In this situation, an important feature of Galois connections is that one adjoint uniquely determines the other. Hence one can strengthen the above statement to guarantee that any supremum-preserving map between complete lattices is the lower adjoint of a unique Galois connection. The main property to derive this uniqueness is the following: For everyx inA, f ^∗(x) is the least elementy ofB such thatx ≤  f_∗(y). Dually, for everyy inB, f_∗(y) is the greatestx inA such that f ^∗(x) ≤y. The existence of a certain Galois connection now implies the existence of the respective least or greatest elements, no matter whether the corresponding posets satisfy anycompleteness properties. Thus, when one upper adjoint of a Galois connection is given, the other upper adjoint can be defined via this same property.

On the other hand, some monotone function f  is a lower adjointif and only if each set of the form{ x ∈A |  f (x) ≤b }, forb inB, contains a greatest element. Again, this can be dualized for the upper adjoint.

Galois connections also provide an interesting class of mappings between posets which can be used to obtaincategories of posets. Especially, it is possible to compose Galois connections: given Galois connections( f ^∗,  f_∗) between posetsA andB and(g^∗,g_∗) betweenB andC, the composite(g^∗ ∘  f ^∗,  f_∗ ∘g_∗) is also a Galois connection. When considering categories of complete lattices, this can be simplified to considering just mappings preserving all suprema (or, alternatively, infima). Mapping complete lattices to their duals, these categories display autoduality, that are quite fundamental for obtaining other duality theorems. More special kinds ofmorphisms that induce adjoint mappings in the other direction are the morphisms usually considered forframes (or locales).

Every partially ordered set can be viewed as a category in a natural way: there is a unique morphism fromx toy if and only ifx ≤y. A monotone Galois connection is then nothing but a pair ofadjoint functors between two categories that arise from partially ordered sets. In this context, the upper adjoint is theright adjoint while the lower adjoint is theleft adjoint. However, this terminology is avoided for Galois connections, since there was a time when posets were transformed into categories in a dual fashion, i.e. with morphisms pointing in the opposite direction. This led to a complementary notation concerning left and right adjoints, which today is ambiguous.

Galois connections may be used to describe many forms of abstraction in the theory ofabstract interpretation ofprogramming languages.^[11][12]

The following books and survey articles include Galois connections using the monotone definition:

• Brian A. Davey andHilary A. Priestley:Introduction to Lattices and Order, Cambridge University Press, 2002.
• Gierz, Gerhard; Hofmann, Karl H.; Keimel, Klaus; Lawson, Jimmie D.; Mislove, Michael W.;Scott, Dana S. (2003).Continuous Lattices and Domains. Cambridge University Press.
• Marcel Erné, Jürgen Koslowski, Austin Melton, George E. Strecker,A primer on Galois connections, in: Proceedings of the 1991 Summer Conference on General Topology and Applications in Honor of Mary Ellen Rudin and Her Work, Annals of the New York Academy of Sciences, Vol. 704, 1993, pp. 103–125. (Freely available online in various file formatsPS.GZPS, it presents many examples and results, as well as notes on the different notations and definitions that arose in this area.)

Some publications using the original (antitone) definition:

• Mac Lane, Saunders (September 1998).Categories for the Working Mathematician (Second ed.). Springer.ISBN 0-387-98403-8.
• Thomas Scott Blyth,Lattices and Ordered Algebraic Structures, Springer, 2005,ISBN 1-85233-905-5.
• Galatos, Nikolaos; Jipsen, Peter; Kowalski, Tomasz; Ono, Hiroakira (2007).Residuated Lattices. An Algebraic Glimpse at Substructural Logics. Elsevier.ISBN 978-0-444-52141-5.
• Birkhoff, Garrett (1940).Lattice Theory. Vol. 25. Amer. Math. Soc. Coll. Pub.
• Ore, Øystein (1944), "Galois Connexions",Transactions of the American Mathematical Society,55 (3):493–513,doi:10.2307/1990305,JSTOR 1990305

• Galois theory
• Order theory
• Abstract interpretation
• Closure operators

• Articles with short description
• Short description is different from Wikidata