×

Definable encodings in the computably enumerable sets. (English) Zbl 0977.03022

In this paper, the authors announce some recent results on the computably enumerable (c.e.) sets. One set of results involves invariant classes and another set involves automorphisms of the c.e. sets. The proof of these results uses a new form of definable coding for the c.e. sets. One very interesting theorem is that \(\text{high}_n\) \((\overline{\text{low}_n})\) c.e. degrees are invariant for all \(n\geq 2\). This theorem solves the long standing Martin Invariance Conjecture; the conjecture is not true. Another interesting result about automorphisms of the c.e. sets is that any two hhsimple sets \(H_1\) and \(H_2\) are automorphic iff they are \(\Delta_3^0\)-automorphic iff \({\mathcal L}^*(H_1) \simeq _{\Delta_3^0} {\mathcal L}^*(H_2)\). This result completely characterizes when two hhsimple sets are automorphic.

MSC:

03D25 Recursively (computably) enumerable sets and degrees

References:

[1] Degrees of classes of recursively enumerable sets 41 pp 695– (1976)
[2] DOI: 10.2307/1970842 · Zbl 0253.02040 · doi:10.2307/1970842
[3] DOI: 10.1002/malq.19660120125 · Zbl 0181.30504 · doi:10.1002/malq.19660120125
[4] Definability, automorphisms, and dynamic properties of computably enumerable sets 2 pp 199– (1996)
[5] DOI: 10.1006/aima.1997.1687 · Zbl 0890.03016 · doi:10.1006/aima.1997.1687
[6] DOI: 10.1016/0168-0072(96)83748-1 · Zbl 0858.03043 · doi:10.1016/0168-0072(96)83748-1
[7] Memoirs of the American Mathematical Society 113 pp 151– (1995)
[8] DOI: 10.1007/BF02760850 · Zbl 0469.03026 · doi:10.1007/BF02760850
[9] On the orbit of hyperhypersimple sets 49 pp 51– (1984)
[10] DOI: 10.1090/S0002-9947-1983-0704618-2 · doi:10.1090/S0002-9947-1983-0704618-2
[11] DOI: 10.2140/pjm.1980.87.135 · Zbl 0467.03040 · doi:10.2140/pjm.1980.87.135
[12] DOI: 10.1007/BF02761377 · Zbl 0384.03025 · doi:10.1007/BF02761377
[13] DOI: 10.1090/S0002-9947-1968-0227009-1 · doi:10.1090/S0002-9947-1968-0227009-1
[14] Degrees of recursively enumerable sets which have no maximal supersets 33 pp 431– (1968) · Zbl 0197.00502
[15] Logic, methodology and philosophy of science, VIII pp 179– (1989)
[16] Frege conference pp 66– (1984)
[17] DOI: 10.1090/S0894-0347-96-00181-6 · Zbl 0862.03025 · doi:10.1090/S0894-0347-96-00181-6
[18] Recursively enumerable sets and degrees (1987)
[19] Handbook of Boolean algebras 3 pp 1097– (1989)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.