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

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

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

Если - нумерация , s , n N и 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 сохраняет отношение порядка (точнее: a b 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. Если  – конечное множество, то и  – конечное множество, имеющее то же число элементов, и нао