Proof that a statement involving quantifiers is false

155 Views Asked by At

I believe that the sentence $\forall x (P(x)\rightarrow \exists y Q(x,y))$ false? Is it sufficient to define:

1) The Domain of $x, y $

2) The predicates $P(x)$ and $Q(x,y)$

so that for some $x$ and $y$, $P(x)$ is true while $Q(x,y)$ is false?

1

There are 1 best solutions below

2
On BEST ANSWER

It was established in the comments that the OP knows that to prove that $\forall x(P(x)\to\exists yQ(x,y))$ isn't a logical truth, it suffices to find domains for $x$ and $y$ and interpretations for $P$ and $Q$ such that $\forall x(P(x)\to\exists yQ(x,y))$ is false.

What was intutive for me to think about was considering $x,y$ raging over the natural numbers and letting $P(x)$ mean '$x$ is a natural number'.

Think about an order relation for $Q$ solves the problem.