Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
In order to make the question precise, you'll need to explain what you mean by "equivalent" and what you mean by "universally true or universally false". –  Carl Mummert Sep 24 '11 at 23:39
@Carl : Indeed. I updated the post accordingly. –  Ewan Delanoy Sep 28 '11 at 19:01

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.