Date: Sunday, April 29, 2012
Time: 11 am-4:15 pm
Place: Mathematical Sciences Building (MSB) 118, University of Connecticut
|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|
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.
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.
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.