# When is a first-order formula is existential and when is it universal?

So I have a few questions about determining which formula it is:

So if a binary predicate symbol $X$ denotes an edge between two variables, say $x$ and $y$, for the following formulas

• Why is $\forall x \exists y\,(X[xy]\lor X[yx])$ universal and $\exists x \forall y\,(X[xy]\lor X[yx])$ existential? I mean for the second formula all $y$ are within the scope of $\forall y$, so shouldn't it be universal as well?

• And if you have a formula like this: $(\exists x X[xy]) \odot X[yx]$, where $\odot$ denotes an arbitrary binary connective, would this be a binary connective formula or an existential formula?

Thanks.

• Could you please tell us exactly what definition of "existential/universal formula" you are using? Usually, one defines a formula $\alpha(a_1,\dots, a_k)$ to be existential if it is in the form $\exists r_1 \cdots \exists r_m \beta(a_1,\dots,a_k, r_1,\dots,r_m)$ where $\beta$ is quantifier-free, same for universal formulas. According to this definition, your formulas would be neither existential nor universal. – quicksort Jan 18 '17 at 14:19

## 2 Answers

The key to the usage is to transform the formula to an equivalent formula that is in prenex form.

A formula $F$ is in prenex form if $F \equiv Q_1 x_1 ...Q_m x_m\; G$ where $G$ is a quantifier free formula and $Q_1,...,Q_m$ are quantifiers.

A formula $F$ is universal if it is equivalent to a formula in prenex form that has only universal quantifiers.

There is an important model theoretic property of universal formulas: a universal formula that is satisfiable in some structure $S$ is also satisfiable in any substructure $P$ of $S$.

Why is $\forall x \exists y(X[xy]∨X[yx])$ universal and $\exists x \forall y(X[xy]∨X[yx])$ existential? I mean for the second formula all $y$ are within the scope of $\forall y$, so shouldn't it be universal as well?

Either sentence is neither universal nor existential. One can easily come up with an example structure where $F\equiv\forall x \exists y(X[xy]∨X[yx])$ is true but is not true for a substructure.

Let $S=\{0,1\}$ and $X[xy]\equiv x\not=y$, then F is true in $S$ but is not true for any one-element substructure of $S$.

Now for the second question

And if you have a formula like this: $H\equiv(\exists x X[xy])⊙X[yx]$, where ⊙ denotes an arbitrary binary connective, would this be a binary connective formula or an existential formula?

In order to find the prenex form we rename the variable $x$ in the scope of the existential quantifier to get $H'\equiv(\exists z X[zy])⊙X[yx]$.

Now suppose $⊙$ is disjunction or conjunction then we can consider an equivalent formula $H''\equiv\exists z X[zy]⊙X[yx]$ that is in prenex form and is an existential formula.

However if $⊙$ were an implication then the formula $H$ would be equivalent to $H'''\equiv\forall z X[zy] \Rightarrow X[yx]$. The formula $H'''$ is clearly a universal formula.

why is AxEy(X[xy]vX[yx]) Universal and ExAy(X[xy]vX[yx]) existential?

The first formula translates to:

"For all x, there exists a y such that..."

The second formula translates to:

"There exists an x for which all y..."

In other words, the outermost denominator determines whether the formula is universal or existential (if it has a global scope). As you can see above, interchanging the place of the quantifiers changes the meaning of the formula.

I mean for the second formula all y are within the scope of Ay, so it should be universal as well??

The formula states that there exists an x for which all y (within that subset) share a property, not that all y in the universe share that property.

And if you have a formula like this:

(Ex X[xy]) V (X[yx]),

where V denotes a binary connective, would this be a binsary connective formula >or an existential formula?

Essentially, this formula isn't necessarily existential or universal since there is no shared global scope.

What it translates to (if for example we take V to be OR) is:

"There exists an x which has an edge between x and y OR there is an edge between y and x".

To answer the question; this is a combination of two formulas, the first of which is existential (denoted by the E) and the second of which is atomic with a truth-value that is determined by the meaning of x and y (as they are free variables since they do not fall under the scope of a quantifier).

• You cannot randomly interchange quantifiers, that's simply a rule of FOL. There are rules for interchanging but they generally involve negation (i.e. ~ExP then AxP). This doesn't follow from the fact that the outer quantifier determines whether a formula is universal or existential, but then again I didn't claim that (it was merely used to explain why you cannot interchange at will as it leads to a different formula). – DeBunkeD Jan 18 '17 at 14:20
• I've clarified the post in your favour. – DeBunkeD Jan 18 '17 at 14:33