1
$\begingroup$

This is my first post on the mathematics stack exchange so please bear with me..

I am new to quantifier logic and I just can't seem to wrap my head around it.

I have been given four statements and I have to determine whether they are true or false.

Simple enough. The four statements are:

  1. $\forall x \in \mathbb{R} \ \forall y \in \mathbb{R} \ ((y>x) \implies (x=0))$
  2. $\forall x \in \mathbb{R} \ \exists y \in \mathbb{R} \ ((y>x) \implies (x=0))$
  3. $\exists x \in \mathbb{R} \ \forall y \in \mathbb{R} \ ((y>x) \implies (x=0))$
  4. $\forall x \in \mathbb{R} \ (\forall y \in \mathbb{R} \ (y>x)) \implies (x=0)$

My problem with these statements is that all of them seem to be false. Starting with the first statement, if $y$ is greater than $x$ for all values of $x$ and $y$ then couldn't $x$ just be anything less than $y$ in the reals? It does not have to stop at zero does it? Which is why $x=0$ is confusing because $x$ could just be negative.

All of the other statements seem to have a similar problem in that $y$ being greater than $x$ doesn't necessarily imply $x=0$ especially when $x$ is in the reals. I would understand it if $x \in \mathbb{N}$ and $y \in \mathbb{N}$ because the well ordering principle would apply and (at least for statement 3) $x$ would be forced to be zero because all $y$ are greater than $x$, but it doesn't apply here to the reals.

Please help. I have spent so much time mulling over this it isn't even funny anymore. Frankly, it's just frustrating..

Thank you all.

$\endgroup$
  • $\begingroup$ Yes, logic with implications and quantifiers can be very tricky. It might be helpful to look at the negation of the statements. When you look at their negations, you can easily see that it should be F, T, T, T. $\endgroup$ – Braindead Feb 6 '14 at 6:13
  • $\begingroup$ You must be careful with the scope of quantifiers: $\forall x \forall y (\phi(x,y) \rightarrow \psi(x,y))$ is not the same as $\forall x \forall y \phi(x,y) \rightarrow \forall x \forall y \psi(x,y)$. See also the comments below with Braindead. $\endgroup$ – Mauro ALLEGRANZA Feb 6 '14 at 7:47
1
$\begingroup$

For each statement, you should try to either prove or disprove it.

If you have a hunch that a statement is false, start by trying to disprove it. If you're unable to disprove it at first, consider whether you need to improve your strategy to disprove it, or whether you've discovered something that suggests maybe the statement is true after all, and then you should try to prove it.

When trying to disprove something, start by negating the statement, and then trying to prove the negation. For example, suppose we think statement 2 is false. The negation of the that sentence is:

$$\exists x \in \mathbb{R} \forall y \in \mathbb{R} ((y > x) \wedge (x\neq 0))$$

Have you learned how to systematically negate a sentence with quantifiers, logical connectives, etc? Assuming you're fine with that, now let's try to prove this.

  1. The sentence is an existential statement, that is, it's of the form $\exists x \phi(x)$ where $\phi (x)$ is some sub-formula. How do you prove an existential statement? You need to find an $x$ that makes the sub-formula true. Just for illustration, let's guess that $x=7$ will work (in practice, you will usually need to choose your witnesses more judiciously).
  2. Now we're trying to prove: $\forall y \in \mathbb{R}((y > 7) \wedge (7 \neq 0))$. This is a universal statement. That is, it's of the form $\forall y \psi (y)$. How do you prove a universal statement? Let $y$ be arbitrary (make no assumptions about it, other than that it's in $\mathbb{R}$), and try to prove that the resulting sub-formula is true for this totally arbitrary $y$.
  3. Now we need to prove $(y > 7) \wedge (7 \neq 0)$. This is a conjunction. How do you prove a conjunction is true? Prove that both conjuncts are true. The latter conjunct is obviously true. Is the former conjunct, $y > 7$ true regardless of what $y$ is? No!

So the above attempt to prove the negation of statement 2 failed. Does the approach seem salvageable? If so, find an $x$ that will work. If not, then maybe statement 2 is true after all, and we should try to prove statement 2 (rather than its negation) itself.

In summary:

  1. Decide whether you want to first try to prove or disprove a given statement
    • If disprove, write the negation of the statement
  2. Prove the resulting statement (either original statement or its negation) by breaking it down one sub-formula at a time, applying the correct strategy at each stage depending on the type of the sub-formula:
    • For existentials, try to come up with a witness, and substitute that value in the sub-formula
    • For universals, let the quantified variable be arbitrary, and try to prove the sub-formula
    • For conjunctions, try to prove both sub-formulas
    • etc.
  3. If your proof works out, you're done. If not, consider improving it or change your mind as to whether you want to prove or disprove the original sentence, and start back at step 1.
$\endgroup$
0
$\begingroup$

In mathematics, "IF P THEN Q" doesn't really mean that one causes another.

It is more helpful to think of it as its equivalent

"(Not P) or Q"

You can check the truth table to see that they are logically equivalent.

Let's see why the second statement is true. Rewriting, we have:

For any $x$, there is a $y$ so that $y\le x$ or $x=0$.

This is certainly true! (Do you see why?)

Other statements can be checked in a similar manner.

Note: Here is another way to look at statement 2.

If you negate statement 2, you get:

There is an $x$ so that for any $y$, $y>x$ and $x\ne0$.

This is an obviously false statement since no single value of $x$ is smaller than all real numbers.

Since the negation is false,the original statement is true.

$\endgroup$
  • $\begingroup$ Is $y$ kind of like a free variable in the "Q" of the second statement (or any of the four statements for than matter). So if $x=0$ is at all possible for that statement then $\neg P \vee Q$ will always be true right? $\endgroup$ – skwear Feb 6 '14 at 6:31
  • $\begingroup$ I am not really sure what you mean. It is true that "Q" is unaffected by $y$. Just the fact that $x=0$ is possible doesn't make that true. $\endgroup$ – Braindead Feb 6 '14 at 6:37
  • $\begingroup$ For instance, in the example I have in the response, $x$ ranges through all real values, because it is "forall $x$" $\endgroup$ – Braindead Feb 6 '14 at 6:39
  • $\begingroup$ @skwear - see my comment above. Tha sentence "for any x, there is a y so that y≤x or x=0" must be transalted as $\forall x \exists y (y \le x \lor x = 0)$. If so, nor $x$ nor $y$ are free in the subformula that is in the scope of the quantifiers. $\endgroup$ – Mauro ALLEGRANZA Feb 6 '14 at 7:50

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.