# Iterating definability

An odd -- probably basic -- question about model theory:

For $\mathcal{M}$ a structure in a (first-order) signature $\Sigma$, let $\mathcal{M}'$ be the structure in signature $\Sigma\sqcup\lbrace U\rbrace$ -- with $U$ a unary relation -- whose reduct to $\Sigma$ is $\mathcal{M}$, and interprets $U$ as $$U^{\mathcal{M}'}=\lbrace a: a\text{ is definable in \mathcal{M}}.\rbrace$$

Up to the choice of unary relation symbol $U$, this is well defined; moreover, we can iterate this through the ordinals: $$\mathcal{M}^{(0)}=\mathcal{M}, \quad \mathcal{M}^{(\alpha+1)}=(\mathcal{M}^{(\alpha)})', \quad \mathcal{M}^{(\lambda)}=\bigcup_{\beta<\lambda}\mathcal{M}^{(\beta)} \,\,(\lambda \text{ limit}).$$ (The union notation is technically inappropriate, but its meaning is clear.) Now, for any $\mathcal{M}$, let $$D(\mathcal{M}, \alpha)=\lbrace a\in\mathcal{M}: a\text{ is definable in \mathcal{M}^{(\alpha)}}\rbrace$$ be the set of elements of $\mathcal{M}$ definable after stage $\alpha$. Let $D(\mathcal{M}, \infty)=\bigcup_{\alpha\in ON} D(\mathcal{M}, \alpha)$ be the set of all eventually definable elements, and for $a\in D(\mathcal{M}, \infty)$ let the age of $a$, $age_\mathcal{M}(a)$, be the least $\beta$ such that $a\in D(\mathcal{M}, \beta)$. Clearly for each $\mathcal{M}$ there is a least upper bound, $m_\mathcal{M}$, on the ages of elements of $D(\mathcal{M}, \infty)$.

Some very easy observations:

• If $\mathcal{M}=(M, <)$ is a well-ordering, then $D(\mathcal{M}, \infty)=M$, since the $\alpha$th element of $\mathcal{M}$ is definable by stage $\alpha$ at the latest.

• Even if $\mathcal{M}$ is strongly minimal, $\mathcal{M}'$ need not be: consider $\mathcal{M}=\mathbb{N}+\mathbb{Z}$ as a linear order. Presumably other niceness properties such as stability are also not preserved, but I don't have examples yet.

My question is, what is known about the set $D(\mathcal{M}, \infty)$, the age function $age_\mathcal{M}$, or the invariant $m_\mathcal{M}$? I've been playing around with this idea for a bit, but my model theory is not very strong; I'm sure this has been treated before, but I haven't been able to find a reference.

(In case anyone is interested, I initially thought that there would be connections with notions of rank, as long as $\mathcal{M}$ is sufficiently nice; in fact, I came up with this question after using some dubious analogies to try to explain forking and rank to a friend. As far as I can tell, this initial hope is in fact bogus, but that's where this came from.)

There are two other questions about this that I'm especially interested in. First, what if we augment first-order logic by adding a logical unary relation $D$ whose interpretation is stipulated to always be $D(\mathcal{M}, \infty)$ -- the resulting model theory seems wild (compactness and Lowenheim-Skolem fail extremely badly), but this logic "comes from" first-order logic in a natural way; is there anything nice we can say about it? Second, this time closer to computability theory: what if we replace "definable" with $\Sigma_1$-definable? Does $m_\mathcal{M}$ now have a recursion-theoretic interpretation? I consider these as just curiosities, compared to the main question (which, though more vague, I hope is still appropriate), but if anyone has anything to say on either count I'd be extremely interested.

-
Very nice idea. Could you clarify: you add another new predicate symbol at each stage? So we have in effect $U^{(\alpha)}$ for each ordinal $\alpha$, and the "union" that you mention for $\mathcal{M}^{(\lambda)}$ is an expansion of $\mathcal{M}$ with $\lambda$ many separate predicates? –  Joel David Hamkins Jul 16 '13 at 13:52
I doubt that much can be said from the model-theory side. Note that you can start with a structure $M$ and construct a structure $M'$ in which you replace each element of $M$ by infinitely many indistinguishable copies of it and add an equivalence relation whose quotient is $M$. Then no element is definable. Now add constants to name an arbitrary set of elements. Your construction will stop at the first stage and end up adding a predicate for the named constants, which could be an arbitrary set. –  Pierre Simon Jul 16 '13 at 16:37
Start with $M$ the complex field. Then $M^\prime$ is the complex field with a predicate for the rational numbers. It's easy to see that any irrational element of $M^\prime$ can be moved by an automorphism, so the iteration stops here. Note that in this example $M^\prime$ is unstable. –  Dave Marker Jul 16 '13 at 21:10
@Joel: yes, a new predicate symbol is added at every stage, and the union is just the expansion you describe. –  Noah Schweber Jul 17 '13 at 1:09

Rather than adding a predicate for definability, the idea in these theories, acknowledging Tarski's nondefinability theorem that one cannot have a full classical theory of truth in the language with that truth predicate, is that nevertheless one may build an increasingly robust theory of truth, in a transfinite progression, by successively adding truth predicates over the expanded structure that has been defined so far. One starts with an initial structure $\mathcal{M}$, and then add a predicate for true-in-$\mathcal{M}$, and then a predicate for truth in that structure, and so on transfinitely.
To be precise, if $\mathcal{M}^{(0)}$ is a structure that interprets arithmetic, so one can refer to formulas via Gödel coding, then we define the truth predicate $T^{(0)}$ for this model, where $T^{(0)}(\varphi,\vec a)$ holds if and only if $\mathcal{M}^{(0)}\models\varphi[\vec a]$, where $\varphi$ is any formula in the language of $\mathcal{M}^{(0)}$. Adjoining this new predicate, we form the next structure $\mathcal{M}^{(1)}=\langle M,\ldots,T^{(0)}\rangle$, and then continue the construction just as you did. At stage $\alpha$, we have the $\alpha^{\rm th}$ structure $\mathcal{M}^{(\alpha)}$, and then form the truth predicate $T^{(\alpha)}$ for satisfaction in this structure. In particular, the predicate $T^{(\alpha)}$ concerns formulas $\varphi$ in the language in which earlier truth predicates $T^{(\beta)}$ appear as formal predicates.