Natural Deduction: Epsilon Rule and Its Application

Question

I interpret the first example as, if you have a formula that belongs to all formulas in this language, then it is deductible from any formula in this language. I think my explaining might be wrong or else you can just prove every deduction with this.

For the 2nd example, where did the singular P come from in line 1? It isn't part of the two implicit assumptions. How does it use the 1st example?

Answer 1

Your interpretation of the first example is not correct. $\Sigma$ is an arbitrary set of formulas. It contains some formulas but not necessarily all of them. Also $\Sigma\vdash A$ does not mean "$A$ is deducible from any formula in $\Sigma$". It means, "with assumptions $\Sigma$, you can deduce $A$". In the process of the deduction you might use more than one assumptions from $\Sigma$. So it's not "any" but "some".

Having these in mind, the correct interpretation of the first example is "from a set of formulas you can deduce each of the formulas within the set". For example, if $\Sigma=\{A,B\}$, then $A,B\vdash A$ and $A,B\vdash B$.

So, rule $(\epsilon)$ is: If $\phi\in\Sigma$, then $\Sigma\vdash \phi$.

Let's take step by step the second example. Note that while building a proof, some formulas might be added or removed from the assumptions. So, in the beginning of a proof we can take whatever assumptions we want, as long as in the end only those stated at the excerise remain as assumptions. Therefore, in the beginning of a proof, we choose the set of assumptions that is the most convenient for us to end the proof with the desired set of assumptions. In this example, we start with a set of assumptions $\Sigma=\{\phi\to\psi, \psi\to\xi, \phi\}$ and end with the set $\Sigma'=\Sigma\setminus\{\phi\}=\{\phi\to\psi, \psi\to\xi\}$, which is the desired set of assumptions.

• Line 1: Here, $\Sigma=\{\phi\to\psi, \psi\to\xi, \phi\}$. Since $\phi\to\psi\in\Sigma$, by rule $(\epsilon)$, you get $$\phi\to\psi, \psi\to\xi, \phi\vdash \phi\to\psi$$So, here is a use of the first example.
• Line 2: $\Sigma$ is the same as in line 1 and since $\phi\in\Sigma$, again by rule $(\epsilon)$, you get $$\phi\to\psi, \psi\to\xi, \phi\vdash\phi$$Again, this is a use of the first example.
• Line 3: In the above two lines you have deduced $\Sigma\vdash\phi\to\psi$ and $\Sigma\vdash\phi$. So, by implication elimination you get $$\phi\to\psi, \psi\to\xi, \phi\vdash\psi$$
• Line 4: Since $\psi\to\xi\in\Sigma$, by rule $(\epsilon)$, you get $$\phi\to\psi, \psi\to\xi, \phi\vdash \psi\to\xi$$Again, this is a use of the first example.
• Line 5: In lines 3 and 4, you have deduced $\Sigma\vdash\psi$ and $\Sigma\vdash\psi\to\xi$, so by implication elimination you get $$\phi\to\psi, \psi\to\xi, \phi\vdash\xi$$
• Line 6: Here the rule applied is implication introduction on line 5. But, when applying this rule, the assumption of the implication is removed from the assumptions of the deduction. In other words, if $\Sigma\vdash A$ and $B\in \Sigma$, then $\Sigma\setminus\{B\}\vdash B\to A$. So, take $\Sigma$ to be the same as above, $A=\xi$ and $B=\phi$. Then, you get $$\phi\to\psi, \psi\to\xi\vdash\phi\to\xi$$