In mathematics, especially in order theory, a Galois connection is a particular correspondence between two partially ordered sets ("posets"). Galois connections generalize the correspondence between subgroups and subfields investigated in Galois theory. They find applications in various mathematical theories as well as in the theory of programming. Wikibooks Wikiversity has more about this subject: School of Mathematics Wikiquote has a collection of quotations related to: Mathematics Look up Mathematics in Wiktionary, the free dictionary Wikimedia Commons has media related to: Mathematics Interactive Mathematics Miscellany and Puzzles — A collection of articles on various math topics, with interactive Java... Order theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of a mathematical ordering. ... In mathematics, especially order theory, a partially ordered set (or poset for short) is a set equipped with a partial order relation. ... In group theory, given a group G under a binary operation *, we say that some subset H of G is 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 is a group... In abstract algebra, a field is an algebraic structure in which the operations of addition, subtraction, multiplication and division (except division by zero) may be performed, and the same rules hold which are familiar from the arithmetic of ordinary numbers. ... In mathematics, Galois theory is a branch of abstract algebra. ...

A Galois connection is rather weaker than an isomorphism between the involved posets, but every Galois connection gives rise to an isomorphism of certain sub-posets, as will be explained below. In mathematics, an isomorphism (in Greek isos = equal and morphe = shape) is a kind of mapping between objects, devised by Eilhard Mitscherlich, which shows a relation between two properties or operations. ...

Definition

Suppose (A, ≤) and (B, <=) are two partially ordered sets. 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 mathematics, functions between ordered sets are monotonic (or monotone) if they preserve the given order. ... In mathematics, a function is a relation, such that each element of a set (the domain) is associated with a unique type of another (possibly the same) set (the codomain, not to be confused with the range). ...

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. This terminology relates to the connections to category theory discussed below. As detailed below, each part of a Galois connection uniquely determines the other mapping. Viewing two functions that form a Galois connections as two specifications of the same object, it is convenient to 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. Category theory is a mathematical theory that deals in an abstract way with mathematical structures and relationships between them. ... An asterisk (*) is a typographical symbol or glyph. ...

Alternative definition

The above definition is common in many applications today, and prominent in lattice and domain theory. However, a slightly different notion has originally been derived in Galois theory. 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 term lattice derives from the shape of the Hasse diagrams that result from depicting these orders. ... Domain theory is a branch of mathematics that studies special kinds of partially ordered sets commonly called domains. ...

b ≤ F(a) if and only if a ≤ G(b) . (Note: This is a correction of an earlier definition.)

Both notions of a Galois connection are still present in the literature. In Wikipedia 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 B^op of B. All of the below statements on Galois connections can thus easily be converted into statements about antitone Galois connections. In the mathematical area of order theory, every partially ordered set P gives rise to a dual (or opposite) partially ordered set which is often denoted by Pop. ...

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.

Examples

• The motivating example comes from Galois theory: suppose L/K is a field extension. 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 subgroups 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.

• For an order theoretic example, let U be some set, and let A and B 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. 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".

• Further interesting examples for Galois connections are described in the article on completeness properties. 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 lattices can be characterized by the existence of suitable adjoints. These considerations give some impression of the ubiquity of Galois connections in order theory.

• 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[X₁,...,X_n] ordered by inclusion , and let B be the set of all subsets of Kⁿ ordered by inclusion . If S is a set of polynomials, define F(S) = {xKⁿ : f(x) = 0 for all fS}, the set of common zeros of the polynomials in S. If T is a subset of Kⁿ, define G(T) = {fK[X₁,...,X_n] : f(x) = 0 for all xT}. Then F and G form an antitone Galois connection.

• If f : X → Y is a function, 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 . Interestingly, there is another 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.

• Pick some mathematical object X that has an underlying set, for instance a group, 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.

• A very general comment of Martin Hyland 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.

• Finally, 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) = { yY : mRy for all mM}. 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 .

In abstract algebra, an extension of a field K is a field L which contains K as a subfield. ... In group theory, given a group G under a binary operation *, we say that some subset H of G is 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 is a group... In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ... In mathematics, given a set S, the power set (or powerset) of S, written or 2S, is the set of all subsets of S. In axiomatic set theory (as developed e. ... In mathematics, Heyting algebras are special partially ordered sets that constitute a generalization of Boolean algebras. ... Wikibooks has more about Boolean logic, under the title Boolean Algebra For a basic intro to sets, Boolean operations, Venn diagrams, truth tables, and Boolean applications, see Boolean logic. ... In the mathematical area of order theory, completeness properties assert the existence of certain infima or suprema of a given partially ordered set. ... In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum (join) and an infimum (meet). ... Algebraic geometry is a branch of mathematics which, as the name suggests, combines abstract algebra, especially commutative algebra, with geometry. ... In mathematics, polynomial functions, or polynomials, are an important class of simple and smooth functions. ... Natural number can mean either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). Natural numbers have two main purposes: they can be used for counting (there are 3 apples on the table), and they can be used for ordering (this is... In abstract algebra, a field is an algebraic structure in which the operations of addition, subtraction, multiplication and division (except division by zero) may be performed, and the same rules hold which are familiar from the arithmetic of ordinary numbers. ... In abstract algebra, a polynomial ring is the set of polynomials in one or more variables with coefficients in a ring. ... In mathematics, a function is a relation, such that each element of a set (the domain) is associated with a unique type of another (possibly the same) set (the codomain, not to be confused with the range). ... In mathematics, a group is a set, together with a binary operation, such as multiplication or addition, satisfying certain axioms, detailed below. ... In mathematics, a ring is an algebraic structure in which addition and multiplication are defined and have similar (but not identical) properties to those familiar from the integers. ... A vector space (or linear space) is the basic object of study in the branch of mathematics called linear algebra. ... In group theory, given a group G under a binary operation *, we say that some subset H of G is 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 is a group... In abstract algebra, a branch of mathematics, a subring is a subset of a ring containing the multiplicative identity, which is itself a ring under the same binary operations. ... Screenshot (from SSCX Star Warzone). ... Topological spaces are structures that allow one to formalize concepts such as convergence, connectedness and continuity. ... In mathematics, the closure of a set S consists of all points which are intuitively close to S. A point which is in the closure of S is a point of closure of S. The notion of closure is in many ways dual to the notion of interior. ... In mathematics, the concept of binary relation, sometimes called dyadic relation, is exemplified by such ideas as is greater than and is equal to in arithmetic, or is congruent to in geometry, or is an element of or is a subset of in set theory. ...

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). In the mathematical area of order theory, every partially ordered set P gives rise to a dual (or opposite) partially ordered set which is often denoted by Pop. ...

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. Similarly, since f ^∗f _∗ is deflationary, one finds that

f ^∗ f _∗ f ^∗ f _∗(x) ≤ f ^∗ f _∗(x) ≤ x,

which is equivalent to

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 the 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 mathematics, given a partially ordered set (P, ≤), a closure operator on P is a function C : P → P with the following properties: if x ≤ y, then C(x) ≤ C(y), i. ...

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 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 the mathematical area of order theory, one often speaks about functions that preserve certain limits, i. ... In mathematics, the supremum of an ordered set S is the least element that is greater than or equal to each element of S. Consequently, it is also referred to as the least upper bound (also lub and LUB). ... In mathematics, the domain of a function is the set of all input values to the function. ... In mathematics the infimum of a subset of some set is the greatest element, not necessarily in the subset, that is smaller than all other elements of the subset. ... In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum (join) and an infimum (meet). ...

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 iff 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. In the mathematical area of order theory, completeness properties assert the existence of certain infima or suprema of a given partially ordered set. ... ↔ ⇔ ≡ For other possible meanings of iff, see IFF. In mathematics, philosophy, logic and technical fields that depend on them, iff is used as an abbreviation for if and only if. Common alternative phrases to iff or if and only if include Q is necessary and sufficient for P and P...

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 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). Category theory is a mathematical theory that deals in an abstract way with mathematical structures and relationships between them. ... In category theory, an abstract branch of mathematics, an equivalence of categories is a relation between two categories that establishes that these categories are essentially the same. There are numerous examples of categorical equivalences from many areas of mathematics. ... In mathematics, especially in order theory, a complete Heyting algebra is a Heyting algebra which is complete as a lattice. ...

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 iff 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. Category theory is a mathematical theory that deals in an abstract way with mathematical structures and relationships between them. ... ↔ ⇔ ≡ For other possible meanings of iff, see IFF. In mathematics, philosophy, logic and technical fields that depend on them, iff is used as an abbreviation for if and only if. Common alternative phrases to iff or if and only if include Q is necessary and sufficient for P and P... The existence of many pairs of adjoint functors is a major observation of the branch of mathematics known as category theory. ... In category theory, an abstract branch of mathematics, the dual of a category C is the category formed by reversing all the morphisms of C. That is, we take Cop to be the category with objects that are those of C, but with the morphisms from X to Y in...

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. Abstract interpretation is a theory of sound approximation of the semantics of computer programs, based on monotonic functions over ordered sets, especially lattices. ... A programming language or computer language is a standardized communication technique for expressing instructions to a computer. ...

References

A freely available introduction to Galois connections, presenting many examples and results. Also includes notes on the different notations and definitions that arose in this area:

• M. Erné, J. Koslowski, A. Melton, G. 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. Available online in various file formats: PS.GZ PS

The following standard reference books also include Galois connections using modern notation and definitions:

• B. A. Davey and H. A. Priestley: Introduction to lattices and Order, Cambridge University Press, 2002.
• G. Gierz, K. H. Hoffmann, K. Keimel, J. D. Lawson, M. Mislove, D. S. Scott: Continuous Lattices and Domains, Cambridge University Press, 2003.

Finally, some publications using the original (antitone) definition:

• Garrett Birkhoff: Lattice Theory, Amer. Math. Soc. Coll. Pub., Vol 25, 1940
• Oystein Ore: Galois Connexions, Transactions of the American Mathematical Society 55 (1944), pp. 493-513