Misplaced Pages

In set theory, a mathematical discipline, the Jensen hierarchy or J-hierarchy is a modification of Gödel's constructible hierarchy, L, that circumvents certain technical difficulties that exist in the constructible hierarchy. The J-Hierarchy figures prominently in fine structure theory, a field pioneered by Ronald Jensen, for whom the Jensen hierarchy is named. Rudimentary functions describe a method for iterating through the Jensen hierarchy.

Definition

As in the definition of L, let Def(X) be the collection of sets definable with parameters over X:

${\displaystyle {\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\}}$

The constructible hierarchy, ${\displaystyle L}$ is defined by transfinite recursion. In particular, at successor ordinals, ${\displaystyle L_{\alpha +1}={\textrm {Def}}(L_{\alpha })}$.

The difficulty with this construction is that each of the levels is not closed under the formation of unordered pairs; for a given ${\displaystyle x,y\in L_{\alpha +1}\setminus L_{\alpha }}$, the set ${\displaystyle \{x,y\}}$ will not be an element of ${\displaystyle L_{\alpha +1}}$, since it is not a subset of ${\displaystyle L_{\alpha }}$.

However, ${\displaystyle L_{\alpha }}$ does have the desirable property of being closed under Σ₀ separation.

Jensen's modification of the L hierarchy retains this property and the slightly weaker condition that ${\displaystyle J_{\alpha +1}\cap {\mathcal {P}}(J_{\alpha })={\textrm {Def}}(J_{\alpha })}$, but is also closed under pairing. The key technique is to encode hereditarily definable sets over ${\displaystyle J_{\alpha }}$ by codes; then ${\displaystyle J_{\alpha +1}}$ will contain all sets whose codes are in ${\displaystyle J_{\alpha }}$.

Like ${\displaystyle L_{\alpha }}$, ${\displaystyle J_{\alpha }}$ is defined recursively. For each ordinal ${\displaystyle \alpha }$, we define ${\displaystyle W_{n}^{\alpha }}$ to be a universal ${\displaystyle \Sigma _{n}}$ predicate for ${\displaystyle J_{\alpha }}$. We encode hereditarily definable sets as ${\displaystyle X_{\alpha }(n+1,e)=\{X_{\alpha }(n,f)\mid W_{n+1}^{\alpha }(e,f)\}}$, with ${\displaystyle X_{\alpha }(0,e)=e}$. Then set ${\displaystyle J_{\alpha ,n}:=\{X_{\alpha }(n,e)\mid e\in J_{\alpha }\}}$ and finally, ${\displaystyle J_{\alpha +1}:=\bigcup _{n\in \omega }J_{\alpha ,n}}$.

Properties

Each sublevel J_{α, n} is transitive and contains all ordinals less than or equal to ωα + n. The sequence of sublevels is strictly ⊆-increasing in n, since a Σ_m predicate is also Σ_n for any n > m. The levels J_α will thus be transitive and strictly ⊆-increasing as well, and are also closed under pairing, ${\displaystyle \Delta _{0}}$-comprehension and transitive closure. Moreover, they have the property that

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

as desired. (Or a bit more generally, ${\displaystyle L_{\omega +\alpha }=J_{1+\alpha }\cap V_{\omega +\alpha }}$.)

The levels and sublevels are themselves Σ₁ uniformly definable (i.e. the definition of J_{α, n} in J_β does not depend on β), and have a uniform Σ₁ well-ordering. Also, the levels of the Jensen hierarchy satisfy a condensation lemma much like the levels of Gödel's original hierarchy.

For any ${\displaystyle J_{\alpha }}$, considering any ${\displaystyle \Sigma _{n}}$ relation on ${\displaystyle J_{\alpha }}$, there is a Skolem function for that relation that is itself definable by a ${\displaystyle \Sigma _{n}}$ formula.

Rudimentary functions

A rudimentary function is a V→V function (i.e. a finitary function accepting sets as arguments) that can be obtained from the following operations:

• F(x₁, x₂, ...) = x_i is rudimentary (see projection function)
• F(x₁, x₂, ...) = {x_i, x_j} is rudimentary
• F(x₁, x₂, ...) = x_i − x_j is rudimentary
• Any composition of rudimentary functions is rudimentary
• ∪_z∈yG(z, x₁, x₂, ...) is rudimentary, where G is a rudimentary function

For any set M let rud(M) be the smallest set containing M∪{M} closed under the rudimentary functions. Then the Jensen hierarchy satisfies J_α+1 = rud(J_α).

Projecta

Jensen defines ${\displaystyle \rho _{\alpha }^{n}}$, the ${\displaystyle \Sigma _{n}}$ projectum of ${\displaystyle \alpha }$, as the largest ${\displaystyle \beta \leq \alpha }$ such that ${\displaystyle (J_{\beta },A)}$ is amenable for all ${\displaystyle A\in \Sigma _{n}(J_{\alpha })\cap {\mathcal {P}}(J_{\beta })}$, and the ${\displaystyle \Delta _{n}}$ projectum of ${\displaystyle \alpha }$ is defined similarly. One of the main results of fine structure theory is that ${\displaystyle \rho _{\alpha }^{n}}$ is also the largest ${\displaystyle \gamma }$ such that not every ${\displaystyle \Sigma _{n}(J_{\alpha })}$ subset of ${\displaystyle \omega \gamma }$ is (in the terminology of α-recursion theory) ${\displaystyle \alpha }$-finite.

Lerman defines the ${\displaystyle S_{n}}$ projectum of ${\displaystyle \alpha }$ to be the largest ${\displaystyle \gamma }$ such that not every ${\displaystyle S_{n}}$ subset of ${\displaystyle \beta }$ is ${\displaystyle \alpha }$-finite, where a set is ${\displaystyle S_{n}}$ if it is the image of a function ${\displaystyle f(x)}$ expressible as ${\displaystyle \lim _{y_{1}}\lim _{y_{2}}\ldots \lim _{y_{n}}g(x,y_{1},y_{2},\ldots ,y_{n})}$ where ${\displaystyle g}$ is ${\displaystyle \alpha }$-recursive. In a Jensen-style characterization, ${\displaystyle S_{3}}$ projectum of ${\displaystyle \alpha }$ is the largest ${\displaystyle \beta \leq \alpha }$ such that there is an ${\displaystyle S_{3}}$ epimorphism from ${\displaystyle \beta }$ onto ${\displaystyle \alpha }$. There exists an ordinal ${\displaystyle \alpha }$ whose ${\displaystyle \Delta _{3}}$ projectum is ${\displaystyle \omega }$, but whose ${\displaystyle S_{n}}$ projectum is ${\displaystyle \alpha }$ for all natural ${\displaystyle n}$.

References

1. Wolfram Pohlers, Proof Theory: The First Step Into Impredicativity (2009) (p.247)
2. ^ K. Devlin, An introduction to the fine structure of the constructible hierarchy (1974). Accessed 2022-02-26.
3. R. B. Jensen, The Fine Structure of the Constructible Hierarchy (1972), p.247. Accessed 13 January 2023.
4. S. G. Simpson, "Short course on admissible recursion theory". Appearing in Studies in Logic and the Foundations of Mathematics vol. 94, Generalized Recursion Theory II (1978), pp.355--390

• Sy Friedman (2000) Fine Structure and Class Forcing, Walter de Gruyter, ISBN 3-11-016777-8

• Constructible universe