Inference Lemma Proof?

53 Views Asked by At

Suppose that $\Gamma$ is a subset of $\mathcal{L_0}$, $\phi$ and $\psi$ formulas. If $\Gamma \vdash \psi$ and $\Gamma \vdash (\psi\to \phi)$ then $\Gamma \vdash \phi$.

Proof: Let $\langle \phi_1,\dots,\phi_n\rangle$ be a $\Gamma$-proof of $\psi$, thus $\phi_n = \psi$. Let $\langle \psi_1,\dots,\psi_m\rangle$ be a $\Gamma$-proof of $(\psi\to\phi)$.

Here's where I get lost.

Then $\langle\phi_1,\dots,\phi_n, \psi_1,\dots,\psi_m,\phi\rangle$ is a $\Gamma$-proof and thus $\Gamma \vdash \phi$.

Where is $\phi$ coming from tacked on at the end? Why is this a gamma proof? I feel that for the $\Gamma$-proof of $(\psi\to\phi)$, $\psi_m = (\psi\to\phi)$. So the concatenation of the two should be $\langle\phi_1,\dots,\phi_n, \psi_1,\dots,\psi_m\rangle$ which leads nowhere.

1

There are 1 best solutions below

4
On BEST ANSWER

I suspect that you have a rule of inference that allows you to infer $\varphi$ from the pair of formulas $\psi\to\varphi$ and $\psi$. If so, the final step of the proof is justified by the earlier appearance of $\varphi_n$ and $\psi_m$ in the proof.