`[<<][compsci][>>][..]`
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

Notes:

* 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/

```
`[Reply][About]`
`[<<][compsci][>>][..]`