Search code examples
logicpredicatequantifiersfirst-order-logic

Quantifiers, nesting, scope - free and bound variables

I couldn't find a proper explanation to several questions i have about the scope of quantifiers, free and bound variables.

1) ∃X(p(X,Y) & ∃Y(X,Y)) - I am wondering about the second X. Is it still in the scope of the ∃X quantifier,because it's actually nested under ∃Y? If it is not in the scope of ∃X then is it a free variable? I am thinking it's should be bound to ∃X.
2)∃X(p(Y,Z) & ∃X(q(Y,Z)) - is the second ∃X needed at all? Does it change anything for the free variables Y and Z?

I have more questions of this type but those two bother me the most currently. And answering them might make me get the idea in general and answer myself the next questions.

Also if you have a resource where stuff of this type are explained in detail I will be thankful!

Thank you in advance!

Solution

    1. Yes, the second X is bound by ∃X. (If you had ∃X p(X,Y) & ∃Y(X,Y) instead, it depends on the convention used; in some books it's understood as ∃X(p(X,Y) & ∃Y(X,Y)), in others as (∃X p(X,Y)) & ∃Y(X,Y)).

    2. No, the second ∃X doesn't change anything (the first one doesn't either).

    3. Free extra example: in ∃X(p(Y,Z) & ∃X(q(X,Z)), the outer ∃X doesn't bind anything (and thus removing it gives an equivalent formula) because the only X is already bound by the inner one.