3
$\begingroup$

Consider the following variant of the Lévy hierarchy on formulas : let $\Phi$ be the set of all meaningful formulas on the alphabet $\in,=,\vee,\wedge,(,),\neg,\exists,\forall$ and a countable set of variables $x_1,x_2, \ldots$. Let $\Sigma_0=\Pi_0$ consists of all formulas in $\Phi$ without quantifiers at all (in the usual Lévy hierarchy, we would replace this with bounded quantifiers), and by induction, let $\Sigma_n$ be the set of formulas of the form $\exists t_1 \exists t_2 \ldots \exists t_r \psi$ where $\psi$ is in $\Pi_{n-1}$, and let $\Pi_n$ be the set of formulas of the form $\forall t_1 \forall t_2 \ldots \forall t_r \psi$ where $\psi$ is in $\Sigma_{n-1}$.

Now let $\Delta$ be the set of sentences that are equivalent to some $\Sigma_1$ formula and equivalent also to some $\Pi_1$ formula at the same time (here "equivalent" means provably equivalent : I say that $\phi$ is equivalent to $\psi$ when $\phi \Leftrightarrow \psi$ is a theorem of ZFC). For example, if $\phi$ is an universally false sentence (i.e. $\neg \phi$ is a theorem of ZFC), we have $\phi \Leftrightarrow \exists x\ (x \neq x)$ and $\phi \Leftrightarrow \forall x\ (x \neq x)$, so that $\phi$ is in $\Delta_1$. Are there other sentences in $\Delta_1$ besides the universally true or universally false ones?

  • 0
    @Ca$r$l : Indeed. I updated the post acco$r$dingl$y$.2011-09-28

1 Answers 1

5

If "equivalent" just means "logically equivalent" then the answer is that any $\Delta_1$ sentence $\phi$ is either true in every structure or false in every structure. From elementary model theory, we know that because $\phi$ is logically equivalent to an existential formula, it is preserved under taking superstructures. Because it is logically equivalent to a universal formula, it is preserved under taking substructures.

Let $A$, $B$ be any two structures for your language. Then the "disjoint union" $C$ of $A$ and $B$ is a superstructure of both, where you rename the elements of $B$ if necessary so that $|A| \cap |B| = \emptyset$ and then you let $\in^C$ be $\in^A \cup \in^B$. Therefore $\phi$ has the same truth value in $A$ and $B$ because $B$ is a substructure of a superstructure of $A$.

The same thing works for any first-order language if we take "equivalent" to mean "logically equivalent" and we take "universally true" to mean "true in every structure for the language", without requiring that the structures have to satisfy any particular theory.