# UConn Logo University of Connecticut UC Title Fallback

UConn Logic Group / Department of Mathematics / CLAS

# New England Recursion and Definability Seminar

## NERDS 1.0

### Overview

Date: Sunday, April 29, 2012
Time: 11 am-4:15 pm
Place: Mathematical Sciences Building (MSB) 118, University of Connecticut

### Schedule

 11:00–12:00 Marcia Groszek (Dartmouth College) An open problem in reverse mathematics and infinitary combinatorics 12:15–2:00 Lunch and discussion time 2:00–3:00 Karen Lange (Wellesley College) Degrees of orderings on torsion-free abelian groups 3:15–4:15 Johanna Franklin (University of Connecticut) Degrees which are low for isomorphism

### Abstracts

#### Marcia Groszek

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

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

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.