Iterated jump noncomputability and compactness

Gavin Dooley (Notre Dame du Lac)

Aug 05. 2025, 15:50 — 16:50

We analyze “iterated jump” versions of the following four principles: the atomic model theorem with subenumerable types (AST), the diagonally noncomputable principle (DNR), weak weak Kőnig’s lemma (WWKL), and weak Kőnig’s lemma (WKL). Each of these principles has a well-known characterization in terms of computability-theoretic notions (namely, in terms of noncomputable sets, diagonally noncomputable functions, Martin-Löf randoms, and PA degrees, respectively). The logical relationships between the "iterated jumps" of these principles include, among other things, an infinite chain and an infinite antichain, the latter of which represents a strong form of non-linearity in terms of provability strength among “natural” combinatorial principles. A copy of the relevant preprint can be found here: https://arxiv.org/abs/2506.20620.

Further Information
Venue:
ESI Schrödinger and Boltzmann Lecture Hall
Recordings:
Recording
Associated Event:
Reverse Mathematics (Thematic Programme)
Organizer(s):
Juan Aguilera (TU Vienna)
Linda Brown Westrick (Penn State U)
Noam Greenberg (Victoria U of Wellington)
Denis Hirschfeldt (U of Chicago)