Some reductions between theorems around ATR
Speaker:
Jun Le Goh, Cornell University
Date and Time:
Monday, June 4, 2018 - 11:00am to 11:20am
Location:
University of Waterloo - MC 5501
Abstract:
We study theorems with reverse mathematical strength around ATR from the point of view of computability-theoretic reducibilities. Consider the ATR-like problem of producing the jump hierarchy on a given well-ordering. Consider also its "two-sided" version: given a linear ordering $L$, produce either a jump hierarchy on $L$ or an infinite $L$-descending sequence. We present reductions between these problems and weak comparability of well-orderings, the restriction of Fraïssé's conjecture to well-orderings, and König's duality theorem. In particular, we answer a question of Marcone by showing that comparability of well-orderings is Weihrauch equivalent to its weak version.