Predicate Formulae: Bound and Free

Question

(P(x, y) ∨ (∀x (∃y (Q(x) → R(x, y,z)))))

I know that for P(x,y), x and y are free because there are no quantifiers. But for (∀x (∃y (Q(x) → R(x, y,z)))), x and y are are bounded, and z is free.

In this case, which occurrences of each variable in the tree are bound and which are free?

Answer 1

As you say corrcetly, in the subformula $P(x,y)$ the occurrences of $x$ and $y$ are both free.

For:

$∀x \ (∃y \ (Q(x) → R(x, y, z)))$,

we have that only $z$ has a free occurrence.

The parentheses "define" the scope of the quantifiers. The scope of $\forall x$ is the formula: $∃y \ (Q(x) → R(x, y, z))$. Thus, both occurrences of $x$ in it are bound.

The same for $\exists y$, having scope: $Q(x) → R(x, y, z)$.

---

We may define formally:

Consider any variable $x$. For each formula $\alpha$, we define what it means for $x$ to occur free in $\alpha$:

1. For atomic $α, x$ occurs free in $α$ iff $x$ occurs in $α$.

2. $x$ occurs free in $(¬α)$ iff $x$ occurs free in $α$.

3. $x$ occurs free in $(α → β)$ iff $x$ occurs free in $α$ or in $β$ [and the same for the others binary connectives].

4. $x$ occurs free in $(∀y \ α)$ iff $x$ occurs free in $α$ and $x \ne y$ [and the same for $\exists$].

---

If you use a parsing tree to analyze your formula, you will have $\lor$ as the root and the subformula $P(x,y)$ as left leaf.

$P(x,y)$ is not in the scope of any quantifier, and thus all occurrences of variables in it a free.

On the right branch we will find the node $\forall x$, and thus all occurrences of $x$ in the sub-tree starting from it will be in its scope, and thus will be bound.

And so on.