1
$\begingroup$

I'm trying to show that for a non-empty set $X$, the following statements are true for logical statements $P(x)$ and $Q(x)$:

  • $∃x∈X$, ($P(x)$ or $Q(x)$) $\iff$ $(∃x∈X, P(x))$ or $(∃x∈X, Q(x))$
  • $∃x∈X$, ($P(x)$ and $Q(x)$) $\implies$ $(∃x∈X, P(x))$ and $(∃x∈X, Q(x))$

Is it possible to use truth tables to show this? I can't think of any other way to go about it. Any help would be appreciated.

$\endgroup$
  • $\begingroup$ You could use instantiation of $\exists$ quantifier apart from other axioms to prove this statement too, the universe of discourse being the elements of X. $\endgroup$ – bat_of_doom Nov 9 '16 at 15:59
1
$\begingroup$

The 1st statement can indeed be proved by writing out the associated truth table. If you need further assistance with that (which you probably won't need), let me know.

The truth table for '$\exists x P(x)$ or $\exists x Q(x)$' would look like this: truth table

Now calculate the truth table for $\exists x \in X \colon P(x) \text{ or } Q(x)$ and compare those two. If they agree in each instance, they are equivalent.

The 2nd statement can be handled similarly. Only in this case, you need to verify that whenever the truth table for $\exists x \in X \colon P(x) \text{ and } Q(x)$ shows true, then so does the truth table for $\exists x \in X P(x) \text{ and } \exists x \in X Q(x)$.

edit: In any way, it's way more comfortable to prove these facts without referring to truth tables.

Claim: $\exists x \in X (P(x) \text{ and } Q(x)) \implies \exists x \in X P(x) \text{ and } \exists x \in X Q(x)$.

Proof. If $\exists x \in X (P(x) \text{ and } Q(x)$ is false, then the implication is vacuously true. Otherwise there is some $c \in X$ such that both $P(c)$ and $Q(c)$ are true. So in particular, there is some $x \in X$ such that $P(x)$ is true (namely $x=c$). And there is also some $x \in X$ such that $Q(x)$ is true (again, take $x=c$). Therefore $\exists x \in X P(x) \text{ and } \exists x \in X Q(x)$ is true. Q.E.D.

$\endgroup$
  • $\begingroup$ Thanks for the guidance. I'm still confused by the $∃x∈X$ part and how you would incorporate that into a truth table $\endgroup$ – aL_eX Nov 9 '16 at 15:21
  • $\begingroup$ Oh, and I made a mistake in the second statement by writing $\iff$ instead of $\implies$. Sorry about that $\endgroup$ – aL_eX Nov 9 '16 at 15:23
  • 1
    $\begingroup$ @aL_eX I edited my answer to take both of your comments into account. $\endgroup$ – Stefan Mesken Nov 9 '16 at 15:38
1
$\begingroup$

The informal way I would approach this would be to partition $X$ into 4 sets:

  • $X_{00}$ The $x$ where $\lnot P(x)$ and $\lnot Q(x)$
  • $X_{01}$ The $x$ where $\lnot P(x)$ and $Q(x)$
  • $X_{10}$ The $x$ where $P(x)$ and $\lnot Q(x)$
  • $X_{11}$ The $x$ where $P(x)$ and $Q(x)$

Also using the relation

$$\bigg(\exists x \in {A \cup B}~:~ R(x)\bigg) \iff \bigg((\exists x \in A~:~ R(x)) \lor (\exists x \in B ~:~ R(x))\bigg)$$

Then work out the left hand side:

$$\begin{array} {rccl} \exists x \in X ~:~ (P(x) \lor Q(x)) & \iff & & \exists x \in X_{00} ~:~ (P(x) \lor Q(x)) \\ & & \lor & \exists x \in X_{01} ~:~ (P(x) \lor Q(x)) \\ & & \lor & \exists x \in X_{10} ~:~ (P(x) \lor Q(x)) \\ & & \lor & \exists x \in X_{11} ~:~ (P(x) \lor Q(x)) \\ \\ & \iff & & \exists x \in X_{00} ~:~ (\bot \lor \bot) \\ & & \lor & \exists x \in X_{01} ~:~ (\bot \lor \top) \\ & & \lor & \exists x \in X_{10} ~:~ (\top \lor \bot) \\ & & \lor & \exists x \in X_{11} ~:~ (\top \lor \top) \\ \\ & \iff & & \bot \\ & & \lor & (X_{01} \ne \emptyset) \\ & & \lor & (X_{10} \ne \emptyset) \\ & & \lor & (X_{11} \ne \emptyset) \end{array}$$

And the right hand side

$$\begin{array} {rccl} (\exists x \in X ~:~ P(x)) \lor (\exists x \in X ~:~ Q(x)) & \iff & & \exists x \in X_{00} ~:~ P(x) \lor \exists x \in X_{01} ~:~ Q(x) \\ & & \lor & \exists x \in X_{01} ~:~ P(x) \lor \exists x \in X_{01} ~:~ Q(x) \\ & & \lor & \exists x \in X_{10} ~:~ P(x) \lor \exists x \in X_{10} ~:~ Q(x) \\ & & \lor & \exists x \in X_{11} ~:~ P(x) \lor \exists x \in X_{11} ~:~ Q(x) \\ \\ & \iff & & \exists x \in X_{00} ~:~ \bot \lor \exists x \in X_{01} ~:~ \bot \\ & & \lor & \exists x \in X_{01} ~:~ \bot \lor \exists x \in X_{01} ~:~ \top \\ & & \lor & \exists x \in X_{10} ~:~ \top \lor \exists x \in X_{10} ~:~ \bot \\ & & \lor & \exists x \in X_{11} ~:~ \top \lor \exists x \in X_{11} ~:~ \top \\ \\ & \iff & & \bot \lor \bot \\ & & \lor & \bot \lor (X_{01} \ne \emptyset) \\ & & \lor & (X_{10} \ne \emptyset) \lor \bot \\ & & \lor & (X_{11} \ne \emptyset) \lor (X_{11} \ne \emptyset) \end{array}$$

Then you just have to establish:

$$\begin{array} {c} \bigg(\bot \lor (X_{01} \ne \emptyset) \lor (X_{10} \ne \emptyset) \lor (X_{11} \ne \emptyset)\bigg) \\ \iff \\ \bot \lor \bot \lor \bot \lor (X_{01} \ne \emptyset) \lor (X_{10} \ne \emptyset) \lor \bot \lor (X_{11} \ne \emptyset) \lor (X_{11} \ne \emptyset) \end{array}$$

Same thing can be done for the second relation, working it out for $\exists x \in X ~:~ (P(x) \land Q(x))$ and $\exists x \in X ~:~ P(x) \land \exists x \in X ~:~ Q$.

A formal (natural deduction) proof of the second would be:

$$\begin{array} {rll} (1) & \quad \quad Px \land Qx & \text{Premise} \\ (2) & \quad \quad Px & \text{And Elim of 1} \\ (3) & \quad \quad \exists t ~ Pt & \text{Exists Intro of 2} \\ (4) & \quad \quad Qx & \text{And Elim of 1} \\ (5) & \quad \quad \exists t ~ Qt & \text{Exists Intro of 4} \\ (6) & \quad \quad \exists t ~ Pt \land \exists t ~ Qt & \text{And Intro of 3 and 5} \\ \\ (7) & \quad \quad \exists x (Px \land Qx) & \text{Premise} \\ (8) & \quad \quad \exists t ~ Pt \land \exists t ~ Qt & \text{Or Elimination of 7, 1 through 6} \\ \\ (9) & \exists x (Px \land Qx) \Rightarrow (\exists t ~ Pt \land \exists t ~ Qt) & \text{Implication Intro of 7 through 8} \\ \end{array}$$

$\endgroup$

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.