Harvard/MIT Logic Seminar

Fall 2012

Organizers: Nate Ackerman, Rachel Epstein, Cameron Freer, and Rehana Patel.

To be added to the mailing list, please contact freer@math.removethis.mit.andthis.edu.


    The computably enumerable sets: the tardy sets, the $\mathcal{D}$-maximal sets and the low sets.

    We will survey recent work on the computably enumerable sets focusing on a collection of results that implies that the tardy sets break up into infinitely many orbits and similarly for the $\mathcal{D}$-maximal sets. In the tardy case all of the known orbits avoid the complete sets. Can the same be said for the $\mathcal{D}$-maximal sets? At the end we will address the question of which sets are automorphic to low sets.


    Cofinality spectrum problems in model theory, set theory and general topology.

    Recent work of Malliaris and Shelah on model-theoretic questions around saturation of regular ultrapowers has led also to theorems in set theory and general topology, notably the solution of the oldest problem on cardinal invariants of the continuum. The talk will outline the general program and some features of this recent proof.


  • Friday November 9: Rod Downey (Victoria University of Wellington)

    3:30 pm, Science Center Room 411, Harvard University

    The computability theory of the Finite Intersection Principle.

    A family of sets ${\mathcal F}=\{A_i\mid i\in J\}$ has FIP iff for any finite $I\subset J$, $\cap_{i\in I}A_i\ne \emptyset.$ The FIP principle says that any collection of sets has a maximal subcollection with FIP. The reverse maths and effective content of this principle, classically equivalent to choice, was initiated by Dzharfarov and Mummert. They showed, for instance, that there is a computable family with no computable maximal FIP subfamily. We say that a degree ${\bf a}$ is FIP iff it has the ability to compute a solution to any computable instance of FIP. Dzharfarov and Mummert's result says that ${\bf 0}$ is not FIP. Dzharfarov and Mummert showed that each nonzero c.e. degree is FIP, all FIP degrees are hyperimmune, and several classes of 1-generics degree were FIP.

    We extend these investigations by giving new (shorter) proofs of some of Dzharfarov and Mummert's work, and also showing that all 1-generics are FIP, and showing that, for the $\Delta_2^0$ degrees, that the FIP degrees are precisely the ones that bound 1-generic degrees. We could hope that this characterization extends to the general hyperimmune case, since hyperimmune degrees resemble $\Delta^0_2$ ones. However, we can also show that there is a minimal $\Delta_3^0$ FIP degree. This last result has some technical complexity as it is a full approximation argument constructing a hyperimmune $\Delta_3^0$ degree, which does not seem to have occurred in the literature hitherto.

    Joint work with Diamondstone, Greenberg, and Turetsky.


  • Tuesday November 27: Koushik Pal (University of Maryland, College Park)

    4:00 pm, Science Center Room 507, Harvard University

    Unstable Theories with an Automorphism.

    Kikyo and Shelah showed that if $T$ is a first-order theory in some language $L$ with the strict-order property, then the theory $T_\sigma$, which is the old theory $T$ together with an $L$-automorphism $\sigma$, does not have a model companion in $L_\sigma$, which is the old language $L$ together with a new unary predicate symbol $\sigma$. However, it turns out that if we add more restrictions on the automorphism, then $T_\sigma$ can have a model companion in $L_\sigma$. I will show some examples of this phenomenon in two different context — the linear orders and the ordered abelian groups. In the context of the linear orders, we even have a complete characterization of all model complete theories extending $T_\sigma$ in $L_\sigma$. This is joint work with Chris Laskowski.


  • Wednesday December 5: Max Weiss (University of British Columbia / Harvard University)

    4:00 pm, Science Center Room B-10, Harvard University

    The logic of the Tractatus.

    In his 1921 book the Tractatus, Wittgenstein proposed that every sentence of a language can be represented as the joint denial of some "specifiable" multiplicity of sentences. Such a representation would determine well-founded ancestries for all sentences, terminating only in sentences whose truth-conditions are fixed independently.

    The complexity of languages which can be analyzed in this way depends on the strength of the condition that a multiplicity of sentences be specifiable. A natural suggestion is that a multiplicity is specifiable if it is r.e. However, this leads to a computationally intractable syntax. So, we develop a finer analysis of specifiability, based on schematization and iterated substitution. The resulting system strictly extends FOL=, in particular by expressing the concept of transitive closure. This is work in progress, and we conclude with some open questions.