Sunday, April 29, 2012
11 am - 4:15 pm
The inaugural New England Recursion and Definability seminar will be held at the University of Connecticut in Storrs, CT. Please RSVP by emailing Reed Solomon, but do not let a lack of RSVP stop you from coming if you decide to at the last minute!
The best place to park is in the North Parking Garage which is right next to MSB (but which costs money) or in the open lot across North Eagleville Road from this garage (which is free if there are spots). After parking, exit the North Garage at the end where you entered with your car. MSB will be directly across the street. To get to MSB 118, you have to take a round-about way since the Math Department offices are locked during the weekend. Cross the street towards MSB but instead of entering the building, walk around the outside of the building to your right. After rounding the corner, there will be an entrance to MSB about 100 yards down on your left. Enter MSB and go up the stairs (or take the elevator) up one floor. When you come out of the stairs (or off the elevator), turn right and go through a door to a short hallway which ends in two seminar rooms. MSB 118 is the seminar room on the right.
|11:00 - 12:00||Marcia Groszek (Dartmouth)|| An open problem in reverse mathematics|
and infinitary combinatorics
|12:15 - 2:00||Lunch and discussion time|
|2:00 - 3:00||Karen Lange (Wellesley)|| Degrees of orderings on torsion-free |
|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 ---> TT^1---> 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.