2
$\begingroup$

I am finding it quiet understand the scope of a quantifier, and some other concepts of logic.

For example the below the scenarios below:

Scenario 1) (∀y H(y) → ∃z W(z, y)) → ∃z G(z)

Question: Is the "y" in the above formula being scoped by universal quantifier ∀y ?

Scenario 2) ∃y(∀y H(y) → ∃z W(z, y)) → ∃z G(z)

Question: Can you have 2 quantifiers, quantifying the same variable i.e."y" for scenario 2 ?

Scenario 3) (∀y H(y) → ∃z G(z)) → ∃z W(z, y)

Question :

Is the "y" in the "∃z W(z, y)" of the above formula considered to be free ?

Scenario 4) (∀z H(y) → ∃y W(z, y)) → ∃z G(z)

Question: What would be the scope for the scenario above ?

Scenario 5) (∀y H(y) → ∃z∃y W(z, y)) → ∃z G(z)

Question: What would be the scope for the scenario above ?

Scenario 6) (∀y H(y) → ∃z W(z, y)) → ∃x G(z)

Question: What would be the scope for the scenario above ?

Detail for each question will be highly welcomed.

Thanks in advance.

$\endgroup$
2
  • 1
    $\begingroup$ Too many questions. Regarding the first one, you ask about "the $y$", but there are two of them and the answer depends on which you mean. The answer to the second question is yes: the first $y$ is bound by the universal quantifier, the second by the existential one. The answer to the third one is yes. Concerning questions 4, 5 and 6: scope of what? $\endgroup$
    – Git Gud
    Dec 24 '16 at 20:21
  • 1
    $\begingroup$ Review the basic definition : Scope of a Quantifier. $\endgroup$ Dec 24 '16 at 20:36
9
$\begingroup$

It's often a matter of parentheses:

In a formula like $\forall y P(y)$ the $y$ in $P(y)$ is within the scope of the $\forall y$, but in a formula like $\forall y Q(x) \land P(y)$ it is not, since this formula would be parsed as being a conjunction, whose left conjunct is $\forall y Q(x)$, and right conjunct being $P(y)$, i.e. they get 'separated'. If you want the $y$ to be within the scope, you'd need to use parentheses: $\forall y (Q(x) \land P(y))$, and indeed now you are dealing with a universal statement.

Let me use colors to indicate the scope in each of your sentences:

Scenario 1) $(\color{red}{∀y }H(\color{red}{y}) → \color{blue}{∃z} W(\color{blue}{z}, y)) → \color{green}{∃z} G(\color{green}{z})$

Question: Is the "y" in the above formula being scoped by universal quantifier ∀y ?

=> first $y$ yes, second one not

Scenario 2) $\color{red}{∃y}(\color{blue}{∀y} H(\color{blue}{y}) → \color{green}{∃z} W(\color{green}{z}, \color{red}{y})) → \color{yellow}{∃z} G(\color{yellow}{z})$

Question: Can you have 2 quantifiers, quantifying the same variable i.e."y" for scenario 2 ?

=> You can never have a variable quantified by two quantifiers ... if a variable falls within the scope of multiple quantifiers for the variable, then it is only quantified by the most 'inside' one

Scenario 3) $(\color{red}{∀y} H(\color{red}{y}) → \color{blue}{∃z} G(\color{blue}{z})) → \color{green}{∃z} W(\color{green}{z}, y)$

Question :

Is the "y" in the "∃z W(z, y)" of the above formula considered to be free ?

=> Correct

Scenario 4) $(\color{red}{∀z} H(y) → \color{blue}{∃y} W(z, \color{blue}{y})) → \color{green}{∃z} G(\color{green}{z})$

Question: What would be the scope for the scenario above ?

=> in all cases, the quantifiers merely quantify the atomic formula right after it. Thus, both the first $y$ and the second $z$ are free.

Scenario 5) $(\color{red}{∀y} H(\color{red}{y}) → \color{blue}{∃z}\color{green}{∃y} W(\color{blue}{z}, \color{green}{y})) → \color{yellow}{∃z} G(\color{yellow}{z})$

=> Again, in all cases, the quantifiers merely quantify the atomic formula right after it.

Question: What would be the scope for the scenario above ?

Scenario 6) $(\color{red}{∀y} H(\color{red}{y}) → \color{blue}{∃z} W(\color{blue}{z}, y)) → \color{green}{∃x} G(\color{green}{z})$

Question: What would be the scope for the scenario above ?

=> And once again, in all cases, the quantifiers merely quantify the atomic formula right after it. So the second $y$ is free.

$\endgroup$
4
  • $\begingroup$ Thank you so much for your in-depth analysis of the scenario. Literally, have cleared up all mis-conceptions. $\endgroup$ Dec 25 '16 at 20:27
  • $\begingroup$ Example 1: ∀yH(y) Example 2: ∀y(H(y) v D(y)) Example 3: ∀y(H(x,y) v D(y)) All these "y" are bound to the universal quantifier, the only variable not bound is the "x" in Example 3. $\endgroup$ Dec 25 '16 at 20:43
  • $\begingroup$ Summary - For a variable to be bound it needs to be quantified by a quantifier immediately before it. The only instance this does not hold would be the case were ∃y(∀yH(y)→∃zW(z,y)) . As the “y” for “H(y)” is being quantified by “∀y” and the “y” for “∃zW(z,y)” being quantified by “∃y” . In essence, couldn’t the formula original formula be re-written like this “ ∃y(∀xH(x)→∃zW(z,y)). $\endgroup$ Dec 25 '16 at 20:50
  • 1
    $\begingroup$ @JackRoberts Yes, all correct! $\endgroup$
    – Bram28
    Dec 26 '16 at 8:16

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.