Possible Duplicate:
Negation of nested quantifiers

The problem is:

∃x∀y(x ≥ y)

With a domain of all real positive integers.

The negation is:

∀x∃y(x < y)

so, if y = x + 1

the negation is true.

That means the negation of the negation (or, the original problem) is false.

My question is, that if the original problem is ∃x∀y(x ≥ y), why can't x = y and prove the problem true?

• Perhaps I'm missing the point, but for x=y, the first predicate is satisfied. What's the actual question? – Simon MᶜKenzie Sep 7 '12 at 23:39
• That's what I'm saying, but how can the original problem as well as it's negation be true? – david.keck Sep 8 '12 at 1:51

This question was answered by M. Alaggan at cs.stackexchange. Below is the original answer:

The answer is in the quantifiers. Read from left to right. It starts with "there exists" X. So pick an X in your head. Say X = 5. We can not pick Y here because it doesn't have a value yet and we MUST pick a value for X NOW. Now proceed to read the next quantifier which reads "for all Y". Oops. We can't say for all Y because we already set Y = X.

Actually if you are going to look for a solution that satisfies the original formula, it should be of the form "X=(some positive integer)", with Y not involved at all, as it is a bound variable (as opposed to being a free variable which we can choose).

However, the formula says "there is a (single, and specific) positive integer X which all integers are less than or equal to it" which is clearly false because given any positive integer X, X+1 is a positive integer which is not less than nor equal to it (which is what the negated formula says!)."

M. Alaggan 1614

Your base predicate states that there exists some real number that's larger than or equal to all other real numbers (i.e that there is a highest real number).

The inverse states that every real number has a number larger than it (i.e. that there is no highest real number).

Your test cases don't produce a paradox because feeding x=y into the first predicate means that you're no longer working with R+. If all you have in your test set is a single number, then of course there's a maximum value. All you show with this test is that:

In a set containing a single real number, there exists a highest value

All that having been said, I'm sure you'll get a better answer on math.stackexchange.com!

• Thanks for your answer! I got an answer over at CS. I'll post it here in case someone else comes across this in the future. – david.keck Sep 8 '12 at 13:14
• This instance of the question has been closed as a duplicate. You might want to repost your answer on the open original. – Raphael Sep 9 '12 at 7:04