Galois connection
In mathematics, especially in order theory, a Galois connection is a particular correspondence (typically) between two partially ordered sets (posets). The same notion can also be defined on preordered sets or classes; this article presents the common case of posets. Galois connections generalize the correspondence between subgroups and subfields investigated in Galois theory (named after the French mathematician Évariste Galois). They find applications in various mathematical theories.
A Galois connection is rather weak compared to an order isomorphism between the involved posets, but every Galois connection gives rise to an isomorphism of certain sub-posets, as will be explained below.
The literature contains two closely related notions of "Galois connection". In this article, we will distinguish between the two by referring to the first as (monotone) Galois connection and to the second as antitone Galois connection.
The term Galois correspondence is sometimes used to mean bijective Galois connection, just is simply an order isomorphism (or dual order isomorphism, dependently on whether we take monotone or antitone Galois connections).
Contents
- 1 Definitions
- 2 Examples
- 3 Properties
- 4 Closure operators and Galois connections
- 5 Existence and uniqueness of Galois connections
- 6 Galois connections as morphisms
- 7 Connection to category theory
- 8 Applications in the theory of programming
- 9 Notes
- 10 References
Definitions
(Monotone) Galois connection
Let (A, ≤) and (B, ≤) be two partially ordered sets. A monotone Galois connection between these posets consists of two monotone^{[1]} functions: F : A → B and G : B → A, such that for all Template:Mvar in Template:Mvar and Template:Mvar in Template:Mvar, we have
- F(a) ≤ b if and only if a ≤ G(b).
In this situation, Template:Mvar is called the lower adjoint of Template:Mvar and Template:Mvar is called the upper adjoint of F. 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 of adjoint functors in category theory as discussed further below. Other terminology encountered here is coadjoint (resp. adjoint) for the lower (resp. upper) adjoint.
An essential property of a Galois connection is that an upper/lower adjoint of a Galois connection uniquely determines the other:
- F(a) is the least element Template:Overset with a ≤ G(Template:Overset), and
- G(b) is the largest element Template:Mvar with F(Template:Overset) ≤ b.
Given a Galois connection with lower adjoint Template:Mvar and upper adjoint Template:Mvar, we can consider the compositions GF : A → A, known as the associated closure operator, and FG : B → B, known as the associated kernel operator. Both are monotone and idempotent, and we have a ≤ GF(a) for all Template:Mvar in Template:Mvar and FG(b) ≤ b for all Template:Mvar in Template:Mvar.
A Galois insertion of Template:Mvar into Template:Mvar is a Galois connection in which the closure operator Template:Mvar is the identity on Template:Mvar.^{[3]}
Antitone Galois connection
The above definition is common in many applications today, and prominent in lattice and domain theory. However the original notion in Galois theory is slightly different. In this alternative definition, a Galois connection is a pair of antitone, i.e. order-reversing, functions F : A → B and G : B → A between two posets Template:Mvar and Template:Mvar, such that
- b ≤ F(a) if and only if a ≤ G(b).
The symmetry of Template:Mvar and Template:Mvar in this version erases the distinction between upper and lower, and the two functions are then called polarities rather than adjoints.^{[4]} Each polarity uniquely determines the other, since
- F(a) is the largest element Template:Mvar with a ≤ G(b), and
- G(b) is the largest element Template:Mvar with b ≤ F(a).
The compositions GF : A → A and FG : B → B are the associated closure operators; they are monotone idempotent maps with the property a ≤ GF(a) for all Template:Mvar in Template:Mvar and b ≤ FG(b) for all Template:Mvar in Template:Mvar.
The implications of the two definitions of Galois connections are very similar, since an antitone Galois connection between Template:Mvar and Template:Mvar is just a monotone Galois connection between Template:Mvar and the order dual B^{op} of Template:Mvar. All of the below statements on Galois connections can thus easily be converted into statements about antitone Galois connections.
Examples
Monotone Galois connections
Power set; implication and conjunction
For an order theoretic example, let Template:Mvar be some set, and let Template:Mvar and Template:Mvar both be the power set of Template:Mvar, ordered by inclusion. Pick a fixed subset Template:Mvar of Template:Mvar. Then the maps Template:Mvar and Template:Mvar, where F(M) = L ∩ M, and G(N) = N ∪ (U \ L), form a monotone Galois connection, with Template:Mvar being the lower adjoint. A similar Galois connection whose lower adjoint is given by the meet (infimum) operation can be found in any Heyting algebra. Especially, it is present in any Boolean algebra, where the two mappings can be described by F(x) = (a ∧ x) and G(y) = (y ∨ ¬a) = (a ⇒ y). In logical terms: "implication from Template:Mvar" is the upper adjoint of "conjunction with Template:Mvar".
Lattices
Further interesting examples for Galois connections are described in the article on completeness properties. Roughly speaking, it turns out that the usual functions ∨ and ∧ are lower and upper adjoints to the diagonal map X → X × X. The least and greatest elements of a partial order are given by lower and upper adjoints to the unique function X → {1}. Going further, even complete lattices can be characterized by the existence of suitable adjoints. These considerations give some impression of the ubiquity of Galois connections in order theory.
Transitive group actions
Let Template:Mvar act transitively on Template:Mvar and pick some point Template:Mvar in Template:Mvar. Consider
the set of blocks containing Template:Mvar. Further, let consist of the subgroups of Template:Mvar containing the stabilizer of Template:Mvar.
is a monotone, one-to-one Galois connection.^{[5]} As a corollary, one can establish that doubly transitive actions have no blocks other than the trivial ones (singletons or the whole of Template:Mvar): this follows from the stabilizers being maximal in Template:Mvar in that case. See doubly transitive group for further discussion.
Image and inverse image
If f : X → Y is a function, then for any subset Template:Mvar of Template:Mvar we can form the image F(M) = f (M) = {f(m) | m ∈ M} and for any subset Template:Mvar of Template:Mvar we can form the inverse image G(N) = f ^{−1}(N) = {x ∈ X | f (x) ∈ N}. Then Template:Mvar and Template:Mvar form a monotone Galois connection between the power set of Template:Mvar and the power set of Template:Mvar, both ordered by inclusion ⊆. There is a further adjoint pair in this situation: for a subset Template:Mvar of Template:Mvar, define H(M) = {y ∈ Y | f ^{−1}({y}) ⊆ M}. Then Template:Mvar and Template:Mvar form a monotone Galois connection between the power set of Template:Mvar and the power set of Template:Mvar. In the first Galois connection, Template:Mvar is the upper adjoint, while in the second Galois connection it serves as the lower adjoint.
In the case of a quotient map between algebraic objects (such as groups), this connection is called the lattice theorem: subgroups of Template:Mvar connect to subgroups of G/N, and the closure operator on subgroups of Template:Mvar is given by Template:Overline = HN.
Span and closure
Pick some mathematical object Template:Mvar that has an underlying set, for instance a group, ring, vector space, etc. For any subset Template:Mvar of Template:Mvar, let F(S) be the smallest subobject of Template:Mvar that contains Template:Mvar, i.e. the subgroup, subring or subspace generated by Template:Mvar. For any subobject Template:Mvar of Template:Mvar, let G(U) be the underlying set of Template:Mvar. (We can even take Template:Mvar to be a topological space, let F(S) the closure of Template:Mvar, and take as "subobjects of Template:Mvar" the closed subsets of Template:Mvar.) Now Template:Mvar and Template:Mvar form a monotone Galois connection between subsets of Template:Mvar and subobjects of Template:Mvar, if both are ordered by inclusion. Template:Mvar is the lower adjoint.
Syntax and semantics
A very general comment of William Lawvere^{[6]} is that syntax and semantics are adjoint: take Template:Mvar to be the set of all logical theories (axiomatizations), and Template:Mvar the power set of the set of all mathematical structures. For a theory T ∈ A, let F(T) be the set of all structures that satisfy the axioms Template:Mvar; for a set of mathematical structures Template:Mvar, let G(S) be the minimum of the axiomatizations which approximate Template:Mvar. We can then say that F(T) is a subset of Template:Mvar if and only if Template:Mvar logically implies G(S): the "semantics functor" Template:Mvar and the "syntax functor" Template:Mvar form a monotone Galois connection, with semantics being the lower adjoint.
Antitone galois connections
Galois theory
The motivating example comes from Galois theory: suppose L/K is a field extension. Let Template:Mvar be the set of all subfields of Template:Mvar that contain Template:Mvar, ordered by inclusion ⊆. If Template:Mvar is such a subfield, write Gal(L/E) for the group of field automorphisms of Template:Mvar that hold Template:Mvar fixed. Let Template:Mvar be the set of subgroups of Gal(L/K), ordered by inclusion ⊆. For such a subgroup Template:Mvar, define Fix(G) to be the field consisting of all elements of Template:Mvar that are held fixed by all elements of Template:Mvar. Then the maps E Template:Mapsto Gal(L/E) and G Template:Mapsto Fix(G) form an antitone Galois connection.
Algebraic topology: covering spaces
Analogously, given a path-connected topological space Template:Mvar, there is an antitone Galois connection between subgroups of the fundamental group π_{1}(X) and path-connected covering spaces of Template:Mvar. In particular, if Template:Mvar is semi-locally simply connected, then for every subgroup Template:Mvar of π_{1}(X), there is a covering space with Template:Mvar as its fundamental group.
Linear algebra: annihilators and orthogonal complements
Given an inner product space Template:Mvar, we can form the orthogonal complement F(X) of any subspace Template:Mvar of Template:Mvar. This yields an antitone Galois connection between the set of subspaces of Template:Mvar and itself, ordered by inclusion; both polarities are equal to Template:Mvar.
Given a vector space Template:Mvar and a subset Template:Mvar of Template:Mvar we can define its annihilator F(X), consisting of all elements of the dual space V ^{∗} of Template:Mvar that vanish on Template:Mvar. Similarly, given a subset Template:Mvar of V ^{∗}, we define its annihilator G(Y) = {x ∈ V | φ(x) = 0 ∀φ ∈ Y}. This gives an antitone Galois connection between the subsets of Template:Mvar and the subsets of V ^{∗}.
Algebraic geometry
In algebraic geometry, the relation between sets of polynomials and their zero sets is an antitone Galois connection.
Fix a natural number Template:Mvar and a field Template:Mvar and let Template:Mvar be the set of all subsets of the polynomial ring K[X_{1}, ..., X_{n}] ordered by inclusion ⊆, and let Template:Mvar be the set of all subsets of K^{n} ordered by inclusion ⊆. If Template:Mvar is a set of polynomials, define the variety of zeros as
the set of common zeros of the polynomials in Template:Mvar. If Template:Mvar is a subset of K^{n}, define I(U) as an ideal of polynomials vanishing on Template:Mvar, that is
Then Template:Mvar and I form an antitone Galois connection.
The closure on K^{n} is the closure in the Zariski topology, and if the field Template:Mvar is algebraically closed, then the closure on the polynomial ring is the radical of ideal generated by Template:Mvar.
More generally, given a commutative ring Template:Mvar (not necessarily a polynomial ring), there is an antitone Galois connection between radical ideals in the ring and subvarieties of the affine variety Spec(R).
More generally, there is an antitone Galois connection between ideals in the ring and subschemes of the corresponding affine variety.
Connections on power sets arising from binary relations
Suppose Template:Mvar and Y are arbitrary sets and a binary relation Template:Mvar over Template:Mvar and Y is given. For any subset M of Template:Mvar, we define F(M) = {y ∈ Y | mRy ∀m ∈ M}. Similarly, for any subset N of Y, define G(N) = {x ∈ X | xRn ∀n ∈ N}. Then F and Template:Mvar yield an antitone Galois connection between the power sets of Template:Mvar and Template:Mvar, both ordered by inclusion ⊆.
Many antitone Galois connections arise in this way; examples include the original connection from Galois theory, the connections in linear algebra and the connection from algebraic geometry explained above.
Properties
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 to x ≤ f_{∗}( f ^{∗}(x)), for all Template:Mvar in Template:Mvar. By a similar reasoning (or just by applying the duality principle for order theory), one finds that f ^{∗}( f_{∗}(y)) ≤ y, for all Template:Mvar in Template:Mvar. These properties can be described by saying the composite f ^{∗} ∘ f_{∗} is deflationary, while f_{∗} ∘ f ^{∗} is inflationary (or extensive).
Now consider x, y ∈ A such that x ≤ y, then using the above one obtains x ≤ 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 all Template:Mvar in Template:Mvar. 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 ^{∗} are idempotent.
It can be shown (see Blyth or Erné for proofs) that a function f is a lower (resp. upper) adjoint if and only if f is a residuated mapping (resp. residual mapping). Therefore, the notion of residuated mapping and monotone Galois connection are essentially the same.
Closure operators and Galois connections
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 a closure operator on Template:Mvar. Dually, f ^{∗} ∘ f_{∗} is monotone, deflationary, and idempotent. Such mappings are sometimes called kernel operators. In the context of frames and locales, the composite f_{∗} ∘ f ^{∗} is called the nucleus 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 operator Template:Mvar on some poset Template:Mvar gives rise to the Galois connection with lower adjoint f ^{∗} being just the corestriction of Template:Mvar to the image of Template:Mvar (i.e. as a surjective mapping the closure system c(A)). The upper adjoint f_{∗} is then given by the inclusion of c(A) into Template:Mvar, that maps each closed element to itself, considered as an element of Template:Mvar. 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 of Template:Mvar (elements Template:Mvar with f_{∗}( f ^{∗}(x)) = x) are mapped to elements within the range of the kernel operator f ^{∗} ∘ f_{∗}, and vice versa.
Existence and uniqueness of Galois connections
Another important property of Galois connections is that lower adjoints preserve all suprema that exist within their domain. Dually, upper adjoints preserve all existing infima. From these properties, one can also conclude monotonicity of the adjoints immediately. The adjoint functor theorem for order theory states that the converse implication is also valid in certain cases: especially, any mapping between complete 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 every Template:Mvar in Template:Mvar, f ^{∗}(x) is the least element Template:Mvar of Template:Mvar such that x ≤ f_{∗}(y). Dually, for every Template:Mvar in Template:Mvar, f_{∗}(y) is the greatest Template:Mvar in Template:Mvar 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 any completeness 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 adjoint if and only if each set of the form {x ∈ A | f (x) ≤ b}, for Template:Mvar in Template:Mvar, contains a greatest element. Again, this can be dualized for the upper adjoint.
Galois connections as morphisms
Galois connections also provide an interesting class of mappings between posets which can be used to obtain categories of posets. Especially, it is possible to compose Galois connections: given Galois connections ( f ^{∗}, f_{∗}) between posets Template:Mvar and Template:Mvar and (g^{∗}, g_{∗}) between Template:Mvar and Template:Mvar, 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, this categories display auto duality, that are quite fundamental for obtaining other duality theorems. More special kinds of morphisms that induce adjoint mappings in the other direction are the morphisms usually considered for frames (or locales).
Connection to category theory
Every partially ordered set can be viewed as a category in a natural way: there is a unique morphism from x to y if and only if x ≤ y. A monotone Galois connection is then nothing but a pair of adjoint functors between two categories that arise from partially ordered sets. In this context, the upper adjoint is the right adjoint while the lower adjoint is the left 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 arrows pointing in the opposite direction. This led to a complementary notation concerning left and right adjoints, which today is ambiguous.
Applications in the theory of programming
Galois connections may be used to describe many forms of abstraction in the theory of abstract interpretation of programming languages.^{[7]}^{[8]}
Notes
- ↑ Monotonicity follows from the following condition. See the discussion of the properties. It is only explicit in the definition to distinguish it from the alternative antitone definition. One can also define Galois connections as a pair of monotone functions that satisfy the laxer condition that for all Template:Mvar in Template:Mvar, x ≤ g( f (x)) and for all y in B, f(g(y)) ≤ y.
- ↑ Gierz, p. 23
- ↑ {{#invoke:citation/CS1|citation |CitationClass=book }}
- ↑ Galatos, p. 145
- ↑ See Alperin, Bell, Groups and Representations (GTM 162), p. 32
- ↑ William Lawvere, Adjointness in foundations, Dialectica, 1969, available here. The notation is different nowadays; an easier introduction by Peter Smith in these lecture notes, which also attribute the concept to the article cited.
- ↑ {{#invoke:citation/CS1|citation
|CitationClass=book
}}
For a counterexample for the false theorem in Sect.7 (p.243 top right), see: Template:Cite techreport - ↑ {{#invoke:citation/CS1|citation |CitationClass=book }}
References
The following books and survey articles include Galois connections using the monotone definition:
- Brian A. Davey and Hilary A. Priestley: Introduction to lattices and Order, Cambridge University Press, 2002.
- Gerhard Gierz, Karl H. Hofmann, Klaus Keimel, Jimmie D. Lawson, Michael W. Mislove, Dana S. Scott: Continuous Lattices and Domains, Cambridge University Press, 2003.
- 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 formats PS.GZ PS, 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:
- {{#invoke:citation/CS1|citation
|CitationClass=book }}
- Thomas Scott Blyth, Lattices and Ordered Algebraic Structures, Springer, 2005, ISBN 1-85233-905-5.
- Nikolaos Galatos, Peter Jipsen, Tomasz Kowalski, and Hiroakira Ono (2007), Residuated Lattices. An Algebraic Glimpse at Substructural Logics, Elsevier, ISBN 978-0-444-52141-5.
- Garrett Birkhoff: Lattice Theory, Amer. Math. Soc. Coll. Pub., Vol 25, 1940
- Øystein Ore: Galois Connexions, Transactions of the American Mathematical Society 55 (1944), pp. 493–513