Иерархия Дженсена

В теории множеств , математической дисциплине, иерархия Йенсена или J-иерархия представляет собой модификацию L Гёделя конструктивной иерархии , которая позволяет обойти определенные технические трудности, существующие в конструктивной иерархии. J-иерархия занимает видное место в теории тонкой структуры, области, впервые разработанной Рональдом Дженсеном , в честь которого названа иерархия Дженсена. Простейшие функции описывают метод перебора иерархии Дженсена.

Определение

Как и в определении L , пусть Def( X ) будет набором множеств, определяемых параметрами над X :

{\textrm {Def}}(X):=\{\{y\in X\mid \Phi (y,z_{1},...,z_{n}){\text{ is true in }}(X,\in )\}\mid \Phi {\text{ is a first order formula}},z_{1},...,z_{n}\in X\}

Конструируемая иерархия, $L$ определяется трансфинитной рекурсией . В частности, в ординалах-преемниках $L_{\alpha +1}={\textrm {Def}}(L_{\alpha })$ .

Трудность этой конструкции состоит в том, что каждый из уровней не замыкается при образовании неупорядоченных пар ; для данного $x,y\in L_{\alpha +1}\setminus L_{\alpha }$ , набор $\{x,y\}$ не будет элементом $L_{\alpha +1}$ , поскольку оно не является подмножеством $L_{\alpha }$ .

Однако, $L_{\alpha }$ действительно обладает желательным свойством замкнутости при Σ ₀ разделении . ^[1]

Модификация иерархии L, предложенная Йенсеном, сохраняет это свойство и несколько более слабое условие, согласно которому $J_{\alpha +1}\cap {\mathcal {P}}(J_{\alpha })={\textrm {Def}}(J_{\alpha })$ , но также закрыт при спаривании. Ключевой метод заключается в кодировании наследственно определяемых множеств $J_{\alpha }$ по кодам; затем $J_{\alpha +1}$ будет содержать все наборы, коды которых находятся в $J_{\alpha }$ .

Нравиться $L_{\alpha }$ , $J_{\alpha }$ определяется рекурсивно . Для каждого порядкового номера $\alpha$ , мы определяем $W_{n}^{\alpha }$ быть универсальным $\Sigma _{n}$ предикат для $J_{\alpha }$ . Мы кодируем наследственно определяемые множества как $X_{\alpha }(n+1,e)=\{X_{\alpha }(n,f)\mid W_{n+1}^{\alpha }(e,f)\}$ , с $X_{\alpha }(0,e)=e$ . Затем установите $J_{\alpha ,n}:=\{X_{\alpha }(n,e)\mid e\in J_{\alpha }\}$ и, наконец, $J_{\alpha +1}:=\bigcup _{n\in \omega }J_{\alpha ,n}$ .

Характеристики

Каждый подуровень Jα _{транзитивен и , n} содержит все ординалы, меньшие или равные αω + n . Последовательность подуровней является строго ⊆-возрастающей по n , поскольку предикат Σ _m также является Σ _n для любого n > m . Таким образом, уровни J _α будут транзитивными и строго ⊆-возрастающими, а также замкнутыми относительно спаривания: $\Delta _{0}$ -понимание и транзитивное замыкание. Более того, они обладают свойством,

J_{\alpha +1}\cap {\mathcal {P}}(J_{\alpha })={\text{Def}}(J_{\alpha }),

по желанию. (Или в более общем плане, $L_{\omega +\alpha }=J_{1+\alpha }\cap V_{\omega +\alpha }$ . ^[2])

Уровни и подуровни сами по себе являются ₁ равномерно определимыми (т.е. определение J _{α , n} в J _β не зависит от β ) и имеют равномерный ₁ вполне упорядоченный порядок. Кроме того, уровни иерархии Йенсена удовлетворяют лемме о конденсации , подобно уровням исходной иерархии Гёделя.

Для любого $J_{\alpha }$ , учитывая любые $\Sigma _{n}$ отношение к $J_{\alpha }$ , для этого отношения существует скулемовская функция , которая сама может быть определена с помощью $\Sigma _{n}$ формула. ^[3]

Рудиментарные функции

Простейшая функция — это V ^н→V-функция (т.е. конечная функция, принимающая множества в качестве аргументов), которую можно получить в результате следующих операций: ^[2]

F ( x ₁ , x ₂ , ...) = x _i элементарно (см. функцию проекции )
F ( x ₁ , x ₂ , ...) = { x _i , x _j } элементарно
F ( Икс ₁ , Икс ₂ , ...) знак равно Икс _я - Икс _j является элементарным
Любая композиция рудиментарных функций является рудиментарной.
∪ _{z ∈ y} G ( z , x ₁ , x ₂ , ...) является элементарной, где G является элементарной функцией

Для любого множества M пусть rud( M ) — наименьшее множество, содержащее M ∪{ M }, замкнутое относительно элементарных функций. Тогда иерархия Йенсена удовлетворяет условию J _α+1 = rud( J _α ). ^[2]

проекты

Дженсен определяет $\rho _{\alpha }^{n}$ , $\Sigma _{n}$ проект $\alpha$ , как самый крупный $\beta \leq \alpha$ такой, что $(J_{\beta },A)$ поддается всем $A\in \Sigma _{n}(J_{\alpha })\cap {\mathcal {P}}(J_{\beta })$ и $\Delta _{n}$ проект $\alpha$ определяется аналогично. Одним из основных результатов теории тонкой структуры является то, что $\rho _{\alpha }^{n}$ также является крупнейшим $\gamma$ такое, что не каждый $\Sigma _{n}(J_{\alpha })$ подмножество $\omega \gamma$ есть (в терминологии теории α-рекурсии ) $\alpha$ -конечный. ^[2]

Лерман дает определение $S_{n}$ проект $\alpha$ быть самым большим $\gamma$ такое, что не каждый $S_{n}$ подмножество $\beta$ является $\alpha$ -конечный, где множество $S_{n}$ если это образ функции $f(x)$ выражается как $\lim _{y_{1}}\lim _{y_{2}}\ldots \lim _{y_{n}}g(x,y_{1},y_{2},\ldots ,y_{n})$ где $g$ является $\alpha$ -рекурсивный. В характеристике в стиле Дженсена: $S_{3}$ проект $\alpha$ является крупнейшим $\beta \leq \alpha$ такой, что существует $S_{3}$ эпиморфизм от $\beta$ на $\alpha$ . Существует порядковый номер $\alpha$ чей $\Delta _{3}$ это проект $\omega$ , но чей $S_{n}$ это проект $\alpha$ для всего натурального $n$ . ^[4]

Ссылки

^ Вольфрам Полерс, Теория доказательств: первый шаг к непредикативности (2009) (стр.247)
^ Jump up to: Перейти обратно: ^а ^б ^с ^д К. Девлин, Введение в тонкую структуру конструктивной иерархии (1974). Доступ 26 февраля 2022 г.
^ Р.Б. Дженсен, Тонкая структура конструктивной иерархии (1972), стр.247. По состоянию на 13 января 2023 г.
^ С.Г. Симпсон, «Краткий курс теории допустимой рекурсии». Появляясь в исследованиях по логике и основам математики, том. 94, Обобщенная теория рекурсии II (1978), стр. 355–390.

Сай Фридман (2000) Тонкая структура и принуждение классов , Уолтер де Грюйтер, ISBN 3-11-016777-8

[1] Вольфрам Полерс, Теория доказательств: первый шаг к непредикативности (2009) (стр.247)

[Devlin74-2] Jump up to: Перейти обратно: ^а ^б ^с ^д К. Девлин, Введение в тонкую структуру конструктивной иерархии (1974). Доступ 26 февраля 2022 г.

[3] Р.Б. Дженсен, Тонкая структура конструктивной иерархии (1972), стр.247. По состоянию на 13 января 2023 г.

[4] С.Г. Симпсон, «Краткий курс теории допустимой рекурсии». Появляясь в исследованиях по логике и основам математики, том. 94, Обобщенная теория рекурсии II (1978), стр. 355–390.

[1]

[2]

[3]

[4]