Is there something wrong with this proof question?

74 Views Asked by At

Question: If $P(x)$ is a predicate using a variable x and $Q$ is a statement that does not contain x, show that $$((\exists x.P(x))\implies Q) \iff (\forall x.(P(x)\implies Q))$$

Does this question make sense? I don't even know where to start because it seems to imply that there is a contradiction by itself: the first statement is that there is only one $x$ but the second statement is that there are all $x$. How can both of this be simultaneously true at the same time? Unless we assume there is only one $x$...which I don't think is what the question gives.

Also, what kind of concepts should we use here? The most obvious one I could see is that by taking out the $\exists$ symbol, it becomes a $\forall$ symbol. But I have never seen this concept before. Could the question be set wrongly?

2

There are 2 best solutions below

2
On BEST ANSWER

A universal can be seen as a kind of conjunction over all objects over the domain. That is, if $a,b,c,...$ denote the objects in your domain, then you can think of a universal like this:

$\forall x \: \varphi(x) \approx \varphi(a) \land \varphi(b) \land \varphi(c) \land ...$

I use $\approx$ since this is technically not a logical equivalence, but if you really want to prove the above equivalence, you'd need to go into formal semantics, and that might be a bit to much to ask for a beginner in logic. But, what you would be doing there does follow this basic idea, so let's just leave it more informal.

OK, so now:

$$(\exists x \ P(x)) \rightarrow Q \Leftrightarrow \text{ (Implication)}$$

$$\neg (\exists x \ P(x)) \lor Q \Leftrightarrow \text{ (Quantifier Negation)}$$

$$(\forall x \ \neg P(x)) \lor Q \approx$$

$$(\neg P(a) \land \neg P(b) \land \neg P(c) \land ...) \lor Q \Leftrightarrow \text{ (Distribution)}$$

$$(\neg P(a) \lor Q) \land (\neg P(b) \lor Q) \land (\neg P(c) \lor Q) \land ... \Leftrightarrow \text{ (Implication)}$$

$$(P(a) \rightarrow Q) \land (P(b) \rightarrow Q) \land (P(c) \rightarrow Q) \land ... \approx$$

$$\forall x (P(x) \rightarrow Q) $$

8
On

The quantifier $\exists x$ does not mean "only one $x.$" It means "for at least one $x.$"

But there is also another difference in the way the quantifiers are used: one applies only to $P(x)$ and the other applies to the entire implication $P(x)\implies Q.$ Depending on the truth value of $Q,$ it is possible for $P(x)\implies Q$ to be true even though $P(x)$ is false.