Galois connection

In mathematics,Galois connection isparticular correspondence between two partially ordered sets. Galois connections generalizecorrespondence between subgroupssubfields investigatedGalois theory. They find applicationsvarious mathematical theories as well as intheoryprogramming.

Tablecontents

1 Definition 2 Examples 3 Properties 4 Category theoretic approach 5 References

Definition

Suppose (A, ≤)(B, <=)two partially ordered sets. A Galois connection between these posets consiststwo functions: F : A → BG : B → A, such thatall aAbB, we have

F(a) <= b ifonly if G(b) ≤ a.

Examples

The motivating example comes from Galois theory: suppose L/K isfield extension. Let A besetall subfieldsL that contain K, ordered by inclusion ⊆. If E suchsubfield, write Gal(L/E) forgroupfield automorphismsL that hold E fixed. Let B besetsubgroupsGal(L/K), ordered by inclusion ⊆. For suchsubgroup G, define Fix(G)befield consistingall elementsL thatheld fixed by all elementsG. Thenmaps E |-> Gal(L/E)G |-> Fix(G) formGalois connection.

In algebraic geometry,relation between setspolynomialstheir zero sets isGalois connection: fixnatural number n andfield Klet A besetall subsets ofpolynomial ring K[X₁,...,X_n]let B besetall subsetsKⁿ. Both ABnaturally ordered by inclusion ⊆. If S issetpolynomials, define F(S) = {xKⁿ : f(x) = 0all fS},setcommon zeros ofpolynomialsS. If T issubsetKⁿ, define G(T) = {fK[X₁,...,X_n] : f(x) = 0all xT}. Then FG formGalois connection.

Finally, suppose XYarbitrary sets andbinary relation R over XYgiven. For any subset MX, we define F(M) = { yY : mRyall mM}. Similarly,any subset NY, define G(N) = { xX : xRnall nN}. Then FG yieldGalois connection betweenpower setsXY, if boththemordered by inclusion ⊆.

Properties

If FG provideGalois connection, then both FGorder reversing functions, i.e. a₁ ≤ a₂ implies F(a₂) <= F(a₁)b₁ <= b₂ implies G(b₂) ≤ G(b₁).

Furthermore, we have G(F(a)) ≤ aF(G(b)) <= ball aAbB.

For every a, F(a) islargest x such that G(x) ≤ a. Similarly,every b, G(b) islargest y such that F(y) <= b.

This latter statement shows that an order reversing function F : A → B forms part ofGalois connection ifonly ifevery bB,set {yA : F(y) <= b} haslargest element. If this iscase, then"other half ofGalois connection" Guniquely determined by F.

If FG formGalois connection, we have FGF(a) = F(a)every aAGFG(b) = G(b)every bB. An element aAcalled closed if a = G(F(a)), or equivalently, if ainrangeG. Closed elementsBdefined analogously. FG induce inverse order reversing bijections betweensetclosed elementsA andsetclosed elementsB.

Category theoretic approach

Every partially ordered set can be viewed ascategory innatural way: there'sunique morphism from xy iff x ≤ y. A Galois connectionthen nothing butpairadjoint functors between two categories, wherefirst category arises frompartially ordered set andsecond category isdualone that arises frompartially ordered set.

References

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