2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I don't see a paradox and I am also unable to understand your question. Can you kindly rephrase your question? $\endgroup$ – M. Alaggan Sep 8 '12 at 2:53
  • $\begingroup$ Sorry. I'm new at this. The problem can not be true because it's negation is true. However, it seems to me that x = y would make the problem true. Why is doesn't x = y satisfy the initial problem? $\endgroup$ – david.keck Sep 8 '12 at 2:58
  • $\begingroup$ It's fine, now worries. I am just asking for a clarification of your question so I can help you :) $\endgroup$ – M. Alaggan Sep 8 '12 at 2:59
  • $\begingroup$ I edited my initial comment. I didn't know that enter submitted at first. Sorry. $\endgroup$ – david.keck Sep 8 '12 at 3:01
11
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Great answer. I did not know that X had to be chosen and then compared will all of Y. That makes a lot more sense. Thank you! $\endgroup$ – david.keck Sep 8 '12 at 13:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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