$\Delta_1^1\stackrel{?}{=}FOL$

114 Views Asked by At

Let $\varphi$ be a sentence in second order logic that happens to be in $\Sigma_1^1\cap\Pi_1^1(=:\Delta_1^1)$. It is claimed, that $\varphi$ be equivalent to a sentence in first order logic. Is this true? If so, how does one show this?


Update. Thanks, Andreas. The approach with Interpolators works, now I can rest assured that $FOL=\Delta_{1}^{1}$.

1

There are 1 best solutions below

3
On

This is a consequence of Craig's Interpolation Lemma. Suppose (to simplify notation) that the $\Sigma^1_1$ form of $\phi$ is $(\exists X)\,\alpha(X)$ and the $\Pi^1_1$ form is $(\forall Y)\,\beta(Y)$, where $\alpha(X)$ and $\beta(Y)$ are essentially first-order formulas except that they involve the second-order variables $X$ and $Y$, respectively. (In general, there could be several $X$'s and several $Y$'s but that doesn't affect the idea, only the notation.) Note that we could also consider $\alpha(X)$ and $\beta(Y)$ to be honest first-order sentences, in a vocabulary (= language = signature) that has $X$ and $Y$ as new predicate symbols. The fact that $(\exists X)\,\alpha(X)$ implies $(\forall Y)\,\beta(Y)$ in second-order logic means exactly the same as saying that the implication $\alpha(X)\to\beta(Y)$ is valid in the sense of first-order logic. Now Craig's Lemma provides a first-order formula $\theta$, in which neither $X$ nor $Y$ occurs, such that both $\alpha(X)\to\theta$ and $\theta\to\beta(Y)$ are valid. Translating that information back to the framework of second-order logic, we find that $(\exists X)\,\alpha(X)$ logically implies $\theta$, which in turn logically implies $(\forall Y)\,\beta(Y)$. But, by hypothesis, $(\exists X)\,\alpha(X)$ and $(\forall Y)\,\beta(Y)$ are logically equivalent (because they're both equivalent to the original $\phi$), and so $\theta$ is also equivalent to them.