Galois connection
Encyclopedia
In mathematics
, especially in order theory
, a Galois connection is a particular correspondence (typically) between two partially ordered set
s (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 subgroup
s and subfields
investigated in Galois theory
. 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.
Like Galois theory, Galois connections are named after the French mathematician Évariste Galois
.
. A Galois connection between these posets consists of two monotone functions
: F : A → B and G : B → A, such that for all a in A and b in B, we have
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 ≤; the term adjoint
relates the Galois connections to the notion with the same name from 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. Consequently, it's natural to use a pair of symbols to denote upper and lower adjoints. Unfortunately, no standard notation has emerged. Here we denote a pair of corresponding lower and upper adjoints by f ∗ and f ∗, respectively. Note that the asterisk
is placed above the function symbol to denote the lower adjoint, in contrast to the notation from Erné et al.
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
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.
Both notions of a Galois connection are still present in the literature. In this article the term (monotone) Galois connection will always refer to a Galois connection in the former sense. If the alternative definition is applied, the term antitone Galois connection or order-reversing Galois connection is used.
The implications of both definitions are in fact 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.
Note however that for an antitone Galois connection, it does not make sense to talk about the lower and upper adjoint: the situation is completely symmetrical.
(resp. residual mapping). Therefore, the notion of residuated mapping and monotone Galois connection are essentially the same.
. Let A be the set of all subfields of L that contain K, ordered by inclusion
. If E is such a subfield, write Gal(L /E) for the group of field automorphisms of L that hold E fixed. Let B be the set of subgroup
s of Gal(L /K), ordered by inclusion
. For such a subgroup G, define Fix(G) to be the field consisting of all elements of L that are held fixed by all elements of G. Then the maps E Gal(L /E) and G Fix(G) form an antitone Galois connection.
, there is a Galois connection between subgroups of the fundamental group 
and path-connected covering spaces of 
. In particular, if X is semi-locally simply connected
, then for every subgroup
of 
, there is a covering space with 
as its fundamental group.
. 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" is the upper adjoint of "conjunction".
. It turns out that the usual functions
and 
are adjoints in two suitable Galois connections. The same is true for the mappings from the one element set that point out the least and greatest elements of a partial order. Going further, even complete lattice
s can be characterized by the existence of suitable adjoints. These considerations give some impression of the ubiquity of Galois connections in order theory.
R over X and Y is given. For any subset M of X, we define
. Similarly, for any subset N of Y, define G(N) = { x
X : xRn for all n
N}. Then F and G yield an antitone Galois connection between the power sets of X and Y, both ordered by inclusion 
.
An important special case in linear algebra
is the annihilator
, which includes the orthogonal complement as a special case.
, the relation between sets of polynomial
s 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 Kn ordered by inclusion 
. If S is a set of polynomials, define the variety of zeros as
the set of common zeros of the polynomials in S.
If U is a subset of Kn, define the radical ideal
of polynomials vanishing on U as
Then V and I form an antitone Galois connection.
The closure on the polynomial ring is "radical ideal generated by S", while the closure on
is the closure in the Zariski topology
.
More generally, given a 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
(namely Spec
of the ring).
More generally, there is an antitone Galois connection between ideals in the ring and subschemes of the corresponding affine variety.
, then for any subset M of X we can form the image F(M) = f(M) = {f(m) : m
M} and for any subset N of Y we can form the inverse image G(N) = f -1(N) = {x
X : f(x)
N}. Then F and G form a monotone Galois connection between the power set of X and the power set of Y, both ordered by inclusion 
. There is a further adjoint pair in this situation: for a subset M of X, define H(M) = {y
Y : f -1({y}) 
M}. Then G and H form a monotone Galois connection between the power set of Y and the power set of X. 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 a quotient map between algebraic objects (such as groups), this connection is called the lattice theorem
: subgroups of G connect to subgroups of G/N,
and the closure operator on subgroups of G is given by
.
, ring
, vector space
, etc. For any subset S of X, let F(S) be the smallest subobject of X that contains S, i.e. the subgroup
, subring
or subspace
generated by S. For any subobject U of X, let G(U) be the underlying set of U. (We can even take X to be a topological space
, let F(S) the closure
of S, and take as "subobjects of X" the closed subsets of X.) Now F and G form a monotone Galois connection if the sets and subobjects are ordered by inclusion. F is the lower adjoint.
is that syntax and semantics are adjoint: take A to be the set of all logical theories (axiomatizations), and B 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 T; for a set of mathematical structures S, let G(S) be the minimal axiomatization of S. We can then say that F(T) is a subset of S if and only if T logically implies G(S): the "semantics functor" F and the "syntax functor" G form a monotone Galois connection, with semantics being the lower adjoint.
), 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 if one considers any elements x and y of A such that x ≤ y, then one can clearly use the above findings to obtain
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
because f ∗
f ∗ is inflationary as shown above. On the other hand, since f ∗
f ∗ is deflationary, while f ∗ is monotonic, one finds that
This shows the desired equality. Furthermore, we can use this property to conclude that
i.e., f ∗
f ∗ is idempotent.
f ∗ is monotone (being the composite of monotone functions), inflationary, and idempotent. This states that f ∗
f ∗ is in fact a closure operator
on A. 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 c on some poset A gives rise to the Galois connection with lower adjoint f ∗ being just the corestriction of c to the image of c (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 A, that maps each closed element to itself, considered as an element of A. 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 A (elements x with f ∗(f ∗(x)) = x) are mapped to elements within the range of the kernel operator f ∗
f ∗, and vice versa.
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 lattice
s 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 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 adjoint of a Galois connection is given, the other can be defined via this property. On the other hand, some arbitrary function f is a lower adjoint if and only if
each set of the form { x in A | f(x) ≤ b }, b in B, contains a greatest element. Again, this can be dualized for the upper adjoint.
of posets. Especially, it is possible to compose Galois connections: given Galois connections (f ∗, f ∗) between posets A and B and (g ∗, g ∗) between B and C, 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).
in a natural way: there is a unique morphism from x to y if and only if
x ≤ y. A 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.
of programming language
s.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, especially in order theory
Order theory
Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...
, a Galois connection is a particular correspondence (typically) between two partially ordered set
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
s (posets). The same notion can also be defined on preordered sets or classes
Preordered class
In mathematics, a preordered class is a class equipped with a preorder.-Definition:When dealing with a class C, it is possible to define a class relation on C as a subclass of the power class C \times C . Then, it is convenient to use the language of relations on a set.A preordered class is a...
; this article presents the common case of posets. Galois connections generalize the correspondence between subgroup
Subgroup
In group theory, given a group G under a binary operation *, a subset H of G is called a subgroup of G if H also forms a group under the operation *. More precisely, H is a subgroup of G if the restriction of * to H x H is a group operation on H...
s and subfields
Field (mathematics)
In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...
investigated in Galois theory
Galois theory
In mathematics, more specifically in abstract algebra, Galois theory, named after Évariste Galois, provides a connection between field theory and group theory...
. They find applications in various mathematical theories.
A Galois connection is rather weak compared to an order isomorphism
Order isomorphism
In the mathematical field of order theory an order isomorphism is a special kind of monotone function that constitutes a suitable notion of isomorphism for partially ordered sets . Whenever two posets are order isomorphic, they can be considered to be "essentially the same" in the sense that one of...
between the involved posets, but every Galois connection gives rise to an isomorphism of certain sub-posets, as will be explained below.
Like Galois theory, Galois connections are named after the French mathematician Évariste Galois
Évariste Galois
Évariste Galois was a French mathematician born in Bourg-la-Reine. While still in his teens, he was able to determine a necessary and sufficient condition for a polynomial to be solvable by radicals, thereby solving a long-standing problem...
.
(Monotone) Galois connection
Let (A, ≤) and (B, ≤) be two partially ordered setsPartially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
. A Galois connection between these posets consists of two monotone functions
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
: 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 ifIf and only ifIn logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
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 ≤; the term adjoint
Adjoint
In mathematics, the term adjoint applies in several situations. Several of these share a similar formalism: if A is adjoint to B, then there is typically some formula of the type = .Specifically, adjoint may mean:...
relates the Galois connections to the notion with the same name from category theory
Category theory
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...
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. Consequently, it's natural to use a pair of symbols to denote upper and lower adjoints. Unfortunately, no standard notation has emerged. Here we denote a pair of corresponding lower and upper adjoints by f ∗ and f ∗, respectively. Note that the asterisk
Asterisk
An asterisk is a typographical symbol or glyph. It is so called because it resembles a conventional image of a star. Computer scientists and mathematicians often pronounce it as star...
is placed above the function symbol to denote the lower adjoint, in contrast to the notation from Erné et al.
Antitone Galois connection
The above definition is common in many applications today, and prominent in latticeLattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
and domain theory
Domain theory
Domain theory is a branch of mathematics that studies special kinds of partially ordered sets commonly called domains. Consequently, domain theory can be considered as a branch of order theory. The field has major applications in computer science, where it is used to specify denotational...
. 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.
Both notions of a Galois connection are still present in the literature. In this article the term (monotone) Galois connection will always refer to a Galois connection in the former sense. If the alternative definition is applied, the term antitone Galois connection or order-reversing Galois connection is used.
The implications of both definitions are in fact very similar, since an antitone Galois connection between A and B is just a monotone Galois connection between A and the order dual
Duality (order theory)
In the mathematical area of order theory, every partially ordered set P gives rise to a dual partially ordered set which is often denoted by Pop or Pd. This dual order Pop is defined to be the set with the inverse order, i.e. x ≤ y holds in Pop if and only if y ≤ x holds in P...
Bop of B. All of the below statements on Galois connections can thus easily be converted into statements about antitone Galois connections.
Note however that for an antitone Galois connection, it does not make sense to talk about the lower and upper adjoint: the situation is completely symmetrical.
Equivalent definitions
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 mappingResiduated mapping
In mathematics, the concept of a residuated mapping arises in the theory of partially ordered sets. It refines the concept of a monotone function....
(resp. residual mapping). Therefore, the notion of residuated mapping and monotone Galois connection are essentially the same.
Galois theory
The motivating example comes from Galois theory: suppose L /K is a field extensionField extension
In abstract algebra, field extensions are the main object of study in field theory. The general idea is to start with a base field and construct in some manner a larger field which contains the base field and satisfies additional properties...
. Let A be the set of all subfields of L that contain K, ordered by inclusion
. If E is such a subfield, write Gal(L /E) for the group of field automorphisms of L that hold E fixed. Let B be the set of subgroupSubgroup
In group theory, given a group G under a binary operation *, a subset H of G is called a subgroup of G if H also forms a group under the operation *. More precisely, H is a subgroup of G if the restriction of * to H x H is a group operation on H...
s of Gal(L /K), ordered by inclusion
. For such a subgroup G, define Fix(G) to be the field consisting of all elements of L that are held fixed by all elements of G. Then the maps E Gal(L /E) and G Fix(G) form an antitone Galois connection.Algebraic topology: covering spaces
Analogously, given a path-connected topological spaceTopological space
Topological spaces are mathematical structures that allow the formal definition of concepts such as convergence, connectedness, and continuity. They appear in virtually every branch of modern mathematics and are a central unifying notion...
, there is a Galois connection between subgroups of the fundamental group and path-connected covering spaces of . In particular, if X is semi-locally simply connectedSemi-locally simply connected
In mathematics, specifically algebraic topology, the phrase semi-locally simply connected refers to a certain local connectedness condition that arises in the theory of covering spaces. Roughly speaking, a topological space X is semi-locally simply connected if there is a lower bound on the sizes...
, then for every subgroup
of , there is a covering space with as its fundamental group.Power set
For an order theoretic example, let U be some set, and let A and B both be the power set of U, ordered by inclusion. Pick a fixed subset L of U. Then the maps F and G, where F(M) is the intersection of L and M, and G(N) is the union of N and (U \ L), form a monotone Galois connection, with F being the lower adjoint. A similar Galois connection whose lower adjoint is given by the meet (infimum) operation can be found in any Heyting algebraHeyting algebra
In mathematics, a Heyting algebra, named after Arend Heyting, is a bounded lattice equipped with a binary operation a→b of implication such that ∧a ≤ b, and moreover a→b is the greatest such in the sense that if c∧a ≤ b then c ≤ a→b...
. 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" is the upper adjoint of "conjunction".Lattices
Further interesting examples for Galois connections are described in the article on completeness propertiesCompleteness (order theory)
In the mathematical area of order theory, completeness properties assert the existence of certain infima or suprema of a given partially ordered set . A special use of the term refers to complete partial orders or complete lattices...
. It turns out that the usual functions
and are adjoints in two suitable Galois connections. The same is true for the mappings from the one element set that point out the least and greatest elements of a partial order. Going further, even complete latticeComplete lattice
In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum and an infimum . Complete lattices appear in many applications in mathematics and computer science...
s can be characterized by the existence of suitable adjoints. These considerations give some impression of the ubiquity of Galois connections in order theory.
Binary relations and annihilators
Suppose X and Y are arbitrary sets and a binary relationBinary relation
In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...
R over X and Y is given. For any subset M of X, we define
. Similarly, for any subset N of Y, define G(N) = { xX : xRn for all nN}. Then F and G yield an antitone Galois connection between the power sets of X and Y, both ordered by inclusion .An important special case in linear algebra
Linear algebra
Linear algebra is a branch of mathematics that studies vector spaces, also called linear spaces, along with linear functions that input one vector and output another. Such functions are called linear maps and can be represented by matrices if a basis is given. Thus matrix theory is often...
is the annihilator
Annihilator (ring theory)
In mathematics, specifically module theory, annihilators are a concept that generalizes torsion and orthogonal complement.-Definitions:Let R be a ring, and let M be a left R-module. Choose a nonempty subset S of M...
, which includes the orthogonal complement as a special case.
Algebraic geometry
In algebraic geometryAlgebraic geometry
Algebraic geometry is a branch of mathematics which combines techniques of abstract algebra, especially commutative algebra, with the language and the problems of geometry. It occupies a central place in modern mathematics and has multiple conceptual connections with such diverse fields as complex...
, the relation between sets of polynomial
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
s and their zero sets is an antitone Galois connection.
Fix a natural number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
n and a field
Field (mathematics)
In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...
K and let A be the set of all subsets of the polynomial ring
Polynomial ring
In mathematics, especially in the field of abstract algebra, a polynomial ring is a ring formed from the set of polynomials in one or more variables with coefficients in another ring. Polynomial rings have influenced much of mathematics, from the Hilbert basis theorem, to the construction of...
K[X1,...,Xn] ordered by inclusion
, and let B be the set of all subsets of Kn ordered by inclusion . If S is a set of polynomials, define the variety of zeros asthe set of common zeros of the polynomials in S.
If U is a subset of Kn, define the radical ideal
Radical of an ideal
In commutative ring theory, a branch of mathematics, the radical of an ideal I is an ideal such that an element x is in the radical if some power of x is in I. A radical ideal is an ideal that is its own radical...
of polynomials vanishing on U as
Then V and I form an antitone Galois connection.
The closure on the polynomial ring is "radical ideal generated by S", while the closure on
is the closure in the Zariski topologyZariski topology
In algebraic geometry, the Zariski topology is a particular topology chosen for algebraic varieties that reflects the algebraic nature of their definition. It is due to Oscar Zariski and took a place of particular importance in the field around 1950...
.
More generally, given a 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
(namely SpecSpectrum of a ring
In abstract algebra and algebraic geometry, the spectrum of a commutative ring R, denoted by Spec, is the set of all proper prime ideals of R...
of the ring).
More generally, there is an antitone Galois connection between ideals in the ring and subschemes of the corresponding affine variety.
Image and inverse image
If f : X → Y is a functionFunction (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
, then for any subset M of X we can form the image F(M) = f(M) = {f(m) : m
M} and for any subset N of Y we can form the inverse image G(N) = f -1(N) = {xX : f(x)N}. Then F and G form a monotone Galois connection between the power set of X and the power set of Y, both ordered by inclusion . There is a further adjoint pair in this situation: for a subset M of X, define H(M) = {yY : f -1({y}) M}. Then G and H form a monotone Galois connection between the power set of Y and the power set of X. 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 a quotient map between algebraic objects (such as groups), this connection is called the lattice theorem
Lattice theorem
In mathematics, the lattice theorem, sometimes referred to as the fourth isomorphism theorem or the correspondence theorem, states that if N is a normal subgroup of a group G, then there exists a bijection from the set of all subgroups A of G such that A contains N, onto the set of all subgroups...
: subgroups of G connect to subgroups of G/N,
and the closure operator on subgroups of G is given by
.Span and closure
Pick some mathematical object X that has an underlying set, for instance a groupGroup (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
, ring
Ring (mathematics)
In mathematics, a ring is an algebraic structure consisting of a set together with two binary operations usually called addition and multiplication, where the set is an abelian group under addition and a semigroup under multiplication such that multiplication distributes over addition...
, vector space
Vector space
A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...
, etc. For any subset S of X, let F(S) be the smallest subobject of X that contains S, i.e. the subgroup
Subgroup
In group theory, given a group G under a binary operation *, a subset H of G is called a subgroup of G if H also forms a group under the operation *. More precisely, H is a subgroup of G if the restriction of * to H x H is a group operation on H...
, subring
Subring
In mathematics, a subring of R is a subset of a ring, is itself a ring with the restrictions of the binary operations of addition and multiplication of R, and which contains the multiplicative identity of R...
or subspace
Subspace topology
In topology and related areas of mathematics, a subspace of a topological space X is a subset S of X which is equipped with a natural topology induced from that of X called the subspace topology .- Definition :Given a topological space and a subset S of X, the...
generated by S. For any subobject U of X, let G(U) be the underlying set of U. (We can even take X to be a topological space
Topological space
Topological spaces are mathematical structures that allow the formal definition of concepts such as convergence, connectedness, and continuity. They appear in virtually every branch of modern mathematics and are a central unifying notion...
, let F(S) the closure
Closure (topology)
In mathematics, the closure of a subset S in a topological space consists of all points in S plus the limit points of S. Intuitively, these are all the points that are "near" S. A point which is in the closure of S is a point of closure of S...
of S, and take as "subobjects of X" the closed subsets of X.) Now F and G form a monotone Galois connection if the sets and subobjects are ordered by inclusion. F is the lower adjoint.
Syntax and semantics
A very general comment of William LawvereWilliam Lawvere
Francis William Lawvere is a mathematician known for his work in category theory, topos theory and the philosophy of mathematics.-Biography:...
is that syntax and semantics are adjoint: take A to be the set of all logical theories (axiomatizations), and B 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 T; for a set of mathematical structures S, let G(S) be the minimal axiomatization of S. We can then say that F(T) is a subset of S if and only if T logically implies G(S): the "semantics functor" F and the "syntax functor" G form a monotone Galois connection, with semantics being the lower adjoint.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 theoryDuality (order theory)
In the mathematical area of order theory, every partially ordered set P gives rise to a dual partially ordered set which is often denoted by Pop or Pd. This dual order Pop is defined to be the set with the inverse order, i.e. x ≤ y holds in Pop if and only if y ≤ x holds in P...
), 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 if one considers any elements x and y of A such that x ≤ y, then one can clearly use the above findings to obtain
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)),
i.e., f ∗
f ∗ is idempotent.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 operatorClosure operator
In mathematics, a closure operator on a set S is a function cl: P → P from the power set of S to itself which satisfies the following conditions for all sets X,Y ⊆ S....
on A. 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 c on some poset A gives rise to the Galois connection with lower adjoint f ∗ being just the corestriction of c to the image of c (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 A, that maps each closed element to itself, considered as an element of A. 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 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 preserve all supremaSupremum
In mathematics, given a subset S of a totally or partially ordered set T, the supremum of S, if it exists, is the least element of T that is greater than or equal to every element of S. Consequently, the supremum is also referred to as the least upper bound . If the supremum exists, it is unique...
that exist within their domain. Dually, upper adjoints preserve all existing infima
Infimum
In mathematics, the infimum of a subset S of some partially ordered set T is the greatest element of T that is less than or equal to all elements of S. Consequently the term greatest lower bound is also commonly used...
. 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 lattice
Complete lattice
In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum and an infimum . Complete lattices appear in many applications in mathematics and computer science...
s 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 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
Completeness (order theory)
In the mathematical area of order theory, completeness properties assert the existence of certain infima or suprema of a given partially ordered set . A special use of the term refers to complete partial orders or complete lattices...
. Thus, when one adjoint of a Galois connection is given, the other can be defined via this property. On the other hand, some arbitrary function f is a lower adjoint if and only if
If and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
each set of the form { x in A | f(x) ≤ b }, 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 categoriesCategory theory
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...
of posets. Especially, it is possible to compose Galois connections: given Galois connections (f ∗, f ∗) between posets A and B and (g ∗, g ∗) between B and C, 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 framesComplete Heyting algebra
In mathematics, especially in order theory, a complete Heyting algebra is a Heyting algebra which is complete as a lattice. Complete Heyting algebras are the objects of three different categories; the category CHey, the category Loc of locales, and its opposite, the category Frm of frames...
(or locales).
Connection to category theory
Every partially ordered set can be viewed as a categoryCategory theory
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...
in a natural way: there is a unique morphism from x to y if and only if
If and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
x ≤ y. A Galois connection is then nothing but a pair of adjoint functors
Adjoint functors
In mathematics, adjoint functors are pairs of functors which stand in a particular relationship with one another, called an adjunction. The relationship of adjunction is ubiquitous in mathematics, as it rigorously reflects the intuitive notions of optimization and efficiency...
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
Dual (category theory)
In category theory, a branch of mathematics, duality is a correspondence between properties of a category C and so-called dual properties of the opposite category Cop...
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 interpretationAbstract interpretation
In computer science, abstract interpretation is a theory of sound approximation of the semantics of computer programs, based on monotonic functions over ordered sets, especially lattices. It can be viewed as a partial execution of a computer program which gains information about its semantics In...
of programming language
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
s.