Overview

Date: Sunday, November 8, 2020
Time: Starting at 12:45pm (EST)
Place: Wellesley College (online)

Schedule

(All times in EST time zone.)

12:45pm	General social time if anyone wants to log in early
1pm	James Walsh (Cornell University)	Dilators and omega-model reflection
1:50pm	Break
2:05pm	Justin Miller (University of Notre Dame)	Noncomputable Coding, Density, and Stochasticity
2:30pm	Break
2:55pm	Shelley Stahl (Bridgewater State University)	Dominating Orders on Infinite Graphs
3:20pm	General social time
3:35pm	Peter Gerdes (Oakland University)	Is Every Properly n-REA Degree Extendable?

Abstracts

James Walsh (Cornell University)

Dilators and omega-model reflection

Two types of principles are commonly called “reflection principles” in reverse mathematics. According to syntactic reflection principles for T, every theorem of T (from some complexity class) is true. According to semantic reflection principles, every set belongs to some (sufficiently correct) model of T. We will present a connection between syntactic reflection and semantic reflection in second-order arithmetic: for any Pi^1_2 axiomatized theory T, every set is contained in an omega model of T if and only if every iteration of Pi^1_1 reflection for T along a well-ordering is Pi^1_1 sound. There is a thorough proof-theoretic understanding of the latter in terms of ordinal analysis. Accordingly, these reductions yield proof-theoretic analyses of omega-model reflection principles. This is joint work with Fedor Pakhomov.

Justin Miller (University of Notre Dame)

Noncomputable Coding, Density, and Stochasticity

We introduce the into and within set operations in order to construct sets of arbitrary intrinsic density from any Martin-Löf random. We then show that these operations are useful more generally for working with other notions of density as well, in particular for viewing Church and MWC stochasticity as a form of density.

Shelley Stahl (Bridgewater State University)

Dominating Orders on Infinite Graphs

This project is inspired by an open question regarding the game of Cops and Robbers on Graphs. A finite graph G is cop-win if and only if G is dismantlable, which for finite graphs is a property that is equivalent to the property of being constructible (that is, having a dominating order). However, these equivalences all fail for infinite graphs. This has led to interesting questions around the complexity of a dominating order for an infinite graph, if one exists, and whether the property of being weakly cop-win implies the existence of a dominating order. We address these topics in this talk from a computability perspective.

Peter Gerdes

Is Every Properly n-REA Degree Extendable

A result of Soare and Stob tells us that if A is a non-computable r.e. set then we can extend A to a properly 2-REA set $A \oplus W^A_i$, i.e., a 2-REA set not Turing equivalent to any 1-REA set. Later work by Cholak and Hinman extends this result to show that, although no uniform solution is possible, if A is a properly 2-REA set it can be extended to a properly 3-REA set $A \oplus W^A_i$. We briefly reprise Cholak and Hinman’s result before considering the natural hypothesis: can every properly n-REA set be extended to a properly (n+1)-REA set? We give a negative answer to this question and show that Cholak and Hinman’s result is optimal by constructing a properly 3-REA set A such that for all $i$, $A \oplus W^A_i$ is of 3-REA degree. While $A$ is constructed via a straightforward finite injury argument meeting individual requirements depends on satisfying a combinatorial property which itself requires an interesting priority argument. (This result is the product of joint work with Peter Cholak)