# Help understanding a particular proof of the compactness theorem for Propositional Calculus.

I've reading through this proof, I don't understand the last part: the claim $\tau \models \Sigma$.

Note: I'll use $AP(\varphi)$ and $\text{Var}(\varphi)$ interchangeably, to mean the variables that appear in the formula $\varphi$.

They show that if $X=\{v(p): p\in\text{Var}(\varphi)\}$, it is satisfiable, finite and $X\subseteq\Sigma'$. Then $X\cup\{\varphi\}$ is also satisfiable, as $\Sigma'$ is finitely satisfiable, ok. But then they say "by the relevance lemma, there exists a $\tau'\dots$", but that's not what the relevance lemma says:

Let $ϕ ∈ F orm$ with $τ, \tau' ∈ 2 ^{P rop}$.

If $τ∩AP(ϕ) =\tau ' ∩ AP(ϕ)$, then $ϕ(τ ) = ϕ(τ')$.

They use a weird notation, but what I understand from that is that if $\tau',\tau$ are valuations such that $\tau'(p)=\tau(p)$ for every $p\in\text{Var}(\gamma)$, then $\tau'(\gamma)=\tau(\gamma)$.

I also don't understand what they mean by $\tau'\mid_{AP(\varphi)}\models \varphi$

Could someone clarify the entire paragraph after the "Claim: $\tau\models\Sigma$"? Thanks!

Yes, $$\tau$$ and $$\tau'$$ are truth assignments; see page 2:

$$τ : Prop → \{ 0, 1 \}$$

and see Lecture 3, page 1: Definition 1. A truth assignment, $$τ$$ , is an element of $$2^{PROP}$$.

We can now think of a formula as a circuit, which maps truth assignments to Boolean values: $$\varphi : 2^{PROP} → \{ 0, 1 \}$$.

The Relevance lemma says: if two truth assignments $$\tau, \tau'$$ "agree on" the sentential letters $$p_i$$ of $$\varphi$$, then the formula $$\varphi$$ maps $$\tau$$ and $$\tau'$$ on the same truth value.

$$\tau|_{AP(\varphi)}$$ is the "restriction" of the truth assignment $$\tau$$ to the sentential letters of $$\varphi$$.

In propositional logic, a truth assignment $$\tau$$ is a model; see Lecture 3, page 2: Definition 2. $$\vDash \subseteq (2^{PROP} \times FORM)$$ is a binary relation, between truth assignments and formulas. $$\vDash$$ is called the satisfaction relation.

We define it inductively as follows:

$$τ \vDash p$$, for $$p ∈ PROP$$, if $$τ(p) = 1$$, meaning that $$p$$ holds if $$p$$ is true. [...]

Thus, the Relevance Lemma can be reformulated as :

if $$\tau|_{AP(\varphi)}=\tau'|_{AP(\varphi)}$$, then $$\tau|_{AP(\varphi)} \vDash \varphi$$ iff $$\tau'|_{AP(\varphi)} \vDash \varphi$$.

Regarding the proof of the Compactness Theorem, and specifically of the Claim: $$\tau \vDash \Sigma$$, you are right regarding the statement:

"Then, by the Relevance Lemma, there exists $$τ' \in 2^{PROP}, τ'|_{AP(\varphi)} \vDash \varphi$$ and $$\tau'|_{AP(\varphi)} \vDash X$$";

it is misleading: if $$X ∪ \{ \varphi \}$$ is satisfiable, then - by definition - there exists a truth assignment $$\tau'$$, such that ...

The fact that $$\tau|_{AP(\varphi)} \vDash X$$ is a simple consequence of $$\tau \vDash X$$ and the way $$X$$ is built; clearly, $$\tau|_{AP(\varphi)}$$ and $$\tau$$ "agree on" the sentential letters of $$\varphi$$.

Finally:

$$τ$$ and $$τ'$$ must assign the same value to propositions in $$AP(\varphi)$$, that is, $$\tau|_{AP(\varphi)} = \tau'|_{AP(\varphi)}$$. Therefore $$\tau|_{AP(\varphi)} \vDash \varphi$$ [we have seen above that $$τ'|_{AP(\varphi)} \vDash \varphi$$], and by the Relevance Lemma, $$\tau \vDash \varphi$$ [again : $$\tau|_{AP(\varphi)}$$ and $$\tau$$ "agree on" the sentential letters of $$\varphi$$.].

• I don't understand what's the point of saying "$\tau'\mid_{AP(\varphi)}\models \varphi$": I interpret this as $\tau'\mid_{AP(\varphi)}(\varphi)=1$, but then I think this is an ill-formed expression, as $\tau'\mid_{AP(\varphi)}$ is a function whose domain is $AP(\varphi)$, and thus evaluating it at $\varphi$ could make no sense... Feb 5, 2016 at 20:20
• Also, don't you mean that $\tau,\tau'$ map $\varphi$ to the same truth value (and not the other way around)? I still don't understand what justifies the existence of a $\tau'$ which satisfies $X$ and $\varphi$... Feb 5, 2016 at 20:21