Overview

Date: Sunday, April 29, 2012
Place: University of Connecticut

Schedule

11am	Marcia Groszek (Dartmouth College)
12:15pm	Lunch
2:00pm	Karen Lange (Wellesley College)
3:15pm	Johanna Franklin (University of Connecticut)

Abstracts

Marcia Groszek (Dartmouth College)

An open problem in reverse mathematics and infinitary combinatorics

The complete binary tree $T$, viewed as a partial ordering, satisfies the following partition property for any finite $k$: If the nodes of $T$ are colored in $k$-many colors, then there is a monochromatic subordering isomorphic to $T$. Chubb, Hirst, and McNicholl call this principle $TT^1_k$. We will use $TT^1$ to refer to the principle: $TT^1_k$ holds for all finite $k$. Chubb, Hirst, and McNicholl showed that, over the usual base theory $RCA_0$, $I\Sigma^0_2 \implies TT^1 \implies B\Sigma^0_2$, and posed the question: What is the precise proof-theoretic strength of $TT^1$? Corduan, Groszek, and Mileti showed that the right hand arrow above cannot be reversed: $B\Sigma^0_2$ does not imply $TT^1$. This separates $TT^1$ from Ramsey’s Theorem for $1$-tuples (the pigeonhole principle), which Hirst has shown is equivalent to $B\Sigma_0^2$. This is in contrast to the situation for triples and above, where the standard Ramsey’s Theorem and the binary tree version are equivalent. The precise proof-theoretic strength of $TT^1$ remains unknown.

Karen Lange (Wellesley College)

Degrees of orderings on torsion-free abelian groups

It is well known that an abelian group admits an ordering if and only if it is torsion-free. This classical statement is false, however, from a computable perspective. Downey and Kurtz (1986) showed that there is a computable torsion-free abelian group that admits no computable ordering. We look at generalizations of this result by examining the collections of orderings $X(G)$ on a given computable torsion-free abelian group $G$. Specifically, we are interested in the degree spectrum of $X(G)$, i.e., the set of degrees of orderings of $G$. One way to construct orderings is to use a basis for $G$, and this relationship between bases and orderings has consequences for the degree spectrum of $X(G)$. Given these consequences, it is natural to ask whether the degree spectra of orderings on computable torsion-free abelian groups are closed upward. In joint work with Kach and Solomon, we show the answer is no.

Johanna Franklin (University of Connecticut)

Degrees which are low for isomorphism

Lowness is a common theme in recursion theory. The most familiar definitions of lowness is that a set of natural numbers is low if its jump is as computationally weak as possible, but it is also useful in the study of algorithmic randomness. I will present a lowness notion based in recursive model theory: lowness for isomorphism. We say that a degree is low for isomorphism if whenever it can compute an isomorphism between two computable structures, there is already a computable isomorphism between them. I will present some results in this area from an ongoing project with Ted Slaman and Reed Solomon.