3
$\begingroup$

I'm a college student taking a discrete mathematic course for summer. I took midterm last monday and got back grades and solutions for the exam, but I'm still confused with this specific question.

The question is:

Let $D$ represent a set and $P(x)$ represent a predicate where $x\in D$. Is this a true or false statement? Explain briefly.

"If $\forall x \in D$, $P(x)$ then $\exists x \in D$ such that $P(x)$."

And the answer is: This is a false statement.

How can this statement be false?

( It's late night so I don't wanna bother my professor)

$\endgroup$
2
  • 1
    $\begingroup$ Hint: what if $D$ is empty? $\endgroup$
    – Trebor
    Jun 21, 2020 at 1:15
  • 1
    $\begingroup$ "If every student who bothers the professor late at night fails the course, then there exists a student who has failed." $\endgroup$
    – Blue
    Jun 21, 2020 at 1:15

1 Answer 1

4
$\begingroup$

$\forall x\in D,\,P(x)$ can be vacuously true. For example, $\forall x\in\varnothing\,(x>0)$ is vacuously true, since $\varnothing$ has no elements, but $\exists x\in\varnothing (x>0)$ is false, since clearly no such element exists.

$\endgroup$
4
  • $\begingroup$ Is this whole thing only false for $D=\emptyset$? $\endgroup$ Jun 21, 2020 at 1:45
  • $\begingroup$ @gen-zreadytoperish If $D$ is nonempty, then $\exists x_0\in D$, and if $\forall x\in D:P(x)$, then $P(x_0)$, so $\exists x\in D:P(x)$. So I believe the only fringe case is when $D=\varnothing$. $\endgroup$
    – csch2
    Jun 21, 2020 at 4:15
  • $\begingroup$ Thank you. So I had to assume that the set was empty? $\endgroup$
    – Lumificier
    Jun 22, 2020 at 16:49
  • $\begingroup$ Yes - if $D$ is nonempty then the statement is true, but unfortunately that wasn’t stated as an assumption. $\endgroup$
    – csch2
    Jun 22, 2020 at 18:22

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.