Jensen hierarchy

Definition

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

Def(X) = { {y | y ε X and Φ(y, z₁, ..., z_n) is true in (X, ε)} | Φ is a first order formula and z₁, ..., z_n are elements of X}.

The constructible hierarchy, L is defined by transfinite recursion. In particular, at successor ordinals, L_α+1 = Def(L_α).

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 ε L_α+1 − L_α, the set {x,y} will not be an element of L_α+1, since it is not a subset of L_α.

However, L_α does have the desirable property of being closed under Σ₀ separation.

Jensen's modified hierarchy retains this property and the slightly weaker condition that J α + 1 ∩ Pow ( J α ) = Def ( J α ) , but is also closed under pairing. The key technique is to encode hereditarily definable sets over J_α by codes; then J_α+1 will contain all sets whose codes are in J_α.

Like L_α, J_α is defined recursively. For each ordinal α, we define W n α to be a universal Σ_n predicate for J_α. We encode hereditarily definable sets as X α ( n + 1 , e ) = { X ( n , f ) ∣ W n + 1 α ( e , f ) } , with X α ( 0 , e ) = e . Then set J_{α, n} to be {X(n, e) | e in J_α}. Finally, J_α+1 = ⋃ n ∈ ω J α , 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 α + 1 ∩ Pow ( J α ) = Def ( J α ) ,

as desired.

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. Finally, the levels of the Jensen hierarchy satisfy a condensation lemma much like the levels of Godel's original hierarchy.

Rudimentary functions

A rudimentary function is a function that can be obtained from the following operations:

F(x₁, x₂, ...) = x_i is rudimentary

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

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