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

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

Определение

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

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

Проекция: P _{n , m} ( x ₁ , ..., 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 ( Икс , y ) знак равно грамм ( Икс , ЧАС ( Икс ), y )
F ( Икс , y ) знак равно грамм ( ЧАС ( Икс ), y )

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

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

F ( z , Икс ) знак равно грамм (∪ _{ты ∈ z} F ( ты , Икс ), z , Икс )

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

Примеры примитивно-рекурсивных функций множества:

TC , функция, присваивающая множеству его транзитивное замыкание. ^[1]^: 26
Учитывая наследственно конечное $c$ , постоянная функция $f(x)=c$ . ^[1]^: 28

Расширения

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

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

Примеры примитивно-рекурсивных по ω функций: ^[1] ^{стр.28--29}

$\mathbb {P} _{\omega }(x)=\bigcup _{n<\omega }x^{n}$ .
Функция, присваивающая $\alpha$ тот $\alpha$ уровень $L_{\alpha }$ Геделя конструктивной иерархии .

Примитивное рекурсивное замыкание

Позволять $f_{0}:{\textrm {Ord}}^{2}\to {\textrm {Ord}}$ быть функцией $f(\alpha ,\beta )=\alpha +\beta$ , и для всех $i<\omega$ , ${\tilde {f}}_{i}(\alpha )=f_{i}(\alpha ,\alpha )$ и $f_{i+1}(\alpha ,\beta )=({\tilde {f}}_{i})^{\beta }(\alpha )$ . Пусть L _α обозначает α-ю стадию конструируемой вселенной Гёделя . L _α замкнуто относительно примитивно-рекурсивных функций множества тогда и только тогда, когда α замкнуто относительно каждого $f_{i}$ для всех $i<\omega$ . ^[1]^: 31

Ссылки

Дженсен, Рональд Б.; Карп, Кэрол (1971), «Примитивно-рекурсивные функции множества», Аксиоматическая теория множеств , Proc. Симпозиумы. Чистая математика., вып. XIII, Часть I, Провиденс, Род-Айленд: Амер. Математика. Соц., стр. 143–176, ISBN. 9780821802458 , МР 0281602

В соответствии

^ Jump up to: ^а ^б ^с ^д Р.Б. Дженсен, Рукопись о тонкой структуре, теории внутренней модели и базовой модели ниже одного кардинала Вуда (стр. 22–31). Доступ: 7 декабря 2022 г.

[JensenManuscript-1] Jump up to: ^а ^б ^с ^д Р.Б. Дженсен, Рукопись о тонкой структуре, теории внутренней модели и базовой модели ниже одного кардинала Вуда (стр. 22–31). Доступ: 7 декабря 2022 г.

[1]