Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

Государственное образовательное учреждение

Высшего профессионального образования

РЕФЕРАТ

по курсу "Теории алгоритмов"

"Теория нумераций"

Содержание

О теории нумераций

Предварительные сведения

Вычислимые нумерации

Основные понятия

Главные нумерации

Отделимые нумерации

Минимальные нумерации

Категория нумерованных множеств

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

Категория нумерованных множеств и ее свойства

Список литературы

О теории нумераций

Представляется желательным, чтобы все исследования в теории алгоритмов и ее приложениях проводились на основе «общего знаменателя» – класса всех частично рекурсивных функций. Одним из способов такой редукции к натуральным числам и арифметическим функциям является использование подходящей нумерации.

Нумерация – это отображение некоторого подмножества множества натуральных чисел N на исследуемый класс конструктивных объектов (формул, слов, матриц и т.п.)

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

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

Результаты теории нумераций оказались важными для прояснения ряда трудностей, возникающих при эксплуатации вычислительной техники. Например, одной из важных задач программирования является задача эффективного построения по программе вычисления функции на одной машине программы вычисления той же функции на другой машине. Практическая реализация этих «переводов» («трансляций») для двух универсальных машин оказывается весьма сложной, а часто и не осуществленной.

Под «универсальной вычислительной машиной» будем понимать машину, вычисляющую некоторую двуместную функцию , универсальную для класса всех одноместных частично рекурсивных функций, а под «программой вычисления одноместной частично рекурсивной функции » будем понимать ее номер (один из ее номеров), т.е. такое число n N, что таким образом, если имеются две универсальные вычислительные машины (т.е. две универсальные функции ), то «проблема перевода» может быть сформулирована как проблема существования одноместной общерекурсивной функции f такой что

Однако, как показывают исследования вычислимых нумераций, существуют такие универсальные функции , что желаемой функции f не существует. Более того, существуют и такие что невозможен ни перевод с , ни наоборот.

Тем не менее, в классе так определенных универсальных машин существует «самая» универсальная (которую, по-видимому, только и стоит называть универсальной) в том смысле, что на язык этой машины может быть осуществлен перевод с любой другой универсальной машины. Если же рассматривать машины, которые вычисляют только общерекурсивные (всюду определенные) функции из некоторого достаточно богатого класса, то ситуация становится еще более плохой. Для любой такой машины существует другая машина, вычисляющая тот же класс функций, такая, что обе проблемы перевода неразрешимы. Указанный только что подход к разъяснению трудностей перевода может быть использован для определения понятия сложности класса функций (с помощью полурешетки вычислимых нумераций этого класса).

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

Предварительные сведения

Через O обозначим класс всех одноместных общерекурсивных функций, а через O – класс всех одноместных однозначных общерекурсивных функций.

Двуместная функция с определенная так , называется канторовской нумерующей функцией. Оно осуществляет взаимно-однозначное отображение . Существуют однозначно определенные функции r, такие что

для любых .

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

Для любого существует набор из n одноместных функций такой, что выполнены тождества

Функцию назовем сверткой, а набор – n разверткой.

Если Если f – функция, то график f множество . Будем говорить что множество А m сводится к В (символически ), если существует O такая что для любого . Всякую функцию O удовлетворяющую этому условию называют сводящей (А к В). Еще говорят что f m сводит к А к В.

Категория – это класс ObR объектов R вместе с классом MorR морфизмов R со следующими структурами на этих классах:

1. С каждой парой объектов R связано множество Mor (A, B)MorR множество всех морфизмов из А в В;

И если , то

2. С каждой тройкой объектов R связано отображение : так что для A, B, C, D ObR, если Mor (A, B), Mor (B, C), Mor (C, D), то

3. Для каждого А ObR в Mor (A, A) выделен элемент такой что для любого BObR, любого выполняются равенства

Основные понятия

Пусть , , – семейство всех рекурсивно перечислимых множеств n ок натуральных чисел; вместо часто употребляется просто .

Пусть – семейство рекурсивно перечислимых подмножеств N. Нумерацию этого семейства назовем вычислимой, если множество рекурсивно перечислимо (т.е. ).

Распространим введенное определение на нумерации семейств .

Нумерация семейства , называется вычислимой, если множество рекурсивно перечислимо ().

Предложение 1:

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

Обозначим через , n, семейство всех n местных частично рекурсивных функций, через – отображение, сопоставляющее функции ее график.

Пусть – семейство n местных частично рекурсивных функций. Нумерацию семейства назовем вычислимой, если нумерация семейства графиков функций из , определенная так является вычислимой.

Предложение 2

Нумерация семейства n местных частично-рекурсивных функций вычислимая тогда и только тогда когда частичная (n+1) – местная функция определенная соотношением является частично-рекурсивной.

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

Всякая универсальная функция F для семейства определяет некоторую нумерацию семейства так: . Эта нумерация вычислима тогда и только тогда, когда F частично рекурсивна.

Семейство называется вычислимым если существует по крайней мере одна вычислимая нумерация семейства .

Пусть – две нумерации одного и того же множества S. Говорят что нумерация сводится к нумерации , если существует такая что . Если сводится к , то символически изображаем это так .

Отношение , определенное на множестве H(S) всех нумераций множества S является транзитивным. Следовательно, отношение на H(S) является предпорядком.

Если и для , то эти нумерации эквивалентны и обозначаются . Класс нумераций эквивалентных нумерации обозначим через []. Множество классов эквивалентных нумераций обозначим через L(S).

На множестве H(S) можно задать операцию прямой суммы нумераций . Пусть нумерации , определим нумерацию следующим образом:

Основное свойство операции следующее:

Предложение 3

Пусть тогда сводится к тогда и только тогда когда сводится к и сводится к .

Обозначим через семейство всех вычислимых нумераций и через семейство классов эквивалентных вычислимых нумераций .

Главные нумерации

Рассмотрим понятие главной нумерации для семейства рекурсивно перечислимых множеств. Это понятие позволяет ответить (в случае семейства рекурсивно перечислимых множеств) на вопрос: «какую нумерацию данного множества следует считать наиболее естественной?»

Нумерацию назовем главной, если любая нумерация сводится к .

Нумерацию назовем минимальной, если следует что .

У семейства может существовать не более одной с точностью до эквивалентности главной нумерации. Минимальных нумераций может существовать очень много.

Предложение 1

Семейства обладают главными вычислимыми нумерациями.

Семейство назовем главным подмножеством, если оно обладает главной вычислимой нумерацией.

Предложение 2

Главное подмножество замкнуто относительно объединения возрастающих вычислимых последовательностей своих элементов.

Семейство назовем -подмножеством , если существует частично рекурсивная функция g такая что выполнены условия:

1. если то ;

2. если , то и

Предложение 3

Всякое непустое -подмножеством является главным.

Существуют естественные классы рекурсивно перечислимых множеств, которые не имеют главной вычислимой нумерации. Таковыми, например, являются любые семейства общерекурсивных функций.

Определим понятие предельной точки для семейства.

Одноместная (всюду определенная) функция h называется предельной точкой для семейства S, если для любого nN в S найдется функция g отличная от h такая что .

Предложение 4

Если вычислимое семейство содержит предельную точку, то S не имеет главной вычислимой нумерации.

Следствие

Семейство всех одноместных примитивно рекурсивных функций не имеет главной вычислимой нумерации.

Отделимые нумерации

Во многих вопросах, связанных с употреблением нумераций, важно знать, какие отношения между элементами нумерованного множества можно эффективно распознать по их номерам. Одним из самых первых вопросов является следующий: можно ли по номерам двух элементов эффективно узнать, являются ли они Равными или нет? Те нумерации, для которых этот вопрос решается положительно, называются разрешимыми.

Пусть – нумерация множества S. Рассмотрим бинарное отношение на множестве N определенное так . Отношение является отношением эквивалентности и называется нумерационной эквивалентностью. Нумерация называется разрешимой, если отношение рекурсивно. Нумерацию называется позитивной (негативной) если () рекурсивно перечислимо.

Отношение эквивалентности () на множестве S называется разрешимым (позитивным, негативным), если S рекурсивно (рекурсивно перечислимо, представляет собой дополнение до рекурсивно перечислимого множества).

Таким образом, нумерация разрешима (позитивна, негативна) тогда и только тогда когда таковой является ее нумерационная эквивалентность.

Предложение 1

Нумерация бесконечного множества S является разрешимой тогда и только тогда когда она эквивалентна некоторой однозначной нумерации.

Предложение 2

Если – позитивное (негативное) отношение эквивалентности, то - нумерационная эквивалентность подходящей вычислимой нумерации

Предложение 3

Если - семейство попарно не пересекающихся непустых рекурсивно перечислимых множеств, а - вычислимая нумерация, то позитивна

Предложение 4

Если – семейство общерекурсивных функций, – вычислимая нумерация, то - негативная нумерация.

Отметим некоторые свойства позитивных и негативных нумераций относительно сводимости.

Предложение 5

Если S – бесконечное множество, – негативная нумерация S, то существует однозначная нумерация множества S такая что

Предложение 6

Пусть S – бесконечное множество, - позитивная нумерация множества S. Если существует однозначная нумерация множества S такая что , то – разрешимая нумерация.

Предложение 7

Пусть – позитивная нумерация S и , тогда

Следствие

Позитивные нумерации множества определяют минимальные элементы в L(S)

Минимальные нумерации

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

Нумерация ν: N → некоторого множества называется однозначной, если νn ≠ νm для n ≠ m N.

Интерес к изучению вопроса о существовании однозначных вычислимых нумераций у семейства объясняется такими обстоятельствами:

1. Всякая однозначная нумерация ν минимальна, т.е. [ν] – минимальный элемент в L°(S).

Если семейство S имеет хотя бы одну вычислимую однозначную нумерацию, то для любого R семейство \ {R} вычислимо (даже однозначно вычислимо, т.е. допускает однозначную вычислимую нумерацию).

Замечание: Отмеченное в 2 свойство является нетривиальным.

Справедливо следующее утверждение о семействе П.

Предложение 1. Семейство П обладает счетным семейством попарно неэквивалентных однозначных нумераций.□

Наиболее общими результатами о существовании однозначных вычислимых нумераций являются следующие две теоремы.

Теорема 1. Пусть вычислимое семейство содержит сильно перечислимое семейство конечных множеств такое, что

1. любое множество из S есть объединение возрастающей последовательности множеств из ;

любое множество из содержится в некотором собственном подмножестве из .

Тогда существует однозначная вычислимая нумерация семейства .□

Введем следующие определения. Множество М предельно для семейства множеств , если для любого конечного подмножества M в существует М' такое, что М'. Семейство предельно для семейства , если любое множество из предельно для семейства .

Теорема 2. Пусть вычислимое семейство содержит вычислимое подсемейство такое, что

1. если два множества из имеют непустое пересечение, то одно из них содержится в другом;

частично упорядоченное множество < , > не имеет максимальных элементов;

семейство предельно для семейства .

Тогда существует однозначная вычислимая нумерация семейства .□

Минимальными нумерациями являются также и позитивные (однозначные нумерации, в частности, также позитивны). Сразу следует отметить, что довольно многие семейства не имеют однозначных нумераций, но имеют позитивные нумерации. Укажем простейший пример.

Пусть А – рекурсивно перечислимое нерекурсивное множество, полагаем

Нумерацию определяем так:

Ясно, что – вычислимая нумерация семейства . Можно заключить, что любая другая вычислимая нумерация семейства эквивалентна . Заметим теперь, что – неразрешимая нумерация. Последнее следует из эквивалентности .

Замечание. Естественная нумерация слов конечного алфавита определяет некоторую нумерацию свободной полугруппы с образующими из этого алфавита. Эта нумерация слов определяет (порождает) и нумерацию любой конечно определенной полугруппы, причем последняя, всегда будет позитивной.

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

Предложение 2. Пусть вычислимое семейство содержит вычислимое семейство конечных множеств такое, что S предельно для , тогда имеет позитивную нумерацию.□

Предложение 3. Если вычислимое семейство содержит наибольшее по включению множество, имеет позитивную нумерацию.

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

У П, а также и у других семейств может существовать и много минимальных непозитивных нумераций.

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

Пусть – произвольное непустое не более чем счетное множество. Нумерацией множества назовем всякое отображение ν множества 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, определенная следующим образом:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Категория нумерованных множеств и ее свойства

В предыдущем параграфе изучались нумерации подмножеств некоторого множества и отношение сводимости между нумерациями. Обратимся теперь к «взаимодействию» произвольных нумерованных множеств. Наиболее естественным путем для такого изучения является соответствующей категории – категории нумерованных множеств.

Перейдем к точным определениям. Объектами категории являются все нумерованные множества, включая «пустое» нумерованное множество О. Если – произвольное нумерованное множество, то существует и притом единственный морфизм o из О в . Если = (, ) и = (, ) – произвольные не пустые нумерованные множества, то морфизмом из в назовем всякое отображение , для которого существует функция такая, что , иными словами, если диаграмма

f

N N

коммутативна. То, что – морфизм из в , будет обозначаться так: . Множество всех морфизмов из в обозначим через Mor (). Композиция морфизмов определяется естественным образом. Объект О является нулевым объектом категории .

Отметим следующие простые свойства морфизмов.

Если = (, ) и = (, ), – – вполне перечислимое множество, а – морфизм из в , то – – вполне перечислимое подмножество .

Действительно, пусть такова, что . Тогда . Таким образом, f m – сводит к рекурсивно перечислимому множеству , следовательно, будет – вполне перечислимым.

Если – морфизм из = (, ) в = (, ), то сохраняет предпорядки, определенные нумерациями, т.е. .

Следует из 1.

Если – морфизм из = (, ) в = (, ), то – непрерывное отображение топологического пространства (, ) в топологическое пространство (, ).

Следует из 1.

Еще несколько определений. Через N, будем обозначать нумерованное множество (N, ). Для любого множества через Э () обозначим множество всех отношений эквивалентности на множестве . Это множество относительно естественного отношения включения является полной решеткой; если Э (), то и обозначают точную верхнюю и соответственно нижнюю грань элементов . Для Э (), через обозначим нумерованное множество ( – операция – замыкания ([ для Э (). Более общо, если = (, ) – нумерованное множество, Э (, то – это нумерованное множество (); отображение является, очевидно, морфизмом из в .

Предложение 1. Категория эквивалентна своей полной подкатегории , определенной семейством объектов {O}.

По определению эквивалентности категорий и означает, что существует два ковариантных функтора и таких, что функторы и эквивалентны тождественным функторам и соответственно. В качестве функтора F возьмем функтор вложения категории как подкатегории . Функтор определим так: ; если = (, ), то , для простоты вместо будем просто писать , где – нумерационная эквивалентность нумерации . Существует естественный морфизм , определенный так: для . Легко проверить, что это определение корректно и что – морфизм. На самом деле является эквивалентностью категории , т.е. существует такой морфизм , что =, а =. Действительно, отображение определим так: . Ясно, что – морфизм, обладающий нужными свойствами. Продолжим определение функтора . Пусть = (, = (, ) и такова, что ; определяем так: для . Это определение корректно, так как если , то , , т.е. . Ясно также, что – морфизм из в . Так определенное отображение является функтором. Для проверки того, что функтор эквивалентен тождественному функтору, нужно построить единственное преобразование такое, что все морфизмы являются эквивалентностями категории . В качестве таких нужно взять построенные выше морфизмы .

Следствие. Категория эквивалентна малой категории, т.е. категории, семейство объектов которой образует множество.

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

была коммуникативной. Пусть , тогда положим . Проверим корректность определения ; пусть , тогда . Если такова, что , то , так что – морфизм. Соотношение очевидно. Представление всякого морфизма в виде , где однозначно определены указанным выше способом, назовем каноническим представлением морфизма . Отметим следующие свойства канонического представления: – эпиморфизм, а – мономорфизм. Однако этими двумя свойствами представления оно не определяется однозначно (с точностью до разумной теоретико – категорной эквивалентности). Для того чтобы теоретико – категорно охарактеризовать каноническое представление, введем понятие факторизации. Морфизм факторизацией, если для любого морфизма такого, что , существует единственный морфизм такой, что диаграмма

Лемма. Если диаграмма коммутативна.

коммутативна и и или и – факторизации, то все эти морфизмы – факторизации.□

Предложение 2. Пусть следующая диаграмма:

(без ) коммутативна; – каноническое представление, – факторизация, – мономорфизм. Тогда существует морфизм такой, что – эквивалентность категории и диаграмма, приведенная выше, коммутативна.

Из равенства и мономорфности следует, что , тогда существование морфизма и морфизма таких, что диаграммы

коммутативны, вытекает из того, что и – факторизации. Из единственности таких морфизмов вытекает, что , . Таким образом, – эквивалентность категории . Для проверки коммутативности большой диаграммы достаточно показать только, что . Обозначая , получим . Но так как – факторизация, то может существовать только один морфизм такой, что ; поэтому .

Предложение 2 и показывает нужную «единственность» канонического представления. Впредь под каноническим представлением морфизма будем понимать всякое представление его в виде , где – факторизация, а – мономорфизм.

Для того чтобы понять, что факторизация может быть определена в чисто теоретико – категорных терминах (для этого достаточно такое определение для ), определим объект 1 категории как множество {0}, снабженное единственно возможной нумерацией. Укажем следующие простые свойства:

Для любого нумерованного множества = (, ) существует естественное взаимно однозначное соответствие между множеством и множеством Mor ().

Это соответствие задается отображением множества Mor () в .

1. Если , а Mor (, то .

Легко проверяется.

2. Если , , то .

Если и – нумерованные множества и существует эквивалентность , то и назовем эквивалентными и будем обозначать это так . Отметим, например, что все одноэлементные нумерованные множества эквивалентны .

Если , – два морфизма, то назовем ( и () эквивалентными над (менее точно назовем и эквивалентными над ), если существует эквивалентность такая, что диаграмма

коммутативна.

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

коммутативна, то < изоморфно полной решетке < Э (. Это легко следует из рассмотрения канонических представителей в каждом фактор – объекте.

Заметим, что (используя неточную терминологию) любое нумерованное множество О есть фактор – объект . Действительно, если = (, ), то, как легко проверить, морфизм есть факторизация.

Замечание. Данное здесь определение фактор – объекта является не совсем обычным, так как в теории категорий фактор – объектом (в неточной терминологии) называют всякий эпиморфный образ. Здесь же мы ограничились образами факторизаций.

Подобъектом назовем всякую пару (), где – мономорфизм. (Более точное определение: подобъектом назовем класс Ф всех таких пар (), что () и () эквивалентны в ; последнее означает существование эквивалентности такой, что .) Если – мономорфизм и эпиморфизм одновременно, то () назовем плотным подобъектом .

Каноническое представление морфизма показывает, что всякий эпиоморфный образ имеет плотный подобъект, который есть фактор – объект .

Отметим еще, что морфизм является эквивалентностью в тогда и только тогда, когда он является факторизацией и мономорфизмом.

Обратимся теперь к вопросам полноты категории , т.е. к вопросам замкнутости относительно различных категорных конструкций.

Прямой суммой двух объектов и категории называется объект и два морфизма и такие, что для любых морфизмов , где – произвольный объект, существует единственный морфизм такой, что и .

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

Предложение 3. В категории для любых двух объектов существует их прямая сумма.

Если О, то в качестве (с естественными морфизмами из ) можно взять . Аналогично в случае О. Пусть = (, О и = (, О. рассмотрим сначала случай . Полагаем и так: ; . Тогда (, – нумерованное множество, а тождественные вложения и являются морфизмами в . Покажем, что () есть прямая сумма . Пусть = (, ) – произвольное нумерованное множество и , – два морфизма в .

Определим отображение так: для , для . Тогда, очевидно,, и если отображение таково, что , то . Отсюда следует единственность такого . Остается заметить, что – морфизм. Пусть таковы, что . Тогда для , где , имеем , следовательно, – морфизм. Таким образом, () – прямая сумма. Если , то найдем множество и отображение такие, что , – взаимно однозначное соответствие между . Пусть (, , где . По доказанному выше, для и существует прямая сумма (). Тогда () есть, как нетрудно проверить, прямая сумма .□

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

Предложение 4. В категории для любых двух объектов существует их прямое произведение.

Если О или О, то в качестве (с единственными морфизмами в ) можно взять О. Полагаем ; – проекция на первый сомножитель, – проекция на второй сомножитель. определяется так: , или . Легко проверяется, что – нумерация , а и – морфизмы (, – в соответственно. Проверим, что () есть прямое произведение . Пусть = (, ) – произвольное нумерованное множество и , – два морфизма в соответственно. Определим отображение так: для . Для этого отображения имеем . Очевидно, что – единственное отображение , для которого справедливы указанные равенства. Остается заметить, что – морфизм . Пусть таковы, что . Тогда для , где , имеем . Итак, () – прямое произведение □

Лемма 1. Пусть – произвольные нумерованные множества, отличные от О, () – прямая сумма , () – прямое произведение; тогда существуют такие морфизмы , , ,, что , , , .

Пусть – произвольно выбранные элементы. Определим так: для всех ; определим так: для всех . Очевидно, что и – морфизмы. Положим далее и . Равенства и легко проверяются. Определим морфизмы и так:

тогда, очевидно, имеем и .□

Наряду с прямым произведением и прямой суммой в категории существует и расслоенная сумма.

Перейдем к определению этого понятия. Коммутативная диаграмма

называется универсальным квадратом, если для любого объекта и любой пары морфизмов , такой, что , существует единственный морфизм такой, что , . Если приведенная выше диаграмма является универсальным квадратом, то () называется расслоенной суммой над .

Предложение 5. В категории каждая пара морфизмов , вкладывается в подходящий универсальный квадрат.

Если О, то в качестве нужно просто взять прямую сумму . Далее рассматриваем случаи, когда О. Заметим, что тогда и О и О.

Случай 1. Оба морфизма являются факторизациями. Полагаем , – отношение эквивалентности на множестве . Благодаря свойствам факторизаций существуют и притом единственные морфизмы и такие, что диаграмма

коммутативна. Проверим, что эта диаграмма (без ) является универсальным квадратом. Пусть и – такие морфизмы, что ; если , то ясно, что и . Следовательно, и . Поэтому существует единственный морфизм такой, что . Легко проверяется, что тогда , .

Случай 2. Морфизм является факторизацией, а – мономорфизмом. На множестве определим отношение эквивалентности так: для тогда и только тогда, когда или когда и . Рассмотрим диаграмму

где . Из определения видно, что . Тогда из того, что – факторизация, следует существование единственного морфизма такого, что . Из того, что , следует, что – мономорфизм. Проверка того, что внешний квадрат диаграммы является универсальным квадратом, аналогична случаю 1.

Случай 3. Морфизмы и являются мономорфизмами. С точностью до эквивалентности можно считать, что и морфизмы и являются просто вложениями соответственно. Положим . Из определения видно, что отображения вложения являются морфизмами из в .

Проверим, что диаграмма

является универсальным квадратом. Пусть – произвольное нумерованное множество, а : и : – такие морфизмы, что . Последнее означает в нашем случае, что ограничения и совпадают. Следовательно, существует (единственное) отображение , ограничениями которого на и являются соответственно и . Проверим, что есть морфизм из в . Действительно, пусть таковы, что . Функцию определим так:

Ясно, что . Проверим, что . Действительно, . То, что и , следует из определения .

Общий случай. Пусть и – произвольные морфизмы. Построим следующую диаграмму (используя канонические представления морфизмов и ):

так, чтобы она была коммутативной, а каждый из квадратов , , , был универсальным. Возможность последовательного построения таких квадратов в порядке номеров вытекает из рассмотрения случаев 1, 2 и 3 соответственно.

Рутинная проверка того, что если – универсальные квадраты, то и внешний квадрат является универсальным, оставляется недоверчивому читателю.

Доказанное предложение означает, что для любой пары объектов над существует их расслоенная сумма.

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

Укажем еще один положительный результат о замкнутости . Пусть – произвольное направленное предупорядоченное множество, а – прямой спектр факторизаций в , т.е. для – нумерованное множество, для – факторизация; для для .

Предложение 6. Существует предел прямого спектра факторизаций, т.е. такой объект и система морфизмов, , , что для любых ; для любого и системы морфизмов , , такой, что для всех , существует и притом единственный морфизм такой, что для всех .

Укажем только построение нумерованного множества и морфизмов , . Зафиксируем некоторое и пусть ; для любого такого, что , через обозначим отношение эквивалентности на множестве . Семейство отношений эквивалентности {} направленно. Пусть ; – отношение эквивалентности на . Полагаем для определяется единственным образом как морфизм из в такой, что . Если , то находим такое, что и ; полагаем .

Инъективным объектом категории называется объект такой, что для любых двух морфизмов , , где – произвольные объекты, а – мономорфизм, существует морфизм такой, что .

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

Предложение 7. В категории не существует нетривиальных инъективных объектов.

Нумерованное множество , где – одноэлементное множество, очевидно, является инъективным объектом. Нетривиальность означает, что нумерованное множество содержит, по крайней мере, два элемента. Предположим противное. Пусть – инъективный объект в и . Пусть таково, что не m – сводится к , , где и определены так:

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

такова, что и .

Итак, – морфизм. Кроме того, – мономорфизм (а также и эпиморфизм). Определим отображение так: . Как и выше, легко показать, что – морфизм из в . Так как – инъективный объект, то существует морфизм такой, что , но так как , то . Следовательно, отображение является морфизмом в , т.е. существует функция такая, что

Для этой функции имеем: если , то и , следовательно, и ; если , то и и , . Следовательно,

Функция – сводит к , что противоречит выбору . Получаем противоречие.

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

Предложение 8. Нумерованное множество является проективным в категории тогда и только тогда, когда конечно, – разрешимая нумерация .

Действительно, пусть , а – разрешимая нумерация ; ); тогда , – рекурсивные множества. Пусть и – произвольные нумерованные множества, – эпиморфизм, а – произвольный морфизм. Из того, что , и существования морфизма следует, что . Тогда и . Пусть ; пусть . Существование элементов следует из тог, что – отображение на . Пусть – отображение из в , определенное так: . Покажем, что – морфизм. Пусть таковы, что . Определим функцию так:

Ясно, что , и из определений и сразу следует, что . Итак, – морфизм, и, очевидно, .

Пусть – произвольный проективный объект. Морфизм является эпиморфизмом, поэтому (ввиду проективности для и ) должен существовать морфизм такой, что . Ясно, что – мономорфизм. Пусть такова, что . Тогда для . Следовательно, рекурсивно, – разрешимая нумерация. Докажем одно вспомогательное утверждение.

Лемма 2. Если – счетное множество, – разрешимая нумерация , , то объект эквивалентен , т.е. .

Определим рекурсией функцию так: . Из условий леммы вытекает, что . Пусть определено так: . Для существует и обратный морфизм, для его определения введем функцию так: . Из того, что , следует, что . Поэтому существует отображение такое, что . Тогда – морфизм из в и , .

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

Отметим еще, что О также является проективным. Очевидно, что два конечных нумерованных множества с разрешимыми нумерациями эквивалентны тогда, когда они имеют одинаковое число элементов. Поэтому существует счетное множество проективных, попарно не эквивалентных нумерованных множеств такое, что любое другое проективное нумерованное множество эквивалентно одному из этого множества. В качестве такого множества можно взять, например, последовательность 0, 1, 2, …

Нумерованное множество назовем отделимым, если – отделимая нумерация .

Наиболее удобно свойство отделимости может быть описано в следующих понятиях. Пусть – полная подкатегория категории , объектами которой являются все отделимые нумерованные множества.

Предложение 9. Существует (ковариантный) функтор (функтор отделения) и естественное преобразование тождественного функтора в такие, что

1. для любого преобразование есть факторизация;

для любых и отделимого нумерованного множества отображение

взаимно однозначно.

Пусть – произвольное нумерованное множество. Определим на отношение эквивалентности так:

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

Полагаем – факторизация по отношению . Из определения легко видеть, что отделимо. Через обозначим морфизм факторизации . Докажем теперь, что – «наибольший» отделимый фактор – объект , т.е. докажем, что для любого отделимого нумерованного множества и любого морфизма существует (и притом единственный) морфизм такой, что диаграмма

коммутативна.

Рассмотрим каноническое представление морфизма :

где – факторизация, а – мономорфизм. Так как ( – подобъект , а отделимо, то и отделимо. Тогда из определения отношения легко следует, что , но тогда существует отображение такое, что . Так как и – факторизации, то и – морфизмы. Этот (очевидно, единственный) морфизм и удовлетворяет соотношению . Итак, доказано свойство: отображение взаимно однозначно для отделимого . Доопределим теперь функтор . Он уже определен на объектах. Пусть – морфизм. Рассмотрим диаграмму

Так как есть морфизм из в отделимое нумерованное множество , то по доказанному выше свойству существует и притом единственный морфизм , который делает диаграмму коммутативной. Полагаем . Из определения сразу видно, что – функтор, а – естественное преобразование в .

В другой терминологии предложение 9 означает, что функтор вложения имеет левый сопряженный, а именно – функтор ).

Список литературы

1. Ершов Ю.Л. «Теория нумераций», Издательство «Наука» Главная редакция физико-математической литературы, Москва, 1997 г., 416 с.