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