A remarkable theorem of Shelah states that if $\kappa$ is a singular strong limit cardinal of uncountable cofinality, then there is a subset $x$ of $\kappa$, such that $HOD_x$ contains the powerset of $\kappa$. We show that in general this is not the case for countable cofinality. Using a version of diagonal supercompact extender Prikry forcing, we construct a generic extension in which there is a singular cardinal $\kappa$ with countable cofinality, such that $\kappa^+$ is supercompact in $HOD_x$ for all $x\subset\kappa$. This is joint work with Cummings, Friedman, Magidor, and Rinot and was obtained during a SQuaRE meeting at AIM.

Hide abstract

The success of model theory in attacking problems in Diophantine geometry has given rise to related questions in similar settings.

Recent work by Ullmo and Yafaev considers the uniformizing map $p:V \rightarrow A$ from a complex $n$-space onto an $n$-dimensional complex abelian variety (as usual, $A$ can be identified with the quotient of $V$ by a lattice). They then take a subset $X$ of $V$ which is either algebraic or more generally definable in an o-minimal structure, and consider both the Zariski closure and the topological closure of $p(X)$ in $A$.

In a project which is still in progress, we apply model theoretic machinery in order to understand these two types of closures. Our goal is to give new proofs to some known results (e.g. the Ax-Lindemman theorem), and also to gain a new insight into conjectures of Ullmo-Yafaev about these closures, which I will recall in the talk.

Hide abstract

If $A$ and $B$ are countable structures, then $A$ is Muchnik reducible to $B$ if every $\omega$-copy of $B$ computes an $\omega$-copy of $A$. This can be interpreted as saying that $B$ is intrinsically at least as complicated as $A$. While this is a natural way to compare the complexity of structures, it was limited to the countable setting until Schweber introduced an extension to arbitrary structures: if $A$ and $B$ are (possibly uncountable) structures, then $A$ is generically Muchnik reducible to $B$ if in some (equivalently, any) forcing extension that makes $A$ and $B$ countable, $A$ is Muchnik reducible to $B$.

I will review what is known about the generic Muchnik degrees, including recent work with with Andrews, Schweber, and Soskova. We have proved the existence of a structure with degree strictly between Cantor space and Baire space. It remains open whether an expansion of Cantor space can be strictly in between, but we have proved that no closed expansion or unary expansion can work. Similar results hold for the interval between Baire space and the Borel complete degree (i.e., the degree that bounds all Borel structures). The proofs mix descriptive set theory (including some use of determinacy) with injury and forcing constructions native to computable model theory.

Hide abstract

Let $G$ be a countably infinite group and let $\text{Sub}_{G}$ be the compact space of subgroups $H \leqslant G$. Then a probability measure $\nu$ on $\text{Sub}_{G}$ which is invariant under the conjugation action of $G$ on $\text{Sub}_{G}$ is called an invariant random subgroup. In this talk, I will present some recent results on the invariant random subgroups of simple locally finite groups and discuss some of the many open problems in this area.

Hide abstract

The Globally Valued Fields (GVF) project is a joint effort with E. Hrushovski to understand (standard and) non-standard global fields - namely fields in which a certain abstraction of the product formula holds. One possible motivation is to give a model-theoretic framework for various asymptotic distribution results in global fields.

Formally, a GVF is a field together with a "valuation" in the additive group of an $L^1$ space, such that the integral of $v(a)$ vanishes for every non-zero $a$.

Natural model-theoretic questions regarding GVFs (existence of a model companion, stability, ...), translate to the development of some form of geometry over such fields. There are in fact two flavours for this - a "global" geometry, based on intersection theory, and a "local" geometry, based on the study of the fields at each (standard) valuation separately, combined with a single local-global principle (or, at our level, axiom) called "fullness".

I shall discuss the general setting, as well as the fullness axiom and some recent progress regarding full GVFs.

Hide abstract

This paper will consider the historical development and current use of the notion of structure. I will investigate the algebraic history of the mathematical notion of structure (Corry [1996]) and use this to claim that philosophically oriented mathematical and scientific structuralists (e.g., Shapiro [2005] and French [2000]) implicitly, and problematically, presume a set-theoretic notion of structure. The aim here is to show how a category-theory notion of structure allows for a more perspicuous account of both mathematical and logical structure.

Using the Eilenberg-Mac Lane axioms, we define a cat-structured system as an abstract system of two abstract sorts, viz., 'objects' and 'morphisms' that satisfy the category axioms. The significance of this definition is twofold: 1) it allows us to avoid set-theoretic underpinnings (i.e., 'objects' need not be elements or sets and 'morphisms' need not be functions), and 2) it allows us to abstractly characterize both mathematical and logical structure. Moreover, besides offering an alternative to set-theoretic "foundationalist" accounts of structure, this investigation can further be used to inform the "logic as language" versus "logic as calculus" debate (Goldfarb, [2001]).

Hide abstract

Conjectures in computational complexity such as $P \neq NP$ assert that no efficient program exists for solving many important computational problems. However the general problem of mathematically proving complexity lower bounds remains a mystery: for most prominent lower bound problems, we do not know how to begin proving them true. While computer scientists are extremely adept at designing algorithms, it still seems very difficult to reason about all possible efficient algorithms, including those that we will never see or execute, and argue that none of them can solve an NP-complete problem.

As there are presently enormous gaps in our lower bound knowledge, a central question on the minds of today's complexity theorists is: how will we find better ways to reason about all efficient programs? I will argue that some progress can be made by (very deliberately) thinking algorithmically about lower bounds: looking at lower bound problems as algorithm design problems of a different form. I will outline some new approaches for viewing lower bounds in this way. Time permitting, I will also discuss how some old lower bound methods in circuit complexity have given way to new developments in algorithms.

Hide abstract

To every topological group, one can associate a unique universal minimal flow (UMF): a flow that maps onto every minimal flow of the group. For some groups (for example, the locally compact ones), this flow is not metrizable and does not admit a concrete description. However, for many "large" Polish groups, the UMF is metrizable, can be computed, and carries interesting combinatorial information. The talk will concentrate on some new results that give a characterization of metrizable UMFs of Polish groups. It is based on two papers, one joint with I. Ben Yaacov and J. Melleray, and the other with J. Melleray and L. Nguyen Van Thé.

Hide abstract

I will discuss recent advances in the classification of expansions of the ordered real additive group in terms of the complexity of their definable sets. While arising as a part of Chris Miller's tameness program, this line of research connects to several different areas inside and outside of logic, among which are automata theory, descriptive set theory, neostability and metric geometry. In this talk I will describe these connections and report on recent joint work with Antongiulio Fornasiero and Erik Walsberg.

Hide abstract