1
$\begingroup$

Given that $P(x) \Leftrightarrow Q(x)$, I want to check if the followings are correct?

  • $\forall x. P(x) ~ \Leftrightarrow ~ \forall x. Q(x)$
  • $\exists x. P(x) ~ \Leftrightarrow ~ \exists x. Q(x)$

I think that they are correct, but I do not know how to formally prove it.

Can anyone help me to prove or disprove it?

Thank you very much!

$\endgroup$
2
  • $\begingroup$ What does $P(x)\Leftrightarrow Q(x)$ mean, when you haven't specified $x$? $\endgroup$
    – Mankind
    Jul 19, 2015 at 8:24
  • $\begingroup$ Hi, here $x$ is a variable and $P(x)$ and $Q(x)$ are two predicates $\endgroup$
    – Trung Ta
    Jul 19, 2015 at 8:57

1 Answer 1

1
$\begingroup$

You may prove these either by using truth trees, or by contradiction. I will leave out a few steps

1) By contradiction: Assume

I)$\forall x P(x) $ And this implies

II)$\forall x \not Q(x)$

Use any $a$ to instantiate ,

III)$ \not Q(a)$ Now use I) , to conclude.....for this $a$:

IV) $P(a)$ Now use:

V) $P(x) \Leftrightarrow Q(x)$ (specifically, use that $P(x) \Leftrightarrow Q(x)$ implies $P \Rightarrow Q$ and $Q \Rightarrow P$) , to derive a contradiction.

Let me know if you want to use truth trees.

$\endgroup$
4
  • $\begingroup$ Hi, thanks for your efforts! It seems that your proof shows that $\forall x. P(x) \not\Rightarrow \neg (\forall x. Q(x))$. Is it equivalent with $\forall x. P(x) \wedge \forall x. Q(x)$? Can you show how to use the truth tree? Thank you very much! $\endgroup$
    – Trung Ta
    Jul 19, 2015 at 9:01
  • 1
    $\begingroup$ @TrungTa: It is a proof by contradiction: I assume $A$, separately assume not $B$, arrive at a contradiction, so I conclude $B$, and then I conclude $A$ implies $B$. $\endgroup$
    – Gary.
    Jul 19, 2015 at 14:57
  • $\begingroup$ Thanks for your clarification. Yes, you are right! In addition, I think that the words "∀xP(x) and this implies ∃xQ̸(x)" in your proof confuses me. May be your assumption is just "∀xP(x) and ∃xQ̸(x)" are Valid. (as mentioned in your comment). Thank you very much, again! $\endgroup$
    – Trung Ta
    Jul 19, 2015 at 15:11
  • $\begingroup$ @TrungTa: My apologies, that was a typo. Please see the edits and let me know. $\endgroup$
    – Gary.
    Jul 19, 2015 at 15:27

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.