Максимальный набор
В теории рекурсии , математической теории вычислимости , максимальное множество — это коконечное рекурсивно перечислимое подмножество 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 , Second Series, 100 (1), Annals of Mathematics: 80–120, doi : 10.2307/1970842 , JSTOR 1970842 , MR 0360235
 | Эта математической логике статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее . |