Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
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
MathSciNet review: 1209095
Full-text PDF Free Access

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?)


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: http://dx.doi.org/10.1090/S0002-9939-1994-1209095-6
PII: S 0002-9939(1994)1209095-6
Keywords: Permutations, presentations, automorphism, recursively enumerable
Article copyright: © Copyright 1994 American Mathematical Society