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.

  • $\begingroup$ 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? $\endgroup$ – user38200 Dec 4 '13 at 15:43
  • $\begingroup$ 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}$? $\endgroup$ – Joel David Hamkins Dec 4 '13 at 15:46
  • $\begingroup$ 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 $\endgroup$ – user38200 Dec 4 '13 at 15:51
  • $\begingroup$ 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$. $\endgroup$ – Joel David Hamkins Dec 4 '13 at 15:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.