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.

  • 2
    $\begingroup$ See Compactness Theorem for Propositional Logic. $\endgroup$ – Mauro ALLEGRANZA Apr 18 at 15:29
  • $\begingroup$ @Chrysa Hi, are you familiar with truth trees? I can show you an easy and intuitive proof. $\endgroup$ – Simone Apr 19 at 20:42
  • $\begingroup$ I am familiar with those. I would appreciate it if you showed me this proof. $\endgroup$ – 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.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.