WikiDer > Примитивная рекурсивная функция набора

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

Определение

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

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

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

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

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

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

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

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

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

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

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

• Дженсен, Рональд Б.; Карп, Кэрол (1971), "Примитивные рекурсивные функции множества", Аксиоматическая теория множеств, Proc. Симпози. Pure Math., XIII, Часть I, Providence, R.I .: Amer. Математика. Soc., Стр. 143–176, ISBN 9780821802458, МИСТЕР 0281602