2
$\begingroup$

My question is simple, as the title says: can I safely remove (or add) a quantifier if the variable bound to it is not used in any predicate following it?

As an example: I wanted to prove $$ \exists x(P(x) \implies \forall yP(y))$$ My proof went like this: $$ \exists x(P(x) \implies \forall yP(y)) \iff \exists x(\neg P(x) \lor \forall yP(y)) \iff \neg \forall xP(x) \lor \exists x \forall yP(y)$$ (The last equivalence follows from distributivity of existential quantifier over disjunction).

Now, we see that in the second clause the $x$ is not used, so it could be any element of the universe of discourse. Hence we remove it and replace the bound variable $y$ to $x$ to get: $$ \neg \forall xP(x) \lor \forall xP(x) $$ An obvious tautology. Q.E.D. (?)

It seems to me that all I've done is legal, at least assuming that the universe of discourse is not an empty set. Am I correct or can I not do this? Equivalently can I add quantifiers (like in the example below)? $$ \forall xP(x) \land Q(y) \iff \forall xP(x) \land \forall xQ(y) \iff \forall x(P(x) \land Q(y))$$

$\endgroup$
  • $\begingroup$ yes you can ignore quantifiers that don't bind anything. $\endgroup$ – Apostolos Jun 10 '17 at 21:45
4
$\begingroup$

Yes, this is correct. More precisely, if $P$ is any formula in which the variable $x$ does not appear, then $\exists x P$ and $\forall x P$ are each equivalent to $P$ over any nonempty universe of discourse (if you don't know the universe is nonempty, all you can say is $\exists x P \implies P$ and $P\implies\forall x P$).

(To be clear, if you're working in some specific formal deductive system rather than the informal logic that mathematicians usually work with, you would need to justify these statements using only the rules of your deductive system. Exactly how you do this depends on what your deductive system is.)

$\endgroup$
2
$\begingroup$

Yes, those quantifiers are called Null Quantifiers. And we have as a general equivalence principle:

Null Quantification

Where $\varphi$ does not contain $x$ as a free variable:

$\forall x \varphi \Leftrightarrow \varphi$

$\exists x \varphi \Leftrightarrow \varphi$

$\endgroup$
  • $\begingroup$ How can you prove this? $\endgroup$ – Ben-ZT Feb 26 '18 at 3:34
  • $\begingroup$ @Ben-ZT Are you looking for a proof based on the formal semantics of the quantifiers, or a formal derivation? $\endgroup$ – Bram28 Feb 26 '18 at 12:52

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.