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$. 



Non-definable elements vs indiscernible elements
Here is one fairly general thing to say:


* If $A$ is [$\kappa$-saturated](http://en.wikipedia.org/wiki/Saturated_model) 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.


