1
$\begingroup$

I did it in two different ways (I looked at this post but I can not get anything useful because I do not understand if it represents a $T, C$ or contingency).

I have to say if the following complex propositional function (in $\mathbb R$) represents a tautology, contradiction or contingency:

$$\exists xP(x)\wedge\neg\exists yQ(y)\wedge\forall z(P(z)\Rightarrow Q(z)).$$

I tried to do it in two different ways, and both give me that it represents a contradiction:

  • I singled out everything in one variable: $ a $. In this way you can remove the quantifiers: $$P(a)\wedge\neg Q(a)\wedge(P(a)\Rightarrow Q(a))\quad\underbrace{\Leftrightarrow}_{\textrm{Modus Tollens}}\\P(a)\wedge\neg P(a)\Leftrightarrow \textrm{Contradiction}.$$

  • Transform them into premises and see their truth values: $$\begin{array}{lc} \exists xP(x)&(1)\\\neg\exists {\color{red}y}Q(y)&(2)\\\forall z(P(z)\Rightarrow Q(z))&(3) \end{array}$$ First of $(2)$ we can conclude $\forall y\neg Q (y)$. Then, because they are premises, $\exists xP(x)$ must be true, and since $\forall y\neg Q (y)$ must also be true, we conclude that $Q(y)$ must be false. Therefore, since the third premise speaks of "for all $z$" we can consider $P(x)\Rightarrow Q(y)$ as particular cases of $z$, that is, $T\Rightarrow F$ (which is false) and therefore, there is a contradiction in the third premise, so the whole expression is a contradiction.


Are my reasoning very bad? If so, please, how could you solve the exercise (without much difficulty)?

Thanks!

$\endgroup$
  • 1
    $\begingroup$ You're right that it's a contradiction. But $\lnot\exists yQ(y)$ does not mean $\lnot Q(a)$ for some $a$. It means $\forall y\lnot Q(y)$. You can see the sentence is a contradiction simply by translating it into English: it says there is a P, and there's no Q, and that every P is a Q. But if there's a P and every P is a Q, then there's a Q; contradiction. $\endgroup$ – symplectomorphic Apr 7 '18 at 18:50
  • $\begingroup$ Wow thank you! I think you do not mention the quantifiers. Can I know why it is like that? Why did not you publish it as an answer? Just curious $\endgroup$ – manooooh Apr 7 '18 at 18:56
  • $\begingroup$ But why $\mathbb R$ ? $\endgroup$ – Mauro ALLEGRANZA Apr 7 '18 at 19:00
  • $\begingroup$ @MauroALLEGRANZA The statement says it's like that. $\endgroup$ – manooooh Apr 7 '18 at 19:03
  • $\begingroup$ What do you mean I "do not mention the quantifiers"? Of course I did: "there is" is a quantifier; so is "every." $\endgroup$ – symplectomorphic Apr 7 '18 at 19:31
3
$\begingroup$

It is a contradiction.

And your argument is basically correct.

We have $∃xP(x)$ and thus, for some $a$, $P(a)$ holds.

We have also $∀z(P(z) \to Q(z))$. The quantified formula holds for every object, and thus also for $a$ : $P(a) \to Q(a)$.

Thus, by modus ponens : $Q(a)$.

But $¬∃yQ(y)$ is equivalent to $∀y¬Q(y)$. Again, the quantified formula holds for every object, and thus also for $a$ : $¬Q(a)$.

Having derived both : $Q(a)$ and $¬Q(a)$, we have to conclude that the formula is unsatisfiable, i.e. a contradiction.

$\endgroup$
  • $\begingroup$ Since the other user did not publish it as an answer, I give it to you. I like the elegance with which you say it. Thank you! $\endgroup$ – manooooh Apr 7 '18 at 19:02

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.