0
$\begingroup$

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 $<S,S\rightarrow P,P>$, 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 $<R\rightarrow P,(R\rightarrow P)\rightarrow((\neg S\vee R)\rightarrow(S\rightarrow P)),\neg S\vee R,(\neg S\vee R)\rightarrow(S\rightarrow P),S,S\rightarrow P,P>$, 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?

$\endgroup$
3
  • $\begingroup$ The result is simple if we assume that $\Sigma$ is finite. Otherwise, we have to prove Compactness. $\endgroup$ Oct 21, 2020 at 8:43
  • $\begingroup$ Oh yes. Thank you for informing that. $\endgroup$
    – kkkk
    Oct 21, 2020 at 9:01
  • $\begingroup$ @MauroALLEGRANZA I actually don't follow your thought. Could you write an answer for the "trick" please? $\endgroup$
    – kkkk
    Oct 21, 2020 at 10:47

1 Answer 1

0
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .