# Not logical consequence (First-order logic)

• Oct 18th 2010, 02:31 AM
Greg98
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!
• Oct 18th 2010, 07:06 AM
Failure
Quote:

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\$).
• Oct 18th 2010, 07:07 AM
emakarov
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".