Why is first-order logic (without arithmetic) VALIDITY only recursively enumerable, and not recursive?
However, I am not seeing why VALIDITY is not recursive as well, because given a formula $\phi$, one could run two Turing Machines for THEOREMHOOD, one on $\phi$ and the other on $\neg \phi$, concurrently. Since at least one of them is valid, it is always possible to decide whether $\phi$ is valid, or not valid. What am I missing?


This is wrong. A formula $\phi$ is valid iff it holds in all models.

It is not true that at least one of $\phi$ and $\lnot\phi$ must be valid: both might hold in some models, but not all of them.

Trivial example: take FOL with two constant symbols ${\sf a}, {\sf b}$, and the formula $\phi \equiv {\sf a}={\sf b}$. Then $\phi$ holds in some models (those which interpret $\sf a$ and $\sf b$ with the same point), but not all of them (a model can map them to distinct points). And indeed, FOL can not prove ${\sf a} = {\sf b}$ nor ${\sf a} \neq {\sf b}$.