# Propositional Logic: $Τ\vDash\varphi\implies\existsΤ_0\subseteq T$ such that $Τ_0\vDash\varphi$

Suppose $$Τ$$ is an infinite set of propositional types and $$\varphi$$ a propositional type. Prove that if $$Τ\vDash\varphi$$, then a finite set $$Τ_0\subseteq T$$ exists, such that $$Τ_0\vDash\varphi$$.

I understand this is true based on my intuition but I cannot think of a strict mathematical way to justify it.

Any help would be appreciated.

• – Mauro ALLEGRANZA Apr 18 at 15:29
• @Chrysa Hi, are you familiar with truth trees? I can show you an easy and intuitive proof. – Simone Apr 19 at 20:42
• I am familiar with those. I would appreciate it if you showed me this proof. – Chrysa Apr 21 at 14:11

I was thinking about the proof using truth trees I promised you, but that would be a graphical nightmare of Tex, and I'm not sure I'm capable of providing it here. So I'm outlining a different proof instead; see if this convinces you, if not then I'll prove it using the method I promised you but I'm afraid it would have to be rather wordy and descriptive.

Since you're are familiar with truth trees then I presume that I don't have to persuade you about the fact that "$$Z\vDash\varphi$$" can be put as "$$Z,\neg\varphi\vDash$$" , (in words: "$$Z,\neg\varphi$$ is inconsistent"). So the claim you were trying to wrap your head around is a particular case of the Compactness Theorem for propositional logic which can be stated as:

if $$Z\vDash$$ then, for some finite $$Z'$$, included in $$Z$$, $$Z\vDash$$ .

A lemma $$(L1)$$: Let "$$\Gamma\succcurlyeq$$" mean: "for some finite $$\Gamma'$$, included in $$\Gamma$$, $$\Gamma'\vDash$$". For any sentence-letter $$P_i$$: If $$\Gamma,P_i\succcurlyeq$$ and $$\Gamma,\neg P_i\succcurlyeq$$ then $$\Gamma\succcurlyeq$$.

Proof: suppose $$\Gamma,P_i\succcurlyeq$$ and $$\Gamma,\neg P_i\succcurlyeq$$, then by definition for some finite $$\Gamma'$$ in $$\Gamma$$, we have $$\Gamma',P_i\vDash$$ and also for some finite $$\Gamma''$$ in $$\Gamma$$, we have $$\Gamma'',\neg P_i\vDash$$. But if $$\Gamma'',\neg P_i\vDash$$ then $$\Gamma''\vDash P_i$$, and together with $$\Gamma',P_i\vDash$$ then by Cutting we get $$\Gamma',\Gamma''\vDash$$. But $$\Gamma',\Gamma''$$ is also finite and included in $$\Gamma$$, thus the result follows $$\Box$$

Let $$\Gamma$$ name some formulae, possibly a coutable infinity of them, and let $$P_1,P_2,P_3,...$$ be a list, possibly infinite, of all the sentence-letters in $$\Gamma$$. Define recursively a series of formulae as such: $$\Gamma_0 = \Gamma,$$

$$\Gamma_{n+1} =\begin{cases}\Gamma_n, P_{n+1}\;\;\text{if}\;\;\Gamma_n,\neg P_{n+1}\,\succcurlyeq, \\ \Gamma_n,\neg P_{n+1}\;\;\text{otherwise}. \end{cases}$$

Assume $$\Gamma\not\succcurlyeq$$, to be read as "it's not the case that $$\Gamma\succcurlyeq$$", (in words: "$$\Gamma$$ finitely satisfiable", "all finite $$\Gamma'$$ in $$\Gamma$$ are consistent"). As an inductive hypothesis let $$\Gamma_k\not\succcurlyeq$$, hence, by $$(L1)$$, $$\;$$ $$\Gamma_k,P_{k+1}\not\succcurlyeq$$ $$\;$$ or $$\;$$ $$\Gamma_k,\neg P_{k+1}\not\succcurlyeq$$. But in both cases it means that $$\Gamma_{k+1}\not\succcurlyeq$$.

Now we define an interpretation $$I$$ by stipulating that, for each letter $$P_n$$ $$|P_n|_I=1\;\;\text{iff}\;\; P_n\;\text{is in}\; \Gamma_n.$$ Define $$\pm P_i$$ to be either $$P_i$$ or $$\neg P_i$$, and let $$\phi$$ be any formula in $$\Gamma$$, containing just the letters $$P_i,...,P_j$$. Then by our construction, for some choice of $$\pm P_i$$ we have $$\pm P_i,...,\pm P_j$$ $$\,$$ in $$\,$$ $$\Gamma_j$$, and $$\pm P_i,...,\pm P_j$$ is finite. So by the inductive result just above $$\pm P_i,...,\pm P_j$$ is also consistent. But then $$\pm P_i,...,\pm P_j \vDash\phi$$ (think about truth tables if you need convincing for it), and since, by construction of $$\Gamma_j$$, the premises are true then so is $$\phi$$; that is: $$|\phi|_I=1$$.

So all formulae $$\phi_n$$ (no matter how many) are true in the intepretation $$I$$, this means that $$\Gamma$$ cannot be inconsistent, or symbolically: $$\Gamma\nvDash$$. We just proved that if $$\,\Gamma\not\succcurlyeq\,$$ then $$\,\Gamma\nvDash\,$$, which is just the contrapositive of the theorem we're trying to prove: $$\text{if} \;\; \Gamma\vDash \;\; \text{then} \;\; \Gamma\succcurlyeq.$$