2

I am working through an introductory book on mathematical proofs and I have a question about an equivalence I have proven.

The exercise says to show that $$\exists x(P(x) \to Q(x))$$ is equal to $$\forall xP(x) \to \exists xQ(x)$$

I can do that with these steps: $$\exists x(P(x) \to Q(x))$$ $$\exists x(\lnot P(x) \lor Q(x))$$ $$\exists x \lnot P(x) \lor \exists x Q(x)$$ $$\lnot \forall x P(x) \lor \exists x Q(x)$$ $$\forall xP(x) \to \exists xQ(x)$$

But will someone please help me verbalize why these are equivalent? They don't seem to be, though I just showed that they are.

I thought an example might help me, so I gave $P(x)$ and $Q(x)$ these meanings:

$P(x) \Rightarrow x$ has a first name of "Sam"
$Q(x) \Rightarrow x$ has a last name of "Bishop"

I would then interpret the first statement like this:

There is a person such that if he or she has a first name of "Sam" then that person has a last name of "Bishop".

However, I would interpret the second statement like this:

If everyone has a first name of "Sam", then there is a person who has a last name of "Bishop".

The first statement is only predicated on something being true about one person, but the second statement requires that something be true for everyone. (As I understand it.) What am I missing?

sam.bishop
  • 311

3 Answers3

2

The first statement says that there is at least one person such that if their first name is Sam, then their last name is Bishop. This can be true in two ways: There is a Sam Bishop, or there is somebody who is not named Sam.

  • If there is a Sam Bishop, then certainly, if everyone is named Sam, someone is also a Bishop.
  • If there is someone who is not named Sam, then "Everyone is named Sam" is false, so "Everyone is named Sam implies someone is a Bishop" is trivially true.

Conversely if "Everyone is named Sam implies someone is a Bishop" is true, then either

  • Everyone is named Sam, and so someone is a Bishop, and is therefore Sam Bishop.
  • Or there is someone who is not named Sam, and for that person "If his name is Sam, he is a Bishop" is trivially true.

In either case, there is someone such that if his name is Sam, he is a Bishop.

Paul Sinclair
  • 43,643
1

Your intuition may be confused by the apparent similarity to the familiar statement $\forall x\;(P(x)\to Q(x))$ vis "all peas are in a queue."

But your existential expression is not the same sort of thing at all.

Firstly, evaluate the truth of the statement: "If a horse is a car, then it can fly."

Well, here the antecedent is false, thus the implication is true.

$\exists x (P(x)\to Q(x))$

"There is something which, if it were a pea, then it would be in a queue."

This statement is satisfied if (1) there is at least one pea that is in a queue, or (2) there is something that is not a pea.   The statement is only falsified if there are no peas that are in a queue and there is nothing else but peas.

$\forall x\,P(x) \;\to\; \exists Q(x)$

"If all things are peas, then something is in a queue."

Ditto.

Graham Kemp
  • 129,094
0

The other answers have been very helpful, but to make sure I understand this I am going to attempt to answer it myself.

I don't think I gained anything by introducing definitions for $P(x)$ and $Q(x)$. It's sufficient to focus on the fact that the two statements are true and false in the same situations:

  • If the set of possible values for $x$ is empty, then both statements are false. In this case, $x$ doesn't exist, so the first statement is false. The second statement is also false because the universal quantifier is true over the empty set, making the antecedent true, but again $x$ doesn't exist so the consequent is false.
  • If $P(x)$ is true and $Q(x)$ is false for all possible values of $x$, then both statements are false. This is pretty easy to see.
  • If $P(x)$ is true and $Q(x)$ is true for all possible values of $x$, then both statements are true. This is also easy to understand.
  • If $P(x)$ is false for any value of $x$, then both statements are trivially true. In both cases it's because an implication is true if the antecedent is false.
  • If $P(x)$ and $Q(x)$ are true for at least one value of $x$, then both statements are true. Here the second statement is trivially true again, but the first statement is true according to its straightforward reading.
sam.bishop
  • 311