Embeddings between well-orderings: computability-theoretic reductions
type: Item
instance of: scholarly article
title: Embeddings between well-orderings: computability-theoretic reductions
zbMATH Open document ID: 1479.03008
author: Jun Le Goh
published in: Annals of Pure and Applied Logic
publication date: 2020-04-14T00:00:00Z
review text: For any two well-orders, one always embeds into the other. In fact, for any two well-orders, one is always isomorphic to an initial segment of the other. When considering countable well-orders in subsystems of second-order arithmetic, both of these facts are equivalent to the system of arithmetical transfinite recursion over the base system of recursive comprehension [\textit{S. G. Simpson}; Subsystems of second order arithmetic. Cambridge: Cambridge University Press; Urbana, IL: Association for Symbolic Logic (ASL) (2009; Zbl 1181.03001); \textit{H. M. Friedman} and \textit{J. L. Hirst}; Ann. Pure Appl. Logic 47, No. 1, 11--29 (1990; Zbl 0706.03044)]. The present work analyzes the complexity of producing embeddings between countable well-orders from the perspective of the Weihrauch degrees. Think of a mathematical problem as consisting of a collection of instances and, for each instance, an associated collection of solutions to that instance. In order to apply the methods of computability theory, restrict to problems where all instances and solutions are countable mathematical objects, such as countable well-orders and embeddings between countable well-orders. One such problem \(\mathsf{P}\) Weihrauch reduces to another such problem \(\mathsf{Q}\) (written \(\mathsf{P} \leq_W \mathsf{Q}\)) if there is a uniformly computable procedure for using problem \(\mathsf{Q}\) to solve problem \(\mathsf{P}\). Specifically, \(\mathsf{P} \leq_W \mathsf{Q}\) if there are Turing machines \(\Phi\) and \(\Psi\) such that \(\Phi\) encodes \(\mathsf{P}\)-instances into \(\mathsf{Q}\)-instances and \(\Psi\) decodes \(\mathsf{Q}\)-solutions into \(\mathsf{P}\)-solutions. This means that \(\Phi(I)\) is a \(\mathsf{Q}\)-instance whenever \(I\) is a \(\mathsf{P}\)-instance, and \(\Psi(I, S)\) is a \(\mathsf{P}\)-solution to the \(\mathsf{P}\)-instance \(I\) whenever \(S\) is a \(\mathsf{Q}\)-solution to the \(\mathsf{Q}\)-instance \(\Phi(I)\). Two problems \(\mathsf{P}\) and \(\mathsf{Q}\…
reviewed by: Paul Shafer
Mathematics Subject Classification ID: 03B30
Mathematics Subject Classification ID: 03D30
Mathematics Subject Classification ID: 03D80
Mathematics Subject Classification ID: 03F35
Mathematics Subject Classification ID: 03D55
zbMATH DE Number: 7189161
zbMATH Keywords: arithmetical transfinite recursion
zbMATH Keywords: Weihrauch reducibility
zbMATH Keywords: Fraïssé's conjecture
zbMATH Keywords: reverse mathematics
MaRDI profile type: Publication
full work available at URL: j.apal.2020.102789
OpenAlex ID: W3006530830
cites work: The uniform content of partial and linear orders
cites work: The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma
cites work: The Vitali Covering Theorem in the Weihrauch Lattice
cites work: On the algebraic structure of Weihrauch degrees
cites work: Recursive well-founded orderings
cites work: On uniform relationships between combinatorial problems
cites work: Cohesive avoidance and strong reductions
cites work: Weak comparability of well orderings and reverse mathematics
cites work: Ranked structures and arithmetic transfinite recursion
cites work: Countable retracing functions and \(\Pi_2^0\) predicates
cites work: SEARCHING FOR AN ANALOGUE OF ATR0 IN THE WEIHRAUCH LATTICE
cites work: On Fraissé's order type conjecture
cites work: Fraïssé’s conjecture in Π11-comprehension
cites work: Computability on the Countable Ordinals and the Hausdorff-Kuratowski Theorem (Extended Abstract)
cites work: Q4040890
cites work: Q4764120
cites work: Q3395521
DOI: 10.1016/J.APAL.2020.102789
description: scientific article; zbMATH DE number 7189161