Editing Galois connection (section)

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