Нумерации множества и его подмножеств

Пусть - произвольное непустое не более чем счетное множество. Нумерацией множества назовем всякое отображение н множества N всех натуральных чисел на множество . Пара = (S, н), где н - некоторая нумерация множества S, называется нумерованным множеством. Для дальнейшего будет удобно считать, что и пустое множество Ш обладает некоторой единственной «нумерацией» o, а «нумерованное» множество (Ш, o) будем обозначать О.

Пусть - два подмножества S и - нумерации множеств соответственно. Будем говорить, сводится к (), если = o (и тогда = Ш) или o, o и существует общерекурсивная функция f такая, что x = f(x) для любого , короче = . Такую функцию будем называть сводящей. Заметим, что из следует, что . Действительно, если = o, то , если же o и s, то x = s для некоторого xN, но x = f(x). Легко проверяется, что отношение сводимости является рефлексивным и транзитивным. Если , то нумерации и назовем эквивалентными (. Класс всех нумераций, эквивалентных н, обозначим через [н].

Если - нумерация , s, nN и n = s, то число n называется - номером элемента s. Сводимость нумерации к означает, что по любому - номеру любого элемента из можно эффективно найти некоторый - номер этого же элемента.

Множество всех нумераций множества S обозначим через H (S), а множество всех нумераций подмножества S (включая пустое) обозначим через H*(S). Определим отображение r множества H* (S) на Р(S) - множество всех подмножеств S - так: r(o) Ш; r(н) н(N) для нo H*(S). Отметим, что для любого подмножества и H*(S) = .

Множество классов эквивалентных нумераций множества S (подмножеств S) обозначим через L (S) (L*(S)). На этих множествах отношение сводимости индуцирует отношение частичного порядка, которое будем обозначать также . Отображение r: H*(S) Р(S) индуцирует отображение L*(S) Р(S), которое также будем обозначать через r. Ясно, что r сохраняет отношение порядка (точнее: ab L*(S)r(a). Как и выше для .

На множестве H*(S) определим операцию прямой суммы нумераций.

Пусть H*(S); если = o, то ; если = o, то ; пусть o o и , , тогда нумерация множества определяется так:

Предложение 1. Если H*(S), то тогда, когда .?

Следствие. Частично упорядоченные множества L*(S) и L(S) являются верхними полурешетками, а для операции точной верхней грани справедливо следующее соотношение: для H*(S)

[] = [].?

Заметим, что L(S) L*(S) является коидеалом, т.е. удовлетворяет условию

a L(S) L*(S), a

Полезно заметить и то, что r(a) = ()) для любых a, b L*(S).

Предложение 2. Полурешетка L*(S) является дистрибутивной полурешеткой с нулем [o].

Нужно доказать, что если H*(S) и , то существуют такие H*(S), что и . Ясно, что если = o, то в качестве нужно также взять o. Пусть o и пусть f Х - функция, которая сводит к , т.е. = ) f. Определяем множества так: , . Множества рекурсивно перечислимы. Если Ш, то полагаем o; если Ш, то пусть Х такова, что ; , и пусть . Если = Ш, то полагаем o; если Ш, то пусть Х такова, что ; , и пусть . Из определения видно, что . Поэтому достаточно показать, что . Рассмотрим случай Ш и Ш (другие случаи проще). Пусть таковы, что и для ; и для . Определим функцию так:

- общерекурсивная функция. Проверим, что = (). Пусть x таково, что f(x) четно, тогда

= ()() (2 ().

Пусть х таково, что f(x) нечетно, тогда

= ()() (2 ().

Итак, = () и . Покажем теперь, что и . Пусть , тогда

) f

) f.

Следовательно, , () и .?

Следствие. Если a L*(S) (L(S)), то полурешетка является дистрибутивной полурешеткой.?

Сводимость нумераций довольно близка понятию m - сводимости. Сейчас укажем простейшую связь.

Предложение 3. Если H*(S), , - нумерация множества , то для любого .

Действительно, если f Х - сводящая функция, т.е. = , то легко видеть, что функция f m - сводит .?

Необходимое условие сводимости нумераций, указанное в этом предложении, конечно, не является достаточным, однако существует частный случай, когда это так.

Рассмотрим пример, когда . Для любого собственного подмножества М множества N определим нумерацию множества S так:

Нумерация является просто характеристической функцией множества М. Нумерованное множество ({0,1},) будем обозначать .

Нетрудно проверить, что для имеем тогда и только тогда, когда . Отсюда вытекает следующее

Предложение 4. Верхняя полурешетка L({0,1}) классов эквивалентных нумераций множества {0,1} изоморфна верхней полурешетке всех m - степеней собственных подмножеств N.?

Следствие. Полурешетка классов эквивалентных нумераций двухэлементного множества имеет мощность континуума.

Действительно, собственных подмножеств N континуум, а каждая m - степень состоит не более чем из счетного семейства множеств.?

Отметим, что если S одноэлементно, то S имеет только одну нумерацию и, следовательно, в этом случае L(S) одноэлементна.

Если , то, очевидно, H*() H*(), L*() L*() и L*() является идеалом полурешетки L*(). Можно ли так же естественно вложить L() в L()? Ответ, вообще говоря, будет отрицательным в смысле «естественности», но некоторые изоморфные вложения L() в L() в качестве идеала будут построены. Конечно, нетривиальным случаем является только случай, когда - собственное подмножество .

Предложение 5. Пусть - собственное подмножество , а - минимальный элемент в L(), тогда отображение для b L() (операция определена в L*() L() L()) есть изоморфное отображение L() на некоторый идеал L().

Ясно, что - гомоморфизм полурешетки L() в полурешетку L(). Покажем, что - изоморфизм. Для этого достаточно проверить, что если для (). Пусть и ()=. Из последнего следует, что . Так как L*() - дистрибутивная полурешетка, то существуют c и d такие, что , и =. Так как , то ) =; а так как , то ) =. Следовательно, Ш, = o и =. Получаем противоречие. Итак, - изоморфизм. Пусть b L(), c L() и c; тогда существуют такие, что и . Так как , а , то . Но и . Следовательно, и L(). Но так как а - минимальный элемент L() и , то . Покажем теперь, что L(). Для этого достаточно показать, что . Включение уже показано; из того, что , а , следует, что ) = . Следовательно, = , L(). Из следует, что и L(). Таким образом, L()) - идеал L().?

Для того чтобы применять предложение 5 для решения вопроса о вложении L() в L(), нужно выяснить вопрос о существовании минимальных элементов в полурешетках L(S).

Предложение 6. Если S конечно, то L(S) имеет наименьший элемент и является дистрибутивной полурешеткой.

Пусть и . Определим нумерацию этого множества так: , если m < n, и , если . Пусть - произвольная нумерация S и - некоторые - номера элементов соответственно. Определяя функцию f так, что f(i) для i < n и f(i) для , получаем и f Х. Следовательно, и [] - наименьший элемент L(S).?

Следствие. Если S - конечное множество, содержащее, по крайней мере, два элемента, то полурешетка L(S) континуальна.?

Предложение 6 показывает, что «естественное» вложение L() в L() (для ) существует, когда конечно.

В случае бесконечного S полурешетка L(S) не имеет наименьшего элемента, но имеет много минимальных. Для установления этого напомним следующее определение. Нумерация множества S называется однозначной, если нn ? нm для любых n ? m N.

Предложение 7. Если S - счетное множество, то существует точно континуум попарно не эквивалентных и даже попарно несравнимых однозначных нумераций множества S.

Пусть - группа всех перестановок множества N, - подгруппа общерекурсивных перестановок N. Хорошо известно, что счетна, а имеет мощность континуума, отсюда следует, что множество левых смежных классов также имеет мощность континуума. Пусть - некоторая фиксированная однозначная нумерация множества S. Тогда любая другая однозначная нумерация может быть однозначно представлена в виде , а класс нумераций, эквивалентных нумерации , состоит из всех нумераций вида , так что существует взаимно однозначное соответствие между классами эквивалентных однозначных нумераций множества S и смежными классами из . Так как неэквивалентные однозначные нумерации, очевидно, не сравнимы, то отсюда и следует заключение предложения.?

Следствие 1. Если S - счетное множество, L(S) имеет континуум минимальных нумераций.

Следствие 2. Если S - не более чем счетное множество, содержащее, по крайней мере, два элемента, L(S) имеет идеал, изоморфный полурешетке всех m - степеней собственных подмножеств N.

Это вытекает из предложения 5 и следствия 1.

Обратимся теперь к вопросу об изоморфизме полурешеток L(S), и L(), L*() для двух не более чем счетных множеств S и . Ясно, что если S и равномощны, то эти полурешетки соответственно изоморфны. Если S конечно, а бесконечно, то L(S) имеет наименьший элемент, а L() наименьшего элемента не имеет, следовательно, в этом случае L(S) и L() не изоморфны. Полурешетка имеет наименьший элемент. Рассмотрим, какие же минимальные (отличные от [o]) элементы она имеет. Каждому элементу s соответствует одноэлементное множество L({s}) . Нетрудно проверить, что соответствующий элемент будет минимальным, этот элемент будем обозначать . Пусть a - произвольный отличный от нуля элемент , тогда r(a) Ш. Пусть s r(a), тогда легко проверяется, что . Проведенные рассмотрения доказывают следующее

Предложение 8. Отображение устанавливает взаимно однозначное соответствие между элементами S и минимальными элементами .

Следствие. и L*() изоморфны тогда и только тогда, когда и равномощны.

Итак, неясным остается только вопрос, изоморфны ли полурешетки и L() для конечных множеств и , имеющих не менее двух элементов. Оказывается, что полурешетка для конечных , имеющих, по крайней мере, два элемента, обладает замечательным свойством универсальности, которое в качестве следствия влечет изоморфизм всех таких полурешеток. Переходим к точной формулировке этого результата.

Дистрибутивную полурешетку L назовем допустимой, если она имеет нуль и если всякий главный идеал L не более чем счетен. Заметим, что если конечно, то - допустимая полурешетка.

Теорема 1. Пусть - конечное множество, имеющее, по крайней мере, два элемента; пусть L - допустимая полурешетка мощности меньше континуума, - идеал L и - изоморфное вложение на идеал , тогда существует изоморфное вложение на идеал , которое продолжает (т.е. ).

Следствие 1. Если и - конечные множества, имеющие, по крайней мере, два элемента, то полурешетки и L() изоморфны.

Следствие 2. Если - конечное множество, имеющее, по крайней мере, два элемента, то полурешетка изоморфна полурешетке всех m - степеней собственных подмножеств N.

Следствие 3. Если , то полурешетка и изоморфны.

Это также нетрудное следствие свойства универсальности, указанного в теореме.

Перейдем теперь к изучению более тонкого отношения сводимости между нумерациями. Пусть - непустые подмножества , 1 - сводится к (), если существует одно - однозначная общерекурсивная функция f (1 - сводящая функция) такая, что = . Класс всех одноместных одно - однозначных общерекурсивных функций обозначим . Нумерации назовем изоморфными (), если существует общерекурсивная перестановка f (т.е. и ) такая, что = . Отношение является транзитивным, а отношение является отношением эквивалентности.

Теорема 2. Пусть - две нумерации множества . Если и , то .

Пусть и 1 - сводят и соответственно, т.е. = и = . Определим теперь функции следующим образом:

Имеем и .

Положим , . Заметим, что для любого

Лемма 1. Если - конечное множество, то и - конечное множество, имеющее то же число элементов, и наоборот. В этом случае

Покажем сначала, что либо функция , либо она является строго периодической, т.е. существует z > 0 такое, что . Предположим, что . Тогда существуют такие, что . Но , а . Так как , имеем .

Итак, если - конечное множество, содержащее n + 1 элемент, то его элементы представляют собой значения функции от первых n +1 аргументов. Пусть

Тогда . Имеем

так как и . Эти элементы различны, а

Итак, если конечно, то конечно, и отображение осуществляется взаимно однозначное соответствие между и . Аналогично, отображение осуществляется взаимно однозначное соответствие между и . Если конечно, то и конечно. Но . Отсюда очевидно, что также конечно и , так что .

Цилиндром нумерации н: N > S называется нумерация с (н): N > S, определенная следующим образом:

Нумерация называется цилиндрической, если она изоморфна своему цилиндру.

Сформулируем ряд свойств введенных понятий.

1. Если - две нумерации множества , - однозначная нумерация и , то . Если, кроме того, однозначна, то .

Действительно, пусть f - функция, которая сводит . Тогда и f принимает каждое натуральное число как значение, другими словами, . Функция и, очевидно, сводит . Если однозначны, то f - общерекурсивная перестановка натурального ряда.?

С помощью приведенного рассуждения на самом деле доказывается и

Лемма 2. Пусть - две нумерации множества . Если существует , сводящая , такая, что , то .?

2. Если - две нумерации множества , - однозначная нумерация, то из следует .

На самом деле любая функция f, сводящая , будет из . Действительно, если = , то из следует = . Из однозначности нумерации следует, что .?

3. и , следовательно, и .

Функция и сводит .

Функция r сводит

Следствие. Существуют эквивалентные, но не изоморфные нумерации.

Действительно, пусть - некоторая однозначная нумерация . Тогда . Но всякая нумерация, изоморфная однозначной, должна быть однозначной. Нумерация , очевидно, неоднозначная. Имеем .?

4. Если - две нумерации множества , - цилиндрическая нумерация, то из следует .

Действительно, пусть сводит . Предположим еще, что есть цилиндр: . Определим так:

тогда 1 - сводит . Если - цилиндр, то, рассматривая , имеем , как выше. Но , по определению цилиндрической нумерации, следовательно, .?

Следствие. Если - две цилиндрические нумерации , то из следует .?

Лемма 3. Пусть - некоторая нумерация множества . Если существует двуместная общерекурсивная функция h такая, что , то - цилиндрическая нумерация.

По свойству 3 и . Пусть f сводит , т.е. . Определим функцию так:

Тогда 1 - сводит . По теореме 2 имеем .?

Следствие. Пусть - произвольная нумерация множества , тогда цилиндр является цилиндрической нумерацией.

Действительно, функция удовлетворяет условиям леммы.

На нумерованном множестве = (, ) введем две новые «структуры», используя следующее понятие: подмножество называется вполне перечислимым (точнее, - вполне перечислимым), если рекурсивно перечислимо. Бинарное отношение, на , которое назовем - предпорядком, определим так: для

для любого вполне перечислимого подмножества .

Легко проверить, исходя из определения, что отношение рефлексивно и транзитивно, т.е. действительно является предпорядком. Заметим, что справедливо следующее

Предложение 9. Предпорядок является частичным порядком (т.е. ) тогда и только тогда, когда нумерация является отделимой.

Действительно, в соответствии с определением отделимой нумерации существует такая последовательность <> рекурсивно перечислимых множеств, что 1) для любого , если и , то ; 2) если , то для некоторого, либо и , либои . Проверим, что множества , являются вполне перечислимыми подмножествами . Действительно, и, если , то существует такое, что . Но тогда и . Итак, рекурсивно перечислимо, а вполне перечислимо. Пусть и пусть , таковы, что , ; так как , то . По свойству 2) найдется такое, что либо и , либои ; тогда либо , либо . Следовательно, либо , либо и - частичный порядок.

Наоборот, если - частичный порядок, то пусть - последовательность всех вполне перечислимых подмножеств (число их не более чем счетно); пусть , тогда без труда проверяется, что последовательность <> рекурсивно перечислимых множеств удовлетворяет определениям 1) и 2) отделимой нумерации.

Введем на топологию , задав ее базисом, состоящим из всех вполне перечислимых подмножеств (легко проверить, что пересечение двух вполне перечислимых подмножеств также вполне перечислимо).

Предложение 10. Топология является отделимой (т.е. (, ) - - пространство) тогда и только тогда, когда нумерация отделима.

Нумерованное множество = (, ) назовем отделимым, если выполнено одно из следующих трех эквивалентных условий:

1) нумерация отделима;

2) предпорядок является частичным порядком;

3) топология отделима.