Predicate logic, proof of validity of sequent.

364 Views Asked by At

The goal is to prove that $\forall x (P(x) \land Q(x)) \vdash \forall x (P(x) \to Q(x))$ in natural deduction.

Would like to find out if I did this natural deduction correctly and if not where did I go wrong?

Image of natural deduction proof of validity

Any advice would be appreciated. Thank you!

1

There are 1 best solutions below

0
On BEST ANSWER

It is mostly okay, but needs a little tweaking.

The first assumption should be arbitrary. $P(x_0)$ is an assumption, not derived from the premise. Conditional Introduction discharges the second assumption, and Universal Introduction immediately finishes the proof.

$$\def\fitch#1#2{\quad\begin{array}{|l}#1\\\hline #2\end{array}}\fitch{~~1.~~\forall x~(P(x)\land Q(x))\hspace{10ex}\textsf{Premise}}{\fitch{~~2.~~[x_0]\hspace{20.5ex}\textsf{Assumption (Arbitrary Witness)}}{\fitch{~~3.~~P(x_0)\hspace{15ex}\textsf{Assumption}}{~~4.~~P(x_0)\land Q(x_0)\hspace{6.5ex}\textsf{Universal Elimination (1,2)}\\~~5.~~Q(x_0)\hspace{14.75ex}\textsf{Conjunction Elimination (4)}}\\~~6.~~P(x_0)\to Q(x_0)\hspace{9ex}\textsf{Conditional Introduction (3-5)}}\\~~7.~~\forall x~(P(x)\to Q(x))\hspace{9.25ex}\textsf{Universal Introduction (2-6)}}$$

Now, some proof formats do allow you to combine the assumptions, in which case Universal Introduction also handles the conditional.

$$\fitch{~~1.~~\forall x~(P(x)\land Q(x)\hspace{10ex}\textsf{Premise}}{\fitch{~~2.~~[x_0]~P(x_0)\hspace{13ex}\textsf{Assumption (Restricted Arbitrary Witness)}}{~~3.~~P(x_0)\land Q(x_0)\hspace{8.75ex}\textsf{Universal Elimination (1,2)}\\~~4.~~Q(x_0)\hspace{17ex}\textsf{Conjunction Elimination (3)}}\\~~5.~~\forall x~(P(x)\to Q(x))\hspace{8.25ex}\textsf{Universal Introduction (2-4)}}$$