Galois connection

In mathematics, especially in order theory, a Galois connection is a particular correspondence between two partially ordered sets ("posets"). Galois connections generalize the correspondence between subgroups and subfields investigated in Galois theory. They find applications in various mathematical theories as well as in the theory of programming.

Definition

Suppose (A, ≤) and (B,

Related Topics:
Monotone - Function

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:F(a) ≤ b if and only if a ≤ G(b).

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

In this situation, F is called the lower adjoint of G and G is called the upper adjoint of F. This terminology relates to the connections to category theory discussed below. As detailed below, each part of a Galois connection uniquely determines the other mapping. Viewing two functions that form a Galois connections 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.

Related Topics:
Category theory - Asterisk

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Alternative definition

The above definition is common in many applications today, and prominent in lattice and domain theory. However, a slightly different notion has originally been derived in Galois theory. 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

Related Topics:
Lattice - Domain theory

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:b ≤ F(a) if and only if a ≤ G(b) . (Note: This is a correction of an earlier definition.)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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 Bop of B. 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.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~