Примитивная рекурсивная функция набора - Primitive recursive set function

В математика, примитивные рекурсивные функции множества или же примитивные рекурсивные порядковые функции являются аналогами примитивные рекурсивные функции, определенная для наборы или же порядковые скорее, чем натуральные числа. Их представил Дженсен и Карп (1971).

Определение

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

Основные функции:

Проекция: п_п,м(Икс₁, ..., Икс_п) = Икс_м для 0 ≤м ≤ п
Нуль: F(Икс) = 0
Присоединение элемента к набору: F(Икс, у) = Икс ∪ {у}
Тестирование членство: C(Икс, у, ты, v) = Икс если ты ∈ v, и C(Икс, у, ты, v) = у иначе.

Правила генерации новых функций подстановкой:

F(Икс, у) = грамм(Икс, ЧАС(Икс), у)
F(Икс, у) = грамм(ЧАС(Икс), у)

куда Икс и у - конечные последовательности переменных.

Правило генерации новых функций рекурсией:

F(z, Икс) = грамм(∪_{ты ∈ z} F(ты, Икс), z, Икс)

Примитивная рекурсивная порядковая функция определяется таким же образом, за исключением того, что начальная функция F(Икс, у) = Икс ∪ {у} заменяется на F(Икс) = Икс ∪ {Икс} ( преемник из Икс). Примитивно-рекурсивные порядковые функции такие же, как и примитивно-рекурсивные функции множества, которые отображают порядковые числа в порядковые.

Также можно добавить больше начальных функций для получения большего учебный класс функций. Например, порядковая функция ω^α не является примитивно рекурсивным, поскольку постоянная функция со значением ω (или любым другим бесконечный набор ) не является примитивно рекурсивным, поэтому можно добавить эту постоянную функцию к начальным функциям.

Примитивная рекурсивная функция набора - Primitive recursive set function

Определение

Рекомендации