Sun Sep 20 10:51:08 CEST 2009

Galois Connection

A Galois connection is a kind of morphism between posets.  Starting
with Lecture 10b [1] from Cousout's course at MIT[2].  The basic
property is expressed as:

        a(x) [= y   iff   x <= g(y)

Galois connections are interesting when they are used to relate sets
of different ``sizes''.  Let's take a be the abstraction operation
which maps the larger poset P,<= to the smaller poset Q,[=.

Page 112 in the slides, (page 28 in the pdf/4) has a picture of a
Galois connection.  From this, the point is that while a roundtrip

         g . a

can shift around elements in P, it will not change the order relation
<= in P.  I.e. some elements in P are promoted (or dually demoted),
but never in a way that they switch order.  In other words, g . a is
extensive. This is captured in the following theorem:

  From the properties: a,g monotone, a . g reductive, g . a extensive
  follows that a, g form a Galois connection.

f extension: x <= f(x)
f reductive: f(x) <= x


   * as with most related to posets, each GC has a dual which reverses
     the order relations in P and Q and exchanges the roles of a and g.

   * GCs compose using ordinary function composition of the a's and
     g's (as opposed to Galois correspondences)

   * GCs can be combined as sums (linear, disjoint, smashed),
     products and powers.

[1] http://web.mit.edu/16.399/www/lecture_10-maps1/Cousot_MIT_2005_Course_10b_4-1.pdf
[2] http://web.mit.edu/16.399/www/