Galois connection

# Galois connection

Discussion

Encyclopedia
In mathematics
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 sets
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...

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

aG(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
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 lattice
Lattice (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
bF(a) if and only if aG(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 mapping
Residuated 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 extension
Field 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 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 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 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...

, 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
Semi-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 algebra
Heyting 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 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...

. 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
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 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 relation
Binary 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 geometry
Algebraic 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 as
the set of common zeros of the polynomials in S.

If U is a subset of Kn, define the radical 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 topology
Zariski 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 Spec
Spectrum 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 : XY is a function
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...

, then for any subset M of X we can form the image F(M) = f(M) = {f(m) : mM} 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 group
Group (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 Lawvere
William 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 TA, 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: AB 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 xf( f(x)), for all x in A. By a similar reasoning (or just by applying the duality principle for order theory
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...

), one finds that f( f(y)) ≤ y, for all y in B. These properties can be described by saying the composite ff is deflationary, while ff is inflationary (or extensive).

Now if one considers any elements x and y of A such that xy, then one can clearly use the above findings to obtain
xf(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 ff is inflationary as shown above. On the other hand, since ff 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., ff is idempotent.

## Closure operators and Galois connections

The above findings can be summarized as follows: for a Galois connection, the composite ff is monotone (being the composite of monotone functions), inflationary, and idempotent. This states that ff is in fact a closure operator
Closure 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, ff is monotone, deflationary, and idempotent. Such mappings are sometimes called kernel operators. In the context of frames and locales, the composite ff 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 suprema
Supremum
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 xf(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 categories
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...

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 (gf, fg) 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
Complete 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 category
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...

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

xy. A Galois connection is then nothing but a pair of 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 interpretation
Abstract 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.