Day 1: consistent and maximally consistent sets. Day 2: Lindenbaum's Lemma, the Truth Lemma and the Completeness Theorem. Day 3: strong completeness and compactness.
By the end of this week you will be able to:
Today we set up the plan of the proof of the Completeness Theorem and carry out its first step: from a formula that cannot be deduced we build a consistent set, and we study the largest consistent sets.
The Soundness Theorem says that \(\vdash\) never proves too much: every theorem is a tautology. The Completeness Theorem says that \(\vdash\) proves enough: every tautology is a theorem. In symbols, if \(\models\varphi\) then \(\vdash\varphi\). Soundness was proved by looking at a deduction line by line. For completeness there is no deduction to look at: we are given only a truth table, and we must show that a deduction exists.
We prove the contrapositive: if \(\nvdash\varphi\), then \(\not\models\varphi\). So we start from a formula \(\varphi\) that has no deduction, and we must produce a valuation that makes \(\varphi\) false. The plan has four steps, shown in Figure 1.
Step 2 is where the real work is. A consistent set such as \(\{\neg\varphi\}\) says very little; a maximally consistent set says something about every formula, and that is what a valuation needs.
We collect the facts about consistency that the plan needs. The first says that an inconsistent set is useless as a set of assumptions: it proves everything.
Proof. (a) Let \(\Gamma\) be inconsistent: \(\Gamma\vdash\varphi\) and \(\Gamma\vdash\neg\varphi\) for some \(\varphi\). Let \(\psi\) be any formula. By Lemma 9.5(a), \(\vdash\neg\varphi\to(\varphi\to\psi)\), so \(\Gamma\vdash\neg\varphi\to(\varphi\to\psi)\) by Proposition 8.35(b). Two applications of MP (Proposition 8.35(c)) give \(\Gamma\vdash\varphi\to\psi\) and then \(\Gamma\vdash\psi\). Conversely, if \(\Gamma\) deduces every formula, it deduces \(p\) and \(\neg p\), so it is inconsistent.
(b) If \(\Gamma\vdash\varphi\) and \(\Gamma\vdash\neg\varphi\), then \(\Delta\vdash\varphi\) and \(\Delta\vdash\neg\varphi\) by Proposition 8.35(b). □
The proof of Proposition 10.1(a) is a recipe. From \(\varphi\) and \(\neg\varphi\) we deduce any \(\psi\) by writing out the deduction of \(\neg\varphi\to(\varphi\to\psi)\): (L1) gives \(\neg\varphi\to(\neg\psi\to\neg\varphi)\), and (L3) turns \(\neg\psi\to\neg\varphi\) into \(\varphi\to\psi\).
Line 3 is (L1) with \(\varphi:=\neg p\) and \(\psi:=\neg q\); line 5 is (L3) with \(\varphi:=p\) and \(\psi:=q\).
The next lemma is the tool for step 1 of the plan. It says: if \(\neg\varphi\) leads both to \(\psi\) and to \(\neg\psi\), then \(\varphi\) holds.
For all formulas \(\varphi,\psi\): \(\ \vdash(\neg\varphi\to\neg\psi)\to((\neg\varphi\to\psi)\to\varphi)\).
Proof. By the Deduction Theorem, applied twice, it is enough to show \(\neg\varphi\to\neg\psi,\ \neg\varphi\to\psi\vdash\varphi\):
Line 3 is (L3) with \(\psi\) in place of \(\varphi\) and \(\varphi\) in place of \(\psi\). □
If \(\Gamma\nvdash\varphi\), then \(\Gamma\cup\{\neg\varphi\}\) is consistent.
Proof. Suppose that \(\Gamma\cup\{\neg\varphi\}\) is inconsistent: for some \(\psi\), \(\Gamma,\neg\varphi\vdash\psi\) and \(\Gamma,\neg\varphi\vdash\neg\psi\). By the Deduction Theorem, \(\Gamma\vdash\neg\varphi\to\psi\) and \(\Gamma\vdash\neg\varphi\to\neg\psi\). By Lemma 10.3 and MP twice, \(\Gamma\vdash\varphi\). This contradicts \(\Gamma\nvdash\varphi\). □
Note that the proposition does not assume that \(\Gamma\) is consistent. It does not need to: if \(\Gamma\) is inconsistent, then \(\Gamma\vdash\varphi\) for every \(\varphi\) by Proposition 10.1(a), so the hypothesis \(\Gamma\nvdash\varphi\) never holds. With \(\Gamma=\varnothing\) the proposition is step 1 of the plan: if \(\nvdash\varphi\), then \(\{\neg\varphi\}\) is consistent.
Let \(\Gamma\) be consistent.
Proof. (a) Suppose \(\Gamma,\varphi\vdash\psi\) and \(\Gamma,\varphi\vdash\neg\psi\). By the Deduction Theorem, \(\Gamma\vdash\varphi\to\psi\) and \(\Gamma\vdash\varphi\to\neg\psi\). Since \(\Gamma\vdash\varphi\), MP gives \(\Gamma\vdash\psi\) and \(\Gamma\vdash\neg\psi\). So \(\Gamma\) is inconsistent, contrary to the assumption.
(b) Either \(\Gamma\nvdash\varphi\), and then \(\Gamma\cup\{\neg\varphi\}\) is consistent by Proposition 10.4; or \(\Gamma\vdash\varphi\), and then \(\Gamma\cup\{\varphi\}\) is consistent by (a). □
Self-check only. Nothing here counts towards your grade.
Write a deduction for each claim, following the recipe of Example 10.2. You may use (assump.), (L1) to (L9),
MP and HS. Type \(\neg\) as ~, \(\to\) as ->, \(\wedge\) as & and
\(\vee\) as \/, or use the buttons. Use "Add line" for more lines.
(a) As in Example 10.2(a), with \(q\) in place of \(p\) and \(p\) in place of \(q\):
(b) First \(q\) by MP, then the recipe with \(\varphi:=q\) and \(\psi:=\neg r\):
(c) First take the conjunction apart with (L4) and (L5):
A set of formulas \(\Gamma\) is maximally consistent if \(\Gamma\) is consistent and every set \(\Delta\) with \(\Gamma\subsetneq\Delta\) is inconsistent.
Equivalently: \(\Gamma\) is consistent, and \(\Gamma\cup\{\varphi\}\) is inconsistent for every formula \(\varphi\notin\Gamma\). (If some \(\Delta\supsetneq\Gamma\) were consistent, pick \(\varphi\in\Delta\setminus\Gamma\); then \(\Gamma\cup\{\varphi\}\subseteq\Delta\) would be consistent by Proposition 10.1(b).)
So a maximally consistent set is a consistent set that is as large as a consistent set can be: adding any new formula destroys consistency.
Part (b) gives, for every valuation, one maximally consistent set. The next proposition is the form in which maximality is used.
\(\Gamma\) is maximally consistent if and only if \(\Gamma\) is consistent and for every formula \(\varphi\), \(\varphi\in\Gamma\) or \(\neg\varphi\in\Gamma\).
Since \(\Gamma\) is consistent, it never contains both: so for every \(\varphi\), exactly one of \(\varphi\in\Gamma\) and \(\neg\varphi\in\Gamma\) holds.
Proof. (\(\Rightarrow\)) Let \(\Gamma\) be maximally consistent and let \(\varphi\) be a formula. By Proposition 10.5(b), \(\Gamma\cup\{\varphi\}\) or \(\Gamma\cup\{\neg\varphi\}\) is consistent. By maximality a consistent superset of \(\Gamma\) is \(\Gamma\) itself. So \(\varphi\in\Gamma\) or \(\neg\varphi\in\Gamma\).
(\(\Leftarrow\)) Let \(\Gamma\) be consistent and contain \(\varphi\) or \(\neg\varphi\) for every \(\varphi\). Let \(\Delta\supsetneq\Gamma\) and pick \(\psi\in\Delta\setminus\Gamma\). Since \(\psi\notin\Gamma\), we have \(\neg\psi\in\Gamma\subseteq\Delta\). So \(\Delta\vdash\psi\) and \(\Delta\vdash\neg\psi\), and \(\Delta\) is inconsistent. Hence \(\Gamma\) is maximally consistent.
If both \(\varphi\in\Gamma\) and \(\neg\varphi\in\Gamma\), then \(\Gamma\vdash\varphi\) and \(\Gamma\vdash\neg\varphi\) by (assump.), so \(\Gamma\) is inconsistent. □
If \(\Gamma\) is maximally consistent and \(\Gamma\vdash\varphi\), then \(\varphi\in\Gamma\). In particular, every theorem belongs to every maximally consistent set.
Proof. Suppose \(\Gamma\vdash\varphi\) and \(\varphi\notin\Gamma\). By Proposition 10.8, \(\neg\varphi\in\Gamma\), so \(\Gamma\vdash\neg\varphi\). Then \(\Gamma\) is inconsistent, a contradiction. If \(\vdash\varphi\), then \(\Gamma\vdash\varphi\) by Proposition 8.35(b), so \(\varphi\in\Gamma\). □
Membership in a maximally consistent set behaves like truth: a negation is in \(\Gamma\) exactly when the formula is not, and an implication is in \(\Gamma\) exactly when its antecedent is not or its consequent is.
Let \(\Gamma\) be maximally consistent. For all formulas \(\varphi,\psi\):
Proof. (a) is Proposition 10.8: exactly one of \(\varphi\), \(\neg\varphi\) is in \(\Gamma\).
(b) (\(\Leftarrow\)) If \(\psi\in\Gamma\): by (L1), \(\Gamma\vdash\psi\to(\varphi\to\psi)\), and MP gives \(\Gamma\vdash\varphi\to\psi\). If \(\varphi\notin\Gamma\): then \(\neg\varphi\in\Gamma\) by (a); by Lemma 9.5(a), \(\Gamma\vdash\neg\varphi\to(\varphi\to\psi)\), and MP gives \(\Gamma\vdash\varphi\to\psi\). In both cases \(\varphi\to\psi\in\Gamma\) by Proposition 10.9. (\(\Rightarrow\)) Let \(\varphi\to\psi\in\Gamma\). If \(\varphi\in\Gamma\), then MP gives \(\Gamma\vdash\psi\), so \(\psi\in\Gamma\) by Proposition 10.9. So \(\varphi\notin\Gamma\) or \(\psi\in\Gamma\).
(c) If \(\varphi\wedge\psi\in\Gamma\), then (L4), (L5) and MP give \(\Gamma\vdash\varphi\) and \(\Gamma\vdash\psi\), so both are in \(\Gamma\). If \(\varphi,\psi\in\Gamma\), then (L6) and MP twice give \(\Gamma\vdash\varphi\wedge\psi\), so \(\varphi\wedge\psi\in\Gamma\).
(d) If \(\varphi\in\Gamma\), then (L7) and MP give \(\Gamma\vdash\varphi\vee\psi\); if \(\psi\in\Gamma\), use (L8). Conversely, let \(\varphi\vee\psi\in\Gamma\) and \(\varphi\notin\Gamma\). Then \(\neg\varphi\in\Gamma\). By Definition 9.1, \(\varphi\vee\psi\) is the formula \(\neg\varphi\to\psi\), so MP gives \(\Gamma\vdash\psi\) and \(\psi\in\Gamma\). □
Let \(\Gamma\) be maximally consistent with \(p\in\Gamma\) and \(q\notin\Gamma\). We decide, for several formulas, whether they belong to \(\Gamma\). Each answer follows from the status of the parts.
The answers depend only on which primitive propositions are in \(\Gamma\), in the same way that the truth value of a formula depends only on the values of its primitive propositions. Compare: under the valuation with \(v(p)=\mathrm T\), \(v(q)=\mathrm F\), the five formulas have the values \(\mathrm T,\mathrm F,\mathrm T,\mathrm T,\mathrm F\), matching the answers above. This is no accident; it is the Truth Lemma of Day 2.
Self-check only. Nothing here counts towards your grade.
Let \(\Gamma\) be maximally consistent with \(p\in\Gamma\), \(q\notin\Gamma\) and \(r\in\Gamma\). For each formula, decide whether it is in \(\Gamma\), using Proposition 10.10.
(a) \(\neg r\notin\Gamma\): \(r\in\Gamma\), rule (a).
(b) \(q\to p\in\Gamma\): the antecedent \(q\) is not in \(\Gamma\), rule (b).
(c) \(p\to q\notin\Gamma\): \(p\in\Gamma\) and \(q\notin\Gamma\), rule (b).
(d) \(\neg(p\to q)\in\Gamma\): \(p\to q\notin\Gamma\) by (c), rule (a).
(e) \(p\wedge\neg q\in\Gamma\): \(p\in\Gamma\) and \(\neg q\in\Gamma\), rule (c).
(f) \(q\vee r\in\Gamma\): \(r\in\Gamma\), rule (d).
(g) \(\neg p\vee\neg r\notin\Gamma\): neither \(\neg p\) nor \(\neg r\) is in \(\Gamma\), rule (d).
(h) \(\neg(p\to p)\notin\Gamma\): \(p\to p\in\Gamma\) by rule (b) (its consequent is in \(\Gamma\)), or because it is a theorem (Proposition 10.9); then rule (a).
Today we extend any consistent set to a maximally consistent one, read the result as a valuation, and prove that every tautology has a deduction.
The construction of today adds formulas to a set one at a time, and it must consider every formula. So we need all formulas in a single list \(\varphi_1,\varphi_2,\varphi_3,\dots\). The primitive propositions are \(p_1,p_2,p_3,\dots\); as usual we write \(p,q,r\) for \(p_1,p_2,p_3\).
There is a list \(\varphi_1,\varphi_2,\varphi_3,\dots\) in which every formula appears exactly once.
Proof. A formula is a finite string of symbols from \(\neg\), \(\to\), \((\), \()\) and the primitive propositions. For \(n\ge1\) let \(F_n\) be the set of formulas that have at most \(n\) symbols and use only \(p_1,\dots,p_n\). Each \(F_n\) is finite: there are finitely many strings of length at most \(n\) over an alphabet of \(n+4\) symbols. Every formula lies in some \(F_n\): take \(n\) at least the length of the formula and at least the largest index of a primitive proposition in it. Now list the members of \(F_1\) in any order, then the members of \(F_2\) that are not in \(F_1\), then the members of \(F_3\) that are not in \(F_2\), and so on. Every formula appears, at the stage of the first \(F_n\) that contains it, and it appears only there. □
Many lists work. For the examples below we choose short lists that begin with the formulas we care about; the rest of the list does not matter for the first few steps.
Every consistent set \(\Gamma\) is contained in a maximally consistent set \(\Gamma'\).
Proof. Fix a list \(\varphi_1,\varphi_2,\dots\) of all formulas (Lemma 10.12). We define sets \(\Gamma_0,\Gamma_1,\Gamma_2,\dots\) by recursion: \[\Gamma_0=\Gamma,\qquad \Gamma_{n+1}=\begin{cases}\Gamma_n\cup\{\varphi_{n+1}\}&\text{if }\Gamma_n\cup\{\varphi_{n+1}\}\text{ is consistent,}\\ \Gamma_n&\text{otherwise.}\end{cases}\] So at stage \(n+1\) we look at the formula \(\varphi_{n+1}\) and add it if this keeps the set consistent; otherwise we skip it. Let \(\Gamma'=\bigcup_{n\ge0}\Gamma_n\), the set of formulas that belong to some \(\Gamma_n\). We prove four claims.
Claim 1: each \(\Gamma_n\) is consistent. By induction on \(n\). \(\Gamma_0=\Gamma\) is consistent by assumption. If \(\Gamma_n\) is consistent, then \(\Gamma_{n+1}\) is either \(\Gamma_n\cup\{\varphi_{n+1}\}\), which was added only because it is consistent, or \(\Gamma_n\) itself.
Claim 2: \(\Gamma=\Gamma_0\subseteq\Gamma_1\subseteq\Gamma_2\subseteq\cdots\subseteq\Gamma'\). Each \(\Gamma_{n+1}\) contains \(\Gamma_n\) by definition, and each \(\Gamma_n\) is contained in the union \(\Gamma'\).
Claim 3: \(\Gamma'\) is consistent. Suppose \(\Gamma'\vdash\psi\) and \(\Gamma'\vdash\neg\psi\). Take a deduction of \(\psi\) from \(\Gamma'\) and a deduction of \(\neg\psi\) from \(\Gamma'\). Together they have finitely many lines, so they use finitely many members of \(\Gamma'\) as assumptions, say \(\chi_1,\dots,\chi_m\). Each \(\chi_i\) lies in some \(\Gamma_{n_i}\). Let \(N\) be the largest of \(n_1,\dots,n_m\) (and \(N=0\) if \(m=0\)). By Claim 2, all of \(\chi_1,\dots,\chi_m\) lie in \(\Gamma_N\). So both deductions are deductions from \(\Gamma_N\): every line is an axiom, a member of \(\Gamma_N\), or follows by MP. Hence \(\Gamma_N\vdash\psi\) and \(\Gamma_N\vdash\neg\psi\), which contradicts Claim 1.
Claim 4: \(\Gamma'\) is maximally consistent. By Definition 10.6 and Claim 3, it is enough to show that \(\Gamma'\cup\{\psi\}\) is inconsistent for every \(\psi\notin\Gamma'\). Let \(\psi\notin\Gamma'\). The formula \(\psi\) is in the list, say \(\psi=\varphi_k\). Since \(\varphi_k\notin\Gamma'\) and \(\Gamma_k\subseteq\Gamma'\), we have \(\varphi_k\notin\Gamma_k\). So at stage \(k\) the formula was skipped, which means that \(\Gamma_{k-1}\cup\{\varphi_k\}\) is inconsistent. Since \(\Gamma_{k-1}\subseteq\Gamma'\), the set \(\Gamma'\cup\{\varphi_k\}\) contains \(\Gamma_{k-1}\cup\{\varphi_k\}\), so it is inconsistent by Proposition 10.1(b).
By Claims 2 to 4, \(\Gamma'\) is a maximally consistent set containing \(\Gamma\). □
Two remarks on the proof. First, the recursion is a definition, not a procedure that we could run: at each stage, exactly one of "\(\Gamma_n\cup\{\varphi_{n+1}\}\) is consistent" and "it is inconsistent" is true, and this is all the definition needs; it does not tell us how to find out which one. Second, Claim 3 uses the finiteness of deductions in an essential way: a deduction from an infinite set still has finitely many lines.
Let \(\Gamma=\{p\to q\}\). To decide whether a set is consistent we use the two tools we have: a satisfying valuation shows consistency (Corollary 9.22), and a pair of deductions of \(\psi\) and \(\neg\psi\) shows inconsistency.
| Stage | Set considered | Consistent? | Result |
|---|---|---|---|
| 1 | \(\Gamma_0\cup\{\neg q\}=\{p\to q,\ \neg q\}\) | Yes: \(v(p)=v(q)=\mathrm F\) satisfies it. | \(\Gamma_1=\{p\to q,\ \neg q\}\) |
| 2 | \(\Gamma_1\cup\{p\}=\{p\to q,\ \neg q,\ p\}\) | No: it deduces \(q\) by MP and \(\neg q\) by (assump.). | \(\Gamma_2=\Gamma_1\) |
| 3 | \(\Gamma_2\cup\{q\}=\{p\to q,\ \neg q,\ q\}\) | No: \(q\) and \(\neg q\) are both members. | \(\Gamma_3=\Gamma_2\) |
| 4 | \(\Gamma_3\cup\{\neg p\}=\{p\to q,\ \neg q,\ \neg p\}\) | Yes: \(v(p)=v(q)=\mathrm F\) satisfies it. | \(\Gamma_4=\{p\to q,\ \neg q,\ \neg p\}\) |
| 5 | \(\Gamma_4\cup\{q\to p\}\) | Yes: under \(v(p)=v(q)=\mathrm F\), \(q\to p\) is true. | \(\Gamma_5=\{p\to q,\ \neg q,\ \neg p,\ q\to p\}\) |
The valuation \(v(p)=v(q)=\mathrm F\) satisfies every set in this run.
In (a), \(\neg p\in\Gamma'\); in (b), \(p\in\Gamma'\). The maximally consistent extension depends on the order of the list. Lindenbaum's Lemma promises some extension, not a unique one.
Step 3 of the plan: a maximally consistent set can be read as a valuation.
Let \(\Gamma\) be maximally consistent. The valuation \(v_\Gamma\) is defined on the primitive propositions by \[v_\Gamma(p)=\begin{cases}\mathrm T&\text{if }p\in\Gamma,\\ \mathrm F&\text{if }p\notin\Gamma.\end{cases}\]
By definition, \(v_\Gamma\) agrees with \(\Gamma\) on the primitive propositions. The Truth Lemma says that it agrees with \(\Gamma\) on all formulas.
Let \(\Gamma\) be maximally consistent. For every formula \(\varphi\), \[[\![\varphi]\!]_{v_\Gamma}=\mathrm T\quad\text{if and only if}\quad\varphi\in\Gamma.\]
Proof. By induction on the number of connectives in \(\varphi\). Since \(\wedge\) and \(\vee\) are abbreviations, \(\varphi\) is a primitive proposition, a negation or an implication.
\(\varphi=p\). \([\![p]\!]_{v_\Gamma}=v_\Gamma(p)\), and \(v_\Gamma(p)=\mathrm T\) iff \(p\in\Gamma\) by Definition 10.15.
\(\varphi=\neg\psi\). Assume the claim for \(\psi\). Then \([\![\neg\psi]\!]_{v_\Gamma}=\mathrm T\) iff \([\![\psi]\!]_{v_\Gamma}=\mathrm F\) iff \(\psi\notin\Gamma\) (induction hypothesis) iff \(\neg\psi\in\Gamma\) (Proposition 10.10(a)).
\(\varphi=\psi\to\chi\). Assume the claim for \(\psi\) and \(\chi\). Then \([\![\psi\to\chi]\!]_{v_\Gamma}=\mathrm T\) iff \([\![\psi]\!]_{v_\Gamma}=\mathrm F\) or \([\![\chi]\!]_{v_\Gamma}=\mathrm T\) iff \(\psi\notin\Gamma\) or \(\chi\in\Gamma\) (induction hypothesis) iff \(\psi\to\chi\in\Gamma\) (Proposition 10.10(b)). □
The proof is short because Proposition 10.10 did the work: the membership rules for \(\neg\) and \(\to\) are the truth table clauses for \(\neg\) and \(\to\), with "\(\in\Gamma\)" in place of "true".
Definition 10.15 makes sense for any set \(\Gamma\), but the Truth Lemma fails without maximal consistency.
We now put the steps together. The first theorem is the heart of the matter: it turns a consistent set into a valuation.
Every consistent set of formulas is satisfiable.
Proof. Let \(\Gamma\) be consistent. By Lindenbaum's Lemma there is a maximally consistent \(\Gamma'\supseteq\Gamma\). By the Truth Lemma, \(v_{\Gamma'}\) makes every member of \(\Gamma'\) true. In particular it makes every member of \(\Gamma\) true, so \(v_{\Gamma'}\) satisfies \(\Gamma\). □
Together with Corollary 9.22 this says: a set is consistent if and only if it is satisfiable. We can now decide consistency with truth tables, in both directions. For example, in a run of Lindenbaum's construction a formula is skipped exactly when the set considered is unsatisfiable.
Self-check only. Nothing here counts towards your grade.
Let \(\Gamma=\{\neg p\to q\}\) and suppose the list of all formulas begins \(\varphi_1=\neg q\), \(\varphi_2=\neg p\), \(\varphi_3=p\to q\), \(\varphi_4=q\to r\), \(\varphi_5=r\), \(\varphi_6=p\to\neg r\). For each stage decide whether \(\varphi_n\) is added to \(\Gamma_{n-1}\) or skipped. By Theorem 10.18 and Corollary 9.22, the formula is added exactly when \(\Gamma_{n-1}\cup\{\varphi_n\}\) is satisfiable.
Stage 1. \(\{\neg p\to q,\ \neg q\}\) is satisfied by \(v(p)=\mathrm T\), \(v(q)=\mathrm F\). Added: \(\Gamma_1=\{\neg p\to q,\ \neg q\}\).
Stage 2. \(\Gamma_1\cup\{\neg p\}\): a satisfying valuation would need \(q\) false and \(\neg p\) true, and then \(\neg p\to q\) false. Unsatisfiable, so skipped: \(\Gamma_2=\Gamma_1\).
Stage 3. \(\Gamma_2\cup\{p\to q\}\): \(q\) must be false, so \(\neg p\to q\) forces \(p\) true, and then \(p\to q\) is false. Skipped: \(\Gamma_3=\Gamma_2\).
Stage 4. \(\Gamma_3\cup\{q\to r\}\) is satisfied by \(v(p)=\mathrm T\), \(v(q)=\mathrm F\) and any value of \(r\). Added: \(\Gamma_4=\{\neg p\to q,\ \neg q,\ q\to r\}\).
Stage 5. \(\Gamma_4\cup\{r\}\) is satisfied by \(v(p)=\mathrm T\), \(v(q)=\mathrm F\), \(v(r)=\mathrm T\). Added: \(\Gamma_5=\{\neg p\to q,\ \neg q,\ q\to r,\ r\}\).
Stage 6. \(\Gamma_5\cup\{p\to\neg r\}\): \(r\) is a member, and \(p\) is forced true as in stage 3, so \(p\to\neg r\) is false under every valuation that satisfies \(\Gamma_5\). Skipped: \(\Gamma_6=\Gamma_5\).
For every formula \(\varphi\): if \(\models\varphi\), then \(\vdash\varphi\).
Proof. We prove the contrapositive. Suppose \(\nvdash\varphi\). By Proposition 10.4 with \(\Gamma=\varnothing\), the set \(\{\neg\varphi\}\) is consistent. By Theorem 10.18 some valuation \(v\) satisfies \(\{\neg\varphi\}\), that is, \([\![\neg\varphi]\!]_v=\mathrm T\) and \([\![\varphi]\!]_v=\mathrm F\). So \(\varphi\) is not a tautology: \(\not\models\varphi\). □
With Corollary 9.18 (every theorem is a tautology) we get: \(\vdash\varphi\) if and only if \(\models\varphi\). The two regions of Week 9, Figure 2 are the same region (Figure 3).
To show \(\vdash\varphi\), it is enough to check that \(\varphi\) is a tautology, with a truth table or a short argument; the Completeness Theorem then guarantees that a deduction exists. To show \(\nvdash\varphi\), give a valuation that makes \(\varphi\) false (Soundness). No deduction needs to be written in either case.
| \(p\) | \(q\) | \(p\to q\) | \((p\to q)\to p\) | \(((p\to q)\to p)\to p\) |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | T | T |
| F | T | T | F | T |
| F | F | T | F | T |
The main column is all T, so the formula is a tautology, and by Theorem 10.19 it has a deduction. We know this without having seen the deduction.
Self-check only. Nothing here counts towards your grade.
For each formula decide whether it is a theorem. Use the Method above: a truth table for yes, a valuation for no.
(a) Theorem: this is Peirce's law, Example 10.20(a).
(b) Theorem. False would need \(p\to q\) true, \(\neg q\) true and \(\neg p\) false, so \(p\) true and \(q\) false, and then \(p\to q\) is false.
(c) Not a theorem: \(v(p)=v(q)=\mathrm T\) makes \(\neg p\to q\) true and \(p\to\neg q\) false.
(d) Theorem: it is an instance of (L2), so it even has a one-line deduction.
(e) Not a theorem: \(v(p)=\mathrm T\), \(v(q)=\mathrm F\) makes \(p\vee q\) true and \(p\wedge q\) false.
(f) Theorem. \(\neg(p\to q)\) is true only when \(p\) is true and \(q\) is false, and then the consequent \(p\) is true.
Today we prove that \(\Gamma\vdash\varphi\) and \(\Gamma\models\varphi\) are the same relation, and we derive the Compactness Theorem.
The Completeness Theorem is about tautologies, that is, about \(\varnothing\models\varphi\). The same proof works for any set of assumptions.
For every set of formulas \(\Gamma\) and every formula \(\varphi\): \[\Gamma\vdash\varphi\quad\text{if and only if}\quad\Gamma\models\varphi.\]
A set of formulas is consistent if and only if it is satisfiable.
Proof. Satisfiable sets are consistent by Corollary 9.22; consistent sets are satisfiable by Theorem 10.18. □
The two notions of consequence of this course, the semantic \(\models\) defined by truth tables and the syntactic \(\vdash\) defined by deductions, are the same relation. In Week 9 we had one tool for each side of a question: a deduction to show \(\Gamma\vdash\varphi\), a valuation to show \(\Gamma\nvdash\varphi\). Now one tool decides both sides.
Let \(\Gamma=\{p_1\}\cup\{p_n\to p_{n+1}: n\ge1\}=\{p_1,\ p_1\to p_2,\ p_2\to p_3,\ p_3\to p_4,\ \dots\}\). We claim \(\Gamma\vdash p_{100}\). By Theorem 10.21 it is enough to show \(\Gamma\models p_{100}\). Let \(v\) satisfy \(\Gamma\). We show \(v(p_n)=\mathrm T\) for every \(n\ge1\), by induction on \(n\). For \(n=1\), \(p_1\in\Gamma\). If \(v(p_n)=\mathrm T\), then since \(p_n\to p_{n+1}\) is true under \(v\), also \(v(p_{n+1})=\mathrm T\). In particular \(v(p_{100})=\mathrm T\).
Here the deduction is easy to describe (write \(p_1\), then \(p_1\to p_2\) and \(p_2\) by MP, and so on up to \(p_{100}\)), but note what it uses: only the first hundred members of the infinite set \(\Gamma\). The next section shows that this is always so.
Self-check only. Nothing here counts towards your grade.
For each claim, decide whether it holds, by Theorem 10.21. If it does not hold, give a valuation that satisfies the left side and makes the right side false.
(a) Deducible: if \(p\to q\) and \(\neg q\) are true, then \(p\) cannot be true, so \(\neg p\) is true.
(b) Not deducible: \(v(p)=\mathrm T\), \(v(q)=\mathrm F\) makes \(p\vee q\) true and \(p\to q\) false.
(c) Deducible: if \(p\wedge q\) is false, one of \(p\), \(q\) is false, so one of \(\neg p\), \(\neg q\) is true.
(d) Deducible: if \(p\wedge q\) is true then \(p\) is true, so \(r\) is true by \(p\to r\).
(e) Not deducible: \(v(p)=\mathrm T\), \(v(q)=v(r)=\mathrm F\) makes \(p\wedge q\) false, so \((p\wedge q)\to r\) is true, while \(p\to r\) is false.
(f) Deducible. If \(v(p)=\mathrm T\), the consequent \((q\to p)\to p\) is true. If \(v(p)=\mathrm F\), then \((p\to q)\to q\) has the value of \(q\), and \((q\to p)\to p\) is \(\neg q\to\mathrm F\), which also has the value of \(q\); so the formula is \(q\to q\), true.
A deduction is finite. This simple fact, passed through Theorem 10.21, gives a statement about valuations that mentions no deductions at all.
If \(\Gamma\vdash\varphi\), then there is a finite set \(\Gamma_0\subseteq\Gamma\) with \(\Gamma_0\vdash\varphi\).
Proof. Take a deduction of \(\varphi\) from \(\Gamma\) and let \(\Gamma_0\) be the set of members of \(\Gamma\) that occur as lines of it. \(\Gamma_0\) is finite, because the deduction has finitely many lines, and the same sequence is a deduction of \(\varphi\) from \(\Gamma_0\). □
A set of formulas \(\Gamma\) is satisfiable if and only if every finite subset of \(\Gamma\) is satisfiable.
Proof. (\(\Rightarrow\)) A valuation that satisfies \(\Gamma\) satisfies every subset of \(\Gamma\).
(\(\Leftarrow\)) We prove the contrapositive: if \(\Gamma\) is unsatisfiable, then some finite subset of \(\Gamma\) is unsatisfiable. Let \(\Gamma\) be unsatisfiable. By Corollary 10.22, \(\Gamma\) is inconsistent: \(\Gamma\vdash\psi\) and \(\Gamma\vdash\neg\psi\) for some \(\psi\). By Lemma 10.25 there are finite \(\Gamma_1,\Gamma_2\subseteq\Gamma\) with \(\Gamma_1\vdash\psi\) and \(\Gamma_2\vdash\neg\psi\). Let \(\Gamma_0=\Gamma_1\cup\Gamma_2\), a finite subset of \(\Gamma\). By Proposition 8.35(b), \(\Gamma_0\vdash\psi\) and \(\Gamma_0\vdash\neg\psi\), so \(\Gamma_0\) is inconsistent, and by Corollary 9.22 it is unsatisfiable. □
If \(\Gamma\models\varphi\), then there is a finite set \(\Gamma_0\subseteq\Gamma\) with \(\Gamma_0\models\varphi\).
Proof. From \(\Gamma\models\varphi\) we get \(\Gamma\vdash\varphi\) by Theorem 10.21, then \(\Gamma_0\vdash\varphi\) for a finite \(\Gamma_0\subseteq\Gamma\) by Lemma 10.25, then \(\Gamma_0\models\varphi\) by Soundness. □
Both statements are about truth tables only, but the proof goes through deductions. A direct proof is possible but much longer; the Completeness Theorem lets the finiteness of deductions do the work.
Let \(\Gamma=\{p_1,\ \neg p_5\}\cup\{p_n\to p_{n+1}: n\ge1\}\). The set is unsatisfiable: as in Example 10.24, a valuation that satisfies \(p_1\) and all \(p_n\to p_{n+1}\) makes every \(p_n\) true, so it does not satisfy \(\neg p_5\). By the Compactness Theorem some finite subset is unsatisfiable, and here we can point to it: \[\Gamma_0=\{p_1,\ p_1\to p_2,\ p_2\to p_3,\ p_3\to p_4,\ p_4\to p_5,\ \neg p_5\}.\] A valuation satisfying the first five members makes \(p_5\) true, so it falsifies \(\neg p_5\). The members \(p_5\to p_6,\ p_6\to p_7,\dots\) play no role. Removing any member of \(\Gamma_0\) gives a satisfiable set: for example, without \(p_3\to p_4\), the valuation with \(p_1,p_2,p_3\) true and \(p_4,p_5\) false satisfies the rest.
Proposition 10.4 says: if \(\Gamma\cup\{\neg\varphi\}\) is inconsistent, then \(\Gamma\vdash\varphi\). This question proves the companion statement for \(\Gamma\cup\{\varphi\}\).
| Formula | In \(\Gamma\)? | Reason |
|---|---|---|
| (i) \(r\) | ||
| (ii) \(p\to r\) | ||
| (iii) \(\neg r\vee q\) | ||
| (iv) \((q\to p)\wedge\neg r\) | ||
| (v) \(\neg(p\to q)\to r\) | ||
| (vi) \((r\to p)\to(p\to\neg q)\) |
Let \(\Gamma=\{p\to\neg q\}\).
| \(n\) | \(\varphi_n\) | Added or skipped? | \(\Gamma_n\) | Reason |
|---|---|---|---|---|
| 1 | \(q\) | |||
| 2 | \(p\) | |||
| 3 | \(\neg p\) | |||
| 4 | \(q\to p\) | |||
| 5 | \(\neg p\vee\neg q\) |