Logic Week with W. Hugh Woodin
October 14 to October 21, 2018
Talks
To infinity and far, far beyond
W. Hugh Woodin
Time: Oct. 15, 2018 at 18:30. Location: H5301.
The modern mathematical story of infinity began in the period 1879-84 with a series of papers by Cantor that defined the fundamental framework of the subject. Within 40 years the key ZFC axioms for Set Theory were in place and the stage was set for the detailed development of transfinite mathematics, or so it seemed. However, in a completely unexpected development, Cohen showed in 1963 that even the most basic problem of Set Theory, that of Cantor's Continuum Hypothesis, was not solvable on the basis of the ZFC axioms.The 50 years since Cohen's work has seen a vast development of Cohen's method and the realization that the occurrence of unsolvable problems is ubiquitous in Set Theory. This arguably challenges the very conception of Cantor on which Set Theory is based.
Thus a fundamental dilemma has emerged. On the one hand, the discovery, also over the last 50 years, of a rich hierarchy axioms of infinity seems to argue that Cantor's conception is fundamentally sound. But on the other hand, the developments of Cohen's method over this same period seem to strongly suggest there can be no preferred extension of the ZFC axioms to a system of axioms that can escape the ramifications of Cohen's method.
But this dilemma was itself based on a misconception and recent discoveries now suggest there is a resolution. Slides.
Logic, Algorithms, and Complexity
Yijia Chen
Time: Oct. 17, 2018 at 18:30. Location: H3108
The discipline of theoretical computer science has its early roots in the pioneering work of Church, Turing, and G\"odel. Two important branches of theoretical computer science were already visible right from the beginning: One oriented to computational complexity and algorithms, the other to logic, semantics, and formal methods. The two branches have quite different goals and problems, each developed methods of its own, and they partly use different mathematical tools. Even though their division has been growing steadily during the last 30 years, the two branches come together from time to time as witnessed by the work in areas as descriptive theory, proof complexity, and more recently, parameterized complexity. In this talk, I will use some recent results, including our own, to illustrate how logic can be used to understand complexity, to design efficient algorithms; and how algorithms and complexity can help us to understand expressive power of logic, to prove central results in logic (e.g., G\"odel Incompletenss) from a computational point of view. Slides.Counting modulo $N$ in pseudo-finite fields
Will Johnson
Time: Oct. 18, 2018 at 18:30. Location: HGW2401
Consider the quantifier ``there exists an even number of x such that...'' or more generally the quantifiers ``the number of x such that... is congruent to k mod n.'' These quantifiers make sense in any finite structure. Let $L^+$ be the first order language of rings expanded by these mod-$N$ counting quantifiers. Given a sentence in $L^+$, one can ask whether the sentence holds in all, some, or none of the finite fields. We show that this problem is decidable. In particular, there is an algorithm which can theoretically answer obscure questions like ``does every finite field $\mathbb{F}_q$ with $q > 100$ define a genus 2 smooth projective curve $C$ such that the number of $\mathbb{F}_q$-rational points is odd?''Without the mod $N$ quantifiers, this decidability (of the first order theory of finite fields) was proven by James Ax via a careful analysis of pseudo-finite fields. An infinite field is \emph{pseudo-finite} if it is elementarily equivalent to an ultraproduct of finite fields. Equivalently, the pseudo-finite fields are the infinite fields in the elementary class generated by the finite fields. Ax gave an algebraic characterization of pseudo-finite fields, and a criterion for detecting elementary equivalence. If $K$ is a pseudo-finite field, we show that the $K$-definable sets can be assigned well defined ``sizes'' mod $N$. These ``sizes'' satisfy the expected combinatorial properties with respect to disjoint unions, products, and change-of-$N$. When $K$ is a genuine ultraproduct of finite fields, the ``sizes'' come directly from pseudo-finite counting. The existence of these ``sizes'' for arbitrary pseudo-finite fields follows from a Beth-definability argument combined with facts from algebraic geometry. The aforementioned decidability result for finite fields falls out of the proof. Slides.
Mini Course
Dichotomy theorems and Ultimate $L$
W. Hugh Woodin
Time: Oct. 16, 2018 at 18:30. Location: H3108.
The detailed fine structural study of $L$ arguably began with Jensen’s Covering Lemma from 1975 which in essence is a dichotomy theorem.The prospect of an Ultimate $L$ suggests there should be an ultimate version of Jensen’s Covering Lemma. Remarkably, there is already such a generalization, this is the $HOD$ Dichotomy Theorem. However this theorem makes no reference to Ultimate $L$ even though it seems now to clearly predict that some version of the axiom "$V$ = Ultimate $L$” must hold.
This in turn suggests there might be other theorems in the context of large cardinal axioms which also predict that $V$ must be an ultimate $L$. Such a perspective highlights a whole series of theorems, from Solovay’s theorem of almost 50 years ago that the Singular Cardinal Hypothesis holds above a supercompact cardinal to the recent striking theorem of Usuba which shows that if there is an extendible cardinal then there is a minimum inner model $N$ of $V$ such that $V$ is a generic extension (possibly trivial) of $N$. Slides.
Workshop on foundation of Mathematics
Time: Oct 19, 2018. Location: HGW2401
Program
8:45 - 9:30: Lifting argument for Neeman's forcing with side condition (Wu, Liuzhen)
Neeman introduces the generalized side condition forcing using two type of models. In this talk, we will describe a lifting argument for a modified version of Neeman's forcing in presence of huge cardinals. We will then discuss the similarity between Neeman's forcing and Kunen-style forcing construction in the realm of hugeness. Slides.
9:30 - 10:15: More combinatorics and and topologies on $\omega_1$ (Peng, Yinhe)
The oscillation function -$osc$- introduced by Justin Moore can be used to construct L spaces, L groups, strong negative partition relations. We will analyze further combinatorics properties of $osc$. Some applications to topology will be given. Slides.
10:15 - 10:45: Tea Break
10:45 - 11:30: On Kripke’s Alleged Proof of Church-Turing Thesis (Chen, Long)
Following (Kleene, 1952) , traditionally many people thought of the Church-Turing Thesis [CTT] as unprovable by its nature since it involves the intuitive, informal but not mathematically precise notion of a computable function, although having various strong arguments in its favor, including, most famously, Turing’s analysis of human computation. Recently, stemming from works of (Gandy, 1988; Shoenfield, 1993; Sieg, 2008; Soare, 1996) some reservations have been expressed about the possibility of proving CTT as a theorem (rather than a pure thesis) based on some self-evident axioms as a characterization of intuitive computability, an idea suggested by Gödel himself and part of Turing’s original argument (Argument I). In his recent paper (Kripke, 2013) using another part of Turing’s argument (what is usually called Argument II ) and what he called “Hilbert’s thesis”, Kripke has attempted to prove CTT as a special corollary of Gödel’s completeness theorem. In this talk I will assess Kripke’s new proof and argue that his proof suffers a similar circularity problem of Church’s original argument pointed out already by Sieg (Sieg, 1997) , and that Turing’s main argument of conceptual analysis and axiomatization remains the most plausible one, if any, of a proof of CTT. Slides.
11:30 - 12:15: Projective Singletons (Zhu, Yizheng)
$0^\#$ is a $\Pi^1_2$-singleton whose existence is a large cardinal assumption. Is there any $\Pi^1_2$-singleton whose L-degree is strictly in between 0 and $0^\#$? Friedman answered this question positively by class forcing over L. In this talk, we show how it generalizes to the higher even projective levels. We will describe the main difficulties and show how they are dealt with. This is joint work with Sy D. Friedman and Sandra Müller. Slides.