Can you use universal instantiation to equate two universal quantifiers on the same scope?

294 Views Asked by At

As seen in the answer for this question, not every statement can be safely instantiated. For example, given the statement $\forall x P(x)\rightarrow Q$, it does not follow that $P(a) \rightarrow Q$.

Suppose I have the following: $$ \exists A \exists B \forall x \forall y \ \Omega(A,B,x,y) $$

Can I safely instantiate $y$ to be $x$, such that, given the previous statement, the following holds: $$ \exists A \exists B \forall x \ \Omega(A,B,x,x) $$

If not, when can I be sure that it is safe to instantiate?

1

There are 1 best solutions below

1
On BEST ANSWER

The rule for Universal Instantiation is, in general:

$∀xα → α[t/x]$.

This is simply: "if everything is $P$, then $t$ is $P$", for every object $t$.

But there is a proviso: "provided that term $t$ is substitutable for variable $x$ in $\alpha$ that means: provided that term $t$ has no occurrences of variables that will be "captured" by a quantifier in $\alpha$.

This proviso is needed in order to avoid the following fallacy:

from $∀x∃y(x<y)$, derive $∃y(y<y)$.


Regarding the example with $∀x∀y[x=y∨x≠y]$, how can we apply safely UI ?

  1. $∀x∀y[x=y∨x≠y]$ --- premise

  2. $∀y[z=y∨z≠y]$ --- from 1) by UI (we have to instantiate the outermost quantifier first)

  3. $[z=z∨z≠z]$ --- from 2) by UI

  1. $∀z[z=z∨z≠z]$ --- from 3) by UG.

A comment, regarding the order of quantifiers.

In general, $\forall x \forall y \alpha \equiv \forall y \forall x \alpha$, and the same for the existential one.

Thus, in a nutshell for "adjacent" equal quantifiers the order does not matter.

This is not so for $\forall x \exists y$.



A final comment showing why $\forall x P(x) \to Q \nvDash P(a) \to Q$.

Consider the domain $\mathbb N$ of natural numbers, and let $P(x)$ the formula: $(x > 0)$ and let $Q$ the formula $(1=0)$. Finally, let $a$ the term $1$.

We have that $\forall x (x > 0)$ is False in $\mathbb N$ and $(1=0)$ is False also. Thus $\forall x (x > 0) \to (1=0)$ is True in $\mathbb N$.

But $(1 > 0) \to (1 = 0)$ is not.