Нумерации множества и его подмножеств
Пусть – произвольное непустое не более чем счетное множество. Нумерацией множества назовем всякое отображение ν множества 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. Если – конечное множество, то и – конечное множество, имеющее то же число элементов, и нао
Популярное: Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас... Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (221)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |