On Kunen's Set Theory, Definition II.6.17

Question

Definition II.6.17 of Kunen's Set Theory, is as follows:

Fix $\Gamma : \mathbf{HF} \xrightarrow[\text{onto}]{1-1} \omega$, as in Lemma I.10.17. Working with $\mathcal{L} = \{\in\}$, list the set of all variables $\{v_r : r \in \omega\}$, where $r < s \to \Gamma(v_r) < \Gamma(v_s)$. Call a formula $\varphi$ good iff for some $n \geq 0$, the free variables of $\varphi$ are exactly $v_0,v_1,\dots,v_n$. List the set of all good formulas as $\{\varphi_i : i \in \omega\}$ with $i < j \to \Gamma(\varphi_i) < \Gamma(\varphi_j)$; let $\varphi_i$ have $n_i + 1$ free variables.

Whenever $A \neq \emptyset$, $i \in \omega$ and $\vec{b} \in A^{n_i}$, let $D(A,i,\vec{b}) = \{a \in A : A \models \varphi[b_0,\dots,b_{n_i - 1},a]$}. Then, for $S \in \mathcal{D}^+(A)$, let $i(S)$ be the least $i$ such that $S = D(A,i,\vec{b})$ for some $\vec{b} \in A^{n_i}$. Write $n(S)$ for $n_{i(S)}$.

I am unable to wrap my head around this definition.

1. Here, $v_r,v_s$ etc are variables. In that case, what does it mean to have $\Gamma(v_r) < \Gamma(v_s)$, since these variables can take up various values? E.g. $v_r = 0$ and $v_s = 1$, vs $v_r = 1$ and $v_s = 0$.
2. If $\varphi_i$ is a formula, how does one interpret $\Gamma(\varphi_i)$? In the case that we have $\varphi_i$ is "$x = y$", wouldn't this make no sense?
3. What is $\varphi$ in the definition of $D(A,i,\vec{b})$? Should it be $\varphi_i$ instead?

Thanks for any help in advance.

Remark. For completion sake, Lemma I.10,17 is as follows:

Define $E \subseteq \omega \times \omega$ by: $nEm \leftrightarrow 2 \nmid \lfloor{m2^{-n}}\rfloor$ (equivalently, there is a $1$ in place $n$ in the binary representation of $m$ (counting from the right;sp $43 = 101011_b$ has $1$ in places $0,1,3,5$)). Then $(R(\omega);\in) \cong (\omega;E)$, with the isomorphism $\Gamma$ defined recursively by $\Gamma(y) = \sum\{2^{\Gamma(x)} : x \in y\}$. For example:

• $\Gamma(\emptyset) = \sum\emptyset = 0$
• $\Gamma(1) = \sum\{\emptyset\} = 2^0 = 1$
• $\Gamma(\{1\}) = 2^1 = 2$
• $\Gamma(2) = 2^0 + 2^1 = 3$
• $\Gamma(\{\{1\},0\}) = 2^2 + 2^0 = 5$
• $\Gamma(\{\{\{1\},0\},2,1,0\}) = 2^5 + 2^3 + 2^1 + 2^0 = 43$

$\Gamma^{-1}$ is the Mostoski function $\mathrm{mos}_{\omega,E}$.

Answer 1

1. I guess Kunen deems terms and formulas over the language $\{\in\}$ as hereditarily finite sets, but it is often convenient to regard them as natural numbers. Hence he needs to 'encode' formulas into natural numbers.

   I am not sure that why Kunen imposed the conditions you asked, like $r<s\to \Gamma(v_r)<\Gamma(v_s)$, but you may agree that imposing these conditions makes the encoding simpler and more 'reasonable.' (Nobody would think the encoding of $v_{7}$ is larger than that of $v_{3900}$.) Or you may find the reason for this requirement in a proof of propositions later.

   Since $\Gamma$ is already fixed, we have to view this requirement as for variables, not encoding functions. That is, we have to choose variables $v_i$ under the restriction $\Gamma(v_i)<\Gamma(v_j)$ for $i<j$. (One possible way to choose variables is choosing $v_i$ whose rank is larger than that of all $v_j$ for $j<i$.)

2. For your second question, since every formula is hereditarily finite, $\Gamma$ encodes other formulas well if we determine what $v_i$ are. For example, $\Gamma$ encodes $v_i=v_j$ with no problem.

   In your example, however, you have to clarify what $x$ and $y$ are, in terms of $v_i$. (The natural choice would be $v_0$ and $v_1$.)

3. I agree that $\varphi$ should be $\varphi_i$ as commented. Then $D(A,i,\vec{b})$ means a definable subset of $A$ by $i$th formulas with parameters $\vec{b}$.