# The type of nondefinable elements-2

Consider a countable transitive model $\mathfrak{M}$ of set theory.

Let $X$ be a definable collection of sets of reals.

My question is: is the type of nondefinable elements in $X$ is definable over $Th(\mathfrak{M})$ or not.

(I assume that $X$ is infinite.)

PS: note that the type of nondefinable elements of $X$ is the type $p(x)$ containing all statements of the form: $$\varphi(x) \rightarrow \exists y \neq x \; \varphi(y),$$ for every formula $\varphi(x)$, plus the formula defining $X$.

It depends on $\mathcal{M}$ and on $X$. I take your question to ask whether there is a formula $\phi(x)$ without parameters such that whenever $\mathcal{N}$ has the same theory as $\mathcal{M}$, then $\mathcal{N}\models\phi(A)$ just in case $A\in X^{\mathcal{N}}$ and $A$ is not definable in $\mathcal{N}$.

First, let's describe how it can happen that $\mathcal{M}$ and $X$ admit no such formula $\varphi$. I mentioned this idea in a comment on your earlier question. Suppose that $\mathcal{M}$ is pointwise definable, so that every element of $\mathcal{M}$ is definable without parameters in $\mathcal{M}$, and suppose that $X$ is infinite (it is fine for it to be finite inside $\mathcal{M}$, as long as it is not finite in the meta-theory). In this case, I claim that there can be no such formula $\varphi$. The reason is that every element of $\mathcal{M}$ is definable, and so it must be that $\forall x\neg\varphi(x)$ is true in $\mathcal{M}$ and therefore part of the theory of $\mathcal{M}$. But meanwhile, since $X$ is infinite, there will be elementary extensions $\mathcal{M}\prec\mathcal{N}$ having new elements of $X$, which by elementarity must not be definable. So $\varphi$ will fail to hold of these new non-definable elements of $X$ in $\mathcal{N}$.-

Second, let's describe a positive example, a case for which there is such a formula $\varphi$. Suppose $\mathcal{M}$ does not satisfy $V=\text{HOD}$ and furthermore, that there are sets of reals in $\mathcal{M}$ outside of $\text{HOD}^\mathcal{M}$. This situation can be easily arranged by forcing. Let $X$ be the collection of sets of reals not in $\text{HOD}$. Our assumptions ensure that this is an infinite definable set, but no elements of $X$ are definable, since none are even in $\text{HOD}$, and this fact will be part of the theory of $\mathcal{M}$. So the collection of non-definable elements of $X$ is defined by membership in $X$ and the formula $x=x$, since all elements of $X$ are all non-definable.

The examples illustrate the following general solution.

Theorem. The following are equivalent for any first-order structure $\mathcal{M}$ and any definable set $X$ in $\mathcal{M}$.

1. The type of being a non-definable element of $X$ is principal over $\text{Th}(\mathcal{M})$.

2. The collection of elements of $X$ that are definable in $\mathcal{M}$ is finite. (That is, finite in the meta-theory, considered externally to $\mathcal{M}$)

Proof. ($2\to 1$) If $a_0,\ldots,a_k$ are the definable elements of $X$ in $\mathcal{M}$, where $a_i$ is the unique satisfying instance in $\mathcal{M}$ of $\psi_i(a_i)$, then the non-definable elements of $X$ are exactly the satisfying instances $x$ of the formula: $x\in X\wedge \bigwedge_i\neg\psi_i(x)$. So in this case, the type is definable over the theory of $\mathcal{M}$.

($1\to 2$). Assume toward contradiction that $X$ has infinitely many definable elements in $\mathcal{M}$ and that the non-definability type is principal with the formula $\varphi(x)$, meaning that $\varphi(x)$ is true exactly of the non-definable elements of $X$ in any model elementarily equivalent to $\mathcal{M}$. Consider the theory asserting the theory of $\mathcal{M}$ plus $c\in X\wedge\neg\varphi(c)$ plus $\neg\psi(c)$, where $\psi$ is any formula defining an element of $X$ in $\mathcal{M}$. This theory is consistent, since any finite subset of the theory can be realized in $\mathcal{M}$. Thus, it has a model $\mathcal{N}$. But this model has the object $c$, which is in $X$ and does not satisfy the definition of any definable element of $X$, but also fails $\varphi$. So $c$ is not definable and fails $\varphi$, contradicting our assumption on $\varphi$. QED

So this is a general model-theoretic fact having nothing to do with models of set theory or sets of reals.

• If we know that $X$ is nonempty in HOD ($X$ infinite), and ask if the type of nondefinable elements of $X$ over the theory of $\mathcal{M}$ (where $\mathcal{M}$ is another model of set theory) is principal, do we have an answer? – user38200 Dec 4 '13 at 15:43
• I don't understand your question. What do you mean by "$X$ is nonempty in HOD"? And what do you mean when you say that $\mathcal{M}$ is another model of set theory? Are you referring to the HOD of $\mathcal{M}$? And $x\in\mathcal{M}$? – Joel David Hamkins Dec 4 '13 at 15:46
• I mean that $X$ is definable from ordinals and reals in $\mathcal{M}$, and that a $X$ is definable in $\mathcal{N}$ (where $V=HOD$ in $\mathcal{N}$) by the same formula. And $X$ is nonempty in both models – user38200 Dec 4 '13 at 15:51
• Your question seems to be a moving target. If the definition of $X$ has parameters, it doesn't make sense to use the same definition in $\mathcal{N}$, unless those parameters are also there. And if you don't say something about how the theory of $\mathcal{M}$ and $\mathcal{N}$ are related, then basically anything can happen, since the definition might be: If CH holds, then one thing, but otherwise something else. In this case, $\mathcal{M}$ and $\mathcal{N}$ can think totally different things about $X$. – Joel David Hamkins Dec 4 '13 at 15:55