Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

Permutations and presentations


Authors: Peter Cholak and Rod Downey
Journal: Proc. Amer. Math. Soc. 122 (1994), 1237-1249
MSC: Primary 03D25
DOI: https://doi.org/10.1090/S0002-9939-1994-1209095-6
MathSciNet review: 1209095
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [Ch] P. Cholak, Automorphisms of the lattice of recursively enumerable sets, Ph.D. Dissertation, University of Wisconsin, May, 1991.
  • [CDS] P. Cholak, R. Downey, and M. Stob, Automorphisms of the lattice of recursively enumerable sets: Promptly simple sets, Trans. Amer. Math. Soc. 332 (1992), 555-570. MR 1097164 (92j:03039)
  • [HS] L. Harrington and R. Soare, Post's program and incomplete recursively enumerable sets, Proc. Nat. Acad. Sci. U.S.A. 88 (1991), 10242-10246. MR 1133585 (92k:03019)
  • [Ma] W. Maass, Recursively enumerable generic sets, J. Symbolic Logic 49 (1982), 809-823. MR 683156 (84e:03051)
  • [Po] E. Post, Recursively enumerable sets of positive integers and their decision problems, Bull Amer. Math. Soc. 50 (1944), 248-316. MR 0010514 (6:29f)
  • [So1] R. Soare, Automorphisms of the lattice of recursively enumerable sets, Part I: Maximal sets, Ann. of Math. (2) 100 (1974), 80-120. MR 0360235 (50:12685)
  • [So2] -, Recursively enumerable sets and degrees, Perspect. Math. Logic, Springer-Verlag, Berlin, Heidelberg, New York, and Tokyo, 1987. MR 882921 (88m:03003)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 03D25

Retrieve articles in all journals with MSC: 03D25


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1994-1209095-6
Keywords: Permutations, presentations, automorphism, recursively enumerable
Article copyright: © Copyright 1994 American Mathematical Society

American Mathematical Society