Harvard Logic Seminar

The Harvard Logic Seminar meets Mondays from 5:40pm to 6:40pm in Science Center 507. Email Will Boney (wboney@math.harvard.edu) or Sebastien Vasey (sebv@math.harvard.edu) if you are interested in speaking or being added to the mailing list.

The schedule for the Logic Colloquium can be found here.

Click the date to expand abstracts and names to go to the speaker's website (when available).

Next talk:

  1. March 25: Justin Cavitt "Large Cardinals and Simpler Proofs"

    • Abstract: Extending ZFC by large cardinal axioms not only allows one to prove more theorems, but also allows one to give simpler proofs of ZFC theorems. For example, the proof of Borel determinacy assuming the existence of a measurable cardinal is much simpler than the proof assuming only ZFC. A theorem of Ehrenfeucht and Mycielski indicates that something similar happens whenever an undecidable theory is extended by a new axiom. In this talk, we will review this and related results and discuss potential applications to the large cardinal speedup phenomenon.
Future talks:

Past talks:

    1. March 11: Cameron Freer (MIT) "Computability of exchangeable sequences, arrays, and graphs"

      • Abstract: A sequence of random variables is exchangeable when its distribution is invariant to reorderings of the sequence. This notion of symmetry and its generalizations to arrays, graphs, and other structures, arise in many statistical contexts. Representation theorems due to de Finetti, Aldous-Hoover, and others, describe how exchangeable structures can be written in a way that exposes conditional independence, which is often important for computational purposes. However, these results are not obviously computable. We will present several positive and negative results examining the computable content of these theorems, and will also describe several implications for the design of probabilistic programming languages. Joint work with Nathanael Ackerman, Jeremy Avigad, Daniel Roy, and Jason Rute.
      • Abstract: The entropy of a probability measure on a finite set quantifies one notion of the complexity of the measure. For a finite relational language $L$, and a measure $\mu$ on $L$-structures with underlying set the natural numbers, if $\mu$ is $S_\infty$-invariant then it is determined by its restriction to $L$-structures of the form $\{0, \ldots , n-1\}$. We can therefore canonically assign to $\mu$ its \emph{entropy function}, $En_\mu$, which sends each natural number $n$ to the entropy of the restriction of $\mu$ to $L$-structures with underlying set $\{0, \ldots , n-1\}$. In this talk I will discuss the relationship between the growth rate of $En_\mu$ and the language $L$. If the largest arity of a relation in $L$ is $k$, then $En_\mu$ grows as $O(n^k)$. I will give a precise expression for the coefficient of $n^k$ based on the hypergraphon representation of $\mu$, and show how these notions generalize what is often called the \emph{entropy of a graphon}. When $\mu$ comes from sampling a Borel structure we will show that the growth rate of the entropy function is $o(n^k)$. We will also discuss lower bounds on the possible growth rates of the entropy function in this case. This generalizes work of Hatami-Norine from graphons to hypergraphons. Joint work with Cameron Freer and Rehana Patel.
      • Abstract: The upward Löwenheim-Skolem theorem says that any first-order theory with an infinite model has arbitrarily large models. Such a result completely completely breaks down when we start looking at infinitary logics. In this case, one can still ask what properties of small models imply the existence of larger models. One of the simplest such property is categoricity (the existence of a unique model of a fixed cardinality). In that direction, Shelah proved the remarkable result that an L_{\omega_1, \omega} sentence categorical in aleph_0 and aleph_1 has a model of cardinality aleph_2. Generalizations of this result have been key motivating questions for the development of a classification theory of infinitary logics, and also have also yielded some interesting set theory. We will survey some old results as well as recent developments.
    2. December 3: Tibor Beke (University of Massachusetts-Lowell) "Schanuel functors and the Grothendieck (semi)ring of some theories"

      • Abstract: In a little known article, Schanuel defines a functor from semirings to idempotent semirings and a notion of dimension that is not linearly ordered. He uses it to give an elegant presentation of the Grothendieck semiring of semi-algebraic sets, from which the (much better known) structure of the Grothendieck ring of semi-algebraic sets easily follows. I will review his work and related results on the Grothendieck semiring of algebraically closed fields and similar geometric structures.
      • Abstract: Thanksgiving break is a common tradition in American universities that cancels class for two or three days the week of Thanksgiving. In this cancelled talk, we explore new evidence that this tradition's creep has extended to the cancellation of Monday meetings.
    3. November 12: Rehana Patel, "Around Cherlin's question on countable universal $H$-free graphs"

      • Abstract: A longstanding open problem of Cherlin asks: Is there an algorithm that decides, given as input a finite connected constraint graph H, whether there exists a countable universal H-free graph? I will describe what is known about this decision problem, including old and new results, and discuss some further model-theoretic questions generated by these results.
    4. November 5: Gabriel Goldberg, "Descending sequences in the Mitchell order"

      • Abstract: The axiom I2 is a large cardinal axiom just short of the Kunen inconsistency which implies that the (generalized) Mitchell order is illfounded. We will sketch a proof of a conjecture of Steel that constrains how illfoundedness can occur.
    5. October 29: Douglas Blue, "Sacks’ embedding problem"

      • Abstract: Sacks (1963) conjectured that in ZFC the Turing degrees are universal in the sense that any locally countable partial order of size at most continuum is isomorphic to a subordering of the degrees. This conjecture remains unresolved. Sacks proved it assuming CH, but his method depends on maximal independent sets of degrees being of size continuum. Groszek and Slaman showed that this is independent, indicating the need for a new method. We will review these results and sketch a proof that the arithmetic degrees are universal for continuum sized, locally countable partial orders.
    6. October 15: Will Boney, "Erdős-Rado Classes"

      • Abstract: Ramsey classes are used to construct generalized indiscernibles in models of first-order theories. However, the lack of compactness means that Ramsey's theorem (and its generalizations) are not enough to build indiscernibles in nonelementary classes. Instead, order indiscernibles are built with the Erdos-Rado Theorem. We present a framework for building indiscernibles in (many) nonelementary classes: Erdos-Rado classes (and some variants). The combinatorial definition of these classes is that they satisfy a certain partition relation for building large homogeneous sets when given many colors. We connect this to building indiscernibles, present several examples (some independent of ZFC), and provide some applications.
    7. September 24: Sebastien Vasey, "Forking independence from the categorical point of view"

      • Abstract: Forking is a central notion of model theory, generalizing linear independence in vector spaces and algebraic independence in fields. We develop the theory of forking in abstract, category-theoretic terms, for reasons both practical (we require a characterization suitable for work in accessible categories, a category-theoretic framework encompassing many examples of non-elementary classes) and expository (we hope, with this account, to make forking accessible and useful to a broader mathematical audience).
        In particular, we present an axiomatic definition of what we call a stable independence notion on a category and show that this is in fact a purely category-theoretic axiomatization of the properties of model-theoretic forking in a stable first-order theory. We connect the definition of stable independence to an exactness property, having effective unions, and use this to give new examples where forking occurs: any coregular locally presentable category with effective unions admits a forking-like independence notion. This includes the cases of Grothendieck toposes and Grothendieck abelian categories.
        This is joint work with Michael Lieberman and Jiří Rosický.
    8. April 24: Paul Baginski (Fairfield University), "Model Theoretic Advances for Groups With Bounded Chains of Centralizers"

      • Abstract: A group G has bounded chains of centralizers (G is \M_C) if every chain of centralizers C_G(A_1) \leq C_G(A_2) \leq ... is finite. While this class of groups is interesting in its own right, within model theory MC groups have been examined because they strictly contain the class of stable groups. Stable groups robustly extend ideas from algebraic groups, such as dimension and independence, to a wider setting, including free groups. Stable groups gain much of their strength through a chain condition known as the Baldwin-Saxl chain condition, which implies the \M_C property as a special case.

        Several basic, but key, properties of stable groups have been observed by Wagner [4] and others to follow purely from the \M_C condition (this builds upon the work of Bludov [2], Khukhro [3], and others). These properties were, as one would expect, purely group-theoretic. From the perspective of logic, the class of \M_C groups should be unruly, since the MC condition is not first-order (unless one insists on a uniform bound to the lengths of the chains). Yet the speaker and Tuna Altınel [1] have uncovered that MC groups possess a logical property of stable groups as well, namely the abundance of definable nilpotent subgroups. We shall present this result and describe the current investigations for finding an analogue for solvable subgroups. (Joint work with Tuna Altınel, Universit´e Lyon 1)


        [1] T. Altınel and P. Baginski, Definable envelopes of nilpotent subgroups of groups with chain conditions on centralizers, Proc. Amer. Math. Soc. 142 (2014), no. 5, 1497–1506.

        [2] V.V. Bludov, On locally nilpotent groups with the minimality condition for centralizers, Algebra Logika 37 (1998), 270–278.

        [3] E.I. Khukhro, On solubility of groups with bounded centralizer chains, Glasg. Math. J. 51 (2009), 49–54.

        [4] F.O. Wagner, Stable Groups, London Mathematical Society Lecture Note Series, 240. Cambridge University Press, 1997.

    9. April 3: Warren Goldfarb, "Two Notes on Weak Arithmetics"

      • Abstract: Two results are proved:
        1. Presburger Arithmetic is not finitely axiomatizable, and
        2. There is a consistent recursive extension of Robinson Arithmetic that decides every diophantine sentence.
    10. March 27: Marcos Mazari Armida (Carnegie Mellon University), "Non-forking w-good frames"

      • Abstract: The central notion of Shelah's book on AEC's is that of a good $\lambda$-frame, which is a forking-like notion for types of singletons in abstract elementary classes. In this talk, we will introduce the weaker notion of a w-good $\lambda$-frame. We show that the existence of a w-good frame implies the existence of larger models and show how to extend w-good frames under tameness and amalgamation. As an application(under some cardinal arithmetic hypothesis) we construct a model of size $\lambda^{+++}$ under the assumption of $\lambda$ and $\lambda^+$ categoricity, few models in $\lambda^{++}$ and $(\lambda, \lambda^+)$-tameness.
      • Abstract: Spring Break is a common week (or more) long break in American universities, often observed in March or April. This talk details new insight into the ways that such breaks disrupt weekly scheduled events.
      • Abstract: The Feferman-Vaught Theorem in model theory gives a sort of upper bound on the complexity of definable subsets in a product structure. We show how this theorem implies that subsets whose boundary is dense (in the product topology where every factor structure has the discrete topology) are undefinable. We also show how the upper bound in the F.V. Theorem is the best possible, in the case of the language of rings where each factor structure is an integral domain. Finally, we apply these results to the ring $\prod_{p prime} F_p$, the product of all finite prime fields, and obtain a quantifier elimination result for the structure.
    11. February 20: Andrew Brooke-Taylor (University of Leeds), "Products of CW complexes: the full story"

      • Abstract: CW complexes are used extensively in algebraic topology as a suitable class of spaces to work with, but the product of two CW complexes need not be a CW complex, as shown by Dowker. Whitehead and Milnor gave sufficient conditions on the two spaces for the product to be a CW complex, but until now the known characterisations of those pairs of CW complexes with product a CW complex relied on set-theoretic assumptions about the whole universe, such as the Continuum Hypothesis. In this talk I will present a complete characterisation, valid without assuming any extra set-theoretic axioms, of those pairs of CW complexes whose product is a CW complex.
    12. MONDAY February 12: Alice Medvedev (City University of New York), "Unions of chains of signatures" Note the Monday time!

      • Abstract: We meditate on a particularly naive notion of a limit of a sequence of theories: a union of conservative expansions. That is, we consider a sequence of nested signatures $L_1 \subset L_2 \subset \ldots$, each one a subsignature of the next, and a sequence of $L_i$-theories $T_i$, where each $T_i$ is precisely the set of $L_i$-consequences of $T_{i+1}$ (and hence is a subset of $T_{i+1}$). It turns out that many model-theoretic properties then pass from all $T_i$ to their union $T$; these include consistency, completeness, quantifier elimination, partial quantifier elimination such a model-completeness, elimination of imaginaries, stable embeddedness of some definable set, characterization of algebraic closure; stability, simplicity, rosiness, dependence. Our motivating example is the theory $T$ of fields with an action by $(Q; +)$, seen as a limit of (theories of) fields with $(Z; +)$-actions.
    13. February 6: Jesse Han (McMaster University), "Strong conceptual completeness for \omega-categorical theories"

      • Abstract: Suppose we have some process to attach to every model of a first-order theory some (permutation) representation of its automorphism group, compatible with elementary embeddings. How can we tell if this is really an imaginary sort of our theory?

        In the '80s, Michael Makkai proved that the answer to our question is yes if and only if our given process is compatible with all ultraproducts and all "formal comparison maps" between them (generalizing e.g. the diagonal embedding into an ultrapower). This is known as /strong conceptual completeness/; formally, the statement is that the category Def(T) of definable sets can be reconstructed up to bi-interpretability as the category of "ultrafunctors" Mod(T) \to Set.

        \omega-categorical structures, having few definable sets, are exceptionally simple to understand, and in fact are determined up to bi-interpretability by the action of their automorphism groups. Any general framework which reconstructs theories from their categories of models should therefore be considerably simplified for \omega-categorical theories.

        Indeed, we show:

        1. If T is ω-categorical, then X : Mod(T) → Set is definable, i.e. isomorphic to (M \mapsto ψ(M)) for some formula ψ ∈ T, if and only if X preserves ultraproducts and diagonal embeddings into ultrapowers. This means that all the preservation requirements for ultramorphisms, which a priori get unboundedly complicated, collapse to just diagonal embeddings when T is ω-categorical.

        2. This definability criterion fails if we remove the ω-categoricity assumption. We construct examples of theories and non-definable functors Mod(T) \to Set exhibiting this.
      • Abstract: Szemer\‘{e}di’s regularity lemma for graphs says, roughly speaking, that any finite graph can be approximated by one that has a small structural “skeleton” overlaid with randomness. Malliaris and Shelah have shown that under the model-theoretic tameness condition of stability, this approximation is especially well-behaved: bounds on the size of the so-called “regularity partition” are significantly improved; there are no “irregular pairs” in the partition; and randomness is essentially eliminated. In this talk I will describe a generalisation of the Malliaris-Shelah result to stable finite structures in a finite relational language. This is joint work with Nate Ackerman and Cameron Freer.
    14. November 28: Gabe Conant (University of Notre Dame), "A group version of stable regularity"

      • Abstract: Given an abelian group G and a subset A of G, one can construct a graph on G in which distinct elements x,y in G are connected if x+y is in A. If this graph is stable, then work of Malliaris and Shelah implies that it satisfies a strong form of Szemeredi's regularity lemma (and this has nothing to do with groups). A corollary of recent work of Terry and Wolf is that if G is a finite dimensional vector space over a prime field, then the regular partition of such a stable graph can be obtained using cosets of a subgroup. This motivates a statement of ``coset regularity" for subsets A of arbitrary finite groups G, such that "xy in A" is a stable binary relation. We prove this statement using local stable group theory and an ultraproduct construction. Joint with A. Pillay and C. Terry.
      • Abstract: Thanksgiving break is a common tradition in American universities that cancels class for two or three days the week of Thanksgiving. In this cancelled talk, we explore how this tradition creeps earlier into the week and causes earlier meetings to be cancelled as well.
    15. November 14: Linda Westrick (University of Connecticut), "Towards a notion of computable reducibility for discontinuous functions"

      • Abstract: If X and Y are computably presented uncountable metric spaces, the collection of all functions from X to Y has cardinality too large to allow such functions to be represented as elements of Baire space. Nevertheless, we have some intuitive idea of what it should mean for one discontinuous function to compute another. I will discuss the problem of defining an appropriate notion of computable reducibility on this space. Joint work with Adam Day, Rod Downey and Takayuki Kihara.

      November 15: Steve Jackson will be giving the Logic Colloquium.

    16. November 7: CANCELLED

      November 8:Victoria Gitman will be giving the Logic Colloquium on November 8.

    17. October 31: Sebastien Vasey, "Non-elementary classification theory"

      • Abstract: The classification theory of elementary classes was started by Michael Morley in the early sixties, when he proved that a countable first-order theory with a single model in some uncountable cardinal has a single model in all uncountable cardinals. The proof of this result, now called Morley's categoricity theorem, led to the development of forking, a joint generalization of linear independence in vector spaces and algebraic independence of fields, which is now a central pillar of modern model theory.

        In recent years, it has become apparent that the theory of forking can also be developed in several non-elementary contexts. Prime among those is the axiomatic framework of abstract elementary classes (AECs), encompassing the class of models of any L_{infinity, omega}-theory and closely connected to the more general framework accessible categories. A test question to judge progress in this direction is the forty year old eventual categoricity conjecture of Shelah, which says that a version of Morley's categoricity theorem should hold of any AEC. I will survey recent developments, including the connections with category theory and large cardinals as well as my resolution of the eventual categoricity conjecture for classes of models axiomatized by a universal L_{infty, omega}-theory.
    18. October 24: Will Boney, "Interpolation beyond $\mathbb{L}_{\omega_1, \omega}"

      • Abstract: For a logic $\mathcal{L}$, interpolation holds in $\mathcal{L}$ iff for every implication $\phi \to \psi$, there is a sentence $\chi$ in their common language (in $\mathcal{L}$) such that $\phi \to \chi$ and $\chi \to \psi$. It is well-known that $\mathbb{L}_{\omega, \omega}$ and $\mathbb{L}_{\omega_1, \omega}$ satisfy interpolation, but no other $\mathbb{L}_{\kappa, \lambda}$ does. We discuss a logic $\mathbb{L}^1_\kappa$ developed by Shelah that (for $\kappa = \beth_\kappa$) is intermediate between $\mathbb{L}_{\kappa, \omega}$ and $\mathbb{L}_{\kappa, \kappa}$ and satisfies interpolation.
    19. October 17: Cameron Freer (Borelian and Remine), "Feedback Computability"

      • Abstract: The notion of a feedback query is a natural generalization of choosing for an oracle the set of indices of halting computations. Notice that, in that setting, the computations being run are different from the computations in the oracle: the former can query an oracle, whereas the latter cannot. A feedback computation is one that can query an oracle, which itself contains the halting information about all feedback computations. Although this is self-referential, sense can be made of at least some such computations.

        We'll discuss feedback around Turing computability. In one direction, we examine feedback Turing machines, and show that they provide exactly hyperarithmetic computability. In the other direction, Turing computability is itself feedback primitive recursion (at least, one version thereof). We'll also briefly consider notions for parallel computation, and for Borel maps on Cantor space.

        Joint work with Nate Ackerman and Bob Lubarsky.
    20. October 10: Nate Ackerman, "Trees, Sheaves and Definition by Recursion"

      • Abstract: We will show there is a topological space for which presheaves are the same thing as trees. We will further show that there is a sheaf on this topological space which has an important relationship with Baire space. We will then use these connections to show how a definition by transfinite recursion can be thought of as an operation on sheaves, and how the well-definedness of such a definition can be thought of as a property of the sheaf we are working on. This will then allow us to define a second order tree as a sheaf on a tree and to expand our notion of definition by transfinite recursion to all well-founded second order trees (even those which are ill-founded as normal trees). We will then mention how these techniques can be used to prove a variant of the Suslin-Kleene Separation theorem.
    21. October 3: Jason Rute, "A uniform reducibility in computably presented Polish spaces"

      • Abstract: (Joint work with Tim McNicholl.) In this talk we will define a new uniform computable reducibility between computable Polish spaces. No specialized knowledge of computability theory is required. Given computably presented Polish spaces X and Y, we say x in X is reducible to y in Y if there is a Pi^0_1 subset P of Y and a computable map f : P -> X such that f(y)=x. For each space X one may consider the corresponding degree structure deg(X). For example, deg(2^omega) is (isomorphic to) the truth-table degrees, whereas both deg(omega^omega) and deg(reals) are proper extensions of deg(2^omega). This new reducibility has many motivations. First, it is based on the notion of truth-table reducibility (which we will define). Truth-table reducibility on 2^omega is too restrictive of a setting for working within Baire space or the real numbers. For example, there are functions f in omega^omega not truth-table reducible to any X in 2^omega and sequences X in 2^omega such that X/3 is not truth-table reducible to X. Our reducibility gives the correct generalization of truth-table reducibility to these spaces. Second, this project mirrors Miller's non-trivial work extending Turing reducibility to computably presented Polish spaces. Last, our reducibility grew naturally out of work of the first author on computable arcs and the second author on Schnorr randomness. For example, we show that, for the vector space R^d, every Schnorr random is found in some computable arc.
      • Abstract: It is consistent that the least strongly compact cardinal is the least supercompact cardinal, but it is also consistent that the least strongly compact cardinal is the least measurable cardinal. Which is it? The Ultrapower Axiom is an abstract comparison principle motivated by inner model theory that roughly states that any pair of ultrapowers can be ultrapowered to a common ultrapower. We give a characterization of supercompact cardinals in terms of the Mitchell order and use this to prove that the least strongly compact cardinal is supercompact assuming the Ultrapower Axiom and the GCH.
    22. September 19: Will Boney, "Model-theoretic characterizations of large cardinals"

      • Abstract: Compact cardinals get their names from a characterization in terms of the compactness of L_{\kappa, \kappa}. Measurable and supercompact cardinals also have characterizations in these terms, and Magidor has used second-order logic to characterize supercompacts and extendible cardinals in this way. We will continue this line of model-theoretic characterizations and discuss the characterizations of large cardinals in terms of compactness for omitting types focusing on three logics: L_{\kappa, \kappa}, second-order, and sort logic.
    23. September 12: Sebastien Vasey, "Internal sizes in $\mu$-abstract elementary classes"

      • Abstract: The internal size of an object $M$ inside a given category is, roughly, the least infinite cardinal $\lambda$ such that any morphism from M into the colimit of a $\lambda^+$-directed system factors through one of the components of the system. In the category of set, the internal size of an object is its cardinality. In the category of vector spaces, the internal size is the dimension, and in the category of metric spaces, the internal size is the least cardinality of a dense subset.

        We will discuss questions around internal sizes in the framework of $\mu$-abstract elementary classes ($\μ$-AECs), which are, up to equivalence of categories, the same as accessible categories with all morphisms monomorphisms. We will in particular examine an example of Shelah---a certain class of sufficiently-closed constructible models of set theory---which shows that the categoricity spectrum can behave very differently depending on whether we look at categoricity in cardinalities or in internal sizes. This is joint work with Michael Lieberman and Jiří Rosický.
    24. September 5: Nate Ackerman, "Vaught's Conjecture for a Grothendieck topos"

      • Abstract: In this talk we will give background on $\mathcal{L}_{\infty, \omega}(L)$, categorical logic as well as Grothendieck toposes. We will then show how to make precise a version of Vaught's conjecture for a Grothendieck topos as well as discuss various analogs of Morley's theorem which hold in all Grothendeick toposes (under mild set theoretic assumptions). If we have time we will also discuss analogs of other theorems of $\mathcal{L}_{\infty, \omega}$ for Grothendieck toposes.

    Back to Harvard Logic.
    Back to my homepage.