# Thread: Rules for quantifiers in Predicate Logic

1. ## Rules for quantifiers in Predicate Logic

Hello everybody!

There are some special cases I need to know how to prove (and find it very difficult to find everywhere) using the standard logic identities and nothing very specific like axiomatized systems nor special normal forms like Skolem, etc.

First: how can I determine if the following implication is true or false?

($\displaystyle \forall$x)[P(x)$\displaystyle \rightarrow$Q(x)]$\displaystyle \rightarrow$[$\displaystyle \forall$P(x)$\displaystyle \rightarrow$ $\displaystyle \forall$Q(x)]

A book I have states that it is true, but it doesn't explain why. The exercise pretends the determination of its truth o falsity only using std logical identities like using the implication, the contrapositive, DeMorgan, etc. I also know that $\displaystyle \forall$ only distributes over AND, and $\displaystyle \exists$ only distributes over OR.

Thank you and hope you help me to construct this proof.

2. Originally Posted by LightMath09
Hello everybody!

There are some special cases I need to know how to prove (and find it very difficult to find everywhere) using the standard logic identities and nothing very specific like axiomatized systems nor special normal forms like Skolem, etc.

First: how can I determine if the following implication is true or false?

($\displaystyle \forall$x)[P(x)$\displaystyle \rightarrow$Q(x)]$\displaystyle \rightarrow$[$\displaystyle \forall$P(x)$\displaystyle \rightarrow$ $\displaystyle \forall$Q(x)]

A book I have states that it is true, but it doesn't explain why. The exercise pretends the determination of its truth o falsity only using std logical identities like using the implication, the contrapositive, DeMorgan, etc. I also know that $\displaystyle \forall$ only distributes over AND, and $\displaystyle \exists$ only distributes over OR.

Thank you and hope you help me to construct this proof.
It belongs to the axiom groups of FOL. See page 2 of the below link.

It is a variant of "PRED-3" in the "quantifier axioms" section in the wiki.
First-order logic - Wikipedia, the free encyclopedia

3. Originally Posted by LightMath09
...There are some special cases I need to know how to prove (and find it very difficult to find everywhere) using the standard logic identities and nothing very specific like axiomatized systems nor special normal forms like Skolem, etc....
I have posted a message on http://www.mathhelpforum.com/math-he...824-post2.html about so-called natural deduction, which does not use axioms.

4. Originally Posted by andrei
I have posted a message on http://www.mathhelpforum.com/math-he...824-post2.html about so-called natural deduction, which does not use axioms.
I'll appreciate if you post a proof for the above using a natural deduction.

5. $\displaystyle \begin{array}{rcl} \forall x(P(x)\to Q(x))&\vdash&\forall x(P(x)\to Q(x)).\\ \forall xP(x),\,\forall x(P(x)\to Q(x))&\vdash&\forall xP(x).\\ \forall xP(x),\,\forall x(P(x)\to Q(x))&\vdash&P(x)\to Q(x)\text{ --- }\forall\text{-elimination, 1}.\\ \forall xP(x),\,\forall x(P(x)\to Q(x))&\vdash&P(x).\\ \forall xP(x),\,\forall x(P(x)\to Q(x))&\vdash&Q(x).\\ \forall xP(x),\,\forall x(P(x)\to Q(x))&\vdash&\forall xQ(x).\\ \end{array}$

(I cannot finish the proof because of latex restrictions.) Now by using twice $\displaystyle \forall$-introduction to the 6th deduction, we get above formula.

6. Originally Posted by andrei
$\displaystyle \begin{array}{rcl} \forall x(P(x)\to Q(x))&\vdash&\forall x(P(x)\to Q(x)).\\ \forall xP(x),\,\forall x(P(x)\to Q(x))&\vdash&\forall xP(x).\\ \forall xP(x),\,\forall x(P(x)\to Q(x))&\vdash&P(x)\to Q(x)\text{ --- }\forall\text{-elimination, 1}.\\ \forall xP(x),\,\forall x(P(x)\to Q(x))&\vdash&P(x).\\ \forall xP(x),\,\forall x(P(x)\to Q(x))&\vdash&Q(x).\\ \forall xP(x),\,\forall x(P(x)\to Q(x))&\vdash&\forall xQ(x).\\ \end{array}$

(I cannot finish the proof because of latex restrictions.) Now by using twice $\displaystyle \forall$-introduction to the 6th deduction, we get above formula.

I don't know much about the natural deduction, but it seems like the above proof is similar to that of the first order logic.

If the above proof were the proof of the first order logic, I think the above proof involves a circular reasoning. It is because the last line uses a generalization theorem which in turn uses the above axiom.

A Generalization theorem says that

"If $\displaystyle \Gamma \vdash \phi$ and x does not occur free in any formula in $\displaystyle \Gamma$, then $\displaystyle \Gamma \vdash \forall x\phi$.

The last line has the form,
if $\displaystyle \Gamma \vdash Q(x)$, then $\displaystyle \Gamma \vdash \forall x Q(x)$.

The above Q(x) has obtained by modus ponens from P(x) and $\displaystyle P(x) \to Q(x)$. By the inductive hypothesis, we have $\displaystyle \Gamma \vdash \forall x P(x)$ and $\displaystyle \Gamma \vdash \forall x (P(x) \to Q(x))$.

We obtain $\displaystyle \Gamma \vdash \forall x Q(x)$ by M.P

1. $\displaystyle \Gamma \vdash \forall x P(x)$
2. $\displaystyle \Gamma \vdash \forall x P(x) \to \forall x Q(x)$ (implicitly invoking this line)

Line 2 uses the above axiom. It is obtained by modus ponens of $\displaystyle \forall x (P(x) \to Q(x))$ and the axiom $\displaystyle \forall x (P(x) \to Q(x)) \to (\forall x P(x) \to \forall x Q(x))$.

Rather, the above axiom is obtained by proving
$\displaystyle \{\forall x(\alpha \to \beta), \forall x \alpha \} \models \forall x \beta$.

If any of you is interested in the above proof, I will post it.