Does satisfaction at all arithmetical sets of a second-order arithmetic formula with no bound predicate variables imply its satisfaction?

Question

Let $\varphi(X_1,\ldots,X_r)$ be a second-order arithmetic formula with no bound predicate variables and free predicate variables $X_1,\ldots,X_r$ (all of arity $1$ for simplicity).

Assume every arithmetical instance of $\varphi(X_1,\ldots,X_r)$ is true, that is, for every first-order arithmetic formulas $\psi_1(n),\ldots,\psi_r(n)$ of one free variable, the first-order formula $\varphi(\psi_1,\ldots,\psi_r)$ is true.

Does it follow that $\varphi(X_1,\ldots,X_r)$ is true (in the full model over $\mathbb{N}$)?

Answer 1

Good question! The answer is negative.

Let $\theta(X)$ be the formula saying informally that, when we view $X$ as an $\omega$-by-$\omega$ "array," the first "column" of $X$ is empty and for all $i$ the $(i+1)$th "column" of $X$ is the Turing jump of the $i$th "column" of $X$. Then $\neg\theta(A)$ holds for all arithmetical $A$, but not all sets $A$ in general. Put another way, $\emptyset^{(\omega)}$ is a non-arithmetical set which is an arithmetical (indeed, $\Pi^0_2$) singleton.

Indeed, we can find $\Pi^0_2$ singletons arbitrarily high in the hyperarithmetic hierarchy. If memory serves, Sacks' Higher recursion theory has a good treatment of arithmetical singletons. (Incidentally, a version of this happens in set theory, too, where $0^\sharp$ is $\Delta^1_3$ as a set but $\{0^\sharp\}$ is a $\Pi^1_2$ singleton - see Lemma 25.30 in Jech's big set theory book.)

EDIT: Here's a sketch of $\theta$ in a bit more detail:

$\theta(X)\equiv$ For all $j\in\omega$ we have $\langle 0,j\rangle\not\in X$, and for each $i,j\in\omega$ we have $\langle i+1,j\rangle\in X$ iff there is some $\sigma\in 2^{<\omega}$ such that $(i)$ for all $k<\vert\sigma\vert$ we have $\sigma(k)=1\leftrightarrow \langle i,k\rangle\in X$ and $\Phi_j^\sigma(0)[\vert\sigma\vert]\downarrow$.

Here $\langle\cdot,\cdot\rangle$ is an appropriate pairing function, $\Phi_-^-$ is an appropriate system of oracle Turing machines, and we use the convention that when an oracle machine takes in a finite-length string as an oracle then if it hasn't halted in time at most the length of that string then it goes into an endless loop. We also fix some reasonable coding of finite binary strings by natural numbers. If written out carefully, the above is indeed $\Pi^0_2$.

---

On the other hand, by Gandy's basis theorem if there is a set $X$ satisfying an arithmetical formula $\theta$ over $\mathbb{N}$ then we can find such a set which is "low-for-hyperjump." In particular, Kleene's $\mathcal{O}$ is not an arithmetical singleton.

Answer 2

Here is a different solution.

The answer is no. Consider the statement $\varphi(T)=$"$T$ is not a truth predicate". That is, $T$ is not a set of sentences obeying the Tarski recursion, meaning that it judges correctly all atomic sentences in the language of arithmetic, and it judges a conjunction $\psi\wedge\theta$ true if and only if it judges $\psi$ and $\theta$ true separately; it judges $\neg\psi$ true iff it does not judge $\psi$ true; and it judges $\exists x\psi(x)$ true iff there is some $n$ such that it judges $\psi(\hat n)$ true, where $\hat n$ is the term $1+\cdots+1$ with $n$ summands.

This assertion involves only first-order quantifiers.

By Tarski's theorem, there is no arithmetically definable truth predicate, so every arithmetic instance fulfills $\varphi(T)$, but yet, there is an actual truth predicate.