BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
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 {ω⋅2,ω⋆⋅2} is computably embeddable in {ω2,(ω2)⋆}, the class {ω⋅k,ω⋆⋅k} is \emph{not} computably embeddable in {ω2,(ω2)⋆} for any natural number k≥3.
There is a Turing computable embedding Φ of directed graphs A in undirected graphs. Moreover, there is a fixed tuple of formulas that give a uniform interpretation; i.e., for all directed graphs A, these formulas interpret A in Φ(G). It follows that A is Medvedev reducible to Φ(A) uniformly; i.e., there is a fixed Turing operator that serves for all A. We observe that there is a graph G that is not Medvedev reducible to any linear ordering. Hence, G is not effectively interpreted in any linear ordering. Similarly, there is a graph that is not interpreted in any linear ordering using computable Σ2 formulas. Any graph can be interpreted in a linear ordering using computable Σ3 formulas. Friedman and Stanley gave a Turing computable embedding L of directed graphs in linear orderings. We show that there is no fixed tuple of Lω1,ω formulas that, for all G, interpret the input graph G in the output linear ordering L(G). Harrison-Trainor and Montalbán have also shown this, by a quite different proof.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.