Show that $\textbf{ZF}$ shows $\phi$ is $\Delta_1$

137 Views Asked by At

Fix a $\phi$

Suppose for some finite $S :=\ ${$\psi_1,....\psi_n$},axioms of $\textbf{ZF},$ where

$\textbf{ZF}\vdash\ \forall M$$[(M$ is transitive and $(\psi_1\wedge .....\wedge\psi_n)^{M}$$)\rightarrow \phi$ is absolute for $M$ $]$

$(\psi_1\wedge .....\wedge\psi_n)^{M}$ means the conjunction relativise to $M$

Show that $\textbf{ZF}$ shows $\phi$ is $\Delta_1$

Attempt:

The idea is to use reflection theorem follow by mostowski collapse.

We first reflect $S$ onto some $R(\alpha)$ and apply mostowski collapse to make it transitive,call it $M$, thus by assumption we conclude that $\phi$ is absolute for $M$. But I'm stuck from here on.

Can we conclude absoluteness for $M$ implies $\phi$ must either be $\Delta_0$ or $\Delta_1$ ?

Any help or insight is appreciated.

Cheers

1

There are 1 best solutions below

0
On BEST ANSWER

I think you have missed some assumption on $S$, so I will assume that $S$ is a set of theorems of ZF. For convenience I will assume $S=\{\psi\}$. It does not harm generality.

I claim that $\phi$ is equivalent to $$\forall M :((\text{$M$ is transitive and } \psi^M)\to \phi^M))$$ and $$\exists M :(\text{$M$ is transitive, $\psi^M$ and $\phi^M$})$$ which is $\Pi_1$ and $\Sigma_1$ respectively.

You can see that if $\phi$ holds, then $\phi^M$ holds for all transitive $M$ which satisfies $\psi$. To prove the converse, we should take attendance to a restatement of our assumption: $$\forall M : (\text{$M$ is transitive and $\psi^M$}\to (\lnot\phi\leftrightarrow (\lnot\phi)^M)).$$ From the restatement the converse directly follows: if $\lnot\phi$, then every transitive model $M$ of $\psi$ satisfies $(\lnot\phi)^M$. Therefore, for $M$ is a transitive model of $\psi$ whose existence follows from the reflection principle, we have $\lnot\phi^M$. In short, we have proven the contraposition $$\lnot\phi\implies \exists M :\text{($M$ is transitive, $\psi^M$) and }\lnot\phi^M$$ Hence $\phi$ is equivalent to a $\Pi_1$ sentence.

I will prove the remaining statement, that $\phi$ is equivalent to a $\Sigma_1$ sentence. If $\phi$ holds, and if $M$ is a transitive model of $\psi$ which exists by the reflection theorem, then $\phi^M$. The converse easily follows from our restatement of the assumption mentioned before.