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 of (the lattice of recursively enumerable sets modulo the finite sets) is *induced* by a permutation *p* iff for all *e*, . A permutation *h* is called a *presentation* of iff for all *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 , where *h* is a presentation of . The main result of the paper is to show that there is an effective automorphism of which is not induced by a -permutation.

**[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)**

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