Validity of First Order Logic Formula

301 Views Asked by At

$$\forall z \bigl(Q(z) \supset P(z)\bigr) \supset \exists x \Bigl(\bigl[Q(x) \supset P(a)\bigr] \wedge \bigl[Q(x) \supset P(b)\bigr]\Bigr)$$

I do not know how to start checking this formula. To me, it appears that this should be invalid. But I can not think of any examples. Is this formula valid or invalid?

1

There are 1 best solutions below

2
On

The formula is valid. Here is an informal proof.

Assume that $\forall x[Q(x)\supset P(x)]$ is true. Then both of the formulas $Q(a)\supset P(a)$ and $Q(b)\supset P(b)$ are true.

Now, at least one of the formulas $Q(a)\supset Q(b)$ and $Q(b)\supset Q(a)$ is true. If $Q(a)\supset Q(b)$ is true, then $[Q(a)\supset P(a)]\land[Q(a)\supset P(b)]$ is true. If $Q(b)\supset Q(a)$ is true, then $[Q(b)\supset P(a)]\land[Q(b)\supset P(b)]$ is true. In either case, $\exists x([Q(x)\supset P(a)]\land[Q(x)\supset P(b)])$ is true. Q.E.D.

The reasoning is the same as the way you'd prove in ordinary mathematics: $$\forall x\ [f(x)\le g(x)]\implies\exists x[f(x)\le g(0)\text{ and }f(x)\le g(1)]$$