Рекурсивное Определение

..

ч а с т и ч н о р е к у р с и в н а я ф у н к ц и я,- одно из математич. Уточнений интуитивного понятия вычислимой функции, определяемое следующим образом. Рассматриваются функции, заданные на натуральных числах и с натуральными значениями. Функции предполагаются частичными, т. Е. Определенными, вообще говоря, не для всех значений аргументов. Следующие функции наз. П р о с т е й ш и м и. S(x)=x+1, о(x)=0, . Будем говорить, что n-местная функция yполучена из m-местной функции j и n-местных ф..

такое отношение , где - множество натуральных чисел, что функция f, определенная на условием является рекурсивной функцией. В частности, при любом пуниверсальное отношение и нуль-отношение являются Р. О. Если Rи Sсуть n-местные Р. О., то отношения также будут Р. О. Относительно операций ,' система всех n-местных Р. О. Образует булеву алгебру. В. Е Плиско. ..

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