Harvard Logic Seminar
The Harvard Logic Seminar meets Tuesdays from 5:15pm to 6:15pm in Science Center 507. Email Will Boney (wboney@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.
Next talk:
- 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.
Future talks:
- November 21: No seminar, "Cancelled"
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.
- 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.
- 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.
Past talks:
- November 7: CANCELLED
November 8:Victoria Gitman will be giving the Logic Colloquium on November 8.
- 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.
- 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.
- 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.
- 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.
- 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.
- September 26: Gabriel Goldberg, "The least strongly compact cardinal and the Ultrapower Axiom"
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.
- 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.
- 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ý.
- 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.
You also might be interested in some nearby events:
- UConn is having a special semester in logic with several speakers coming in. The schedule is here.
Back to Harvard Logic.
Back to my homepage.