Overview

Date: Sunday, November 4, 2018
Time: 10am-4pm
Place: Springfield College (Visitor information)

Travel support

Travel support is available for graduate students. Please contact Russell Miller for details.

Schedule

10:30-10:50am	Coffee and pastries	Locklin Hall, Room 232
10:50-11:50	Damir Dzhafarov (University of Connecticut)	Locklin Hall, Room 232
12-12:30	Iva Bilanovic (George Washington University)	Locklin Hall, Room 232
12:30-2	Lunch	Cheney Dining Hall
2-2:30	Zak Evans (Dartmouth College)	Locklin Hall, Room 232
2:40-3:10	Noah Hughes (University of Connecticut)	Locklin Hall, Room 232
3:20-4:20	Karen Lange (Wellesley College)	Locklin Hall, Room 232

Abstracts

Damir Dzhafarov

The uniform content of partial and linear orders

The principle ADS asserts that every linear order on omega has an infinite ascending or descending sequence. This has been studied extensively in the reverse mathematics literature, beginning with the work of Hirschfeldt and Shore. We look at these principles under Weihrauch (uniform) reducibility. For instance, we introduce the principle ADC, which asserts that every such linear order has an infinite ascending or descending chain. This is easily seen to be equivalent to ADS over RCA_0 (even computably equivalent) but we show that ADC is strictly weaker than ADS under Weihrauch reducibility. In fact, we show that even the principle SADS, which is the restriction of ADS to linear orders of type omega + omega^*, is not Weihrauch reducible to ADC. In this connection, we define a more natural stable form of ADS that we call General-SADS, which is the restriction of ADS to linear orders of type k+ω, omega+omega^*, or omega+k, where k is a finite number. We define General-SADC analogously. We prove that General-SADC is not Weihrauch reducible to SADS, and so in particular, each of SADS and SADC is strictly weaker under Weihrauch reducibility than its general version. Finally, we turn to the principle CAC, which asserts that every partial order on ω has an infinite chain or antichain. This has two previously studied stable variants, SCAC and WSCAC, which were introduced by Hirschfeldt and Jockusch, and by Jockusch, Kastermans, Lempp, Lerman, and Solomon, respectively, and which are known to be equivalent over RCA0. Here, we show that SCAC is strictly weaker than WSCAC under even computable reducibility. This is joint work with Astor, Solomon, and Suggs.

Iva Bilanovic

Detecting Properties of Groups

In the 1950s, Adian and Rabin showed that a Markov property is undecidable for the class of finitely presented groups. We explore the analogous questions in the class of recursively presented groups and in the class of computable groups. First, we give a lower bound for the difficulty of detecting an arbitrary Markov property in each class. Then we consider various properties of higher complexity, for example, being cyclic.

Noah Hughes (University of Connecticut)

Generalizations of Hall’s theorem in reverse mathematics

Philip Hall’s theorem gives necessary and sufficient conditions for the existence of a matching on a bipartite graph. In this talk, I will survey some prior work on the reverse mathematics of this principle by Jeff Hirst, and Hirst and Hughes. I will then present some work in progress concerning the reverse mathematics of several generalizations of Hall’s theorem.

Karen Lange

Dynamic and structural properties of the computably enumerable sets

Friedberg and Muchnik famously constructed computably enumerable sets of whole numbers that are noncomputable but do not code the halting set. To build their examples, they independently developed the priority method, a dynamic and flexible construction framework. Harrington and Soare showed that one can identify such examples using only the structure of the collection E of computably enumerable (c.e.) sets under set containment. In other words, they gave a (nonempty) property Q in terms of set containment that is satisfied in E by only incomplete noncomputable c.e. sets. All c.e. sets that satisfy Q have a slow enumeration property called 2-tardiness. We explore n-tardiness, as a means to further understand the interplay between dynamic enumeration properties of c.e. sets and static structural properties of E. We also discuss the structure of D-maximal sets, generalizations of both maximal and hemimaximal sets in E. We use both tardiness and D-maximality to further develop the picture of orbits of sets under automorphisms of E.

Zak Evans

To be announced.