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

logic

Audience: researchers in the topic

Computability theory and applications

Series comments: Description: Computability theory, logic

The goal of this endeavor is to run a seminar on the platform Zoom on a weekly basis, perhaps with alternating time slots each of which covers at least three out of four of Europe, North America, Asia, and New Zealand/Australia. While the meetings are always scheduled for Tuesdays, the timezone varies, so please refer to the calendar on the website for details about individual seminars.