Galois connection

The Galois connection is the mathematical description of an interrelation between two totalities ( sets ). Each element of one set is assigned an element of the other and vice versa, with certain rules still to be observed. It is assumed that the two ensembles are (partially) ordered . The rules should then ensure that the interrelation is compatible with these orders.

An extra-mathematical example of such an interrelation is described by the so-called reciprocity law of the philosophical conceptual theory: "The content and scope of a concept are in inverse relation to one another. That is, the more a concept contains under itself, the less it contains in itself and vice versa".

The Galois connections are named after the French mathematician Évariste Galois . A distinction is made between monotonic and antitonic Galois compounds. The example mentioned of the relationship between scope and content corresponds to the antitone case (the more of one, the less of the other). Without specifying "monotonic" or "antiton", antitonic Galois compounds are meant in this article.

Definitions

Antitone Galois connection

An antitonic Galois connection between two partially ordered sets is a pair of mappings if and are antitonic maps and their compositions and are extensive . This means that the following properties must be met: ${\displaystyle S,~T}$ ${\displaystyle (\sigma ,\tau )}$ ${\displaystyle \sigma \colon S\to T,~\tau \colon T\to S}$ ${\displaystyle \sigma }$ ${\displaystyle \tau }$ ${\displaystyle \sigma \tau }$ ${\displaystyle \tau \sigma }$

1. ${\displaystyle \forall s_{1},s_{2}\in S:s_{1}\leq s_{2}\Rightarrow \sigma (s_{2})\leq \sigma (s_{1})}$
2. ${\displaystyle \forall t_{1},t_{2}\in T:t_{1}\leq t_{2}\Rightarrow \tau (t_{2})\leq \tau (t_{1})}$
3. ${\displaystyle \forall s\in S:s\leq \tau (\sigma (s))}$
4. ${\displaystyle \forall t\in T:t\leq \sigma (\tau (t))}$

It is equivalent to request that

${\displaystyle \forall s\in S,t\in T:s\leq \tau (t)\iff t\leq \sigma (s)}$

is satisfied.

Monotonous Galois connection

Definition: A monotonic Galois connection between two partially ordered sets is a pair of mappings , if and are monotonic maps , extensive and intensive . This means that the following properties must be met: ${\displaystyle S,~T}$ ${\displaystyle (f,g)}$ ${\displaystyle f\colon S\to T,~g\colon T\to S}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle gf}$ ${\displaystyle fg}$

1. ${\displaystyle \forall s_{1},s_{2}\in S:s_{1}\leq s_{2}\Rightarrow f(s_{1})\leq f(s_{2})}$
2. ${\displaystyle \forall t_{1},t_{2}\in T:t_{1}\leq t_{2}\Rightarrow g(t_{1})\leq g(t_{2})}$
3. ${\displaystyle \forall s\in S:s\leq g(f(s))}$
4. ${\displaystyle \forall t\in T:f(g(t))\leq t}$

It is equivalent to request that

${\displaystyle \forall s\in S,t\in T:s\leq g(t)\iff f(s)\leq t}$

is satisfied. A monotonous Galois connection is the special case of a category-theoretical adjunction , where the categories are partially ordered sets. ${\displaystyle (f,g)}$ ${\displaystyle f\dashv g}$

properties

An antitone Galois connection between and has the following properties: ${\displaystyle (\sigma ,\tau )}$ ${\displaystyle S}$ ${\displaystyle T}$

• Symmetry: is a Galois connection between and . ${\displaystyle (\tau ,\sigma )}$ ${\displaystyle T}$ ${\displaystyle S}$
• ${\displaystyle \tau \sigma \tau =\tau }$, by symmetry as well . ${\displaystyle \sigma \tau \sigma =\sigma }$
• ${\displaystyle \tau \sigma }$is an envelope operator on , and thus an envelope operator is on . ${\displaystyle S}$ ${\displaystyle \sigma \tau }$ ${\displaystyle T}$
• Uniqueness: If there is another Galois connection between and , then is . If there is another Galois connection between and , then is ${\displaystyle (\sigma ,\tau ')}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle \tau =\tau '}$ ${\displaystyle (\sigma ',\tau )}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle \sigma =\sigma '}$

A monotonous Galois connection between and has the following properties: ${\displaystyle (f,g)}$ ${\displaystyle S}$ ${\displaystyle T}$

• ${\displaystyle fgf=f}$and . ${\displaystyle gfg=g}$
• ${\displaystyle gf}$is a shell operator on and a kernel operator on . ${\displaystyle S}$ ${\displaystyle fg}$ ${\displaystyle T}$
• If there is another monotonous Galois connection between and , then is . If there is another monotonous Galois connection between and , then is . ${\displaystyle (f,g')}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle g=g'}$ ${\displaystyle (f',g)}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle f=f'}$

application

Theory and application of such Galois compounds are e.g. B. Subject of the Formal Concept Analysis (FBA). In the FBA, objects form one set, the potential properties (characteristics) the associated other set.

Where and are power sets , such as and . These are semi-ordered through inclusion. Under a Galois connection between the sets and then one understands a Galois connection between and . Such can be obtained with the help of relations : Let be a relation between and . The illustrations ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle S={\mathcal {P}}(A)}$ ${\displaystyle T={\mathcal {P}}(B)}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle R\subseteq A\times B}$ ${\displaystyle A}$ ${\displaystyle B}$

${\displaystyle \sigma (X):=\{y\in B~|~\forall x\in X:(x,y)\in R\}}$,

${\displaystyle \tau (Y):=\{x\in A~|~\forall y\in Y:(x,y)\in R\}}$

then establish a Galois connection between and . ${\displaystyle S}$ ${\displaystyle T}$

Examples

• Are the partial orders on and just the equality, a Galois connection (regardless of whether or monotonous antitone) between and a pair of mutually inverse functions. ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle R}$ ${\displaystyle S}$
• The embedding of the whole numbers in the real numbers forms a monotonous Galois connection with the rounding function ,, between and with their ordinary orders. ${\displaystyle i\colon \mathbb {Z} \to \mathbb {R} ;z\mapsto z}$ ${\displaystyle \lfloor -\rfloor \colon \mathbb {R} \to \mathbb {Z} }$ ${\displaystyle i\dashv \lfloor -\rfloor }$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle \mathbb {R} }$
• For every natural number integer division by forming , and the multiplication , d. H. A monotone Galois connection between and , . ${\displaystyle d\neq 0}$ ${\displaystyle d}$ ${\displaystyle \lfloor -/d\rfloor \colon \mathbb {N} \to \mathbb {N} }$ ${\displaystyle d}$ ${\displaystyle -\cdot d\colon \mathbb {N} \to \mathbb {N} }$ ${\displaystyle (\mathbb {N} ,\leq )}$ ${\displaystyle (\mathbb {N} ,\leq )}$ ${\displaystyle (-\cdot d)\dashv \lfloor -/d\rfloor }$

• The following relation exists between a body (with a lower body ) and the Galois group of : ${\displaystyle L}$ ${\displaystyle K}$ ${\displaystyle G=Gal(L/K)}$ ${\displaystyle R}$

${\displaystyle (\phi ,x)\in R\Leftrightarrow \phi x=x.}$

From this a Galois connection between and can be defined. This is examined in the main theorem of Galois theory . This example explains the term Galois connection. ${\displaystyle L}$ ${\displaystyle G}$

• Let us consider a vector space and a second vector space consisting of linear functionals of , i. H. a subspace of the dual space . We define the relation on through ${\displaystyle V}$ ${\displaystyle F}$ ${\displaystyle V}$ ${\displaystyle V^{*}}$ ${\displaystyle R}$ ${\displaystyle V\times F}$

${\displaystyle (v,f)\in R:\Leftrightarrow f(v)=0.}$

This relation defines a Galois connection between and , but also between their subspaces. You then write instead of and instead of , and it counts ${\displaystyle V}$ ${\displaystyle F}$ ${\displaystyle \perp }$ ${\displaystyle \sigma }$ ${\displaystyle \top }$ ${\displaystyle \tau }$

${\displaystyle U^{\perp }=\{f\in V^{*}~|~U\subseteq Kern(f)\},}$

${\displaystyle U^{\top }=\bigcap \limits _{f\in U}Kern(f).}$

• In algebraic geometry there is a Galois connection z. B. between the affine algebraic sets in and the ideals in the polynomial ring , denoting an algebraically closed field. Each algebraic set assigns the ideal of all polynomials that vanish on this set and each ideal assigns that algebraic set that is the common zero set of all polynomials in this ideal. ${\displaystyle ({\mathcal {I}},{\mathcal {V}})}$ ${\displaystyle k^{n}}$ ${\displaystyle k[X_{1},X_{2},\dots X_{n}]}$ ${\displaystyle k}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle {\mathcal {V}}}$

${\displaystyle {\mathcal {I}}(A):=\left\{f\in k[X_{1},X_{2},\dots X_{n}]\,~|~\,f(A)=0\right\}}$

${\displaystyle {\mathcal {V}}(I):=\left\{x\in k^{n}\,~|~\,f(x)=0\;\forall \,f\in I\right\}}$

• In universal algebra , more precisely in equation theory, there is a Galois connection between the systems of equations and the classes of algebras. Here, algebras and terms are of a fixed type. The Galois connection is referred to as the Galois connection of equation theory and differs from the original definition in that it is not just operating on sets, but on classes. Let there be a system of equations over the set of variables and a class of algebras: ${\displaystyle (M,G_{X})}$ ${\displaystyle \Sigma \subseteq T(X)\times T(X)}$ ${\displaystyle X}$ ${\displaystyle {\mathcal {K}}}$

${\displaystyle M(\Sigma ):=\left\{A~|~A\models s\approx t\;\forall \,(s,t)\in \Sigma \right\}}$, the class of all models of ${\displaystyle \Sigma }$

${\displaystyle G_{X}({\mathcal {K}}):=\left\{(s,t)\in T(X)\times T(X)~|~A\models s\approx t\;\forall \,A\in {\mathcal {K}}\right\}}$, the set of all valid equations about in all algebras ${\displaystyle {\mathcal {K}}}$ ${\displaystyle X}$

• In with the standard order applies ${\displaystyle \mathbb {R} }$

${\displaystyle a+b\geq c\iff a\geq c-b}$.

That is, and form a monotonous Galois connection. This property can also be seen as the definition of the subtraction of a number relative to the addition of the same number. In contrast to the definition of subtraction as the addition of the additive inverse, it is also useful in situations where there are no negative numbers. ${\displaystyle x\mapsto x+b}$ ${\displaystyle x\mapsto x-b}$

• There is a prototype image for every image . With regard to the subset relation, it has left and right adjoint , with , defined by ${\displaystyle f\colon A\to B}$ ${\displaystyle f^{-1}\colon {\mathcal {P}}(B)\to {\mathcal {P}}(A)}$ ${\displaystyle \Sigma _{f},\Pi _{f}\colon {\mathcal {P}}(A)\to {\mathcal {P}}(B)}$ ${\displaystyle \Sigma _{f}\dashv f^{-1}\dashv \Pi _{f}}$

${\displaystyle \Sigma _{f}(X):=\{b\in B\mid \exists a\in A:f(a)=b\land a\in X\}}$ and

${\displaystyle \Pi _{f}(X):=\{b\in B\mid \forall a\in A:f(a)=b\Rightarrow a\in X\}}$.

${\displaystyle \Sigma _{f}}$is known as forming the image under ${\displaystyle f}$ .

Individual evidence

1. ↑ Gottlob Benjamin Jasche : Immanuel Kant's logic: a handbook for lectures . Ed .: JH v. Kirchmann. Friedrich Nicolovius, Berlin 1876, ISBN 978-5-88002-810-8 .
2. ↑ Gottlob Benjamin Jasche : Immanuel Kant's logic. December 30, 2015, accessed April 13, 2019 . 
3. ↑ Bernhard Ganter: Discrete Mathematics: Ordered Sets (=  Springer textbook ). Springer-Verlag, Berlin Heidelberg 2013, ISBN 978-3-642-37499-9 .