2
$\begingroup$

I'm having a little trouble understanding the below predicate formula:

$$\exists x P(x, y) \rightarrow Q(x) $$

So if I understand it correctly, the scope of the existential quantifier is $P(x,y)$.

Anything variable that is within the scope of a quantifier or right next to the quantifier symbol, as is the case of x. It is bound. Is this correct?

If so, y is in the scope of $\exists x$ right? Or is it not, because the quantifier is just concerned with the x variable?

$\endgroup$
  • 2
    $\begingroup$ $y$ is certainly a free variable, unaffected by the quantifier. Whether the occurrence of $x$ in $Q(x)$ is bound or free depends on the rules your book uses for the scope of quantifiers, which are not the same everywhere. It's reasonable to assume that the $x$ in $Q(x)$ is bound, but you should really check what your book says. $\endgroup$ – Fabio Somenzi Jan 11 '17 at 6:29
  • $\begingroup$ Consider a formula $\psi$ and an occurrence of a quantifier $∀x$ or $∃x$ in $\psi$. The scope of this occurrence is the subformula of $\psi$ that starts at this occurrence. Thus, if $\psi$ is $\exists xP(x,y) \to Q(x)$ and we consider the occurrence of $\exists x$, then its scope is the subformula $\exists xP(x,y)$. $\endgroup$ – Mauro ALLEGRANZA Jan 11 '17 at 6:58
  • $\begingroup$ We say that an occurrence of a variable $x$ in $\psi$ is bound in $\psi$ if it lies within the scope of a quantifier $∀x$ or $∃x$ with the same variable $x$. We say that the occurrence is free in $\psi$ if it is not bound in $\psi$. Thus the occurrence of $x$ is $P(x,y)$ is bound, because it is in the scope of $∃x$, while the occurrence of $x$ in $Q(x)$ is free. Obviously, $y$ is free, because it is not in the scope of any quantifier $∀y$ or $∃y$. $\endgroup$ – Mauro ALLEGRANZA Jan 11 '17 at 7:02

Your Answer

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

Browse other questions tagged or ask your own question.