Stuck in exercise related to proof theory and first order logic.

99 Views Asked by At

Use the C rule and proposition 2.10 to prove $$\forall x(A(x)\to B(x)\lor C(x))\land\lnot\forall x(A(x)\to B(x)))\vdash\exists x(A(x)\land C(x))$$

[ C rule ]

[ A4 rule ]

enter image description here

This is what I've done so far

By hypothesis,$\forall x(A(x)\to B(x)\lor C(x))\land\lnot\forall x(A(x)\to B(x)))$, particularly $$\lnot\forall x(A(x)\to B(x)))$$ $$\implies\exists\lnot x(A(x)\to B(x)))$$

Also by hypothesis, $$\forall x(\lnot A(x)\lor B(x)\lor C(x))$$

How do I proceed from here? Should I apply C rule or A4 rule?

I don't know how to get $\exists x(A(x)\land C(x))$

1

There are 1 best solutions below

6
On BEST ANSWER

By C-rule, exists a new constant $c$ such that $\vdash_C\neg(A(c)\rightarrow B(c))$ and this is equivalent to $\vdash_CA(c)\wedge \neg B(c)$, so $\vdash_CA(c)$.

As hypothesis you have that $\vdash\forall x((A(x)\rightarrow B(x))\vee C(x))$. Then you can conclude that $\vdash_CC(c)$ (here I use A.4 rule on the previous statement).

Now, by $\exists$-introduction you have $\vdash_C\exists x(A(x)\wedge C(x))$. The conclution follows by proposition 2.10.