Jensen's hierarchy, also known as the **J-hierarchy**, is a modification of Gödel's [[Constructible universe|constructible hierarchy]]. # Rudimentary functions From [Wikipedia](https://en.wikipedia.org/wiki/Jensen_hierarchy) and [[Schindler - Set Theory_ Exploring Independence and Truth]] A *rudimentary function* is a $V^{n}\to V$ function (i.e. a finitary function accepting sets as arguments) that can be obtained from the following operations: - $F(x_1,\dots, x_n) = x_i$ - $F(x_1,\dots, x_n) = \{x_i,x_j\}$ is rudimentary - $F(x_1,\dots, x_n) = x_i \setminus x_j$ - $F(x_1,\dots, x_n)=h(g_{1}(x^{1}_1,\dots, x^{1}_{n_{1}}),\dots,g_{k}(x^{k}_1,\dots, x^{k}_{n_{k}}))$ where $h,g_{1},\dots,g_{k}$ are rudimentary - $F(x_1,\dots, x_n) =\bigcup_{z\in x_{1}}G(z, x_2,\dots, x_n)$ where $G$ is a rudimentary function. If $A$ is any set or class, a function is *rudimentary in $A$* if it can be obtained from the above operations and - $F(x)=x\cap A$. ## Rudimentary closure >[!info] Definition > For any set $M$ let $\mathrm{rud}(M)$ be the smallest set containing $M\cup\{M\}$ closed under the rudimentary functions. > If $A$ is any set or class, for any set $M$ let $\mathrm{rud}^{A}(M)$ be the smallest set containing $M\cup\{M\}$ closed under the rudimentary in $A$ functions. **Lemma.** If $U$ is a transitive set, $A \subseteq U$, then $\mathcal{P}(U)\cap \mathrm{rud}_{A}(U)$ is exactly all subsets of $U$ which are definable in the model $(U;\in,A)$ with parameters from $U$. Important trick (the $\tilde{}$ means "with parameters"): $\mathcal{P}(U) \cap {\tilde \Sigma}_\omega^{(U ; \in, E)}=\mathcal{P}(U) \cap \tilde{\Sigma}_0^{(U \cup\{U\} ; \in, E)}$ >[!info] Definition > A structure $\left(U ; \in, A_1, \ldots, A_m\right)$, where $U$ is transitive and $A_1, \ldots$, $A_m \subset U^{<\omega}$, is called *amenable* if and only if $A_i \cap x \in U$ whenever $0<i \leq m$ and $x \in U$. # The J-hierarchy >[!info] Definition >If $A$ is any set or class, >- $J^{A}_0=\emptyset$ >- $J^{A}_{\alpha+1}=\mathrm{rud}^{A}(J^{A}_\alpha)$ >- $J^{A}_\beta=\bigcup_{\alpha<\beta} J^{A}_\alpha$ if $\beta$ is a limit ordinal > >Then $L[A]=\bigcup_{\alpha\in \mathrm{Ord}}J^{A}_{\alpha}$ ^264f5d >[!note] Remark >In some places e.g. [[Schindler - Set Theory_ Exploring Independence and Truth]], only limit ordinals are used for the indexing (in order to have room for the finer [[Jensen's hierarchy#The S-hierarchy|S-hierarchy]]) so the definition would be >- $J^{A}_0=\emptyset$ >- $J^{A}_{\alpha+\omega}=\mathrm{rud}^{A}(J^{A}_{\alpha})$ >- $J^{A}_{\omega\beta}=\bigcup_{\alpha<\beta} J^{A}_{\omega\alpha}$ if $\beta$ is a limit ordinal. Assume from now on that $E \subseteq \mathrm{Lim}\times V$, denote $\begin{align} E_\alpha=\{x:(\alpha, x) \in E\} \\ E\restriction\alpha=E \cap(\alpha \times V) \end{align}$for limit ordinals $\alpha$, and assume that $E_\alpha \subset J_\alpha[E]$ and that $\left(J_\alpha[E] ; \in, E_\alpha\right)$ is amenable for every limit ordinal $\alpha$. **Lemma.** For every limit ordinal, $J_\alpha[E] \cap \mathrm{OR}=\alpha$, and $\operatorname{Card}\left(J_\alpha[E]\right)=$ $\operatorname{Card}(\alpha)$. **Theorem.** $L[E]\vDash \mathrm{ZFC}$ # The S-hierarchy The auxiliary "S-hierarchy" is defined so that at each step, we add the images of members of the previous step under a certain *finite* list of rudimentary functions. This hierarchy is used in the proof of $L[E]\vDash \mathrm{AC}$. >[!info] Definition >$ > \begin{aligned} > S_0[E] & =\emptyset \\ > S_{\alpha+1}[E] & =\mathbf{S}^E\left(S_\alpha[E]\right) \\ > S_\lambda[E] & =\bigcup_{\xi<\lambda} S_{\xi}[E] \quad \text { for limit } \lambda > \end{aligned} > $ > where $\mathbf{S}^E$ is defined by > $ > \mathbf{S}^E(U)=\bigcup_{i \in\{3,4,5,16\}} F_i^{\prime \prime}(U \cup\{U\}) \cup \bigcup_{i=0, i \neq 3,4,5}^{15} F_i^{\prime \prime}(U \cup\{U\})^2 > $ > where > $ > \begin{aligned} > F_0(x, y) & =\{x, y\} \\ > F_1(x, y) & =x \backslash y \\ > F_2(x, y) & =x \times y \\ > F_3(x) & =\bigcup x \\ > F_4(x) & =\{a: \exists b(a, b) \in x\} \\ > F_5(x) & =\in \cap(x \times x)=\{(b, a): a, b \in x \wedge a \in b\} \\ > F_6(x, y) & =\{\{b:(a, b) \in x\}: a \in y\} \\ > F_7(x, y) & =\{(a, b, c): a \in x \wedge(b, c) \in y\} \\ > F_8(x, y) & =\{(a, c, b):(a, b) \in x \wedge c \in y\} \\ > F_9(x, y) & =(x, y) \\ > F_{10}(x, y) & =\{b:(y, b) \in x\} \\ > F_{11}(x, y) & =\left(x,(y)_0,(y)_1\right) \\ > F_{12}(x, y) & =\left((y)_0, x,(y)_1\right) \\ > F_{13}(x, y) & =\left\{\left((y)_0, x\right),(y)_1\right\} \\ > F_{14}(x, y) & =\left\{\left(x,(y)_0\right),(y)_0\right\} \\ > F_{15}(x, y) & =\{(x, y)\} \\ > F_{16}(x) & =E \cap x . > \end{aligned} > $ > (Here, $(y)_0=u$ and $(y)_1=v$ if $y=(u, v)$ and $(y)_0=0=(y)_1$ if $y$ is not an ordered pair.) **Proposition.** $ S_\beta[E] \in J_\alpha[E]=S_\alpha[E] $ for all limit ordinals $\alpha$ and all $\beta<\alpha$. There is only a finite jump in $\in$-rank from $S_\alpha[E]$ to $S_{\alpha+1}[E]$.