Permutations and presentations

Cholak, Peter; Downey, Rod

doi:10.1090/S0002-9939-1994-1209095-6

Permutations and presentations
HTML articles powered by AMS MathViewer

by Peter Cholak and Rod Downey PDF

Proc. Amer. Math. Soc. 122 (1994), 1237-1249 Request permission

Abstract:

We say that an automorphism $\Phi$ of ${\mathcal {E}^ \ast }$ (the lattice of recursively enumerable sets modulo the finite sets) is induced by a permutation p iff for all e, $\Phi ({W_e}){ = ^ \ast }p({W_e})$. A permutation h is called a presentation of $\Phi$ iff for all e, $\Phi ({W_e}){ = ^\ast }{W_{h(e)}}$. In this paper, we will explore the degree-theoretic connections between these two notions. Using a new proof of the well-known fact that every automorphism is induced by a permutation p, we show that such a p can be found recursively in $h \oplus \emptyset ''$, where h is a presentation of $\Phi$. The main result of the paper is to show that there is an effective automorphism of ${\mathcal {E}^ \ast }$ which is not induced by a ${\Delta _2}$-permutation.

References

Automorphisms of the lattice of recursively enumerable sets

P. Cholak, R. Downey, and M. Stob, Automorphisms of the lattice of recursively enumerable sets: promptly simple sets, Trans. Amer. Math. Soc. 332 (1992), no. 2, 555–570. MR 1097164, DOI 10.1090/S0002-9947-1992-1097164-6
Leo Harrington and Robert I. Soare, Post’s program and incomplete recursively enumerable sets, Proc. Nat. Acad. Sci. U.S.A. 88 (1991), no. 22, 10242–10246. MR 1133585, DOI 10.1073/pnas.88.22.10242
Wolfgang Maass, Recursively enumerable generic sets, J. Symbolic Logic 47 (1982), no. 4, 809–823 (1983). MR 683156, DOI 10.2307/2273100
Emil L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. 50 (1944), 284–316. MR 10514, DOI 10.1090/S0002-9904-1944-08111-1
Robert I. Soare, Automorphisms of the lattice of recursively enumerable sets. I. Maximal sets, Ann. of Math. (2) 100 (1974), 80–120. MR 360235, DOI 10.2307/1970842
Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921, DOI 10.1007/978-3-662-02460-7