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