Editing Galois connection (section)

== Examples ==

===Bijections===
The [[bijection]] of a pair of functions <math>f:X\to Y</math> and <math>g:Y\to X,</math> each other's inverse, forms a (trivial) Galois connection, as follows. Because the [[equality relation]] is reflexive, transitive and antisymmetric, it is, trivially, a [[partial order]], making <math>(X,=)</math> and <math>(Y,=)</math> partially ordered sets. Since <math>f(x)=y</math> if and only if <math>x=g(y),</math> we have a Galois connection.

===Monotone Galois connections===

====Floor; ceiling====
A monotone Galois connection between <math>\Z,</math> the set of [[integer]]s and <math>\R,</math> the set of [[real number]]s, each with its usual ordering, is given by the usual [[embedding]] function of the integers into the reals and the [[floor function]] truncating a real number to the greatest integer less than or equal to it. The embedding of integers is customarily done implicitly, but to show the Galois connection we make it explicit. So let <math>F:\Z\to\R</math> denote the embedding function, with <math>F(n)=n\in\R,</math> while <math>G:\R\to\Z</math> denotes the floor function, so <math>G(x)=\lfloor x\rfloor.</math> The equivalence <math>F(n)\leq x ~\Leftrightarrow~ n\leq G(x)</math> then translates to
:<math>n\leq x ~\Leftrightarrow~ n\leq\lfloor x\rfloor.</math>
This is valid because the variable <math>n</math> is restricted to the integers. The well-known properties of the floor function, such as <math>\lfloor x+n\rfloor=\lfloor x\rfloor+n,</math> can be derived by elementary reasoning from this Galois connection.

The dual orderings give another monotone Galois connection, now with the [[ceiling function]]:
:<math>x\leq n ~\Leftrightarrow~ \lceil x\rceil\leq n.</math>

====Power set; implication and conjunction====
For an order-theoretic example, let {{mvar|U}} be some [[set (mathematics)|set]], and let {{mvar|A}} and {{mvar|B}} both be the [[power set]] of {{mvar|U}}, ordered by [[set inclusion|inclusion]]. Pick a fixed [[subset]] {{mvar|L}} of {{mvar|U}}. Then the maps {{mvar|F}} and {{mvar|G}}, where {{math|''F''(''M''&hairsp;) {{=}} ''L'' ∩ ''M''}}, and {{math|''G''(''N''&hairsp;) {{=}} ''N'' ∪ (''U''&thinsp;\&thinsp;''L'')}}, form a monotone Galois connection, with {{mvar|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 (structure)|Boolean algebra]], where the two mappings can be described by {{math|''F''(''x'') {{=}} (''a'' ∧ ''x'')}} and {{math|''G''(&hairsp;''y'') {{=}} (&hairsp;''y'' ∨ ¬''a'') {{=}} (''a'' ⇒ ''y'')}}. In [[mathematical logic|logical]] terms: "implication from {{mvar|a}}" is the upper adjoint of "conjunction with {{mvar|a}}".

====Lattices====
Further interesting examples for Galois connections are described in the article on [[completeness (order theory)|completeness properties]]. Roughly speaking, the usual functions ∨ and ∧ are lower and upper adjoints to the [[diagonal map]] {{math|''X'' → ''X'' × ''X''}}. The least and greatest elements of a partial order are given by lower and upper adjoints to the unique function {{math|''X'' → {1}.}} 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.

====Transitive group actions====
Let {{mvar|G}} [[group action|act]] [[Group action#Transitivity properties|transitively]] on {{mvar|X}} and pick some point {{mvar|x}} in {{mvar|X}}. Consider

:<math>\mathcal{B} = \{B \subseteq X : x \in B; \forall g \in G, gB = B \ \mathrm{or} \ gB \cap B = \emptyset\},</math>

the set of '''blocks''' containing {{mvar|x}}. Further, let <math>\mathcal{G}</math> consist of the [[subgroup]]s of {{mvar|G}} containing the [[Group action#Orbits and stabilizers|stabilizer]] of {{mvar|x}}.

Then, the correspondence <math>\mathcal{B} \to \mathcal{G}</math>:
:<math> B \mapsto H_B = \{g \in G : gx \in B\}</math>
is a monotone, [[injective function|one-to-one]] Galois connection.<ref>See Alperin, Bell, Groups and Representations (GTM 162), p. 32</ref> As a [[corollary]], one can establish that doubly transitive actions have no blocks other than the trivial ones (singletons or the whole of {{mvar|X}}): this follows from the stabilizers being maximal in {{mvar|G}} in that case. See [[2-transitive group|Doubly transitive group]] for further discussion.

====Image and inverse image====
If {{math|&thinsp;''f'' : ''X'' → ''Y''}} is a [[function (mathematics)|function]], then for any subset {{mvar|M}} of {{mvar|X}} we can form the [[image (mathematics)|image]] {{math|''F''(''M''&hairsp;) {{=}} &thinsp;''f''&thinsp;''M'' {{=}} {&thinsp;''f''&thinsp;(''m'') {{!}} ''m'' ∈ ''M''} }} and for any subset {{mvar|N}} of {{mvar|Y}} we can form the [[inverse image]] {{math|''G''(''N''&hairsp;) {{=}} &thinsp;''f''&nbsp;<sup>−1</sup>''N'' {{=}} {''x'' ∈ ''X'' {{!}} &thinsp;''f''&thinsp;(''x'') ∈ ''N''}.}} Then {{mvar|F}} and {{mvar|G}} form a monotone Galois connection between the power set of {{mvar|X}} and the power set of {{mvar|Y}}, both ordered by inclusion ⊆. There is a further adjoint pair in this situation: for a subset {{mvar|M}} of {{mvar|X}}, define {{math|''H''(''M'') {{=}} {''y'' ∈ ''Y'' {{!}} &thinsp;''f''&nbsp;<sup>−1</sup>{''y''} ⊆ ''M''}.}} Then {{mvar|G}} and {{mvar|H}} form a monotone Galois connection between the power set of {{mvar|Y}} and the power set of {{mvar|X}}. In the first Galois connection, {{mvar|G}} is the upper adjoint, while in the second Galois connection it serves as the lower adjoint.

In the case of a [[quotient group|quotient map]] between algebraic objects (such as [[group (mathematics)|groups]]), this connection is called the [[lattice theorem]]: subgroups of {{mvar|G}} connect to subgroups of {{math|''G''/''N''}}, and the closure operator on subgroups of {{mvar|G}} is given by {{math|{{overline|''H''}} {{=}} ''HN''}}.

====Span and closure====
Pick some mathematical object {{mvar|X}} that has an [[underlying set]], for instance a group, [[ring (mathematics)|ring]], [[vector space]], etc. For any subset {{mvar|S}} of {{mvar|X}}, let {{math|''F''(''S''&hairsp;)}} be the smallest [[subobject]] of {{mvar|X}} that contains {{mvar|S}}, i.e. the [[subgroup]], [[subring]] or [[linear subspace|subspace]] generated by {{mvar|S}}. For any subobject {{mvar|U}} of {{mvar|X}}, let {{math|''G''(''U''&hairsp;)}} be the underlying set of {{mvar|U}}. (We can even take {{mvar|X}} to be a [[topological space]], let {{math|''F''(''S''&hairsp;)}} the [[closure (topology)|closure]] of {{mvar|S}}, and take as "subobjects of {{mvar|X}}{{-"}} the [[closed subset]]s of {{mvar|X}}.) Now {{mvar|F}} and {{mvar|G}} form a monotone Galois connection between subsets of {{mvar|X}} and subobjects of {{mvar|X}}, if both are ordered by inclusion. {{mvar|F}} is the lower adjoint.

====Syntax and semantics====
A very general comment of [[William Lawvere]]<ref>[[William Lawvere]], Adjointness in foundations, Dialectica, 1969, [http://www.tac.mta.ca/tac/reprints/articles/16/tr16abs.html available here]. The notation is different nowadays; an easier introduction by Peter Smith [http://www.logicmatters.net/resources/pdfs/Galois.pdf in these lecture notes], which also attribute the concept to the article cited.</ref> is that ''syntax and semantics'' are adjoint: take {{mvar|A}} to be the set of all [[Theory (mathematical logic)|logical theories]] (axiomatizations) reverse ordered by strength, and {{mvar|B}} the power set of the set of all mathematical structures. For a theory {{math|''T'' ∈ ''A''}}, let {{math|Mod(''T''&hairsp;)}} be the set of all structures that satisfy the [[axiom]]s {{mvar|T}}&hairsp;; for a set of mathematical structures {{math|''S'' ∈ ''B''}}, let {{math|Th(''S''&hairsp;)}} be the minimum of the axiomatizations that approximate {{mvar|S}} (in [[first-order logic]], this is the set of sentences that are true in all structures in {{mvar|S}}). We can then say that {{mvar|S}} is a subset of {{math|Mod(''T''&hairsp;)}} if and only if {{math|Th(''S''&hairsp;)}} logically entails {{mvar|T}}: the "semantics functor" {{math|Mod}} and the "syntax functor" {{math|Th}} form a monotone Galois connection, with semantics being the upper adjoint.

===Antitone Galois connections===

====Galois theory====
The motivating example comes from Galois theory: suppose {{math|''L''/''K''}} is a [[field extension]]. Let {{mvar|A}} be the set of all subfields of {{mvar|L}} that contain {{mvar|K}}, ordered by inclusion ⊆. If {{mvar|E}} is  such a subfield, write {{math|Gal(''L''/''E'')}} for the group of [[field automorphism]]s of {{mvar|L}} that hold {{mvar|E}} fixed. Let {{mvar|B}} be the set of subgroups of {{math|Gal(''L''/''K'')}}, ordered by inclusion ⊆. For such a subgroup {{mvar|G}}, define {{math|Fix(''G'')}} to be the field consisting of all elements of {{mvar|L}} that are held fixed by all elements of {{mvar|G}}. Then the maps {{math|''E'' {{mapsto}} Gal(''L''/''E'')}} and {{math|''G'' {{mapsto}} Fix(''G'')}} form an antitone Galois connection.

====Algebraic topology: covering spaces====
Analogously, given a [[path-connected]] [[topological space]] {{mvar|X}}, there is an antitone Galois connection between subgroups of the [[fundamental group]] {{math|''π''<sub>1</sub>(''X'')}} and path-connected [[covering space]]s of {{mvar|X}}. In particular, if {{mvar|X}} is [[semi-locally simply connected]], then for every subgroup {{mvar|G}} of {{math|''π''<sub>1</sub>(''X'')}}, there is a covering space with {{mvar|G}} as its fundamental group.

====Linear algebra: annihilators and orthogonal complements====
Given an [[inner product space]] {{mvar|V}}, we can form the [[orthogonal complement]] {{math|''F''(''X''&hairsp;)}} of any subspace {{mvar|X}} of {{mvar|V}}. This yields an antitone Galois connection between the set of subspaces of {{mvar|V}} and itself, ordered by inclusion; both polarities are equal to {{mvar|F}}.

Given a [[vector space]] {{mvar|V}} and a subset {{mvar|X}} of {{mvar|V}} we can define its annihilator {{math|''F''(''X''&hairsp;)}}, consisting of all elements of the [[dual space]] {{math|''V''&hairsp;<sup>∗</sup>}} of {{mvar|V}} that vanish on {{mvar|X}}. Similarly, given a subset {{mvar|Y}} of {{math|''V''&hairsp;<sup>∗</sup>}}, we define its annihilator {{math|''G''(''Y''&thinsp;) {{=}} {&hairsp;''x'' ∈ ''V'' {{!}} ''φ''(''x'') {{=}} 0 ∀''φ'' ∈ ''Y''&hairsp;}.}} This gives an antitone Galois connection between the subsets of {{mvar|V}} and the subsets of {{math|''V''&hairsp;<sup>∗</sup>}}.

====Algebraic geometry====
In [[algebraic geometry]], the relation between sets of [[polynomial]]s and their zero sets is an antitone Galois connection.

Fix a [[natural number]] {{mvar|n}} and a [[field (mathematics)|field]] {{mvar|K}} and let {{mvar|A}} be the set of all subsets of the [[polynomial ring]] {{math|''K''[''X''<sub>1</sub>, ..., ''X<sub>n</sub>'']}} ordered by inclusion ⊆, and let {{mvar|B}} be the set of all subsets of {{math|''K''<sup>&hairsp;''n''</sup>}} ordered by inclusion ⊆. If {{mvar|S}} is a set of polynomials, define the [[Algebraic geometry#Affine varieties|variety]] of zeros as

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

the set of common [[root of a polynomial|zeros]] of the polynomials in {{mvar|S}}. If {{mvar|U}} is a subset of {{math|''K''<sup>&hairsp;''n''</sup>}}, define {{math|''I''(''U''&hairsp;)}} as the [[ideal (ring theory)|ideal]] of polynomials vanishing on {{mvar|U}}, that is

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

Then {{mvar|V}} and ''I'' form an antitone Galois connection.

The closure on {{math|''K''<sup>&hairsp;''n''</sup>}} is the closure in the [[Zariski topology]], and if the field {{mvar|K}} is [[Algebraically closed field|algebraically closed]], then the closure on the polynomial ring is the [[Radical of an ideal|radical]] of ideal generated by {{mvar|S}}.

More generally, given a [[commutative ring]] {{mvar|R}} (not necessarily a polynomial ring), there is an antitone Galois connection between radical ideals in the ring and Zariski closed subsets of the [[Algebraic geometry#Affine varieties|affine variety]] {{math|[[Spectrum of a ring|Spec]](''R'')}}.

More generally, there is an antitone Galois connection between ideals in the ring and [[subscheme]]s of the corresponding [[Algebraic geometry#Affine varieties|affine variety]].

====Connections on power sets arising from binary relations====
Suppose {{mvar|X}} and {{mvar|Y}} are arbitrary sets and a [[binary relation]] {{mvar|R}} over {{mvar|X}} and {{mvar|Y}} is given. For any subset {{mvar|M}} of {{mvar|X}}, we define {{math|''F''(''M''&hairsp;) {{=}} {&hairsp;''y'' ∈ ''Y'' {{!}} ''mRy'' ∀''m'' ∈ ''M''&hairsp;}.}} Similarly, for any subset {{mvar|N}} of {{mvar|Y}}, define {{math|''G''(''N''&hairsp;) {{=}} {&hairsp;''x'' ∈ ''X'' {{!}} ''xRn'' ∀''n'' ∈ ''N''&hairsp;}.}} Then {{mvar|F}} and {{mvar|G}} yield an antitone Galois connection between the power sets of {{mvar|X}} and {{mvar|Y}}, both ordered by inclusion ⊆.{{sfn|Birkhoff|1940|loc=§32; 3rd edition (1967): Ch. V, §7 and §8}}

Up to isomorphism ''all'' antitone Galois connections between power sets arise in this way. This follows from the "Basic Theorem on Concept Lattices".<ref>Ganter, B. and Wille, R. ''Formal Concept Analysis -- Mathematical Foundations'', Springer (1999), {{ISBN|978-3-540-627715}}</ref> Theory and applications of Galois connections arising from binary relations are studied in [[formal concept analysis]]. That field uses Galois connections for mathematical data analysis.  Many algorithms for Galois connections can be found in the respective literature, e.g., in.<ref>Ganter, B. and Obiedkov, S. ''Conceptual Exploration'', Springer (2016), {{ISBN|978-3-662-49290-1}}</ref>

The [[General Concept Lattice|general concept lattice]] in its primitive version incorporates both the monotone and antitone Galois connections to furnish its upper and lower bounds of nodes for the concept lattice, respectively.<ref name=":1">{{Cite journal |last1=Liaw |first1=Tsong-Ming |last2=Lin |first2=Simon C. |date=2020-10-12 |title=A general theory of concept lattice with tractable implication exploration |url=https://www.sciencedirect.com/science/article/pii/S0304397520302826 |url-status=live |journal=Theoretical Computer Science |language=en |volume=837 |pages=84–114 |doi=10.1016/j.tcs.2020.05.014 |issn=0304-3975 |s2cid=219514253 |archive-url=https://web.archive.org/web/20200528022615/https://www.sciencedirect.com/science/article/pii/S0304397520302826 |archive-date=2020-05-28 |access-date=2023-07-19}}</ref>