Degrees of indiscernibles in decidable models
Hal A. Kierstead, Jeffrey B. Remmel · Transactions of the American Mathematical Society · 1985
We show that the problem of finding an infinite set of indiscernibles in an arbitrary decidable model of a first order theory is essentially equivalent to the problem of finding an infinite path through a recursive ω \omega -branching tree. Similarly, we show that the problem of finding an infinite set of indiscernibles in a decidable model of an ω \omega -categorical theory with decidable atoms is essentially equivalent to finding an infinite path through a recursive binary tree.