Функция примитивного рекурсивного набора

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

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

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

• Проекция: P n, m (x1,..., x n) = x m для 0 ≤ m ≤ n
• Ноль: F (x) = 0
• Присоединение элемента к набору : F (x, y) = x ∪ {y}
• Проверка принадлежности : C (x, y, u, v) = x, если u ∈ v, и C (x, y, u, v) = y в противном случае.

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

• F(x, y) = G (x, H (x ), y)
• F(x, y) = G (H (x ), y)

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

Правило создания новых функций с помощью рекурсии:

• F (z, x ) = G (∪ u ∈ z F (u, x ), z, x)

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

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

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