Jensen hierarchy#Rudimentary functions

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:

: $\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, $L$ is defined by transfinite recursion. In particular, at successor ordinals, $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 $x, y \in
L_{\alpha+1} \setminus L_\alpha$ , the set $\{x,y\}$ will not be an element of $L_{\alpha+1}$ , since it is not a subset of $L_\alpha$ .

However, $L_\alpha$ does have the desirable property of being closed under Σ₀ separation.Wolfram Pohlers, Proof Theory: The First Step Into Impredicativity (2009) (p.247)

Jensen's modification of the L hierarchy retains this property and the slightly weaker condition that $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 $J_\alpha$ by codes; then $J_{\alpha+1}$ will contain all sets whose codes are in $J_\alpha$ .

Like $L_\alpha$ , $J_\alpha$ is defined recursively. For each ordinal $\alpha$ , we define $W^{\alpha}_n$ to be a universal $\Sigma_n$ predicate for $J_\alpha$ . We encode hereditarily definable sets as $X_{\alpha}(n+1, e) = \{X_\alpha(n, f) \mid W^{\alpha}_{n+1}(e, f)\}$ , with $X_{\alpha}(0, e) = e$ . Then set $J_{\alpha,n} := \{X_\alpha(n, e) \mid e \in J_\alpha\}$ and finally, $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, $\Delta_0$ -comprehension and transitive closure. Moreover, they have the property that

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

as desired. (Or a bit more generally, $L_{\omega+\alpha}=J_{1+\alpha}\cap V_{\omega+\alpha}$ .K. Devlin, [https://core.ac.uk/download/pdf/30905237.pdf An introduction to the fine structure of the constructible hierarchy] (1974). Accessed 2022-02-26.)

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 $J_\alpha$ , considering any $\Sigma_n$ relation on $J_\alpha$ , there is a Skolem function for that relation that is itself definable by a $\Sigma_n$ formula.R. B. Jensen, [https://www.math.cmu.edu/~laiken/papers/FineStructure.pdf The Fine Structure of the Constructible Hierarchy] (1972), p.247. Accessed 13 January 2023.

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 $\rho_\alpha^n$ , the $\Sigma_n$ projectum of $\alpha$ , as the largest $\beta\leq\alpha$ such that $(J_\beta,A)$ is amenable for all $A\in\Sigma_n(J_\alpha)\cap\mathcal P(J_\beta)$ , and the $\Delta_n$ projectum of $\alpha$ is defined similarly. One of the main results of fine structure theory is that $\rho_\alpha^n$ is also the largest $\gamma$ such that not every $\Sigma_n(J_\alpha)$ subset of $\omega\gamma$ is (in the terminology of α-recursion theory) $\alpha$ -finite.

Lerman defines the $S_n$ projectum of $\alpha$ to be the largest $\gamma$ such that not every $S_n$ subset of $\beta$ is $\alpha$ -finite, where a set is $S_n$ if it is the image of a function $f(x)$ expressible as $\lim_{y_1}\lim_{y_2}\ldots\lim_{y_n}g(x,y_1,y_2,\ldots,y_n)$ where $g$ is $\alpha$ -recursive. In a Jensen-style characterization, $S_3$ projectum of $\alpha$ is the largest $\beta\leq\alpha$ such that there is an $S_3$ epimorphism from $\beta$ onto $\alpha$ . There exists an ordinal $\alpha$ whose $\Delta_3$ projectum is $\omega$ , but whose $S_n$ projectum is $\alpha$ for all natural $n$ . 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

References

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

Category:Constructible universe