Deductively prove that $ \vdash (p \land q) \rightarrow p$

91 Views Asked by At

I need to prove that this is a tautology (without using truth tables, i.e. deductively), because I need to use it for another proof.

$$\vdash (p \land q) \rightarrow p$$

I'm allowed to use the following as axioms:

  1. $X \implies (Y \implies X)$

  2. $(X \implies (Y \implies Z)) \implies ((X \implies Y) \implies (X \implies Z)$

  3. $(\neg Y \implies \neg X) \implies (X \implies Y)$

Also, I am allowed to use the regular rules: modus ponens, introduction of conjunction, disjunction and implication, double negation etc.

My thoughts: This doesn't seem too outrageous to prove, but I have no premises to work on. I'm stuck even on the first step because I don't have any premises to work with. Could anyone help? Do I need to make assumptions, for example that $p$ and $q$ are true and use them as premises?

1

There are 1 best solutions below

1
On BEST ANSWER

Every tautology is a formula that is a valid consequence of an empty set of premises, so there is no way to avoid the complication of having no premises to work on. However, this observation should be your first clue on how to proceed. Since no premises are present, you must assume something and build from there. For this reason, most tautologies can be proven by a discharge rule such as conditional proof or reductio ad absurdum (proof by contradiction).

Here, since the main connective in your conclusion is a conditional, a conditional proof is worth attempting.

$ \vdash (p \land q) \to p $

$\{1\} \:\:\:\:\:\:\: 1. \:\: p \land q \:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:$ Assumption for Conditional Proof

$\{1\} \:\:\:\:\:\:\: 2. \:\: p \:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:$ $1$ Conjunction-Elimination

$\{-\} \:\:\:\:\:\: 3. \:\: (p \land q) \to p \:\:\:\:\:$ $1,2$ Conditional Proof

I assume $p \land q$ on line $1$ and, under that assumption, I am able to derive $p$ via conjunction elimination on line $2$. Hence, I am justified in concluding if $p \land q$ then $p$.