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

Рефераты / Математика / Теория нумераций

Ясно, что , и из определений и сразу следует, что . Итак, height=22 src="images/referats/3088/image597.png">– морфизм, и, очевидно, .

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

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

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

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

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

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

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