# Thread: Not logical consequence (First-order logic)

1. ## Not logical consequence (First-order logic)

Hello,
the problem is to show that P isn't logical consequence of Q:
$\displaystyle P = ( \forall x) ( \exists y)r(x,y)$
$\displaystyle Q = ( \exists y) ( \forall x)r(x,y)$

$\displaystyle r$ stands for relation.

Maybe some kind of proof by contradiction would work, but I couldn't make one.

Any help is appreciated. Thanks in advance!

2. Originally Posted by Greg98
Hello,
the problem is to show that P isn't logical consequence of Q:
$\displaystyle P = ( \forall x) ( \exists y)r(x,y)$
$\displaystyle Q = ( \exists y) ( \forall x)r(x,y)$

$\displaystyle r$ stands for relation.

Maybe some kind of proof by contradiction would work, but I couldn't make one.

Any help is appreciated. Thanks in advance!
I think you are mistaken: $\displaystyle Q\Rightarrow P$ is valid. Maybe you want to prove that $\displaystyle P\Rightarrow Q$ is not valid, i.e. that Q is not a consequence of P?
If so I would suggest coming up with a countermodel, i.e. a model in which P is true but Q is not (take, for example, the natural numbers as domain and $\displaystyle r(x,y) := x<y$).

3. Edit: too late.

In fact, P is the logical consequence of Q. Indeed, assume Q and take a y0 that works for all x, i.e., a y0 such that for all x we have r(x, y0). To prove "for all x there exists a y such that r(x, y)", fix an arbitrary x and let y = y0.

It is Q that is not the logical consequence of P. This can be shown by making a counter-model. For example, the domain is the set of people and r(x,y) means "y is x's mother".