Question

Let $\Sigma$ be a one-sorted first-order signature, let $A$ be a $\Sigma$-structure, and let $B \subseteq A$ be a $\Sigma$-substructure. Fix a class $\mathcal{L}$ of formulae over $\Sigma$. We say an element $a$ in $A$ is $\mathcal{L}$-definable over $B$ just if there is some formula $\phi (x, \vec{y})$ in $\mathcal{L}$ such that $A \vDash \phi [a, \vec{b}] \land (\phi [x, \vec{b}] \to (x = a))$ for some finite sequence $\vec{b}$ of elements of $B$; and we say two elements $a, a'$ in $A$ are $\mathcal{L}$-indiscernible over $B$ just if $A \vDash \phi [a, \vec{b}] \leftrightarrow \phi [a', \vec{b}]$ for all formulae $\phi$ in $\mathcal{L}$ and all finite sequences $\vec{b}$ of elements in $B$.

Question. What conditions can we put on $A$, $B$, $\mathcal{L}$, and/or $\Sigma$ so that that an element $a$ is not $\mathcal{L}$-definable over $B$ if and only if there exists $a'$ such that $a$ and $a'$ are $\mathcal{L}$-indiscernible over $B$?

According to Hodges [Model theory, Lem. 4.1.3], if $\mathcal{L}$ is the class of $L_{\omega_1, \omega}$ formulae over $\Sigma$ and $A$ is countable, then non-definability and indiscernibility coincide in the sense described above. However, the proof of the lemma relies entirely on Scott's theorem [Cor. 3.5.4], and it is not clear to me whether this can be generalised. (Hodges [Shorter model theory, just before Thm 3.2.5] says that there is no known satisfactory analogue for uncountable cardinalities.)

I am primarily interested in the case where $\mathcal{L}$ is the class of regular formulae over $\Sigma$, i.e. the smallest class containing the atomic formulae (not including $\bot$) and closed under finite conjunctions (including $\top$) and existential quantification. I do know that there are non-trivial examples when $\mathcal{L}$ is the class of equations: the fundamental theorem of Galois theory implies that non-definability and indiscernibility coincide when $A$ is a Galois extension of $B$.

Answer 1

Here is one fairly general thing to say:

• If $A$ is $\kappa$-saturated and $B$ has size less than $\kappa$, then every element $a\in A$ that is not first-order definable in $A$ using parameters in $B$ will be part of an indiscernible pair, and conversely.

The reason is that if $a$ is not definable in $A$ over $B$, then every finite collection of assertions $\varphi(a,\vec b)$ true in $A$ are also true of some $x\neq a$. So by saturation, that type will be realized by some $a'$, which will be indiscernible from $a$ in $A$ over $B$. Conversely, an element $a$ that is part of an indiscernible pair can never be definable.

There are many weakenings and refinements of the saturation property, and I would expect that the model theorists will be able to say much more.