4.10 Compactness and Maximal Consistent Sets

This section is optional, and nothing outside it depends on it.

Every list of premises in this chapter has been finite, and the proof of completeness needed that: its Step 1 lists the atoms of $\Gamma$ and $\psi$ , and there are only finitely many of them because $\Gamma$ is a finite list (Theorem 4.8.4). But a statement about infinitely many objects can come with infinitely many premises. Give each $n \ge 1$ an atom $p_n$ , read “the $n$ -th lamp is on”, and the rules “the first lamp is on” and “if the $n$ -th lamp is on, so is the next” are one premise for each $n$ . This section defines $\vdash$ and $\models$ for such collections of premises, proves completeness for them by a route different from that of Section 4.8, and deduces from it the compactness theorem: a collection of formulas can be made true all at once as soon as each finite part of it can. The word “collection” keeps its everyday sense throughout; nothing here needs more.

4.10.1. Infinitely many premises

A derivation is finite, so from infinitely many premises it can use only finitely many; a valuation, on the other hand, gives every formula a value at once.

Definition 4.10.1 (Derivability and Entailment from Infinitely Many Premises)

Let $\Gamma$ be a collection of formulas, finite or infinite, and $\psi$ a formula. $\Gamma \vdash \psi$ if $\psi$ is derivable from some finite list of members of $\Gamma$ ; $\Gamma$ is consistent if $\Gamma \nvdash \bot$ . $\Gamma \models \psi$ if every valuation that makes every member of $\Gamma$ true makes $\psi$ true; $\Gamma$ is satisfiable if some valuation makes every member of $\Gamma$ true.

In words: a derivation has finitely many lines, so it can cite only finitely many premises. That is why $\vdash$ goes through finite lists of members, while $\models$ looks at all of $\Gamma$ at once. For a finite list the new definitions agree with the old. A derivation from part of a list is a derivation from the list, by Lemma 2.3.3 (a), so $\vdash$ means what Definition 1.2.3 said, and consistent means what Definition 3.2.1 said. The definitions of $\models$ and satisfiable say for a finite list exactly what Definition 4.5.3 and Definition 4.5.2 said. “Finite list of members” allows repetitions and any order; neither matters, by Lemma 2.3.3 (a) and by the definitions of $\models$ and satisfiable.

An example. Let $\Gamma$ consist of $p_1$ and every formula $p_n \to p_{n+1}$ with $n \ge 1$ . Then $\Gamma \vdash p_3$ : from the finite list $p_1, \ p_1 \to p_2, \ p_2 \to p_3$ , two $\mathrm{{\to}E}$ lines give $p_2$ and then $p_3$ . And $\Gamma \models p_n$ for every $n \ge 1$ : a valuation making every member of $\Gamma$ true makes $p_1$ true, and makes $p_{n+1}$ true whenever it makes $p_n$ true, so it makes every $p_n$ true, by Axiom 4.2.1 on $n$ , started at $1$ .

Quick check. Is the collection consisting of $p_1 \vee p_2$ and every $\neg p_n$ with $n \ge 2$ satisfiable? Is it consistent?

Solution. Satisfiable: the valuation making $p_1$ true and every other atom false makes every member true. Hence consistent. A derivation of $\bot$ would use some finite list of members; that list is made true by the same valuation, so it is satisfiable, hence consistent by Section 4.7, and derives no $\bot$ .

4.10.2. Listing all formulas

The construction below goes through all formulas one at a time, so it needs them in one list.

Lemma 4.10.1 (The Formulas Can Be Listed)

There is a list $\varphi_0, \varphi_1, \varphi_2, \dots$ of formulas in which every formula occurs.

In words: the atoms are listed already ( $p, q, r, p_1, p_2, \dots$ ), and each formula is a finite string of symbols, so the formulas can be listed by size, finitely many at each stage.

Second readingHow to list every formula

Idea. List by size. At stage $n$ , allow only the first $n$ atoms and strings of at most $n$ symbols. Each stage is finite, and every formula fits into some stage.

Proof. Write the atoms in one list $a_1, a_2, a_3, \dots$ (say $p, q, r, p_1, p_2, \dots$ in this order). For each $n \ge 1$ , consider the strings of length at most $n$ over the $n + 8$ symbols $a_1, \dots, a_n, \ \bot, \ \neg, \ \wedge, \ \vee, \ \to, \ \leftrightarrow, \ (, \ ) .$ There are finitely many such strings (at most $(n+8)^n$ of each length up to $n$ ), so finitely many of them are formulas. Stage $n$ lists, in any order, the formulas among them that no earlier stage listed. Write the stages one after another and number the entries $\varphi_0, \varphi_1, \dots$ . Each stage $n$ lists at least the atom $a_n$ , which is available for the first time, so the stages together list infinitely many formulas.

Every formula occurs. Let $\varphi$ have length $\ell$ , and let its atoms be among $a_1, \dots, a_m$ (with $m = 0$ if it has none). At stage $n = \max\{\ell, m\}$ (note $\ell \ge 1$ ), $\varphi$ is a string of length at most $n$ over the symbols of that stage, so it is listed then, or earlier.

4.10.3. Lindenbaum’s construction

The new proof of completeness works the other way round from Section 4.8. It does not build a derivation. It starts from a consistent collection and builds a row that makes all of it true. The row is read off a collection that has made up its mind about every formula.

A collection $\Delta$ is maximal consistent if it is consistent and, for every formula $\varphi$ , $\varphi$ is in $\Delta$ or $\neg\varphi$ is.

The construction rests on one step. Exercise C2 of Section 3.2 (Exercise (C2: Challenge: Splitting an inconsistency, used later)) proved it for finite lists; here it is again, for collections, with its proof.

The key step. If $\Delta$ is consistent, then $\Delta$ with $\varphi$ added, or $\Delta$ with $\neg\varphi$ added, is consistent. Suppose both were inconsistent. Then there are finite lists $\Delta_1$ and $\Delta_2$ of members of $\Delta$ with $\Delta_1, \varphi \vdash \bot$ and $\Delta_2, \neg\varphi \vdash \bot$ (if a derivation of $\bot$ does not use $\varphi$ , or $\neg\varphi$ , adding it as a premise changes nothing, by weakening). By weakening, both hold with the list $\Delta_1, \Delta_2$ in place of $\Delta_1$ and of $\Delta_2$ . A $\mathrm{\neg I}$ box on $\varphi$ gives $\Delta_1, \Delta_2 \vdash \neg\varphi$ , and an $\mathrm{RAA}$ box on $\neg\varphi$ gives $\Delta_1, \Delta_2 \vdash \varphi$ (this is Proposition 3.2.2). Then $\mathrm{\neg E}$ , by chaining (Lemma 2.3.3 (c)), gives $\Delta_1, \Delta_2 \vdash \bot$ , and $\Delta$ would be inconsistent.

Lemma 4.10.2 (Lindenbaum’s Lemma)

Every consistent collection of formulas is contained in a maximal consistent collection.

Idea. Go through the list of all formulas, and add each one or its negation, whichever keeps the collection consistent. The key step says one of them always does. At the end, every formula has been decided, and no contradiction has been let in, because a contradiction would show up at some finite stage.

Proof. Let $\Gamma$ be consistent, and let $\varphi_0, \varphi_1, \dots$ be the list of Lemma 4.10.1. Define collections $\Delta_0, \Delta_1, \dots$ by recursion on $n$ , each from the one before: $\Delta_0 \mathrel{:=} \Gamma ; \qquad \Delta_{n+1} \mathrel{:=} \begin{cases} \Delta_n \text{ with } \varphi_n \text{ added}, & \text{if that collection is consistent;} \\ \Delta_n \text{ with } \neg\varphi_n \text{ added}, & \text{otherwise.} \end{cases}$ Every $\Delta_n$ is consistent, by Axiom 4.2.1: $\Delta_0 = \Gamma$ is; and if $\Delta_n$ is, then $\Delta_{n+1}$ is, by its definition in the first case and by the key step in the second. Each $\Delta_n$ contains the one before.

Let $\Delta$ consist of the formulas that belong to some $\Delta_n$ . Then $\Delta$ contains $\Gamma = \Delta_0$ .

$\Delta$ is consistent. A derivation of $\bot$ from $\Delta$ uses a finite list of members of $\Delta$ . Each of them is in some $\Delta_n$ , so all of them are in the $\Delta_N$ with the largest of those indices $N$ ( $N = 0$ if the list is empty), since the collections grow. That derivation would then show $\Delta_N \vdash \bot$ , but $\Delta_N$ is consistent.

$\Delta$ is maximal. Every formula is some $\varphi_n$ , and $\varphi_n$ or $\neg\varphi_n$ is in $\Delta_{n+1}$ , hence in $\Delta$ . This proves the lemma.

Quick check. Start from $\Gamma = \{p \vee q, \ \neg p\}$ with a list of formulas beginning $p, q$ . What are $\Delta_1$ and $\Delta_2$ ?

Solution. $\Gamma$ with $p$ added is inconsistent ( $p$ and $\neg p$ give $\bot$ by $\mathrm{\neg E}$ ), so $\Delta_1$ adds $\neg p$ , which is already there: $\Delta_1 = \Gamma$ . $\Delta_1$ with $q$ added is satisfiable ( $p = \mathrm{F}$ , $q = \mathrm{T}$ ), hence consistent (Section 4.7), so $\Delta_2$ adds $q$ : $\Delta_2 = \{p \vee q, \ \neg p, \ q\}$ .

4.10.4. A row from a maximal consistent collection

A maximal consistent collection behaves like the collection of formulas that are true in one row: it contains a negation exactly when it lacks the negated formula, a conjunction exactly when it contains both parts, and so on through the clauses of Definition 4.4.2.

Lemma 4.10.3 (Maximal Consistent Collections)

Let $\Delta$ be maximal consistent, and let $\varphi$ , $\psi$ be formulas.

(a) If $\Delta \vdash \varphi$ , then $\varphi \in \Delta$ .
(b) Exactly one of $\varphi$ , $\neg\varphi$ is in $\Delta$ ; and $\bot \notin \Delta$ .
(c) $\varphi \wedge \psi \in \Delta$ iff $\varphi \in \Delta$ and $\psi \in \Delta$ ; $\varphi \vee \psi \in \Delta$ iff $\varphi \in \Delta$ or $\psi \in \Delta$ ; $\varphi \to \psi \in \Delta$ iff $\varphi \notin \Delta$ or $\psi \in \Delta$ ; $\varphi \leftrightarrow \psi \in \Delta$ iff $\varphi$ and $\psi$ are both in $\Delta$ or both not in $\Delta$ .

In words: whatever $\Delta$ derives, it already contains; it decides every formula, one way only; and it treats each connective as the truth table does.

Second readingThe proof: a maximal collection decides everything

Idea. For each clause, find the derivable sequent that says the same thing as the truth table, and let (a) put what $\Delta$ derives into $\Delta$ ; where a formula must be shown missing, derive its negation instead and use (b).

Proof. Derivations from $\Delta$ are combined by Lemma 2.3.3 throughout: two finite lists of members of $\Delta$ can be joined into one, and a sequent already proved can be applied by chaining.

(a) Suppose $\Delta \vdash \varphi$ and $\varphi \notin \Delta$ . By maximality $\neg\varphi \in \Delta$ , so $\Delta \vdash \neg\varphi$ by a one-line derivation, and $\mathrm{\neg E}$ gives $\Delta \vdash \bot$ , against consistency.

(b) At least one of $\varphi$ , $\neg\varphi$ is in $\Delta$ , by maximality. If both were, $\mathrm{\neg E}$ would give $\Delta \vdash \bot$ . And $\bot \in \Delta$ would give $\Delta \vdash \bot$ at once.

(c) Each clause comes from (a), (b) and a derivable sequent.

$\wedge$ . If $\varphi \wedge \psi \in \Delta$ , then $\mathrm{\wedge E}$ gives $\Delta \vdash \varphi$ and $\Delta \vdash \psi$ , so both are in $\Delta$ by (a). If both are in $\Delta$ , $\mathrm{\wedge I}$ gives $\Delta \vdash \varphi \wedge \psi$ , so it is in $\Delta$ by (a).

$\vee$ . If $\varphi \in \Delta$ or $\psi \in \Delta$ , then $\mathrm{\vee I}$ gives $\Delta \vdash \varphi \vee \psi$ , so it is in $\Delta$ by (a). If neither is in $\Delta$ , then $\neg\varphi, \neg\psi \in \Delta$ by (b), and $(\vee 3)$ of Lemma 4.8.1 gives $\Delta \vdash \neg(\varphi \vee \psi)$ ; so $\neg(\varphi \vee \psi) \in \Delta$ by (a), and $\varphi \vee \psi \notin \Delta$ by (b).

$\to$ . If $\varphi \to \psi \in \Delta$ and $\varphi \in \Delta$ , then $\mathrm{{\to}E}$ gives $\Delta \vdash \psi$ , so $\psi \in \Delta$ by (a); hence $\varphi \notin \Delta$ or $\psi \in \Delta$ . Conversely, if $\varphi \notin \Delta$ , then $\neg\varphi \in \Delta$ by (b), and $({\to}1)$ gives $\Delta \vdash \varphi \to \psi$ ; if $\psi \in \Delta$ , then $({\to}2)$ gives it. Either way $\varphi \to \psi \in \Delta$ by (a).

$\leftrightarrow$ . If both $\varphi$ , $\psi$ are in $\Delta$ , $({\leftrightarrow}1)$ gives $\Delta \vdash \varphi \leftrightarrow \psi$ ; if neither, then $\neg\varphi, \neg\psi \in \Delta$ and $({\leftrightarrow}2)$ gives it; in both cases $\varphi \leftrightarrow \psi \in \Delta$ by (a). If exactly one is in $\Delta$ , the other’s negation is in $\Delta$ by (b), and $({\leftrightarrow}3)$ or $({\leftrightarrow}4)$ gives $\Delta \vdash \neg(\varphi \leftrightarrow \psi)$ ; so $\neg(\varphi \leftrightarrow \psi) \in \Delta$ by (a), and $\varphi \leftrightarrow \psi \notin \Delta$ by (b). (With $\varphi \leftrightarrow \psi \in \Delta$ , $\mathrm{{\leftrightarrow}E}$ passes membership from either part to the other, which is the same fact read from the other side.)

So a maximal consistent collection names a row: make an atom true exactly when the collection contains it.

Lemma 4.10.4 (Truth Lemma)

Let $\Delta$ be maximal consistent, and let $v_\Delta$ be the valuation that makes an atom $p$ true exactly when $p \in \Delta$ . Then for every formula $\varphi$ : $v_\Delta(\varphi) = \mathrm{T}$ iff $\varphi \in \Delta$ .

Idea. Induct on $\varphi$ . Each clause of Definition 4.4.2 has a twin in Lemma 4.10.3: part (b) for $\neg$ , part (c) for the binary connectives. The induction hypothesis turns “true under $v_\Delta$ ” into “in $\Delta$ ” for the parts, and the twin does the rest.

Proof. By Theorem 4.3.1, with the property “ $v_\Delta(\varphi) = \mathrm{T}$ iff $\varphi \in \Delta$ ”.

Atoms: this is the definition of $v_\Delta$ . $\bot$ : $v_\Delta(\bot) = \mathrm{F}$ by (V1), and $\bot \notin \Delta$ by Lemma 4.10.3 (b), so both sides of the “iff” fail.

$\neg\varphi$ : $v_\Delta(\neg\varphi) = \mathrm{T}$ iff $v_\Delta(\varphi) = \mathrm{F}$ , by (V2); iff $\varphi \notin \Delta$ , by the induction hypothesis; iff $\neg\varphi \in \Delta$ , by Lemma 4.10.3 (b).

$\varphi \wedge \psi$ : $v_\Delta(\varphi \wedge \psi) = \mathrm{T}$ iff $v_\Delta(\varphi) = \mathrm{T}$ and $v_\Delta(\psi) = \mathrm{T}$ , by (V3); iff $\varphi \in \Delta$ and $\psi \in \Delta$ , by the induction hypothesis; iff $\varphi \wedge \psi \in \Delta$ , by Lemma 4.10.3 (c). The cases $\vee$ , $\to$ , $\leftrightarrow$ are the same: the clause of Definition 4.4.2 for the connective and the clause of Lemma 4.10.3 (c) for it say the same thing, once “true under $v_\Delta$ ” is read as “in $\Delta$ ” for the two parts, as the induction hypothesis allows. This proves the lemma.

4.10.5. Completeness again

Theorem 4.10.5 (Completeness for Infinitely Many Premises)

For every collection $\Gamma$ of formulas, finite or infinite, and every formula $\psi$ : if $\Gamma \models \psi$ , then $\Gamma \vdash \psi$ . Equivalently, every consistent collection is satisfiable.

Idea. If $\Gamma$ does not derive $\psi$ , then adding $\neg\psi$ cannot lead to $\bot$ , since an $\mathrm{RAA}$ box would turn such a derivation into one of $\psi$ . Extend $\Gamma$ with $\neg\psi$ to a maximal consistent collection and read off its row: it makes every member of $\Gamma$ true and $\psi$ false.

Proof. We prove the contrapositive of the first sentence. Suppose $\Gamma \nvdash \psi$ . Then $\Gamma$ with $\neg\psi$ added is consistent. For suppose some finite list of its members derived $\bot$ ; adding $\neg\psi$ to the list if it is not there (weakening), we have $\Gamma_0, \neg\psi \vdash \bot$ for a finite list $\Gamma_0$ of members of $\Gamma$ , and an $\mathrm{RAA}$ box on $\neg\psi$ gives $\Gamma_0 \vdash \psi$ , so $\Gamma \vdash \psi$ . By Lemma 4.10.2, $\Gamma$ with $\neg\psi$ is contained in a maximal consistent $\Delta$ . By Lemma 4.10.4, $v_\Delta$ makes every member of $\Delta$ true, in particular every member of $\Gamma$ , and $\neg\psi$ . So $v_\Delta$ makes $\psi$ false, and $\Gamma \not\models \psi$ .

The equivalence: by Definition 4.10.1 and (V1), $\Gamma$ is satisfiable iff $\Gamma \not\models \bot$ , and consistent iff $\Gamma \nvdash \bot$ . So the first sentence with $\psi = \bot$ is the second. Conversely, given the second, if $\Gamma \nvdash \psi$ , then $\Gamma$ with $\neg\psi$ is consistent, as just shown, hence satisfiable, by a row that refutes $\Gamma \models \psi$ .

Two proofs, two prices. Section 4.8 glued the rows of a truth table into one derivation. That is a construction one can carry out, from $2^n$ row derivations for $n$ atoms, but only for finitely many premises. This section never writes a derivation. It shows that if none exists, then a row exists, by a construction that passes through infinitely many formulas, one at a time, and cannot be finished by hand. The first proof is effective (it writes the derivation down) and limited to finite lists; the second reaches infinite collections and produces no derivation. The second is the route that extends beyond propositional logic.

Second readingA remark on the list of formulas

Besides the rules, and the structural induction and recursion of Section 4.3, the proof used one new fact about the formulas: that they can be listed (Lemma 4.10.1). The construction then decides the formulas in the order of the list, and a different list may give a different $\Delta$ and a different row; any of them refutes $\Gamma \models \psi$ . The proof cites Proposition 2.5.3 nowhere, but its key step uses $\mathrm{RAA}$ , and so does the step from $\Gamma \nvdash \psi$ to the consistency of $\Gamma$ with $\neg\psi$ . It is classical in the same way as the splitting of Section 4.8, which used excluded middle.

4.10.6. Compactness

Theorem 4.10.6 (Compactness)

A collection $\Gamma$ of formulas is satisfiable if and only if every finite list of members of $\Gamma$ is satisfiable. Consequently, $\Gamma \models \psi$ if and only if some finite list of members of $\Gamma$ entails $\psi$ .

Proof. “Only if”: a valuation making every member of $\Gamma$ true makes every member of each finite list true. “If”: every finite list of members of $\Gamma$ is satisfiable, hence consistent, by Section 4.7. So $\Gamma$ is consistent, since a derivation of $\bot$ from $\Gamma$ would use a finite list of members. By Theorem 4.10.5, $\Gamma$ is satisfiable.

For the second sentence: $\Gamma \models \psi$ iff $\Gamma$ with $\neg\psi$ added is unsatisfiable (a valuation making $\Gamma$ true and $\psi$ false is exactly one making both $\Gamma$ and $\neg\psi$ true); iff, by the first sentence, some finite list of its members is unsatisfiable; iff some finite list $\Gamma_0$ of members of $\Gamma$ has $\Gamma_0, \neg\psi$ unsatisfiable (adding $\neg\psi$ to an unsatisfiable list keeps it unsatisfiable, and $\Gamma_0, \neg\psi$ is itself such a list); iff $\Gamma_0 \models \psi$ , by Section 4.5’s reduction of entailment to unsatisfiability.

Example (Infinitely many premises, finitely many used)

Let $\Gamma$ consist of $p_1$ and every $p_n \to p_{n+1}$ with $n \ge 1$ , the lamps of the opening.

(a) Show $\Gamma \models p_{100}$ , and find a finite list of members of $\Gamma$ that entails $p_{100}$ .
(b) Show that a finite list of members of $\Gamma$ that leaves out $p_{50} \to p_{51}$ does not entail $p_{100}$ .

Solution. (a) A valuation making every member of $\Gamma$ true makes $p_1$ true and passes truth from each $p_n$ to $p_{n+1}$ , so it makes every $p_n$ true (Axiom 4.2.1, started at $1$ ), $p_{100}$ among them. The hundred formulas $p_1, \ p_1 \to p_2, \ \dots, \ p_{99} \to p_{100}$ already entail $p_{100}$ : a row making them all true makes $p_1, p_2, \dots, p_{100}$ true, one after another.

(b) Take the valuation making $p_1, \dots, p_{50}$ true and every other atom false. It makes $p_1$ true; it makes $p_n \to p_{n+1}$ true for $n < 50$ (true conclusion) and for $n > 50$ (false hypothesis); only $p_{50} \to p_{51}$ is false. So it makes every member of the finite list true, and $p_{100}$ false.

Compactness says that this is no accident: an entailment from infinitely many premises always rests on finitely many of them. Here every finite list that entails $p_{100}$ must contain all ninety-nine implications up to $p_{99} \to p_{100}$ , since (b)’s argument works with any $p_k \to p_{k+1}$ , $k < 100$ , in place of $p_{50} \to p_{51}$ , and it must contain $p_1$ , since the valuation making every atom false makes all the implications true.

Warning. Compactness promises one valuation for the whole collection when each finite part has one. The valuations of the finite parts may all differ, and the theorem does not say how to find the single one: its proof went through a maximal consistent collection, which nobody writes down.

Remark (Looking ahead). Chapter 7 states completeness and compactness for predicate logic (Section 7.6, optional), without proof; its sketch of completeness follows the route of this section.

4.10.7. Exercises

A. Check your understanding

Exercise (A1)

(a) Why is $\Gamma \vdash \psi$ defined through finite lists of members of $\Gamma$ ?
(b) True or false: an infinite collection $\Gamma$ is consistent iff every finite list of its members is consistent.
(c) In the proof of Lemma 4.10.2, why can $\Delta_n$ with $\varphi_n$ added and $\Delta_n$ with $\neg\varphi_n$ added not both be inconsistent?
(d) $\Delta$ is maximal consistent, $p \in \Delta$ and $q \notin \Delta$ . Is $p \to q$ in $\Delta$ ? Is $\neg(p \wedge \neg q)$ ?
(e) Which result of Section 4.7 does the proof of Theorem 4.10.6 use?

Solution. (a) A derivation has finitely many lines, so it uses finitely many premises.

(b) True, by Definition 4.10.1: $\Gamma \vdash \bot$ means that some finite list of members derives $\bot$ .

(c) By the key step: $\mathrm{\neg I}$ and $\mathrm{RAA}$ would derive $\neg\varphi_n$ and $\varphi_n$ from finitely many members of $\Delta_n$ , and $\mathrm{\neg E}$ then $\bot$ , making $\Delta_n$ inconsistent.

(d) Neither. $p \to q \notin \Delta$ by Lemma 4.10.3 (c), since $p \in \Delta$ and $q \notin \Delta$ . And $\neg q \in \Delta$ by (b), so $p \wedge \neg q \in \Delta$ by (c), so $\neg(p \wedge \neg q) \notin \Delta$ by (b).

(e) That a satisfiable list is consistent (soundness).

Exercise (A2: Drill)

The parts run from judging collections, through the definitions and single stages of the construction, to the lemmas and the theorem, and end with one more collection to judge.

(a) Is the collection of all $p_n$ with $n \ge 1$ satisfiable?
(b) Is the collection of $p_1$ and every $\neg p_n$ with $n \ge 2$ consistent?
(c) Does the collection of all $p_n \to p_{n+1}$ with $n \ge 1$ entail $p_1 \to p_7$ ? If so, which finite list of members does?
(d) Is the collection of $p_1 \vee p_2$ , $\neg p_1$ , $\neg p_2$ and every $p_n$ with $n \ge 3$ satisfiable?
(e) For a finite $\Gamma$ , does Definition 4.10.1 change what $\Gamma \vdash \psi$ means?
(f) Run Lindenbaum’s construction from $\Gamma = \{p\}$ with a list beginning $q, \neg p$ . What are $\Delta_1$ and $\Delta_2$ ?
(g) $\Delta$ is maximal consistent and $p \notin \Delta$ . Is $\neg p \in \Delta$ ? When is $p \vee q \in \Delta$ ?
(h) $p \in \Delta$ and $\neg q \in \Delta$ , with $\Delta$ maximal consistent. Is $p \wedge \neg q \in \Delta$ ?
(i) Can a maximal consistent $\Delta$ contain $p \to q$ , $p$ and $\neg q$ ?
(j) How many formulas of length 1 contain no atom other than $p$ and $q$ ?
(k) Can $\Gamma \models \psi$ hold with no finite list of members of $\Gamma$ entailing $\psi$ ?
(l) Is the collection of all $p_n \leftrightarrow \neg p_{n+1}$ with $n \ge 1$ satisfiable?

Solution.

(a) Yes: every atom true.
(b) Yes: it is satisfiable ( $p_1$ true, every other atom false), hence consistent.
(c) Yes; the list $p_1 \to p_2, \ \dots, \ p_6 \to p_7$ does.
(d) No: its first three members already have no common row.
(e) No (Lemma 2.3.3 (a)).
(f) $\Delta_1 = \{p, q\}$ , which is satisfiable, hence consistent. $\Delta_1$ with $\neg p$ is inconsistent, so $\Delta_2 = \{p, q, \neg\neg p\}$ .
(g) Yes, by Lemma 4.10.3 (b); and $p \vee q \in \Delta$ exactly when $q \in \Delta$ , by (c).
(h) Yes, by Lemma 4.10.3 (c).
(i) No: $\mathrm{{\to}E}$ and $\mathrm{\neg E}$ would derive $\bot$ .
(j) Three: $p$ , $q$ , $\bot$ .
(k) No, by Theorem 4.10.6.
(l) Yes: make $p_n$ true for odd $n$ and false for even $n$ .

B. Practice

Exercise (B1: Running the construction)

Run the construction of Lemma 4.10.2 on $\Gamma = \{p \vee q, \ \neg p\}$ for the first four formulas of a list beginning $p, \ q, \ \neg q, \ p \wedge q$ . Justify each “consistent” by a row and each “inconsistent” by a short derivation of $\bot$ . Then say which values $v_\Delta$ gives $p$ and $q$ , whatever the rest of the list.

Solution. $\Delta_0 = \Gamma$ .

$p$ : $\Gamma$ with $p$ is inconsistent ( $p$ and $\neg p$ , then $\mathrm{\neg E}$ ), so $\Delta_1$ adds $\neg p$ , which is already there.

$q$ : $\Delta_1$ with $q$ is consistent, since the row $p = \mathrm{F}$ , $q = \mathrm{T}$ makes $p \vee q$ , $\neg p$ , $q$ true (Section 4.7); $\Delta_2$ adds $q$ .

$\neg q$ : $\Delta_2$ with $\neg q$ is inconsistent ( $q$ and $\neg q$ , then $\mathrm{\neg E}$ ); $\Delta_3$ adds $\neg\neg q$ .

$p \wedge q$ : $\Delta_3$ with $p \wedge q$ is inconsistent ( $\mathrm{\wedge E}$ gives $p$ , which clashes with $\neg p$ ); $\Delta_4$ adds $\neg(p \wedge q)$ .

Whatever the rest of the list, $\neg p$ and $q$ are in $\Delta$ , so $p \notin \Delta$ by Lemma 4.10.3 (b), and $v_\Delta$ makes $p$ false and $q$ true. Later stages only add formulas, so they cannot change this.

Marking scheme. (6 points)

4: one per stage, with its justification (a row checked, or a derivation of $\bot$ ).
2: the row of $v_\Delta$ on $p$ , $q$ , and why later stages cannot change it.

Exercise (B2: The clause for implication)

Prove the $\to$ clause of Lemma 4.10.3 (c) in full, from parts (a) and (b) and the sequents of Lemma 4.8.1.

Solution. ( $\Rightarrow$ ) Let $\varphi \to \psi \in \Delta$ . If $\varphi \in \Delta$ , the two-premise list $\varphi \to \psi, \ \varphi$ of members of $\Delta$ derives $\psi$ by one $\mathrm{{\to}E}$ line, so $\Delta \vdash \psi$ , and $\psi \in \Delta$ by (a). So either $\varphi \notin \Delta$ or $\psi \in \Delta$ .

( $\Leftarrow$ ) If $\varphi \notin \Delta$ , then $\neg\varphi \in \Delta$ by (b), and $({\to}1)$ , $\neg\varphi \vdash \varphi \to \psi$ , shows $\Delta \vdash \varphi \to \psi$ ; so $\varphi \to \psi \in \Delta$ by (a). If $\psi \in \Delta$ , then $({\to}2)$ , $\psi \vdash \varphi \to \psi$ , does the same.

Marking scheme. (6 points)

3: ( $\Rightarrow$ ), with (a) cited.
3: ( $\Leftarrow$ ), both cases, with (b) used in the first.

C. Going deeper

Exercise (C1: Coloring an infinite graph)

A graph on the vertices $1, 2, 3, \dots$ is given by saying which pairs of vertices are joined. A 3-coloring gives each vertex one of three colors so that joined vertices get different colors. Suppose every finite set of vertices, with the joins among them, can be 3-colored. Prove that the whole graph can. Use atoms $c_{n,i}$ , read “vertex $n$ gets color $i$ ” for $i = 1, 2, 3$ , where the $c_{n,i}$ are distinct atoms (for instance, $c_{n,i}$ is $p_{3n+i}$ ).

Solution. Let $\Gamma$ consist of three kinds of formulas:

$c_{n,1} \vee c_{n,2} \vee c_{n,3}$ , for every vertex $n$ ;
$\neg(c_{n,i} \wedge c_{n,j})$ , for every vertex $n$ and all $i \ne j$ ;
$\neg(c_{m,i} \wedge c_{n,i})$ , for every joined pair $m$ , $n$ and every $i$ .

A valuation making every member of $\Gamma$ true gives each vertex exactly one color (the first two kinds), and joined vertices different colors (the third kind): it is a 3-coloring, coloring $n$ with the $i$ for which $c_{n,i}$ is true.

Every finite list $\Gamma_0$ of members of $\Gamma$ is satisfiable. Its members mention finitely many vertices; call that finite set $F$ . By hypothesis, $F$ with the joins among its vertices has a 3-coloring $\kappa$ . Let $v$ make $c_{n,i}$ true exactly when $n \in F$ and $\kappa(n) = i$ . Each member of $\Gamma_0$ mentions only vertices of $F$ , and $v$ makes it true: the first kind because $\kappa$ colors every vertex of $F$ , the second because it gives each one color, the third because $\kappa$ colors joined vertices of $F$ differently.

By Theorem 4.10.6, $\Gamma$ is satisfiable, and a satisfying valuation is a 3-coloring of the whole graph.

Marking scheme. (10 points)

3: the collection $\Gamma$ , with all three kinds.
2: a valuation making $\Gamma$ true gives a 3-coloring.
4: every finite part satisfiable, with the restriction to the vertices it mentions.
1: Theorem 4.10.6 cited.

Fatal errors (0 for the step): coloring the vertices one at a time and claiming the choices can always be continued, with no argument; a “finite part” argument that colors only the vertices $1, \dots, n$ without checking that every member of $\Gamma_0$ mentions only them.

Exercise (C2: Challenge: Compactness without derivations)

Suppose the atoms are listed $a_1, a_2, \dots$ , and every finite list of members of $\Gamma$ is satisfiable. Choose truth values for $a_1, a_2, \dots$ one at a time, keeping this property:

$(P_n)$ every finite list of members of $\Gamma$ is made true by some valuation that agrees with the choices made for $a_1, \dots, a_n$ .

(a) Show that if $P_n$ holds, a value for $a_{n+1}$ can be chosen so that $P_{n+1}$ holds.
(b) Show that the valuation $v$ given by all the choices makes every member of $\Gamma$ true.
(c) Which earlier results does (b) use?

Solution (Hint 1). For (a), suppose neither value works, and take one finite list witnessing each failure.

Solution. (a) $P_0$ is the hypothesis. Suppose $P_n$ holds and neither value of $a_{n+1}$ works. Then there is a finite list $F_1$ that no valuation agreeing with the choices and making $a_{n+1}$ true satisfies, and a finite list $F_2$ that no valuation agreeing with the choices and making $a_{n+1}$ false satisfies. By $P_n$ , the finite list $F_1, F_2$ is satisfied by some valuation $u$ agreeing with the choices for $a_1, \dots, a_n$ . If $u$ makes $a_{n+1}$ true, it satisfies $F_1$ ; if false, it satisfies $F_2$ . Either way a contradiction. So some value works: choose $\mathrm{T}$ if $\mathrm{T}$ works, and $\mathrm{F}$ otherwise. This gives $P_{n+1}$ , and the rule defines the values by recursion on $n$ .

(b) By (a) and Axiom 4.2.1, $P_n$ holds for every $n$ . Let $\gamma \in \Gamma$ , with its atoms among $a_1, \dots, a_N$ . By $P_N$ , the one-member list $\gamma$ is made true by some valuation agreeing with $v$ on $a_1, \dots, a_N$ . By Lemma 4.4.1, $v$ makes $\gamma$ true.

(c) Lemma 4.4.1, Axiom 4.2.1 ( $P_n$ for every $n$ , from (a)), and a definition by recursion on $n$ (each choice depends on the earlier ones). No derivation and no completeness theorem is used: this proves Theorem 4.10.6 directly.

Marking scheme. (10 points)

5: (a), with the joint list $F_1, F_2$ and both cases of $u$ .
4: (b), with $N$ chosen from the atoms of $\gamma$ , $P_N$ obtained from (a) by Axiom 4.2.1, and Lemma 4.4.1 cited.
1: (c).

Fatal errors (0 for the step): in (a), choosing a value that works for each finite list separately, possibly different for different lists.