Maximal set
In
cofinite or B is a finite variant of A or B is not a superset of A. This gives an easy definition within the lattice
of the recursively enumerable sets.
Maximal sets have many interesting properties: they are
modulo
finite sets). On the one hand, every automorphism maps a maximal set A to another maximal set B; on the other hand, for every two maximal sets A, B there is an automorphism of the recursively enumerable sets such that A is mapped to B.
References
- Friedberg, Richard M. (1958), "Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication", The Journal of Symbolic Logic, 23 (3), Association for Symbolic Logic: 309–316, S2CID 25834814
- Myhill, John (1956), "Solution of a problem of Tarski", The Journal of Symbolic Logic, 21 (1), Association for Symbolic Logic: 49–51, S2CID 19695459
- H. Rogers, Jr., 1967. The Theory of Recursive Functions and Effective Computability, second edition 1987, MIT Press. ISBN 0-07-053522-1.
- Soare, Robert I. (1974), "Automorphisms of the lattice of recursively enumerable sets. I. Maximal sets", MR 0360235
 | This mathematical logic-related article is a stub. You can help Wikipedia by expanding it. |