# Are these two statement equivalent?

$\forall x \exists y P(x,y)$

$\exists x \forall y P(x,y)$

where P(x,y) means x is smaller than y.

I believe that they mean the same thing.

-
They are not equivalent. IHMO, this is perhaps the central issue in predicate logic -- the issue of dependencies among variables that are created by existential specification. Everything else seemed rather straightforward in logic (to me) until I came upon upon it. Like Russell's paradox, it seems to have spurred various formal "solutions" including my own. My DC Proof program is based on it. (Available free at dcproof.com ) – Dan Christensen Dec 7 '12 at 3:51
BTW, I think your second line should be $\exists y\forall x P(x,y)$. – Dan Christensen Dec 7 '12 at 18:19

Assuming you mean $\exists x \forall y P(x,y)$ for your second one, no these are not the same.

Put them into words and it will become clearer:

The first one says:

" Every $x$ is smaller than some $y$. "

The second one says:

" There is some $x$ which is smaller than every $y$. "

These are certainly not saying the same thing. For instance the first one is true in $\mathbb{R}$ but the second one is not.

-

The second condition asserts a form of uniformity.

-

For some relations $P$

$\forall x\exists y P(x,y)$ (1)

is true while

$\exists y\forall x P(x,y)$ (2)

is false. So, (2) does not necessarily follow from (1).

Example

Let the domain of quantification be $U=\{x,y\}$ for distinct $x$ and $y$, and let $P$ be the "is equal to" relation on $U$. It can then be formally proven, by examining each case, that (1) is true (every element of $U$ is equal to itself) while (2) is false (no element of $U$ is equal to every element of $U$).

See formal proof (using the DC Proof 2.0 format) at http://dcproof.com/PopSci.htm

EDIT:

For a slightly different approach see:

$U=\{ 0,1 \}$ and $P(a,b)\leftrightarrow a=b$ at http://dcproof.com/USet-0-1.htm

$U=N$ and $P(a,b)\leftrightarrow b>a$ at http://dcproof.com/GTonN.htm

-