Past Logic Seminar

16 May 2019
Silvain Rideau

Further Information: 

 (work in progress with Martin Hils)


In the spirit of the Ax-Kochen-Ershov principle, one could conjecture that the imaginaries in equicharacteristic zero Henselian fields can be entirely classified in terms of the Haskell-Hrushovski-Macpherson geometric imaginaries, residue field imaginaries and value group imaginaries. However, the situation is more complicated than that. My goal in this talk will be to present what we believe to be an optimal conjecture and give elements of a proof.

7 March 2019
Rahul Santhanam

The well known (and notoriously hard) P vs NP problem asks whether every Boolean function with polynomial-size proofs is also computable in
polynomial time.

The standard approach to the P vs NP problem is via circuit complexity. For progressively richer classes of Boolean circuits (networks of AND, OR and NOT
logic gates), one wishes to show super-polynomial lower bounds on the sizes of circuits (as a function of the size of the input) computing some Boolean
function known to be in NP, such as the Satisfiability problem.

However, there is a more logic-oriented approach initiated by Cook and Reckhow, going through proof complexity rather than circuit complexity. For
progressively richer proof systems, one wishes to show super-polynomial lower bounds on the sizes of proofs (as a function of the size of the tautology) of
some sequence of propositional tautologies.

I will give a brief overview on known results along these two directions, and on their limitations. Somewhat surprisingly, similar techniques have been found
to be useful for these seemingly different approaches. I will say something about known connections between the approaches, and pose the question of
whether there are deeper connections.

Finally, I will discuss how the perspective of proof complexity can be used to formalize the difficulty of proving lower bounds on the sizes of computations
(or of proofs).


26 February 2019
Martin Hils

Further Information: 

joint work with Moshe Kamensky and Silvain Rideau


Let $p$ be a fixed prime number and let $SCVF_p$ be the theory of separably closed non-trivially valued fields of
characteristic $p$. In the talk, we will see that, in many ways, the step from $ACVF_{p,p}$ to $SCVF_p$ is not more
complicated than the one from $ACF_p$ to $SCF_p$.

At a basic level, this is true for quantifier elimination (Delon), for which it suffices to add parametrized $p$-coordinate
functions to any of the usual languages for valued fields. It follows that all completions are NIP.

At a more sophisticated level, in finite degree of imperfection, when a $p$-basis is named or when one just works with
Hasse derivations, the imaginaries of $SCVF_p$ are not more complicated than the ones in $ACVF_{p,p}$, i.e., they are
classified by the geometric sorts of Haskell-Hrushovski-Macpherson. The latter is proved using prolongations. One may
also use these to characterize the stable part and the stably dominated types in $SCVF_p$, and to show metastability.

21 February 2019

If G is a topological group, a G-flow X is a non-empty, compact, Hausdorff space on which G acts continuously; it is minimal if all G-orbits are dense. By a theorem of Ellis, there is a (unique) minimal G-flow M(G) which is universal: there is a continuous G-map to every other G-flow. 

Here, we will be interested in the case where G = Aut(K) for some structure K, usually omega-categorical. Work of Kechris, Pestov and Todorcevic and others gives conditions on K under which structural Ramsey Theory (due to Nesetril - Rodl and others) can be used to compute M(G). 

In the first part of the talk I will give a description of the above theory and when it applies (the 'tame case'). In the second part, I will describe joint work with J. Hubicka and J. Nesetril which shows that the omega-categorical structures constructed in the late 1980's by Hrushovski as counterexamples to Lachlan's conjecture are not tame and moreover, minimal flows of their automorphism groups have rather different properties to those in the tame case. 

14 February 2019
Stanislav Kikot

 The talk is about the normal modal logics of elementary classes defined by first-order formulas of the form
 'for all x_0 there exist x_1, ..., x_n phi(x_0, x_1, ... x_n)' with phi being a conjunction of binary atoms.
 I'll show that many properties of these logics, such as finite axiomatisability,
 elementarity,  axiomatisability by a set of canonical formulas or by a single generalised Sahlqvist formula,
 together with modal definability of the initial formula, either simultaneously hold or simultaneously do not hold.

7 February 2019
Asaf Karagila

Starting with a countable transitive model of V=L, we show that by 
adding a single Cohen real, c, most intermediate models do no satisfy choice. In 
fact, most intermediate models to L[c] are not even definable.

The key part of the proof is the Bristol model, which is intermediate to L[c], 
but is not constructible from a set. We will give a broad explanation of the 
construction of the Bristol model within the constraints of time.

31 January 2019

Here Z is Zermelo’s set theory of 1908, as later formulated: full separation, but no replacement or collection among its axioms. PROVI was presented in lectures in Cambridge in 2010 and later published with improvements by Nathan Bowler, and is, I claim, the weakest subsystem of ZF to support a recognisable theory of set forcing: PROV is PROVI shorn of its axiom of infinity. The provident sets are the transitive non-empty models of PROV. The talk will begin with a presentation of PROV, and then discuss more recent applications and problems: in particular an answer in the system Z + PROV to a question posed by Eugene Wesley in 1972 will be sketched, and two proofs (fallacious, I hope) of 0 = 1 will be given, one using my slim models of Z and the other applying the Spector–Gandy theorem to certain models of PROVI. These “proofs”, when re-interpreted, supply some arguments of Reverse Mathematics.

24 January 2019
Itay Kaplan

NSOP1 is a class of first order theories containing simple theories, which contains many natural examples that somehow slip-out of the simple context.

As in simple theories, NSOP1 theories admit a natural notion of independence dubbed Kim-independence, which generalizes non-forking in simple theories and satisfies many of its properties.

In this talk I will explain all these notions, and in particular talk about recent progress (joint with Nick Ramsey) in the study of Kim-independence, showing transitivity and several consequences.