5
$\begingroup$

Prove that $\exists x \big( P(x) \rightarrow \forall y P(y)\big)$. (Note: Assume the universe of discourse is not the empty set.)

This is an exercise from Velleman's "How To Prove It". What does the statement mean? Wouldn't this mean that there is an object in the universe of discourse such that if $P$ is true for that specific object, then $P$ is true for all objects? I do not see how this is possible, especially since we have a generic universe of discourse. I guess if $P(x)$ is false for at least one $x$, then the statement will indeed be true, and if $P(x)$ is true for every $x$, then every $x$ works for the existence. Here is my solution:

Proof: Suppose not $\exists x \big( P(x) \rightarrow \forall y P(y)\big)$. Then we have that $\forall x P(x)$ and $\forall x \exists y \neg P(y)$. Since the universe of discourse is not empty, we can choose an element $x$ from it. Then we have $P(x)$. Also, we may choose a $y$ such that $\neg P(y)$. But since $y$ is a member of the universe of discourse as well, it follows that $P(y)$. Then we have $P(y)$ and $\neg P(y)$, which is a contradiction. Therefore, $\exists x \big( P(x) \rightarrow \forall y P(y)\big)$. $\square$

$\endgroup$
5
  • 4
    $\begingroup$ Your idea is right. If $12$ is prime, then every number is prime. $\endgroup$
    – GEdgar
    Commented Apr 14, 2020 at 0:37
  • 3
    $\begingroup$ Slight optimization in the proof: you do not need "Then we have $P(x)$." $\endgroup$ Commented Apr 14, 2020 at 7:12
  • 2
    $\begingroup$ See Drinker paradox. $\endgroup$ Commented Apr 14, 2020 at 8:16
  • 1
    $\begingroup$ After you ask a question here, if you get an acceptable answer, you should "accept" the answer by clicking the check mark $\checkmark$ next to it. This scores points for you and for the person who answered your question. You can find out more about accepting answers here: How do I accept an answer?, Why should we accept answers?, What should I do if someone answers my question?. $\endgroup$
    – user400188
    Commented Apr 17, 2020 at 1:51
  • $\begingroup$ @user400188 Sorry for the delay, I was going to look into the sequent calculus but then got distracted. $\endgroup$
    – Iyeeke
    Commented Apr 17, 2020 at 11:58

1 Answer 1

2
$\begingroup$

As GEdgar has pointed out; your proof is correct, and a possible interpretation of the sentence, is that if 12 is prime, then every number is prime. A generalisation of this is the principal of explosion, by assuming falsehood, anything can be derived. In the example, we assume a number possesses a property which it does not.

A second interpretation not covered in GEdgars example, is that of a finite universe of discourse. If there is only one object in the universe of discourse, then if some object possesses a certain property, all objects do.

It is prudent to include a proof of $\exists x \big( P(x) \rightarrow \forall y P(y)\big)$ in a formal deductive system in favour of English. I have adopted the sequent calculus for this, the rules of which you can find here, if you are interested.

Sequent calculus proof

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .