Galois connection - Citizendia

In mathematics, especially in order theory, a Galois connection is a particular correspondence between two partially ordered sets (posets). Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and Order theory is a branch of Mathematics that studies various kinds of Binary relations that capture the intuitive notion of ordering providing a framework for saying In Mathematics, especially Order theory, a partially ordered set (or poset) formalizes the intuitive concept of an ordering sequencing or arrangement Galois connections generalize the correspondence between subgroups and subfields investigated in Galois theory. In Group theory, given a group G under a Binary operation * we say that some Subset H of G is a subgroup of In Abstract algebra, a field is an Algebraic structure in which the operations of Addition, Subtraction, Multiplication and division In Mathematics, more specifically in Abstract algebra, Galois theory, named after Évariste Galois, provides a connection between field theory They find applications in various mathematical theories.

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 Abstract algebra, an isomorphism ( Greek: ἴσος isos "equal" and μορφή morphe "shape" is a bijective

Like Galois theory, Galois connections are named after the French mathematician Évariste Galois.

Definition

Let (A, ≤) and (B, ≤) be two partially ordered sets. A Galois connection between these posets consists of two monotone^[1] functions: F : A → B and G : B → A, such that for all a in A and b in B, we have

F(a) ≤ b if and only if a ≤ G(b). The Mathematical concept of a function expresses dependence between two quantities one of which is given (the independent variable, argument of the function ↔

In this situation, F is called the lower adjoint of G and G is called the upper adjoint of F. This terminology relates the Galois connections to category theory discussed below. In Mathematics, category theory deals in an abstract way with mathematical Structures and relationships between them it abstracts from sets As detailed below, each part of a Galois connection uniquely determines the other mapping. Viewing two functions that form a Galois connection 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. An asterisk ( *) (Latin asteriscum "little star" from Greek ἀστερίσκος) is a Typographical symbol or Glyph

Alternative definition

The above definition is common in many applications today, and prominent in lattice and domain theory. In Mathematics, a lattice is a Partially ordered set (also called a poset) in which every pair of elements has a unique Supremum (the elements' Domain theory is a branch of Mathematics that studies special kinds of Partially ordered sets (posets commonly called domains. 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) . (Note: This is a correction of an earlier definition. )

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 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. In the mathematical area of Order theory, every Partially ordered set P gives rise to a dual (or opposite) partially ordered set which 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.

Examples

Galois theory

The motivating example comes from Galois theory: suppose L /K is a field extension. In Mathematics, more specifically in Abstract algebra, field extensions are the main object of study in field theory. Let A be the set of all subfields of L that contain K, ordered by inclusion $\subseteq$ . 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 $\subseteq$ . In Group theory, given a group G under a Binary operation * we say that some Subset H of G is a subgroup of 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 $\mapsto$ Gal(L /E) and G $\mapsto$ Fix(G) form an antitone Galois connection.

Algebraic topology: covering spaces

Analogously, given a path-connected topological space $X$ , there is a Galois connection between subgroups of the fundamental group $π 1 (X)$ and path-connected covering spaces of $X$ . In Topology and related branches of Mathematics, a connected space is a Topological space which cannot be represented as the disjoint union of Topological spaces are mathematical structures that allow the formal definition of concepts such as Convergence, connectedness, and continuity. In Topology and related branches of Mathematics, a connected space is a Topological space which cannot be represented as the disjoint union of In particular, if X is semi-locally simply connected, then for every subgroup $G$ of $π 1 (X)$ , there is a covering space with $G$ as its fundamental group. In Mathematics, in particular Topology, a Topological space X is called semi-locally simply connected if every point x

Order theory

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. In Mathematics, given a set S, the power set (or powerset) of S, written \mathcal{P}(S P ( S) 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. In Mathematics, Heyting algebras are special Partially ordered sets that constitute a generalization of Boolean algebras named after Arend Heyting Especially, it is present in any Boolean algebra, where the two mappings can be described by F(x) = (a $\wedge$ x) and G(y) = (y $\vee$ $\neg$ a) = (a $\Rightarrow$ y). In Abstract algebra, a Boolean algebra or Boolean lattice is a complemented distributive lattice. 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. In the mathematical area of Order theory, completeness properties assert the existence of certain infima or suprema of a given partially ordered It turns out that the usual functions $\vee$ and $\wedge$ 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. In Mathematics, a complete lattice is a Partially ordered set in which all subsets have both a Supremum (join and an Infimum (meet 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 R over X and Y is given. In Mathematics, a binary relation (or a dyadic or 2-place relation) is an arbitrary association of elements within a set or with elements of For any subset M of X, we define F(M) = { y $\in$ Y : mRy for all m $\in$ M}. Similarly, for any subset N of Y, define G(N) = { x $\in$ X : xRn for all n $\in$ N}. Then F and G yield an antitone Galois connection between the power sets of X and Y, both ordered by inclusion $\subseteq$ .

An important special case in linear algebra is the annihilator, which includes the orthogonal complement as a special case. Linear algebra is the branch of Mathematics concerned with In Mathematics, specifically Module theory, annihilators are a concept that formalizes torsion and generalizes torsion and Orthogonal complement In the mathematical fields of Linear algebra and Functional analysis, the orthogonal complement W^\bot of a subspace W

Algebraic geometry

In algebraic geometry, the relation between sets of polynomials and their zero sets is an antitone Galois connection. Algebraic geometry is a branch of Mathematics which as the name suggests combines techniques of Abstract algebra, especially Commutative algebra, with In Mathematics, a polynomial is an expression constructed from Variables (also known as indeterminates and Constants using the operations

Fix a natural number n and a field K and let A be the set of all subsets of the polynomial ring K[X₁,. In Mathematics, a natural number (also called counting number) can mean either an element of the set (the positive Integers or an In Abstract algebra, a field is an Algebraic structure in which the operations of Addition, Subtraction, Multiplication and division 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 . . ,X_n] ordered by inclusion $\subseteq$ , and let B be the set of all subsets of Kⁿ ordered by inclusion $\subseteq$ . If S is a set of polynomials, define the variety of zeros as

$V(S) = \{x \in K^n : f(x) = 0 \mbox{ for all } f \in S\},$

the set of common zeros of the polynomials in S. Algebraic geometry is a branch of Mathematics which as the name suggests combines techniques of Abstract algebra, especially Commutative algebra, with

If U is a subset of Kⁿ, define the radical ideal of polynomials vanishing on U as

$I(U) = \{ f \in K[X_1,\dots,X_n] : f(x) = 0 \mbox{ for all } x \in U\}.$

Then V and I form an antitone Galois connection. In Ring theory, a branch of Mathematics, the radical of an ideal is a kind of completion of the ideal.

The closure on the polynomial ring is "radical ideal generated by U", while the closure on $K n$ is the closure in the Zariski topology. In Mathematics, namely Algebraic geometry, the Zariski topology is a particular Topology chosen for algebraic varieties that reflects the algebraic

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 $\operatorname{Spec}\,R$ (namely Spec of the ring). Algebraic geometry is a branch of Mathematics which as the name suggests combines techniques of Abstract algebra, especially Commutative algebra, with In Abstract algebra and Algebraic geometry, the spectrum of a Commutative ring R, denoted by Spec( R) is defined to be the set of

More generally, there is an antitone Galois connection between ideals in the ring and subschemes of the corresponding affine variety. Algebraic geometry is a branch of Mathematics which as the name suggests combines techniques of Abstract algebra, especially Commutative algebra, with

Image and inverse image

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) : m $\in$ M} and for any subset N of Y we can form the inverse image G(N) = f^-1(N) = {x $\in$ X : f(x) $\in$ N}. The Mathematical concept of a function expresses dependence between two quantities one of which is given (the independent variable, argument of the function 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 $\subseteq$ . There is a further adjoint pair in this situation: for a subset M of X, define H(M) = {y $\in$ Y : f^-1({y}) $\subseteq$ 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 $\bar H = HN$ . In Mathematics, the lattice theorem, sometimes improperly referred to as the fourth Isomorphism theorem or the correspondence theorem states that there exists a

Span and closure

Pick some mathematical object X that has an underlying set, for instance a group, ring, vector space, etc. In Mathematics, a group is a set of elements together with an operation that combines any two of its elements to form a third element In Mathematics, a ring is an Algebraic structure which generalizes the algebraic properties of the Integers though the rational, real In Mathematics, a vector space (or linear space) is a collection of objects (called vectors) that informally speaking may be scaled and added 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. In Group theory, given a group G under a Binary operation * we say that some Subset H of G is a subgroup of In Mathematics, a subring is a Subset of a ring, which contains the Multiplicative identity and is itself a ring under the same Binary operations Subspace may refer to;Mathematics Euclidean subspace, in linear algebra a set of vectors in n -dimensional Euclidean space that is closed under addition 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. Topological spaces are mathematical structures that allow the formal definition of 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 " ) 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 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. J Martin E Hyland is professor of mathematics at King's College in the University of Cambridge, England. For a theory T $\in$ 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 theory), one finds that f ^∗( f _∗(y)) ≤ y, for all y in B. In the mathematical area of Order theory, every Partially ordered set P gives rise to a dual (or opposite) partially ordered set which These properties can be described by saying the composite f ^∗ $\circ$ f _∗ is deflationary, while f _∗ $\circ$ 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 _∗ $\circ$ f ^∗ is inflationary as shown above. Similarly, since f ^∗ $\circ$ 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 ^∗ $\circ$ f _∗ is idempotent.

Closure operators and Galois connections

The above findings can be summarized as follows: for a Galois connection, the composite f _∗ $\circ$ f ^∗ is monotone (being the composite of monotone functions), inflationary, and idempotent. This states the f _∗ $\circ$ f ^∗ is in fact a closure operator on A. A closure operator on a set S is a function cl P ( S) → P ( S) from the Power set of S Dually, f ^∗ $\circ$ f _∗ is monotone, deflationary, and idempotent. Such mappings are sometimes called kernel operators. In the context of frames and locales, the composite f _∗ $\circ$ f ^∗ is called the nucleus induced by f. In Mathematics, especially in Order theory, a complete Heyting algebra is a Heyting algebra which is complete as a lattice. 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 ^∗ $\circ$ 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. In the mathematical area of Order theory, one often speaks about functions that preserve certain limits i In Mathematics, the domain of a given function is the set of " Input " values for which the function is defined Dually, upper adjoints preserve all existing infima. In Mathematics the infimum of a Subset of some set is the Greatest element, not necessarily in the subset that is less than or equal to all elements of 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 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. In the mathematical area of Order theory, completeness properties assert the existence of certain infima or suprema of a given partially ordered 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.

Galois connections as morphisms

Galois connections also provide an interesting class of mappings between posets which can be used to obtain categories of posets. In Mathematics, category theory deals in an abstract way with mathematical Structures and relationships between them it abstracts from sets 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 ^∗ $\circ$ f ^∗, f _∗ $\circ$ 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. In Category theory, an abstract branch of Mathematics, an equivalence of categories is a relation between two categories that establishes that these categories are More special kinds of morphisms that induce adjoint mappings in the other direction are the morphisms usually considered for frames (or locales). 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 if and only if x ≤ y. In Mathematics, category theory deals in an abstract way with mathematical Structures and relationships between them it abstracts from sets ↔ 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. In Category theory, an abstract branch of Mathematics, the dual category or opposite category C op of a category C is the e. with arrows pointing in the opposite direction. This led to a complementary notation concerning left and right adjoints, which today is ambiguous.

Applications in the theory of programming

Galois connections may be used to describe many forms of abstraction in the theory of abstract interpretation of programming languages. In Computer science, abstract interpretation is a theory of sound approximation of the Semantics of computer programs based on Monotonic functions A programming language is an Artificial language that can be used to write programs which control the behavior of a machine particularly a Computer.

Notes

^ Monotonicity follows from the following condition. See the discussion of the properties. It is only explicit in the definition to distinguish it from the alternative antitone definition. One can also define Galois connections as a pair of monotone functions that satisfy the laxer condition that for all x in A, x ≤ g(f(x)) and for all y in B, f(g(y)) ≤ y.

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. Hofmann, 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
Øystein Ore: Galois Connexions, Transactions of the American Mathematical Society 55 (1944), pp. 493-513

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |

Contents