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

Question

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:

Lemma 2 (Relevance lemma).

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!

Answer 1

Preliminary comments

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

See also page 4:

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