Midwest Computability Seminar


The Midwest Computability Seminar is a joint venture between the University of Chicago, the University of Notre Dame, and the University of Wisconsin-Madison. It meets once or twice per semester at the University of Chicago, and is attended by faculty and students from these universities and others in the area. The seminar started in the fall of 2008.

: Tuesday, October 24, 2017.
PLACE: Ryerson Hall 352 (the Barn), The University of Chicago.
1100 East 58th Street, Chicago, IL 60637.




Noah Schweber

Title: Computability and Banach-Mazur games

Abstract: We'll look at some questions around Banach-Mazur games. On the pure computability-theoretic side, after establishing the effectiveness of some basic facts about Banach-Mazur games we classify the functions computable from all winning strategies for some Banach-Mazur game as exactly the hyperarithmetic sets, using an analogue of Hechler forcing for building strategies. On the reverse mathematical side, we parallel this by showing that Borel Banach-Mazur determinacy is equivalent to ATR0, and that this equivalence goes "level-by-level;" by contrast, we also show that there is a Turing ideal satisfying lightface Σ11-Banach-Mazur determinacy but not containing 0(ω), this time using an analogue of Spector forcing for building strategies.

Don Stull

Title: Effective dimension of points on lines

Abstract: This talk will cover recent work using Kolmogorov complexity to study the dimension of points on lines in the Euclidean plane and its application to important questions in fractal geometry. In particular, we will show that this work strengthens the lower bounds of the dimension of Furstenberg sets. We will also discuss future research and open problems in this area. This talk is based on joint work with Neil Lutz.

Dan Turetsky

Title: C.e. equivalence relations and the linear orders they realize

Abstract: Quotient structures are well studied.  In the case of linear orders, it is known that the order-types realized by c.e. quotient structures are precisely those realized by Δ02 linear orders.  We come at this from a different perspective, by considering, for each c.e. equivalence relation, which order-types can be realized as a quotient by that equivalence relation.  We study the relationship between computability-theoretic properties of the equivalence relation and the algebraic properties of the order-types it can realize.  We also define a pre-order on equivalence relations by comparing the collection of order-types realized in each.

Rose Weisshaar

Title: Countable ω-models of KP and paths through computable ω-branching trees

Abstract: It is well known that the Π01 class CPA ⊆ 2ω of completions of Peano arithmetic is universal among nonempty Π01 subsets of Cantor space. When we consider Π01 subsets of Baire space, however, there is no such universal example. In this talk, we consider a Π01 class CKP ⊆ ωω whose paths compute the complete diagrams of countable ω-models of Kripke-Platek set theory (KP). We develop an analogy between how elements of CPA and CKP try to compute members of nonempty Π01 subsets of Cantor space and Baire space, respectively, and we examine how this analogy breaks down. This is joint work with Julia Knight and Dan Turetsky.

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.