Workshops and Conferences 2016

COLLOQUIUM: The Legacy of Claude Shannon

13 December, 16:00, at Instituto Superior Técnico, Universidade de Lisboa

An introduction to impredicative ordinal notation systems

a minicourse by David Fernández-Duque, Université Paul Sabatier, Toulouse, France

First session: November 2 (Wednesday), 6pm - 7:30pm, room 6.2.33

Second session: November 3 (Thursday), 3:30pm - 5pm, room 6.2.33

In this course we will give an introduction to ordinal notation systems based on collapsing cardinals in the style of Buchholz. Although familiarity with proof-theoretic ordinals is assumed, the course will work gradually, beginning with a quick review of predicative notation systems and introducing some intermediate systems along the way. The course will be divided in two sessions. Session 1: We introduce a general notion of ordinal notation system and show how the usual presentations for $\varepsilon_0$ and $\Gamma_0$ fall into this framework. We discuss the behavior of an uncountable ordinal within a notation system and introduce collapsing functions, culminating in a notation system for the Bachmann-Howard ordinal $\psi(\varepsilon_{\Omega+1})$. Session 2: We establish some important properties of $\psi(\varepsilon_{\Omega+1})$, including its computability. We motivate the role of multiple cardinals by considering collapsing functions with two uncountable cardinals. We then show how these techniques are extended to collapsing infinitely many cardinals. Time permitting, we discuss how larger sets (e.g., an inaccessible) can be used to construct even larger proof-theoretic ordinals.