×

Turing computable embeddings. (English) Zbl 1123.03026

Summary: In [W. Calvert, D. Cummins, J. F. Knight and S. Miller, “Comparing classes of finite structures”, Algebra Logic 43, No. 6, 374–392 (2004; Zbl 1097.03026)], two different effective versions of Borel embedding are defined. The first, called computable embedding, is based on uniform enumeration reducibility, while the second, called Turing computable embedding, is based on uniform Turing reducibility. While [loc. cit.] focused mainly on computable embeddings, the present paper considers Turing computable embeddings. Although the two notions are not equivalent, we can show that they behave alike on the mathematically interesting classes chosen for investigation in [loc. cit.]. We give a “Pull-back Theorem”, saying that if \(\Phi\) is a Turing computable embedding of \(K\) into \(K'\), then for any computable infinitary sentence \(\varphi\) in the language of \(K'\), we can find a computable infinitary sentence \(\varphi^*\) in the language of \(K\) such that for all \({\mathcal A}\in K\), \({\mathcal A} \models\varphi^*\) iff \(\Phi({\mathcal A})\models\varphi\), and \(\varphi^*\) has the same “complexity” as \(\varphi\) (i.e., if \(\varphi\) is computable \(\Sigma_\alpha\), or computable \(\Pi_\alpha\), for \(\alpha\geq 1\), then so is \(\varphi^*)\). The Pull-back Theorem is useful in proving non-embeddability, and it has other applications as well.

MSC:

03C57 Computable structure theory, computable model theory

Citations:

Zbl 1097.03026
PDF BibTeX XML Cite
Full Text: DOI Euclid

References:

[1] Transactions of the American Mathematical Society 353 pp 491–518– (2001)
[2] Algebra and Logic 43 pp 365–373– (2004)
[3] Essential Stability Theory (1996) · Zbl 0864.03025
[4] Computable Structures and the Hyperarithmetical Hierarchy 144 (2000) · Zbl 0960.03001
[5] Solution to a problem on computable embeddings 72 pp 1031–1040– (2007)
[6] Model Theory: An Introduction (2002) · Zbl 1003.03034
[7] Fundament a Mathematicae 175 pp 241–257– (2002)
[8] Fundamenta Mathematicae 170 pp 21–52– (2001)
[9] A Borel reducibility theory for classes of countable structures 54 pp 894–914– (1989) · Zbl 0692.03022
[10] Fundamenta Mathematicae · Zbl 0017.15601
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.