[Solved]: Negation of nested quantifiers

Problem Detail: 

The problem is:

$$\exists x \forall y (x \ge y)$$

With a domain of all real positive integers.

The negation is:

$$\forall x \exists y (x < y)$$

so, if $y = x + 1$, the negation is true.

That means the negation of the negation (i.e. the original problem) is false.

My question is, that if the original problem is $\exists x \forall y (x \ge y)$, why can't I take $x = y$ and prove the problem true?

Asked By : david.keck

Answered By : M. Alaggan

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/3463