Logic Workshop

There is a natural way to formulate fragments of Todorcevic’s strong reflection principle (SRP) which are associated to forcing classes more restrictive than the class of all stationary set preserving forcing notions. The fragment associated to the subcomplete forcings (SC-SRP), while retaining many crucial consequences of SRP, is compatible with CH, and even Jensen's Diamond Principle. In particular, the saturation of the nonstationary ideal, a celebrated consequence of SRP, does not follow from its subcomplete fragment. In fact, adding CH to SC-SRP results in a principle which outright contradicts the saturation of the nonstationary ideal. A specific form of diagonal reflection of stationary sets of ordinal was used by Paul Larson to separate SRP from Martin's Maximum: that form of diagonal reflection follows from MM, but not from SRP. The surprising initial observation is that it does follow from SC-SRP + CH. The key reason for this is that SC-SRP + CH implies the nonsaturation of the nonstationary ideal. Thus, an apparent weakness of SC-SRP + CH turns out to be a strength in this context.

I will introduce the concepts involved and present some further results along these lines. The picture that emerges is that in the context of SC-SRP, saturation and diagonal reflection work against each other.

This is joint work with Hiroshi Sakai.

Tennenbaum's theorem states that no non-standard model of PA is computable. Hence, no unsound extension of PA has computable models. Pakhomov recently showed that this consequence of Tennenbaum's theorem is fragile; it depends on the signature in which PA is presented. In particular, there is a theory T such that (i) T is definitionally equivalent to PA (this is a strong form of bi-interpretability) and (ii) every consistent r.e. extension of T has a computable model. Pakhomov's techniques yield analogous results for ZF and other canonical systems. He asked whether there is a consistent, r.e. theory T such that no theory which is definitionally equivalent to T has a computable model. We answer this question with an ad hoc construction. This is joint work with Patrick Lutz.

A dimension group is a partially ordered Abelian group whose partial order is isolated and directed and has the Riesz interpolation property. A dimension group is simple just in case it has no nontrivial ideals, ideals being directed convex subgroups. By concentrating on the behavior of positive formulas in simple dimension groups, this talk will reveal a well-behaved part of their model theory.

I want to argue that when knowing the model-theory of categories, you kind of know the model-theory of any structure. As the ? at the end of the title suggests, some of this is still speculative.

It is easy to see a category as a first-order structure in the two-sorted language (for objects and morphisms) of categories; a little less to do this foundationally correct (I have given a talk a way back in which I ignored these issues, but I will correct this in the talk, although not mentioning them in this abstract). Now, to any theory T in some first-order language L, we can associate a theory in the language of categories, cat(T), which reflects this theory: the models of cat(T) are isomorphic (as categories) with subcategories of the category Mod(T) of models of T. In fact, any category that is elementary equivalent with Mod(T) is a sub-model of the latter.

This translation from T into cat(T)---from an arbitrary signature to a fixed one---is still mysterious, and as of now, I only know a very few concrete cases. A key role seems to be played by the theory FO, consisting of all sentences in the language of categories which hold in each category of L-structures, for all possible languages L. But I do not even know yet a full axiomatization of FO.

A Borel graph is hyperfinite if it can be written as a countable increasing union of Borel graphs with finite components. It is a major open problem in descriptive set theory to determine the complexity of the set of hyperfinite Borel graphs. In a recent paper, Conley, Jackson, Marks, Seward, and Tucker-Drob introduce the notion of Borel asymptotic dimension, a definable version of Gromov's classical notion of asymptotic dimension, which strengthens hyperfiniteness and implies several nice Borel combinatorial properties. We show that the set of locally finite Borel graphs having finite Borel asymptotic dimension is $\Sigma^1_2$-complete. This is joint work with Jan Grebik.