2
$\begingroup$

$\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.

  • 0
    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 http://www.dcproof.com )2012-12-07
  • 0
    [Consider my answer to similar question, it may be helpful.](http://math.stackexchange.com/questions/64500/confused-between-nested-quantifiers/64731#64731)2012-12-07
  • 0
    BTW, I think your second line should be $\exists y\forall x P(x,y)$.2012-12-07

3 Answers 3

9

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.

-1

The second condition asserts a form of uniformity.

-1

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