Рекурсивное Отношение

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

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

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

всюду определенный частично рекурсивный оператор. В. Е. Плиско. ..