# Ways to define “definability”

The notion of a definable set is not expressible in the language of set theory: there is no formula $\delta(x)$ that is equivalent with there being a formula $\phi(y)$ such that $x = \lbrace y : \phi(y)\rbrace$, i.e. for which

$$\delta(x) \leftrightarrow (\exists \phi \in \mathsf{Form})\ x = \lbrace y : \phi(y)\rbrace$$

is provable. (Please forgive my blunt use of the set-builder notation $\lbrace y : \phi(y)\rbrace$. I know there's the rub.)

The same holds for (unrestricted) definitions with parameters: there is no formula $\delta(x)$ that is equivalent with there being a formula $\phi(y,z_1,\dots,z_n)$ such that $x = \lbrace y : \phi(y,z_1,\dots,z_n)\rbrace$ for some $z_1,\dots,z_n$, i.e. for which

$$\delta(x) \leftrightarrow (\exists \phi \in \mathsf{Form})(\exists z_1,\dots,z_n)\ x = \lbrace y : \phi(y,z_1,\dots,z_n)\rbrace$$

is provable.

But the notion of ordinal-definable sets is expressible in the language of set theory (see Jech, p. 194), i.e. there is a formula $\delta(x)$ such that - bluntly said -

$$\delta(x) \leftrightarrow (\exists \phi \in \mathsf{Form})(\exists z_1,\dots,z_n)\ x = \lbrace y : \phi(y,z_1,\dots,z_n)\rbrace \wedge \mathsf{ON}(z_i)$$

is provable.

My questions are:

1. Are there other restrictions on the parameters like $\mathsf{ON}(z_i)$ (the formula that states that $z_i$ is an ordinal) that give rise to a definable notion of definability, i.e. a class of accordingly definable sets?

2. Can these restrictions been characterized? What do they have in common, eventually? What is essential?

3. Are there restrictions $\Psi(\phi)$ on the formulas that comparably give rise to a definable notion of definability, i.e. there would be a formula $\delta(x)$ such that $$\delta(x) \leftrightarrow (\exists \phi \in \mathsf{Form})(\exists z_1,\dots,z_n)\ x = \lbrace y : \phi(y,z_1,\dots,z_n)\rbrace \wedge \Psi(\phi)$$ is provable.

4. Or maybe some mixture $\Psi(\phi,z_1,\dots,z_n)$?

Question 3 includes: Can we - in a Goedelian way - define for a formula (as a set), that some of its arguments must fulfill some other formula?

I am glad to see this question, Hans, which I believe gets right to the heart of the definability concept, on which some of your recent questions have focused. This is an excellent question.

First, let me say that I dispute your characterization of the OD sets. The claim that you state is not what is proved about OD, since your claim is not expressible, as it makes use of a Tarskian truth predicate (you quantify over the formulas $\varphi$, and then refer to the truth of $\varphi$), but we have no such truth predicate. Similarly, question 3 is problematic, since it also essentially refers to a truth predicate, and this is the typical pitfall of those who treat definability naively.

What is actually proved is this. We have a definable class OD, and then we prove, as a separate claim about each formula $\varphi$, that the set defined by $\varphi$ with ordinal parameters is in OD. And conversely, we can see directly that each set in OD is defined by a formula with ordinal parameters.

The crucial thing that makes it work in the case of OD is the reflection theorem, which says of every formula $\varphi$ (as a separate theorem for each formula), there is a proper class club of ordinals $\alpha$ for which $\varphi$ is absolute between $V_\alpha$ and $V$. Thus, we define that $x\in \text{OD}$ just in case there is $\alpha$ such that $x$ is definable in the structure $\langle V_\alpha,{\in}\rangle$ with ordinal parameters (this is expressible since $V_\alpha$ is a set and so we may refer to truth in it). The point now is that if $x$ is ordinal definable by some formula in $V$, then this will reflect to some $V_\alpha$, and so $x$ will be placed into OD. And conversely, if we think that $x$ is ordinal definable in $V_\alpha$, then by using those parameters, plus $\alpha$, plus the Gödel code of the formula, we can define $x$ from ordinal parameters in $V$.

In regard to question 3, the analysis shows that every set in OD is actually $\Delta_2$-definable from ordinals, since if $x$ is defined by some formula $\varphi(\cdot,\vec \alpha)$, then we may fix a $\beta$ above $\vec\alpha$ for which $\varphi$ is absolute between $V_\beta$ and $V$, and note that $x$ is definable inside $V_\beta$ by $\varphi(\cdot,\vec\alpha)$. But now we can define $x$ in $V$ using parameter $\beta$ as "the set defined in $V_\beta$ by $\varphi(\cdot,\vec\alpha)$." This can be expressed as a $\Sigma_2$ assertion and also as a $\Pi_2$ assertion, using parameters $\vec\alpha,\beta$ and $\varphi$. And so we thereby bring the complexity of the definition down. The amusing thing, now, is that we have thereby reduced definability to a case for which we do have a Tarskian truth predicate, since there is a $\Sigma_n$-expressible truth predicate for $\Sigma_n$ truth.

One can generalize beyond ordinal definability, provided that one has these essential features. Namely, if $Z$ is a class of parameters, including the natural numbers, such that we have a definable map $z\mapsto M_z$, for $z\in Z$, which reflect truth from $V$, in the sense first, that the union of all $M_z$ is $V$, and that for any formula $\varphi$ there are sufficiently large $M_z$ where $\varphi$ is absolute between $M_z$ and $V$. We can then define that $x$ is $Z$-definable, if $x$ is definable in some $M_z$ using parameters from $Z$.

In the case of ordinal definability, the structures are $\alpha\mapsto V_\alpha$. One could use regular-cardinal-definability, via $\kappa\mapsto H_{\kappa^+}$, but this would give the same OD notion. Although it will always be fine to refer to a larger definable class of parameters than the ordinals, there aren't any strictly smaller classes of parameters to my knowledge that give a distinct notion of definability than ordinal-definability.

• Another relevant remark is that, in the presence of appropriate large cardinals, one can have full truth predicates (and therefore be able to formalize definability) for certain inner models, which in practice may suffice for one's purposes. – Andrés E. Caicedo Nov 2 '13 at 18:28
• Thanks a lot! This answers to a great part my questions #1 and #2. But what about questions #3 and #4 (including the side question)? Have you answered them implicitly (and I just didn't recognize)? – Hans-Peter Stricker Nov 2 '13 at 18:35
• Does my edit answer question 3 for you? We don't actually need complicated formulas to define sets in OD. – Joel David Hamkins Nov 2 '13 at 18:36
• It does! (My comment was on hold for too long.) – Hans-Peter Stricker Nov 2 '13 at 18:41
• Indeed, if he had changed the first letter of the first word, and the second letter of the second word, and so on, then we could be more sure of his identity... – Joel David Hamkins Nov 2 '13 at 20:10

With respect to question 3: one way to do this is to restrict the quantifier complexity of the formulas. That is, for every constant $k$, one can define a formula $\delta_k(x)$ expressing “$x$ is definable by a $\Sigma_k$-formula with parameters”. Here, a formula $\phi(\vec x)$ is $\Sigma_k$ (in the Lévy hierarchy) if it can be written in the form $\exists y_1\,\forall y_2\,\exists y_3\,\dots Qy_k\,\theta(\vec x,\vec y)$, where all quantifiers in $\theta$ are bounded.

$\def\Tr{\mathrm{Tr}}$EDIT: Let me clarify how exactly $\Sigma_k$-formulas can be used to answer question 3. What I wrote above is true, but useless by itself, because definability of sets by formulas allowing arbitrary parameters is not an interesting notion (every set is trivially definable from itself as a parameter). But the Lévy hierarchy provides more than that:

• For every $k>0$, there is a truth definition for $\Sigma_k$-formulas, which is itself $\Sigma_k$. That is, there is a $\Sigma_k$-formula $\Tr_k(n,x)$ such that ZF proves $$\phi(x)\leftrightarrow\Tr_k(\ulcorner\phi\urcorner,x)$$ for every $\Sigma_k$-formula $\phi(x)$, where $\ulcorner\phi\urcorner$ is the Gödel number of $\phi$. This is essentially optimal: if a class of formulas has a truth definition, it is up to equivalence included in some $\Sigma_k$ (because the truth definition itself is in $\Sigma_k$ for some $k$).

• If $k>0$, and $X$ is a class of possible parameters which includes $\omega$ and is closed under pairing (that is, $X\times X\subseteq X$), there is a formula $\delta(x)$ which expresses “$x$ is $\Sigma_k$-definable using parameters from $X$”, namely $$\delta(x)=\exists n\in\omega\,\exists z\in X\,\forall y\,(y\in x\eq\Tr_k(n,\langle y,z\rangle)).$$ (Here, the pairing operation on $X$ does not have to be the standard Kuratowski pair. For example, one can define an injection $\mathrm{Ord}\times\mathrm{Ord}\to\mathrm{Ord}$, which allows us to take $X=\mathrm{Ord}$, so this generalizes ordinal definability. Also, I believe the assumption $\omega\subseteq X$ is redundant as long as $|X|\ge2$, because one can reconstruct a suitable copy of $\omega$ inside $X$ using the pairing operation.)

• I observe that en.wikipedia.org/wiki/L%C3%A9vy_hierarchy is in dire need of fixing. – Emil Jeřábek supports Monica Nov 2 '13 at 18:31
• And indeed, when $k\geq 2$, then the ordinal definable $\Sigma_k$ sets agree with the OD sets. – Joel David Hamkins Nov 2 '13 at 18:37
• Judging from your recent comments, it would seem that you and me interpret question 3 in a different way. My reading is that Hans is asking for restrictions on formulas that ensure a definable notion of definability without requiring parameters to be ordinals. – Emil Jeřábek supports Monica Nov 2 '13 at 18:42
• @Emil: You are right, that's what I was asking for. – Hans-Peter Stricker Nov 2 '13 at 18:43