0
$\begingroup$

"Show that ∃x(P(x) ∧ R(x)) is a logical consequence of (1)∀x(Q(x)→P(x)) and (2)∃x(Q(x)∧R(x))."

In normal English I can explain it (I think), but I'm having trouble writing it down as a proper mathematical proof.

There exists an x where Q(x) is true and R(x) is true (2). Since for all x where Q(x) is true P(x) is also true, there exists an x where R(x) is true and P(x) is true.

Right? How do I write that down formally and concisely?

$\endgroup$
1
  • 1
    $\begingroup$ What system of axioms and rules of inference are you using? $\endgroup$
    – ShyPerson
    Apr 3 at 4:59

2 Answers 2

0
$\begingroup$

Your reasoning makes sense. By (2), there is some object, call it $c$, such that $Q(c)$ and $R(c)$ are both true. By (1) and $Q(c)$ we can deduce $P(c)$. We have that $P(c)$ and $R(c)$ are both true, which proves $\exists x (P(x)\land R(x))$.

How to "formally" prove something (especially if it's fairly obvious like this) depends on which kinds of proof steps (rules of inference) you're allowed to use.

You could formulate this argument as:

$\endgroup$
0
$\begingroup$

How do I write that down formally and concisely?

Using a form of natural deduction (screenshot):

enter image description here

Plain-text version:

1   ALL(x):[Q(x) => P(x)] & EXIST(x):[Q(x) & R(x)]
    Premise

2   ALL(x):[Q(x) => P(x)]
    Split, 1

3   EXIST(x):[Q(x) & R(x)]
    Split, 1

4   Q(y) & R(y)
    E Spec, 3

5   Q(y)
    Split, 4

6   R(y)
    Split, 4

7   Q(y) => P(y)
    U Spec, 2

8   P(y)
    Detach, 7, 5

9   P(y) & R(y)
    Join, 8, 6

10  ALL(x):[Q(x) => P(x)] & EXIST(x):[Q(x) & R(x)]
    => EXIST(x):[P(x) & R(x)]
    Conclusion, 1
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .