The Galois connection between syntax and semantics (updated)

In his classic Dialectica paper `Adjointness in foundations’ (1969), F. William Lawvere writes of `the familiar Galois connection between sets of axioms and classes of models, for a fixed [signature]‘.

But even if long familiar folklore to category theorists, the idea doesn’t in fact seem to be that widely known. The ideas however are pretty enough, elementary enough, and illuminating enough to be worth rehearsing briskly in an accessible stand-alone form. Here’s my attempt.

I wrote these notes a while ago (inspired by an improptu talk by Nathan Bowler), as part of a longer planned piece (hence the perhaps overkill first chapter). The longer piece is now on the back burner. But this excerpt is reasonably polished and might be useful. (The previous version has now been improved/corrected in the light of Laurant Méhats’ comments. Further corrections or suggestions for improvement gratefully received as usual.)

This entry was posted in Logic. Bookmark the permalink.

5 Responses to The Galois connection between syntax and semantics (updated)

  1. Laurent Méhats says:

    I’ve read the first section on posets. Here are three comments of decreasing importance.

    In Theorem 1.2.2 on p. 5, I think you should mention that (P-)+ = P and (Q+)- = Q for what we actually need to answer ‘no’ to the question is that we can go back and forth between partially and strictly ordered sets, not simply that a partially ordered set can be turned into a strictly ordered one and conversely. Or is this what “definitional link” conventionally means ?

    Example 5 on p. 3 is about N\{0} ordered by divisibility. I guess you don’t want to bother us readers with 0/0 but then on p. 5 you mention N strictly ordered by divisibility followed by Theorem 1.2.2 which implies that it can be extended into a partial order. That’s fine but it rises the distracting question of what 0/0 should be (or of whether extending a strict order also extends its informal meaning).

    In the second example on p. 9 (penultimate line), I guess you mean “where the greatest divisor of m, n is 1″ rather than “where m, n have no common divisors”.

  2. Dmitry Kulagin says:

    Thank you! It is very clear and useful introduction.

  3. Pingback: Caesarian « Log24

  4. Pingback: Universal properties and Galois connections | Patterns in Functional Programming

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>