The category of logics and the category of cologics

306 Views Asked by At

The concept of a dual category is ubiquitous in category theory.

I was wondering whether there are any clear, intuitive examples of cologics? I saw a paper by Alex Kruckman ("First-order cologic for profinite structures") which speaks of a particular cologic; however, I wondered whether there were standard examples of cologics in the literature. Perhaps it would be good to have an explanation of the notion of the category of logics (and an example) and then of the category of cologics.

Is there also such a notion of a comodel (and the category of models?) ? What would, for example, the category of models of a first order language be?

1

There are 1 best solutions below

1
On BEST ANSWER

Thanks for the advertisement for my paper! Unfortunately, the paper doesn't exist yet - I haven't finished writing it - but there are some slides available on my website which give the main idea.

You question actually contains a lot of questions, and possibly some misconceptions. Maybe I'll start by briefly saying what I'm trying to do with my notion of cologic, and then I'll address what you wrote and try to clear some things up.

A formula $\varphi(\overline{x})$ of ordinary first-order logic comes with a finite set of free variables $\{x_1,\dots,x_n\}$. Given a structure $M$ and an interpretation of the variables (i.e. a function $\{x_1,\dots,x_n\}\to M$, which we identify with its image, a tuple $\overline{a}$ of elements of $M$), we can define what it means for $\overline{a}$ to satisfy $\varphi(\overline{x})$ in $M$, written $M\models \varphi(\overline{a})$. So formulas describe properties of finite pieces of $M$ (functions from finite sets to $M$), and the first-order quantifiers $\exists$ and $\forall$ allow us to explore how $M$ is built up (as a directed colimit) from finite pieces.

On the other hand, there are mathematical objects which are more fundamentally described by their finite quotients (maps to finite pieces, rather than from finite pieces). Maybe the canonical example is profinite groups, which are not first-order structures in the usual sense (thanks to the topology). So, for example, in the context of profinite groups, a formula of cologic describes a property of a finite quotient of a profinite group $G$ (a continuous function $G\to H$, where $H$ is a finite group equipped with the discrete topology), and quantifiers allow us to explore how $G$ is built up as an inverse limit (a codirected limit) of finite pieces.

The actual path I take to defining cologic is first to describe an abstract version of first-order logic with semantics in a locally finitely presentable category (essentially, this is a category in which every object is built up as a directed colimit of finitely presentable pieces in a precise sense - examples include the category of sets and the category of $L$-structures for a first-order language $L$), and then to define a "first-order cologic" to be the same construction applied to the opposite of a category whose dual is locally finitely presentable (for example, the dual of the category of profinite groups is locally finitely presentable, and the first-order cologic of profinite groups is the first-order logic of $\mathsf{ProFinGrp}^{\text{op}}$).

So for me, a cologic is not defined by looking at some category of logics and dualizing, or even thinking of a fixed logic as corresponding to categorical structure and dualizing, as you might do in categorical logic. Rather, the dualization is happening in the semantic category (the category of structures / models).

Now to address some of the things you wrote:

The concept of a cocategory is ubiquitous in category theory.

Do you mean the concept of "opposite category" or it synonym "dual category"? These terms mean something different than "cocategory", which is much less common.

I was wondering whether there are any clear, intuitive examples of cologics ... [or] standard examples of cologics in the literature.

The main example of a "cologic" in the literature is the cologic of profinite groups defined by Cherlin, van den Dries, and Macintyre, in the course of their study of the model theory of PAC fields by way of their absolute Galois groups. Their paper, The Elementary Theory of Regularly Closed Fields, was never published, but you can read an outline in the note Decidability and Undecidability Theorems for PAC Fields, or in papers by Zoe Chatzidakis like this one, or in Nina Frohn's PhD thesis. These authors take a different (less abstract) approach to cologic than I do, defining it specifically in the context of profinite groups. In the special case of profinite groups, my cologic has essentially the same expressive power as the earlier notion.

As far as I know, there is no general notion of "cologic" other than these. If there's some other example in the literature, I'd like to know about it.

Perhaps it would be good to have an explanation of the notion of the category of logics (and an example) and then of the category of cologics.

I know of no way to define a general "category of logics". There is already a difficulty in providing a satisfying definition of what counts as a "logic", much less what counts as a morphism between logics. There is a notion of abstract logic, which is the setting of Lindström's theorem, and abstract logics are partially ordered by their expressivity, but many logics (modal logics, continuous logic, etc.) are not abstract logics in the sense of Lindström's theorem.

In categorical logic, the philosophy is that for a fixed logic, we can assocate to every theory $T$ in that logic a category with certain extra structure (determined by the logic). Then an interpretation of one theory in another corresponds to a functor between their categories which preserves the relevant structure. So to each logic, we get a category of theories in that logic, with interpretations as morphisms. Maybe this is something like what you're asking for.

Is there also such a notion of a comodel (and the category of models?) ? What would, for example, the category of models of a first order language be?

It's easy to define the category of models of a first-order language or theory. If you take the objects to be the models, you have several choices of arrows: the most common choices are elementary embeddings, embeddings, and homomorphisms. It's a natural question to ask which categories arise in this way. One property that the category of models together with elementary embeddings always has is accessibility.

I think I've already addressed your question about "comodels" - my notion of cologic actually starts with the semantic notion of a "costructure". And given a theory of my cologic, the category of "comodels" for that theory will always be co-accessible (the dual of an accessible category).