Максимальный набор
В теории рекурсии , математической теории вычислимости , максимальное множество — это коконечное рекурсивно перечислимое подмножество A натуральных чисел, такое, что для каждого дальнейшего рекурсивно перечислимого подмножества B натуральных чисел, либо B коконечно , либо B является конечным вариантом A , либо B не является надмножеством A. Это дает простое определение в решетке рекурсивно перечислимых множеств.
Максимальные множества обладают многими интересными свойствами: они простые , гиперпростые , гипергиперпростые и r-максимальные; последнее свойство говорит, что каждое рекурсивное множество R содержит либо только конечное число элементов дополнения A , либо почти все элементы дополнения A. Существуют r-максимальные множества, которые не являются максимальными; некоторые из них даже не имеют максимальных супермножеств. Майхилл (1956) задался вопросом, существуют ли максимальные множества, и Фридберг (1958) построил одно. Соаре (1974) показал, что максимальные множества образуют орбиту относительно автоморфизма рекурсивно перечислимых множеств по включению ( по модулю конечных множеств). С одной стороны, каждый автоморфизм отображает максимальное множество A в другое максимальное множество B ; с другой стороны, для каждых двух максимальных множеств A , B существует автоморфизм рекурсивно перечислимых множеств такой, что A отображается в B.
Ссылки
- Фридберг, Ричард М. (1958), «Три теоремы о рекурсивном перечислении. I. Разложение. II. Максимальное множество. III. Перечисление без дублирования», Журнал символической логики , 23 (3), Ассоциация символической логики: 309–316, doi : 10.2307/2964290, JSTOR 2964290, MR 0109125, S2CID 25834814
- Майхилл, Джон (1956), «Решение проблемы Тарского», Журнал символической логики , 21 (1), Ассоциация символической логики: 49–51, doi : 10.2307/2268485, JSTOR 2268485, MR 0075894, S2CID 19695459
- Х. Роджерс-младший, 1967. Теория рекурсивных функций и эффективная вычислимость , второе издание 1987, MIT Press. ISBN 0-262-68052-1 (мягкая обложка), ISBN 0-07-053522-1 .
- Соаре, Роберт И. (1974), «Автоморфизмы решетки рекурсивно перечислимых множеств. I. Максимальные множества», Annals of Mathematics , Вторая серия, 100 (1), Annals of Mathematics: 80–120, doi :10.2307/1970842, JSTOR 1970842, MR 0360235
 | Эта статья, связанная с математической логикой, является заглушкой . Вы можете помочь Википедии, расширив ее. |
