Midwest Computability Seminar

XXVI
Part vii



The Midwest Computability Seminar is meeting remotely in the winter and spring of 2021. The recurring Zoom link is:

https://notredame.zoom.us/j/99754332165?pwd=RytjK1RFZU5KWnZxZ3VFK0g4YTMyQT09

Meeting ID: 997 5433 2165

Passcode: midwest



slides    video   (this version might need to be downloaded to be viewed)    YouTube video


This session will be held jointly with the Computability Theory and Applications Online Seminar.


DATE: Monday, May 3rd, 2021

TIME: 3:30 - 4:30 PM Central Time

SPEAKER: André Nies - Auckland University

TITLE:
Maximal towers and ultrafilter bases in computability theory

ABSTRACT:
The tower number and ultrafilter numbers are cardinal characteristics from set theory that are defined in terms of sets of natural numbers with almost inclusion. The former is the least size of a maximal tower. The latter is the least size of a collection of infinite sets with upward closure a non-principal ultrafilter.

Their analogs in computability theory will be defined in terms of collections of computable sets, given as the columns of a single set. We study their complexity using Medvedev reducibility. For instance, we show that the ultrafilter number is Medvedev equivalent to the problem of finding a function that dominates all computable functions, that is, highness. In contrast, each nonlow set uniformly computes a maximal tower.

Joint work with Steffen Lempp, Joseph Miller, and Mariya Soskova

Draft available at https://www.cs.auckland.ac.nz/research/groups/CDMTCS/researchreports/download.php?selected-id=769



Past Sessions

Previous Seminars:


If you haven't been receiving the announcements and would like to be included in the list, send an email to drh@math.uchicago.edu.