A Note on Computable Embeddings for Ordinals and Their Reverses

We continue the study of computable embeddings for pairs of structures, i.e. for classes containing precisely two non-isomorphic structures. Surprisingly, even for some pairs of simple linear orders, computable embeddings induce a non-trivial degree structure. Our main result shows that although [Fo...

Descripción completa

Detalles Bibliográficos
Autores principales: Bazhenov, Nikolay, Vatev, Stefan
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2020
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7309500/
http://dx.doi.org/10.1007/978-3-030-51466-2_1
_version_ 1783549219870605312
author Bazhenov, Nikolay
Vatev, Stefan
author_facet Bazhenov, Nikolay
Vatev, Stefan
author_sort Bazhenov, Nikolay
collection PubMed
description We continue the study of computable embeddings for pairs of structures, i.e. for classes containing precisely two non-isomorphic structures. Surprisingly, even for some pairs of simple linear orders, computable embeddings induce a non-trivial degree structure. Our main result shows that although [Formula: see text] is computably embeddable in [Formula: see text], the class [Formula: see text] is not computably embeddable in [Formula: see text] for any natural number [Formula: see text].
format Online
Article
Text
id pubmed-7309500
institution National Center for Biotechnology Information
language English
publishDate 2020
record_format MEDLINE/PubMed
spelling pubmed-73095002020-06-23 A Note on Computable Embeddings for Ordinals and Their Reverses Bazhenov, Nikolay Vatev, Stefan Beyond the Horizon of Computability Article We continue the study of computable embeddings for pairs of structures, i.e. for classes containing precisely two non-isomorphic structures. Surprisingly, even for some pairs of simple linear orders, computable embeddings induce a non-trivial degree structure. Our main result shows that although [Formula: see text] is computably embeddable in [Formula: see text], the class [Formula: see text] is not computably embeddable in [Formula: see text] for any natural number [Formula: see text]. 2020-06-24 /pmc/articles/PMC7309500/ http://dx.doi.org/10.1007/978-3-030-51466-2_1 Text en © Springer Nature Switzerland AG 2020 This article is made available via the PMC Open Access Subset for unrestricted research re-use and secondary analysis in any form or by any means with acknowledgement of the original source. These permissions are granted for the duration of the World Health Organization (WHO) declaration of COVID-19 as a global pandemic.
spellingShingle Article
Bazhenov, Nikolay
Vatev, Stefan
A Note on Computable Embeddings for Ordinals and Their Reverses
title A Note on Computable Embeddings for Ordinals and Their Reverses
title_full A Note on Computable Embeddings for Ordinals and Their Reverses
title_fullStr A Note on Computable Embeddings for Ordinals and Their Reverses
title_full_unstemmed A Note on Computable Embeddings for Ordinals and Their Reverses
title_short A Note on Computable Embeddings for Ordinals and Their Reverses
title_sort note on computable embeddings for ordinals and their reverses
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7309500/
http://dx.doi.org/10.1007/978-3-030-51466-2_1
work_keys_str_mv AT bazhenovnikolay anoteoncomputableembeddingsforordinalsandtheirreverses
AT vatevstefan anoteoncomputableembeddingsforordinalsandtheirreverses
AT bazhenovnikolay noteoncomputableembeddingsforordinalsandtheirreverses
AT vatevstefan noteoncomputableembeddingsforordinalsandtheirreverses

Ejemplares similares