8
$\begingroup$

Is the term $$\forall x p(x) \rightarrow \forall x q(x)$$ equal to $$\forall x (p(x) \rightarrow \forall x q(x))$$ or $$(\forall x p(x)) \rightarrow (\forall x q(x))$$

In other words: What is the operator precedence of $\forall$ and $\exists$? Does it make a difference?

$\endgroup$
  • 1
    $\begingroup$ You have to use parentheses; $∀x(p(x) \to ∀xq(x))$ is equivalent to : $∃xp(x) \to ∀xq(x)$. Thus, in $∀xp(x) \to ∀xq(x)$ we assume that the scope of the leftmost quantifiers is only $p(x)$. In other words, the quantifiers has the same priority that $\lnot$, i.e. higher than the binary connectives. $\endgroup$ – Mauro ALLEGRANZA Feb 16 '15 at 16:54
  • $\begingroup$ @MauroALLEGRANZA Do you want to say that $\forall x p(x) \rightarrow \forall x q(x)$ is not a valid formula? $\endgroup$ – Martin Thoma Feb 16 '15 at 17:04
  • $\begingroup$ It is, Moose. The second choice is equivalent to your posted statement, but not the first choice you give.$$\forall x p(x) \rightarrow \forall x q(x) \equiv (\forall x p(x)) \rightarrow (\forall x q(x))$$ $\endgroup$ – Namaste Feb 16 '15 at 17:19
  • $\begingroup$ Of course it is admissible; but if you ask if it is "well-formed" you have to check with your specifications. If you ask if is a "correct" abbreviation, my answer is : YES, but I read it as : $((∀xp(x)) → (∀xq(x)))$. $\endgroup$ – Mauro ALLEGRANZA Feb 16 '15 at 17:30
8
$\begingroup$

There is no "precedence" between quantifiers: in a formula like $\forall x \ \exists y \ \varphi$, the "inner" $\exists$ is in the scope of the "outer" $\forall$.

The recursive definition of formula for FOL is (having defined term) more or less this :

(i) $t_1=t_2$ and $P^n(t_1,\ldots,t_n)$ are atomic formulas, where $t_1,\ldots,t_n$ are terms and $P^n$ is a $n$-ary predicate symbol;

(ii) if $\varphi, \psi$ are formulas, then $\lnot \varphi, \varphi \land \psi, \varphi \lor \psi, \varphi \to \psi$ are formulas;

(iv) if $\varphi$ is a formula, then $((∀x)\varphi), ((∃x)\varphi)$ are formulas.

Then we can introduce abbreviations for readibility; see :

For parentheses we will omit mention of just as many as we possibly can. Toward that end we adopt the following conventions:

  1. Outermost parentheses may be dropped. For example, $∀x α → β$ is $(∀x α → β)$.

  2. $\lnot, ∀$, and $∃$ apply to as little as possible. For example,

$¬α ∧ β$ is $((¬α) ∧ β)$, and not $¬(α ∧ β)$;

$∀x α → β$ is $(∀x α → β)$, and not $∀x(α → β)$;

$∃x α ∧ β$ is $(∃x α ∧ β)$, and not $∃x(α ∧ β)$.

In such cases we might even add gratuitous parentheses, as in $(∃x α)∧β$.

  1. ∧ and ∨ apply to as little as possible, subject to item 2. For example, $¬α ∧ β → γ$ is $((¬α) ∧ β) → γ$.

  2. When one connective is used repeatedly, the expression is grouped to the right. For example, $α → β → γ$ is $α → (β → γ)$.

Thus, we have a "formal" specification for the syntax: it must be unambiguous, i.e. "processable" by a machine.

$\endgroup$
  • 2
    $\begingroup$ Thank you for the detailed answer. ((2) was what I needed to know) $\endgroup$ – Martin Thoma Feb 16 '15 at 17:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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