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?

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

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

"I'll start with your last question (in the comments); namely "Why doesn't x = y satisfy the initial problem".

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!)."

shareedit answered 9 hours ago

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!

  • $\begingroup$ 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. $\endgroup$ – david.keck Sep 8 '12 at 13:14
  • $\begingroup$ This instance of the question has been closed as a duplicate. You might want to repost your answer on the open original. $\endgroup$ – Raphael Sep 9 '12 at 7:04

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