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

реферат

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

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

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

f

N N

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

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

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

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

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

Следует из 1.

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

Следует из 1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Если , , то .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Делись добром ;)