Complexity of Recursively Inseparable Sets

Question

I am interested in examples of recursively inseparable sets. A standard example is the set of positive integers encoding a Turing machine that halts in an odd number of steps on blank input versus integers encoding a TM that halts in an even number of steps. I am hoping to come up with something much simpler to define in FOL. One idea I had was the set of positive integers whose Goodstein's sequence terminates in an odd number of steps versus those whose sequence terminates in an even number of steps. Can the length of Goodstein's sequence be made into a first order statement? Basically, I want to know how simple the definition of recursively inseparable sets can be.

Answer 1

On expressing the length of the Goodstein sequence ...

Let $g(n, k)$ be the $k$-th value in the Goodstein sequence starting at $n$. $g$ is evidently a primitive recursive function (its value can be computed without open-ended searches), so the two-place function can be represented by a three-place $\Sigma_1$ wff arithmetical wff $\mathsf{G(x, y, z)}$.

The length $l$ of the sequence starting from $n$ is the least $k$ such that $g(n, k) = 0$. Formally that gets expressed as $\mathsf{G(n, l, 0) \land \forall y(y < l \to \neg G(n, y, 0)}$.

Is that any help?