Overview
Date: Sunday April 30, 2017
Time: 10am-3:20pm
Place: Dartmouth College, Kemeny Hall, Room 105 (Directions).
The 11th installment of the New England Recursion and Definability Seminar (NERDS) will be a joint meeting of the Mid Atlantic Mathematical Logic Seminar (MAMLS).
Travel funding is available through the NSF, via MAMLS. Please contact Brooke Andersen if you like to apply for it. Thank you to Arthur Apter for making this support available
Schedule
(All times in EST time zone.)
| 10:00-10:30 | Coffee (Kemeny Hall, Room 300) |
| 10:30-11:30 | Theodore Slaman (UC Berkeley) |
| 11:40-12:10 | Rose Weisshaar (University of Notre Dame) |
| 12:10-1:40 | Lunch (in Kemeny Hall) |
| 1:40-2:40 | Noah Schweber (University of Wisconsin) |
| 2:50-3:20 | Seth Harris (Dartmouth College/Drew University) |
Abstracts
Theodore Slaman
Irrationality Exponents and Effective Hausdorff Dimension
With will discuss joint work with Veronica Becher and Jan Reimann. We generalize the classical theorem by Jarnik and Besicovitch on the irrationality exponents of real numbers and Hausdorff dimension. Let a be any real number greater than or equal to 2 and let b be any non-negative real less than or equal to 2/a. We show that there is a Cantor-like set with Hausdorff dimension equal to b such that, with respect to its uniform measure, almost all real numbers have irrationality exponent equal to a. We give an analogous result relating the irrationality exponent and the effective Hausdorff dimension of individual real numbers. We prove that there is a Cantor-like set such that, with respect to its uniform measure, almost all elements in the set have effective Hausdorff dimension equal to b and irrationality exponent equal to a. In each case, we obtain the desired set as a distinguished path in a tree of Cantor sets.
Rose Weisshaar
Forcing partial orders comparable to the Mathias and Cohen forcing partial orders
Cholak, Dzhafarov, Hirst and Slaman showed that, for $n \geq 3$, every Mathias $n$-generic computes a Cohen $n$-generic. In some sense, then, the forcing partial order associated to Mathias forcing is stronger than that associated to Cohen forcing. Motivated by this idea, we define a collection $\mathcal{C}$ of {\it Cohen-Mathias-like} forcing partial orders $(\mathbb{P}, \leq)$ and say that $\mathbb{P} \leq_{\mathcal{C}} \mathbb{Q}$ ($\mathbb{Q}$ is stronger than $\mathbb{P}$) if, for all $n$, there is an $m$ such that every $m$-generic for $\mathbb{Q}$ computes an $n$-generic for $\mathbb{P}$. There are partial orders $\mathbb{P}_{Cohen}$ and $\mathbb{P}_{Mathias}$ in $\mathcal{C}$ whose $n$-generics are exactly the traditional Cohen and Mathias $n$-generics, respectively. The translation of Cholak, Dzhafarov, Hirst and Slaman’s result in this setting is that $\mathbb{P}_{Cohen} \leq_{\mathcal{C}} \mathbb{P}$ for every $\mathbb{P} \in \mathcal{C}$. We also show, using methods from Cholak, Dzhafarov and Soskova, that $\mathbb{P} \leq_{\mathcal{C}} \mathbb{P}_{Mathias}$ for every $\mathbb{P} \in \mathcal{C}$, and discuss some other partial orders that lie on top of $\mathcal{C}$.
Noah Schweber
Some $\Pi^0_1$ sets in higher recursion theory
In this talk we’ll look at some examples – in the context of $\alpha$-recursion theory, for appropriate $\alpha$ – of natural $\Pi^0_1$ sets which are of maximal Turing degree, but are not complete among $\Pi^0_1$ sets for many-one reducibility. We’ll see that these sets rely crucially on facts about higher recursion theory with no analogues in the classical setting – in particular, the existence of *strong true stages*, ordinals $\beta$ such that every halting computation with index $<\beta$ on input $<\beta$ halts in time $<\beta$. At the end we'll say a bit about what kinds of strong true stages we *can* have in classical recursion theory.
The talk gives an overview and ends with open questions (of which there remain many).
Seth Harris
On-Line Algorithms and Reverse Mathematics
Consider a two-player game (played by Alice and Bob) in which Alice asks a sequence (a) and Bob responds with a sequence (b) with no knowledge of Alice’s future requests. A problem P is solvable by an on-line algorithm if Bob has a winning strategy in this game, where Bob wins the game if (\bar{a}, \bar{b}) constitutes a solution to P. For example, if we take P to be a graph coloring problem, Alice plays by adding a new vertex and edges connecting it to previous vertices; Bob chooses a color for that vertex. The graph is on-line colorable if Bob has a winning strategy in this game.
Given a problem P, the corresponding sequential problem SeqP asserts the existence of an infinite sequence of solutions to P.
We will show that the reverse-mathematical strength of SeqP is directly related to the on-line solvability of P, and we will exactly characterize which sequential problems are solvable in RCA_0, WKL_0, and ACA_0. This is joint work with François Dorais.