# First-order prefixes

• Jan 12th 2013, 07:26 AM
andrei
First-order prefixes
Quote:

Explain the difference between the first-order prefixes:
(a) \$\displaystyle \exists x\forall y\$ and \$\displaystyle \forall x\exists y\$;
(b) \$\displaystyle \exists x\forall y\exists z\$ and \$\displaystyle \forall x\exists y\forall z\$;
(c) \$\displaystyle \forall x\exists y\forall z\exists w\$ and \$\displaystyle \exists x\forall y\exists z\forall w\$.
First, I notice that each prefix can be obtained by negation from the other one in the pair. Also, I can show a formula such that different prefixes produce different truth values. For example, consider (c):
\$\displaystyle \forall x\exists y\forall z\exists w(x+z=y+w)\$ is true, but \$\displaystyle \exists x\forall y\exists z\forall w(x+z=y+w)\$ is false. I ask whether I missed something.
• Jan 14th 2013, 05:47 AM
emakarov
Re: First-order prefixes
Quote:

Originally Posted by andrei
I ask whether I missed something.

Your answer is correct. Another thing you may add is whether \$\displaystyle \exists x\forall y\,A(x,y)\$ implies \$\displaystyle \forall x\exists y\,A(x,y)\$ and vice versa, and similarly for (b) and (c).