Overview

Date: Saturday, May 30, 2020
Time: Starting at 12pm (EST)
Place: Online video conference (hosted by Johanna Franklin, Hofstra University)

Schedule

(All times in EST time zone.)

12pm	General social time if anyone wants to log in early
1pm	Wesley Calvert (Southern Illinois University)	Degrees High for Isomorphism (Slides)
1:50pm	Break
2:15pm	Dino Rossegger (University of Waterloo)	Analytic equivalence relations and their degree spectra (Slides)
2:35pm	Break
3pm	Henry Towsner (University of Pennsylvania)	Borel combinatorics goes wrong in HYP (Slides)
3:50pm	General social time

Abstracts

Wesley Calvert

Degrees High for Isomorphism

For some structures, called computably categorical, any two computable isomorphic copies are isomorphic by a computable isomorphism. For other structures, of course, a higher oracle is needed to compute the isomorphisms. We aim to characterize the degrees that we call “high for isomorphism” — the degrees relative to which every computable structure is computably categorical.

Dino Rossegger

Analytic Equivalence Relations and Their Degree Spectra

A well known result in descriptive set theory by Louveau and Rosendal shows that the bi-embeddability relation on the class of graphs is a $$\mathbf{\Sigma}^1_1$$-complete equivalence relation with respect to Borel reducibility. We give a Borel reduction from bi-embeddability on graphs to elementary bi-embeddability on graphs and thus obtain that elementary bi-embeddability on graphs is also $$\mathbf{\Sigma}^1_1$$-complete. An analysis of this reduction shows that it is computable and that it is faithful on equivalence classes. Using these facts and the concept of the jump of a structure we show that every bi-embeddability spectrum of a graph is the elementary bi-embeddability spectrum of a graph.

Henry Towsner

Borel combinatorics goes wrong in HYP

It is generally understood that, within Reverse Mathematics, questions involving Borel sets generally require the theory ATR0 as a base theory, since proving that codes for Borel sets have the basic properties we would expect already requires ATR0. In particular, ATR0 is needed to ensure the existence of the “evaluation maps” which are used to determine whether or not a set X belongs to the Borel set coded by a Borel code C. Recently, Astor-Dzhafarov-Montalbán-Solomon-Westrick suggested a way around this difficulty, but restricting consideration to “completely determined Borel codes”: those codes for which evaluation maps always happen to exist. They introduced a “decorated trees” construction in order to build completely determined Borel codes which nonetheless fail to have the property of Baire.

Here we use this technique in HYP, the model of hyperarithmetic sets, to build a variety of Borel codes which are completely determined but otherwise anomalous, including: a Borel well-ordering of the universe, Borel 2-colorings of any connected acyclic graph, and a counterexample to the Borel Dual Ramsey Theorem.

This is joint work in progress with Rose Weisshaar and Linda Brown Westrick.