Galois connection
In mathematics, especially in order theory, a Galois connection is a particular correspondence (typically) between two partially ordered sets (posets). Galois connections find applications in various mathematical theories. They generalize the fundamental theorem of Galois theory about the correspondence between subgroups and subfields, discovered by the French mathematician Évariste Galois.
A Galois connection can also be defined on
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 term Galois correspondence is sometimes used to mean a
Definitions
(Monotone) Galois connection
Let (A, ≤) and (B, ≤) be two
: F : A → B and G : B → A, such that for all a in A and b in B, we have- F(a) ≤ b if and only if a ≤ G(b).
In this situation, F is called the lower adjoint of G and G 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 left adjoint (respectively right adjoint) for the lower (respectively 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 with a ≤ G(), and
- G(b) is the largest element with F() ≤ b.
A consequence of this is that if F or G is
Given a Galois connection with lower adjoint F and upper adjoint G, we can consider the
A Galois insertion of B into A is a Galois connection in which the kernel operator FG is the
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 A and B, such that
- b ≤ F(a) if and only if a ≤ G(b).
The symmetry of F and G 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 b with a ≤ G(b), and
- G(b) is the largest element a 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 a in A and b ≤ FG(b) for all b in B.
The implications of the two definitions of Galois connections are very similar, since an antitone Galois connection between A and B is just a monotone Galois connection between A and the order dual Bop of B. 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 U be some
Lattices
Further interesting examples for Galois connections are described in the article on
Transitive group actions
Let G act transitively on X and pick some point x in X. Consider
the set of blocks containing x. Further, let consist of the subgroups of G containing the stabilizer of x.
Then, the correspondence :
is a monotone,
Image and inverse image
If f : X → Y is a
In the case of a
Span and closure
Pick some mathematical object X that has an
Syntax and semantics
A very general comment of William Lawvere[6] is that syntax and semantics are adjoint: take A to be the set of all logical theories (axiomatizations) reverse ordered by strength, and B the power set of the set of all mathematical structures. For a theory T ∈ A, let Mod(T ) be the set of all structures that satisfy the axioms T ; for a set of mathematical structures S ∈ B, let Th(S ) be the minimum of the axiomatizations that approximate S (in first-order logic, this is the set of sentences that are true in all structures in S). We can then say that S is a subset of Mod(T ) if and only if Th(S ) logically entails T: the "semantics functor" Mod and the "syntax functor" Th form a monotone Galois connection, with semantics being the upper adjoint.
Antitone Galois connections
Galois theory
The motivating example comes from Galois theory: suppose L/K is a
Algebraic topology: covering spaces
Analogously, given a
Linear algebra: annihilators and orthogonal complements
Given an inner product space V, we can form the orthogonal complement F(X ) of any subspace X of V. This yields an antitone Galois connection between the set of subspaces of V and itself, ordered by inclusion; both polarities are equal to F.
Given a vector space V and a subset X of V we can define its annihilator F(X ), consisting of all elements of the dual space V ∗ of V that vanish on X. Similarly, given a subset Y of V ∗, we define its annihilator G(Y ) = { x ∈ V | φ(x) = 0 ∀φ ∈ Y }. This gives an antitone Galois connection between the subsets of V 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 n and a field K and let A be the set of all subsets of the polynomial ring K[X1, ..., Xn] ordered by inclusion ⊆, and let B be the set of all subsets of K n ordered by inclusion ⊆. If S is a set of polynomials, define the variety of zeros as
the set of common
of polynomials vanishing on U, that isThen V and I form an antitone Galois connection.
The closure on K n is the closure in the Zariski topology, and if the field K is algebraically closed, then the closure on the polynomial ring is the radical of ideal generated by S.
More generally, given a commutative ring R (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
Connections on power sets arising from binary relations
Suppose X and Y are arbitrary sets and a binary relation R over X and Y is given. For any subset M of X, 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 G yield an antitone Galois connection between the power sets of X and Y, both ordered by inclusion ⊆.[7]
Up to isomorphism all 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 in formal 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]
The general 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]
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 x in A. By a similar reasoning (or just by applying the duality principle for order theory), one finds that f ∗( f∗(y)) ≤ y, for all y in B. 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 x in B. 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
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 a residuated mapping (respectively 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
The above considerations also show that closed elements of A (elements x 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
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 x in A, f ∗(x) is the least element y of B such that x ≤ f∗(y). Dually, for every y in B, f∗(y) is the greatest x in A 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 b in B, 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
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 morphisms 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.[11][12]
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 x in A, x ≤ g( f (x)) and for all y in B, f (g(y)) ≤ y.
- ^ Gierz, p. 23
- ISSN 0302-9743.
- ^ 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.
- ^ Birkhoff, 1st edition (1940): §32, 3rd edition (1967): Ch. V, §7 and §8
- ISBN 978-3-540-627715
- ISBN 978-3-662-49290-1
- from the original on 2020-05-28. Retrieved 2023-07-19.
- ISSN 1435-2702. (However the original article only considers complete lattices)
- ^ Patrick Cousot; Radhia Cousot (Jan 1979). "Systematic Design of Program Analysis Frameworks" (PDF). Proc. 6th ACM Symp. on Principles of Programming Languages (POPL). ACM Press. pp. 269–282.
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:
- ISBN 0-387-98403-8.
- 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
- JSTOR 1990305