Войти
В теории рекурсии, то математическая теория вычислимости, А максимальное множество является coinfinite перечислимого подмножества из натуральных чисел таким образом, что для каждого дополнительно перечислимому подмножества B натуральных чисел, либо Б является коконечен или В представляет собой конечный вариант А или Б не надмножество А. Это дает простое определение в решетке рекурсивно перечислимых множеств.
Максимальные множества обладают многими интересными свойствами: они просты, гиперпростое, гипергиперпростые и г-максимален; последнее свойство говорит, что каждое рекурсивное множество R содержит либо только конечное число элементов дополнения A или почти всех элементов дополнения A. Есть r-максимальные множества, которые не являются максимальными; некоторые из них даже не имеют максимальных суперсетов. Майхилл (1956) спросил, существуют ли максимальные множества, и Фридберг (1958) построил их. Соар (1974) показал, что максимальные множества образуют орбиту относительно автоморфизма рекурсивно перечислимых множеств по включению ( по модулю конечных множеств). С одной стороны, каждый автоморфизм отображает максимальное множество A в другое максимальное множество B ; С другой стороны, для каждых двух множеств максимальных, Б существует автоморфизм из перечислимых множеств, что отображается B.
