Monday, March 31, 2008

A short note on Galois connections

I've been thinking about various topics in Dunn's book, one of them his idea of gaggles, which are generalizations of the idea of Galois connections. I just noticed a connection to this post in the early Dunn material. In the proof that every variety is equationally definable, the same sort of Galois connection is appealed to that is in the linked post at Logic Matters. First, a brief explanation of Galois connections.

A Galois connection is a pair of functions (f: A→B,g:B→A) on partially ordered sets (A, ≤) and (B, ≤') such that fa≤' b iff a≤ gb. Dunn finds these in a lot of places, most surprising to me were the ones in modal logic. I hope to work out a more detailed post on their application and interest soon.

To return to the proof mentioned above, for our partially ordered sets, we take classes of algebras ordered with ⊆ and classes of equations, also ordered with ⊆. For the functions, we take the operation e that maps a class of algebras to the class of equations valid in it and the operation a that maps a class of equations to the class of algebras that validate every member of the class. (a, e) form a Galois connection. This is important for the proof mentioned above. It is obvious that for a class of algebras K, K⊆ (Ke)a. To finish the proof, which I won't do here, one just needs to prove that (Ke)a⊆ K. This involves a fair amount of technical machinery and several lemmas, but it is pretty in the end. [Edit: There is also the same relations starting with a set Q of equations, i.e. Q⊆ (Qa)e.]

Why do I mention this? This is an illustration of the connection in Peter Smith's post. The models are the algebras and the equations are the axioms. Algebras and equations are rather restricted forms of models and sets of axioms, so this doesn't get the full generality indicated in his post. It's not clear how to get that generality based on this example, since the proof of the latter inclusion, (Ke)a⊆ K, depends on K being a variety, at least closed under homomorphic images. This is, at least, a fairly intuitive illustration of the connection between classes of models and of axioms. I am having trouble getting Lawvere's paper, so I don't know if there is more to his idea than this sketch. [Edit: It occurs to me that for the Galois connection we don't need the identity that we get in the case of varieties. The important relations are the ones mentioned above, K, K⊆ (Ke)a and Q⊆ (Qa)e. There might be a more general way of getting identity, but this should be enough for indicating the Galois connection between models and sets of axioms.]

No comments: