# tautological implication and deduction

My problem goes like this: Show that whenever $$\Sigma\vDash\tau$$, then there exists a deducion from $$\Sigma$$, the last component of which is $$\tau$$.

I tried to use the definition and work backward: Given $$\tau$$ with $$\Sigma\vDash\tau$$, if $$\tau$$ is tautology, or $$\tau\in\Sigma$$, then we are done. If not, but if one can find a wff $$\alpha$$ that satisfies the statement that $$\gamma$$ is tautology, or that $$\gamma\in\Sigma$$ for each of $$\gamma\in\{\alpha,\alpha\rightarrow\tau\}$$, then we are also done. $$(*)$$Otherwise, choose $$\alpha\in\Sigma$$ and consider $$\alpha\rightarrow\tau$$. Note that since $$\Sigma\vDash\alpha$$, we have that $$\Sigma\vDash(\alpha\rightarrow\tau)$$. Then since $$\Sigma\vDash(\alpha\rightarrow\tau)$$, we follow the above step again (but if we follow the $$(*)$$'s step, do it with $$\beta\in\Sigma-\{\alpha\}$$ so that we don't choose same $$\alpha$$ twice.). We claim that these steps finish at some point.

For example, say we have $$\Sigma=\{\neg S\vee R,R\rightarrow P,S\}$$ and we want a deduction from $$\Sigma$$, the last component of which is $$P$$. First we try $$$$, and see that it is not a deduction. So we look at $$<\neg S\vee R,(\neg S\vee R)\rightarrow(S\rightarrow P),S,S\rightarrow P,P>$$ and we see that this is not a deduction either. So we now look at $$$$, and we see that this is indeed a deduction finishing the steps.

And now I just need to show that the above steps finish at some point where I am stuck. Any idea?

• The result is simple if we assume that $\Sigma$ is finite. Otherwise, we have to prove Compactness. Oct 21, 2020 at 8:43
• Oh yes. Thank you for informing that.
– kkkk
Oct 21, 2020 at 9:01
– kkkk
Oct 21, 2020 at 10:47

Indeed, if $$\Sigma$$ is finite, the above steps finishes at somepoint; one can actually show that the above step finishes when the steps were applied until all the members of $$\Sigma$$ is used for the step $$(*)$$ repeatedly. The reason is $$\Sigma\vDash\tau$$. Let's look at an example.

Let $$\Sigma=\{\alpha,\beta,\gamma\}$$, and we want to have a deducion from $$\Sigma$$, the last component of which is $$\tau$$, and say $$\Sigma\vDash\tau$$. If we apply the step $$(*)$$ repeatedly until we use all the member of $$\Sigma$$, then we get, for instance, $$<\alpha,\alpha\rightarrow(\beta\rightarrow(\gamma\rightarrow \tau)),\beta, \beta\rightarrow(\gamma\rightarrow \tau), \gamma,\gamma\rightarrow \tau,\tau>$$.

Now if we look at $$\alpha\rightarrow(\beta\rightarrow(\gamma\rightarrow \tau))$$ we can see that it is tautology, because of $$\Sigma\vDash\tau$$: $$\alpha\rightarrow(\beta\rightarrow(\gamma\rightarrow \tau))$$ cannot have $$F$$ truth values, because if $$\alpha,\beta,\gamma$$ are true, then $$\tau$$ cannot be $$F$$ (because of $$\Sigma\vDash\tau$$), which is the only way to get $$F$$ for $$\alpha\rightarrow(\beta\rightarrow(\gamma\rightarrow \tau))$$.

If $$\Sigma$$ is infinite, then consider the following corollary to the compactness theorem: $$\text{if }\Sigma\vDash\tau,\text{ then there is a finite }\Sigma_0\subseteq\Sigma\text{ such that }\Sigma_0\vDash\tau.$$Then we can argue as above with $$\Sigma_0$$.