Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

3 Answers 3

up vote 8 down vote accepted

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.

share|improve this answer

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

share|improve this answer

The second condition asserts a form of uniformity.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.