0
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – quicksort
    Jan 18, 2017 at 14:19

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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).

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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). $\endgroup$
    – DeBunkeD
    Jan 18, 2017 at 14:20
  • 1
    $\begingroup$ I've clarified the post in your favour. $\endgroup$
    – DeBunkeD
    Jan 18, 2017 at 14:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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