A Note on Computable Embeddings for Ordinals and Their Reverses

Nikolay Bazhenov, Stefan Vatev

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Abstract

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 is computably embeddable in, the class is not computably embeddable in for any natural number.

Original languageEnglish
Title of host publicationBeyond the Horizon of Computability - 16th Conference on Computability in Europe, CiE 2020, Proceedings
EditorsMarcella Anselmo, Gianluca Della Vedova, Florin Manea, Arno Pauly
PublisherSpringer Gabler
Pages1-13
Number of pages13
ISBN (Print)9783030514655
DOIs
Publication statusPublished - 1 Jul 2020
Event16th Conference on Computability in Europe, CiE 2020 - Fisciano, Italy
Duration: 29 Jun 20203 Jul 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12098 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference16th Conference on Computability in Europe, CiE 2020
CountryItaly
CityFisciano
Period29.06.202003.07.2020

Keywords

  • Computable embedding
  • Enumeration operator
  • Linear order

Fingerprint

Dive into the research topics of 'A Note on Computable Embeddings for Ordinals and Their Reverses'. Together they form a unique fingerprint.

Cite this