Category and Model Theory
September 21st, 2007 by WaltI was reading Eric Schechter’s Handbook of Analysis and its Foundations when I had a small epiphany about (of all things) the relationship between model theory and category theory. In contrast to universal algebra, the concept of homomorphism is not very important in model theory. A model is a very rigid object. From the point of view of algebra, a free group (for example) is a very flexible object with many homomorphic images. From the point of view of model theory, the free group comes bundled with every theorem that it satisfies, and that includes the statements that every element is different from the identity. The only map that preserves these statements is an embedding into a larger group. The problem is that for every model, every possible statement is either true or false (this means the set of theorems about the free group, or any model, is a complete theory).
What we want to get the analogue of a homomorphic image is to somehow forget those inequality statements. In model theory terms, we want to work with an incomplete theory rather than a complete theory. This is easy to do, and in fact, many naturally-arising theories are incomplete, but this does not guarantee a rich supply of homomorphisms. If a theory is equationally presented (all of its axioms can be put in the form of equalities) such as that of groups or rings, then homomorphisms are easy to come by. But in general, the only types of homomorphisms that exist are embeddings. The theory of fields is typical.
There is a more indirect way to create incomplete theories: boolean-valued models. To force statements to be neither definitely true nor definitely false, we assign intermediate truth values in a Boolean algebra with more than two elements. Despite their exotic logic, these are easy to construct. For example, the set of functions from a set I into a field F is not itself a field, but it forms a boolean-valued model. The truth value of a logical statement becomes the set of elements of I for which the statement holds. A statement is true if it holds for all of I and false if it holds for none of I. Boolean-valued models have lots of homomorphisms.
Several standard constructions can be interpreted in terms of boolean-valued models. The ultraproduct, which creates models in the ordinary sense, not boolean-valued models, works by creating a boolean-valued model and then taking a maximal quotient. (Nonstandard analysis can constructed using an ultraproduct.) Set-theoretic forcing can also be interpreted in terms of boolean-valued models. In turn, boolean-valued models can considered as a special case of sheaf semantics.
September 22nd, 2007 at 11:53 am
As I would guess you already know, this is very related to our discussion about foundations and topoi in the other threads.
The stipulated completeness of models is the source of much logical grief for proof theory, and is also the source of my disgruntlement with uncountables.
Essentially, we could define a model as:
Let M be an object that knows everything there is to know about itself, i.e. every fact about M is encoded within it, and everything that is encoded within it is a fact about itself.
We equip it with a language (its “theory”) so we can formulate questions about it. Gödel’s incompleteness (and Cantor’s diagonalization) are based on the paradox of asking in some theory for M “What is a fact that is not about M”.
Obviously, this causes problems, because if it can answer, some of its knowledge is not about itself, which violates the hypothesis, and if it can’t answer, it doesn’t know EVERYTHING about itself, because it doesn’t know about its relationship with anything that is not contained within it.
You then have to either restrict the theory of the model (the “language” that describes it) so that this question can’t be formulated (which forces it to be a logically inconsistent theory, i.e. every sentence it can utter is true) or accept that the theory will be unable to describe at least some interesting property about the model (be incomplete).
This interacts with computability, uncountability, a topos for constructive set theory and the paradoxes of the AC in a bunch of interesting ways. but we’ve beaten those enough recently, so I’ll stop here.
September 22nd, 2007 at 1:32 pm
Actually, I think model theorists do have a useful definition of homomorphism. If I’m not mistaken, it just means that every atomic formula is preserved. Since negations aren’t atomic, this means that identities are preserved, but non-identities aren’t.
Of course, this might not be something that model theorists normally care about, because it means that two structures that are definitionally equivalent (that is, they can define all the same sets of tuples of elements) won’t have the same homomorphisms.
September 22nd, 2007 at 2:54 pm
Actually, I just noticed something else, based on all this. (Perhaps this is what started your musings.): that the notion of complete in the model theoretic sense is equivalent to complete in the metric space sense.
Take the closed interval [0, 1], a complete metric space. Consider the theory for this model defined by the boolean logic defined as follows: the empty set is false, the complete interval is true, intersect the meet (logical and), union the join (logic or). For this logic to be consistent, the meet of all subsets must be empty, since otherwise you can prove that the empty set is not empty and therefore everything in the system is trivially true, by ex falso quodlibet
By the Baire Category Theorem, any complete metric space has a non-empty infinite intersection. Therefore, the logic describing the interval is inconsistent.
I’m sure this was implicit in some readings in algebraic and logical topology I’ve done before, but it only really struck me in this context.
September 22nd, 2007 at 4:17 pm
Even in situations where the only homomorphisms are models are isomorphisms, the automorphism group of a model can be very interesting: the most famous example is traditional Galois theory.
I’m hoping James Dolan will discuss this in our forthcoming seminar on ‘geometric representation theory’ — he’s been thinking about it a lot these days.
September 23rd, 2007 at 3:06 pm
I wonder if what you say is at all related to metric models considered by Ben-Yakoov and Henson ( along the lines of http://www.aimath.org/ARCC/workshops/continuouslogic.html )
Do any techniques of categoricity theory (stability, forking) generalise to your larger classs of models?
September 27th, 2007 at 3:32 pm
Kenny: True, but I think that model theorists are only interested in that notion in so far as to identify which part of a theory is equationally-defined, which is pretty much homomorphism in the usual sense.
Marc: I didn’t quite understand your construction. What corresponds to the elements of the Boolean algebra? Closed sets?
John: It’s true that homomorphisms for fields are interesting, but they are sharply limited in their uses. It’s quite striking in that to study the theory of groups, most of it is groups (a small part group representations). To study fields, you are basically forced to work with algebraic varieties up to birational isomorphism, which is a long way from where you started.
anonym: That’s a really good question. I don’t know much about stability and forking, so I’d be interested in hearing if how they behave for Boolean-valued models.
September 27th, 2007 at 7:40 pm
Assuming you mean the interval thing, I was reasoning from the usual construction using the opens.
I think you can restrict it to the dense opens, in line with Baire’s theorem, without losing the idea. If two dense opens have a dense open as their intersection this is like asserting p ∧ q and likewise p ∨ q for unions. By the definition of a topological space, these will normally all be true, i.e. only the empty set will be false. But to make this consistent, the intersection of all dense opens must be empty.
Hopefully that makes sense.
It’s kind of a mix of lattice theory and topology in a logical interpretation.
September 28th, 2007 at 7:34 pm
I’m also having a hard time following this, but in any event the poset of opens in [0, 1] is not a Boolean algebra. (It is a complete Heyting algebra.) Also one has to be careful in treating infinite meets: in the lattice of open sets, a (possibly infinitary) meet is obtained by taking the interior of the usual set-theoretic intersection.
Being a Heyting algebra, a topology T can indeed be treated as an (intuitionistic) propositional theory, and one can define a “model” of T as a suitable homomorphism T –> 2, but the notion of homomorphism depends on what logical operations we want to preserve (are we considering just finite meets and finite joins, or perhaps finite meets and arbitrary joins, or what?). It looks as though [reading between the lines] that you are considering the strongest possible notion, where T –> 2 preserves arbitrary meets and arbitrary joins (and presumably the internal implication too) — you do after all speak of infinitary meets.
Now: in the case of a general topology T, the set of homomorphisms f: T –> 2 which preserve arbitrary joins and *finite* meets is in bijection with closed irreducible subsets of the space. If the space is Hausdorff, these closed irreducibles are just points x of the space; the corresponding map f: T –> 2 is defined by f(U) = 1 if x is in U, and f(U) = 0 if not. But an f so defined will not generally preserve arbitrary meets, because the intersection of all opens containing x will have empty interior, unless x is an isolated point. This implies there are *no* models of the theory of the topology of [0, 1], at least with this sense of model.
It is arguable however that this notion of model is inappropriately strong: if you instead demand only preservation of finite meets and arbitrary joins (as would be appropriate for topologies), then you do get a completeness theorem for those topologies of spaces that satisfy the condition that closed irreducibles coincide with points (such spaces are called “sober spaces”).
I am not sure what you are trying to say; what I wrote above is an attempt to guess at part of it. My guess was that “completeness in the model theoretic sense” was referring to a completeness theorem (asserting existence of enough models to semantically detect tautology).
September 29th, 2007 at 10:42 am
There are always details to get you.
Though my example may have not been fully baked, I think there still is a sensible insight to be had about the relationship between the notions of closure and completeness in an algebraic or topological sense and completeness in a logical sense (i.e. the property that cannot coexist with consistency).
Whenever we say that a particular structure is closed under some set of operations, we are in a sense asserting that every element in the structure can be “proved” through those operations. Since this is a very convenient property for reasoning about structures, we often deliberately seek a logic of those operations that is inconsistent, in the sense that “you can’t go wrong” with those operations and derive something that is NOT in the structure. (i.e. false)
But we want to have our cake and eat it too: sometimes we want to use our system to make consistent proofs. What seems to happen then is a shell game: we temporarily weaken the logical system so that it won’t produce inconsistency.
The weaker topological logic you propose for the interval will be consistent with respect to the full structure of the interval, but this implies that it will lose completeness: there will be some dense open that exists in the interval that cannot be generated using the specified operations. (In some sense, this is exactly what the Baire Category Theorem means)
The “constructive topos” discussion we were having, after much thought about it, seems to me to be to be another example of this phenomenon. We started by assuming a category with the usual cartesian closure, and further assert that the subobject classifier is strong enough to specify (distinguish/prove/etc.) all subobjects. We hypothesize that the logic “generated” by this subobject classifier is a Heyting algebra, which seems reasonable, since it is closed under equivalent operations.
But when we try to restrict the subobjects of N to the countable ones, we discover that the logic becomes inconsistent. To me this implies that we didn’t have the closure properties we thought we had to begin with, and that the Heyting algebra actually wasn’t strong enough to distinguish or prove all the subobjects of N in the first place. That’s why it seems consistent when extended to that “model”: we’ve just hidden the incompleteness under another shell.
September 29th, 2007 at 1:25 pm
Hmm… still not making much sense, for various reasons.
Let me try asking one little thing. The Baire category theorem says that in a complete metric space, a countable intersection of dense open sets is dense (it might not be open, of course). I am trying now to parse the phrase “there will be some dense open that exists in the interval that cannot be generated using the specified operations”.
(1) What specified operations do you mean? Please specify.
(2) Generated from what, using these specified operations? I.e., what are you starting with before you apply these operations?
(3) Could you give a concrete example of a “dense open that exists, etc.”?
September 29th, 2007 at 4:18 pm
I meant under finite meets and arbitrary joins.
This might make more sense if I flip this around and set out to build a sensible logic for the interval. I want my logic to be able to distinguish whether two objects are the same or different.
To make such a thing, I need to start with a countable set of primitive propositions. I choose a disjoint set of dense opens. I allow arbitrary joins and finite meets.
We will agree that this will generate a consistent logic of dense opens in the interval. We will also agree that it will not be a complete description of the interval: there is more to the interval than is described by this logic.
I decide instead that I want my logic to be complete, i.e. I want it to account for the bits I missed the first time. So I decide to extend it with some operations I left out the first time, to see if I can pull this off.
The first thing I try is to allow infinite meets; maybe this will generate the whole interval. But immediately I run aground, since, contrary to my assumption that my propositional “basis” was disjoint, I find that Baire tells me they can’t be. (Moreover, as your different argument shows, you can show that there is no model for such a system.)
So instead I develop a complementary logic of closed dense subsets with arbitrary meets and finite joins. This works nicely, and I boldly assume that between the two systems I can generate the whole interval. But can I be sure? Building a unified system of both of them together is a wee bit tricky, and leaves out subsets that are not wholly closed or wholly open. Could I need one of those for some reason, and find a way to build it from the close and open sets that I already have? Unlikely.
If instead I reason from the definition of complete metric space and add an arbitrary “Cauchy sequence” operation, I know that I can generate the whole interval, but as a logic I again have lost the ability to determine sameness and difference: I can’t tell whether arbitrary Cauchy sequences are the same or different in any finite number of steps.
The essence of what I’m claiming is that there is NO logic I can come up with that accounts completely for everything in the interval while remaining consistent.
In some sense I’m further claiming that this is a trivial consequence of incompleteness since a system that can generate the interval is already more powerful than a system to generate arithmetic.
No.
By definition, such a thing is inaccessible from any system I can cook up constructively. This is one of the challenges of being a constructivist: I keep having to try to justify my ideas using constructivist methods in systems that are manifestly not constructive. 
(For example, any intuistionistic logic that admits only two distinct truth values isn’t really constructive; a real intuisionistic logic should be more like that in Walt’s OP)
I think one of the paradoxes is that, when it comes to logic and proof theory, everybody’s default position is constructivist. When we try to extend such things to non-constructive entities like the interval [0,1], weird things happen (like non-measurable sets).
September 30th, 2007 at 7:28 am
Re-reading my last posts in this thread, I’ve decided that I underestimated the difficulty of building a complete (in the model sense) logic of the interval.
My intuitions about the situation are unchanged, but that is still along way from making a convincing case for others.
Thanks Walt and Todd for engaging on this; the effort I’ve put into this has been worthwhile for me. Hope you got some benefit out of it, too, even if only amusement.
October 2nd, 2007 at 4:36 am
i guess nowdays a definition of a model theoriest is that of a someone who knows what forking (and stability) is…it is strange to see a discussion on model theory not referring to these notions which are somehow the only powerful non-trivial notions in model theory.
I am not sure whether your classes of models have been seriously considered in model theory literature, especially relating to stability and forking. although it is likely i just do not know…if you are seriously interested, you might ask Usvyatsov or Ben-Yakov.
about stability : the first question i’d ask is whether there are interesting modelsof your class where a linear ordering with long chains is NOT definable; then one can see whether the powerful techniques of stability theory apply to them…