N_местная функция

Используя канторовскую функцию с, можно определить последовательность общерекурсивных функций такую что - 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. Нумерацию этого семейства назовем вычислимой, если множество рекурсивно перечислимо (т.е.).

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

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