[proofplan] We extend $S$ to a maximal consistent set $\bar{S} \subseteq L(P)$ using [Zorn's Lemma](/theorems/1226), then define a valuation by membership in $\bar{S}$. The technical heart is showing that the union of a chain of consistent sets is consistent; this uses the **finiteness of proofs** — any derivation of $\bot$ uses only finitely many premises, which must all lie in a single element of the chain. Maximality of $\bar{S}$ implies $\bar{S}$ is **complete**: for every sentence $t$, exactly one of $t, \neg t$ lies in $\bar{S}$. The valuation $v(t) := \mathbb{1}_{\bar{S}}(t)$ is then shown to be a model of $\bar{S}$, hence of $S \subseteq \bar{S}$. [/proofplan] [step:Set up the poset of consistent extensions of $S$] Let \begin{align*} X := \{T \subseteq L(P) : T \supseteq S \text{ and } T \text{ is consistent}\}, \end{align*} ordered by set inclusion $\subseteq$. Since $S$ itself is consistent by hypothesis and $S \supseteq S$, we have $S \in X$, so $X \neq \varnothing$. [guided] Our goal is a model $v: L(P) \to \{0, 1\}$ of $S$. The strategy is to first build a **completed** consistent theory $\bar{S}$ — one that already decides every sentence — and then read off the valuation directly from $\bar{S}$. The plan has two phases: 1. Apply Zorn's Lemma to the poset of consistent extensions of $S$, obtaining a maximal consistent $\bar{S} \supseteq S$. 2. Show $\bar{S}$ is **complete** (decides every sentence) and that the natural valuation $v(t) := \mathbb{1}_{\bar{S}}(t)$ is a model of $\bar{S}$, hence of $S$. The poset for Zorn is \begin{align*} X := \{T \subseteq L(P) : T \supseteq S \text{ and } T \text{ is consistent}\}, \quad \text{ordered by } \subseteq. \end{align*} The inclusion $T \supseteq S$ guarantees that maximal elements extend $S$; consistency is the property Zorn will respect. Since $S \in X$ (it extends itself and is consistent), $X$ is non-empty. We must verify the Zorn hypothesis: every chain in $X$ has an upper bound in $X$. This is Steps 2 and 3. [/guided] [/step] [step:Identify the union of a chain as a candidate upper bound] Let $\mathcal{C} = \{T_i : i \in I\} \subseteq X$ be a non-empty chain under $\subseteq$. Define \begin{align*} T := \bigcup_{i \in I} T_i \subseteq L(P). \end{align*} Then $T \supseteq T_i \supseteq S$ for every $i \in I$, so $T \supseteq S$; and $T_i \subseteq T$ for every $i$, so $T$ is an upper bound of $\mathcal{C}$ in $\mathcal{P}(L(P))$. It remains to show $T$ is consistent, so that $T \in X$. [/step] [step:Prove consistency of the chain union via finiteness of proofs] Suppose for contradiction that $T$ is **inconsistent**: $T \vdash \bot$. By the finiteness of proofs — every formal derivation uses only finitely many premises from its set of axioms — there exist finitely many sentences $t_1, \ldots, t_n \in T$ such that \begin{align*} \{t_1, \ldots, t_n\} \vdash \bot. \end{align*} For each $j \in \{1, \ldots, n\}$, since $t_j \in T = \bigcup_{i \in I} T_i$, choose $i_j \in I$ with $t_j \in T_{i_j}$. Consider the finite collection $\{T_{i_1}, \ldots, T_{i_n}\}$. Because $\mathcal{C}$ is a chain (totally ordered by inclusion), this finite subcollection has a maximum: a standard induction on $n$ shows that every finite totally-ordered subset of a poset has a maximum. Let $T_{i_m}$ be that maximum, so $T_{i_j} \subseteq T_{i_m}$ for every $j = 1, \ldots, n$. Then \begin{align*} t_1, \ldots, t_n \in T_{i_m}, \end{align*} and since $\{t_1, \ldots, t_n\} \vdash \bot$, monotonicity of the entailment relation gives $T_{i_m} \vdash \bot$. This contradicts $T_{i_m} \in X$ (i.e., $T_{i_m}$ consistent). Hence $T$ is consistent, $T \in X$, and $T$ is an upper bound of $\mathcal{C}$ in $X$. [guided] Why should the union of a chain of consistent sets be consistent? The crucial logical principle is **finite character of proofs**: any derivation of $\bot$ is a finite syntactic object and uses only finitely many sentences as premises. Formally, if $\Gamma \vdash \bot$, then there is a finite subset $\Gamma_0 \subseteq \Gamma$ with $\Gamma_0 \vdash \bot$. Suppose $T := \bigcup_i T_i$ were inconsistent. Pick a finite inconsistent subset $\{t_1, \ldots, t_n\} \subseteq T$. Each $t_j$ lives in some $T_{i_j}$ — different indices for different $j$'s, potentially. The **chain property** lets us consolidate: any two indices are comparable, so among the finitely many indices $i_1, \ldots, i_n$ there is a largest one $i_m$, and all $t_j$ lie in $T_{i_m}$. Monotonicity of provability (if $\Gamma \vdash \varphi$ and $\Gamma \subseteq \Delta$, then $\Delta \vdash \varphi$) then gives $T_{i_m} \vdash \bot$, contradicting the consistency of each link in the chain. The finiteness of proofs is non-trivial and is essentially why propositional logic is **compact** in the proof-theoretic sense. Without it, the chain-union argument would fail. Note that the argument works even when the language $L(P)$ is uncountable — this is the whole point of the "uncountable case": the finiteness of individual proofs is a statement about each derivation, not about the overall language. Why does this argument fail for a general directed family that isn't a chain? Without total ordering, the finitely many indices $i_1, \ldots, i_n$ might not have a maximum — we would need an upper bound in the family, which directedness only guarantees pairwise. Iterating pairwise-upper-bounding $n$ times does work in a directed family, giving an alternative proof, but the **chain** hypothesis, being strictly stronger, gives the single-step argument we have used. [/guided] [/step] [step:Apply Zorn's Lemma to obtain a maximal consistent extension] By Steps 1-3, $(X, \subseteq)$ is a non-empty poset in which every chain has an upper bound. By [Zorn's Lemma](/theorems/1226), $X$ contains a maximal element $\bar{S}$: a consistent extension $\bar{S} \supseteq S$ such that for every $T \in X$ with $\bar{S} \subseteq T$, we have $T = \bar{S}$. [/step] [step:Show $\bar{S}$ is complete: for every $t \in L(P)$, either $t \in \bar{S}$ or $\neg t \in \bar{S}$] Let $t \in L(P)$. We claim $t \in \bar{S}$ or $\neg t \in \bar{S}$. Suppose $t \notin \bar{S}$. Consider the set $\bar{S} \cup \{t\}$. This is a strict superset of $\bar{S}$, so by maximality of $\bar{S}$ in $X$, it cannot belong to $X$. Since $\bar{S} \cup \{t\} \supseteq \bar{S} \supseteq S$, the condition failing must be consistency: $\bar{S} \cup \{t\}$ is inconsistent, i.e., \begin{align*} \bar{S} \cup \{t\} \vdash \bot. \end{align*} By the Deduction Theorem, $\bar{S} \vdash t \to \bot$, which is (by definition of $\neg$) $\bar{S} \vdash \neg t$. Now consider $\bar{S} \cup \{\neg t\}$. Since $\bar{S} \vdash \neg t$, any derivation from $\bar{S} \cup \{\neg t\}$ can be converted to a derivation from $\bar{S}$ alone (replace appeals to $\neg t$ by derivation of $\neg t$ from $\bar{S}$). In particular, if $\bar{S} \cup \{\neg t\} \vdash \bot$, then $\bar{S} \vdash \bot$, contradicting consistency of $\bar{S}$. So $\bar{S} \cup \{\neg t\}$ is consistent, i.e., $\bar{S} \cup \{\neg t\} \in X$. By maximality of $\bar{S}$, this forces $\bar{S} \cup \{\neg t\} = \bar{S}$, i.e., $\neg t \in \bar{S}$. Conversely, $\bar{S}$ cannot contain both $t$ and $\neg t$: from $\{t, \neg t\}$ one derives $\bot$ (by applying $\neg t = t \to \bot$ to $t$ via modus ponens), so $\{t, \neg t\} \vdash \bot$, and hence $\bar{S} \vdash \bot$ by monotonicity — contradicting consistency. Thus **exactly one** of $t, \neg t$ lies in $\bar{S}$. [guided] **Step 5.A: If $t \notin \bar{S}$, then $\neg t \in \bar{S}$.** The argument proceeds in two sub-steps. *Sub-step A1: $\bar{S} \vdash \neg t$.* Maximality of $\bar{S}$ in $X$ says that any strict consistent extension of $\bar{S}$ that contains $S$ must equal $\bar{S}$. So the strict superset $\bar{S} \cup \{t\}$ — strict because $t \notin \bar{S}$ — must fail to be in $X$. It still extends $S$, so the failure is inconsistency: $\bar{S} \cup \{t\} \vdash \bot$. By the **Deduction Theorem** — the formal statement that $\Gamma \cup \{\varphi\} \vdash \psi \iff \Gamma \vdash \varphi \to \psi$ — this gives $\bar{S} \vdash t \to \bot$, i.e., $\bar{S} \vdash \neg t$ (using $\neg \varphi := \varphi \to \bot$, the standard definition). *Sub-step A2: $\neg t \in \bar{S}$.* We show $\bar{S} \cup \{\neg t\}$ is consistent. If $\bar{S} \cup \{\neg t\} \vdash \bot$, then by substituting a derivation of $\neg t$ from $\bar{S}$ (which exists by A1) for every use of the hypothesis $\neg t$, we get $\bar{S} \vdash \bot$ — contradicting consistency of $\bar{S}$. Hence $\bar{S} \cup \{\neg t\}$ is consistent. Then $\bar{S} \cup \{\neg t\} \in X$ is a consistent extension of $\bar{S}$, so by maximality, $\bar{S} \cup \{\neg t\} = \bar{S}$, i.e., $\neg t \in \bar{S}$. **Step 5.B: $\bar{S}$ does not contain both $t$ and $\neg t$.** If both were in $\bar{S}$, then by modus ponens applied to $\neg t = t \to \bot$ and $t$, we would have $\bar{S} \vdash \bot$, contradicting consistency. So at most one of $t, \neg t$ lies in $\bar{S}$. Combining A and B: **exactly one** of $t, \neg t$ lies in $\bar{S}$. This is the completeness property of $\bar{S}$ — it decides every sentence. [/guided] [/step] [step:Define the valuation from $\bar{S}$ and verify it is a model] Define \begin{align*} v: L(P) &\to \{0, 1\}, \\ v(t) &= \begin{cases} 1 & \text{if } t \in \bar{S}, \\ 0 & \text{if } t \notin \bar{S}. \end{cases} \end{align*} Equivalently, $v(t) = \mathbb{1}_{\bar{S}}(t)$. We verify $v$ respects the propositional connectives (so that $v$ is a well-defined valuation) and that $v(t) = 1$ for every $t \in \bar{S}$ (so that $v \models \bar{S}$, hence $v \models S$). **Respect for $\bot$:** $\bot \notin \bar{S}$ because $\bar{S}$ is consistent (if $\bot \in \bar{S}$, then $\bar{S} \vdash \bot$). Hence $v(\bot) = 0$, as required of a valuation. **Respect for $\to$:** We show $v(t \to u) = 1$ iff ($v(t) = 0$ or $v(u) = 1$), i.e., $v(t \to u) = 1$ iff $v(t) \leq v(u)$. *Forward.* Suppose $v(t \to u) = 1$, i.e., $t \to u \in \bar{S}$. If $v(t) = 1$, then $t \in \bar{S}$. By modus ponens applied to $\{t \to u, t\} \subseteq \bar{S}$, we have $\bar{S} \vdash u$. Then $\bar{S} \cup \{u\}$ is consistent (any derivation from $\bar{S} \cup \{u\}$ of $\bot$ would, after substituting the derivation of $u$ from $\bar{S}$, give $\bar{S} \vdash \bot$, contradiction), so by maximality $u \in \bar{S}$, giving $v(u) = 1$. Hence $v(t) \leq v(u)$. *Reverse.* Suppose $v(t) = 0$ or $v(u) = 1$. - **Case $v(u) = 1$:** Then $u \in \bar{S}$. The sentence $u \to (t \to u)$ is a propositional tautology (and hence provable from the empty set of premises in any standard proof system). By modus ponens, $\bar{S} \vdash t \to u$. Arguing as above (consistency of $\bar{S} \cup \{t \to u\}$ plus maximality), $t \to u \in \bar{S}$, so $v(t \to u) = 1$. - **Case $v(t) = 0$ and $v(u) = 0$:** Then $t \notin \bar{S}$ and $u \notin \bar{S}$. By completeness (Step 5), $\neg t \in \bar{S}$. The sentence $\neg t \to (t \to u)$ — i.e., $(t \to \bot) \to (t \to u)$ — is a propositional tautology, provable in any standard axiomatisation. By modus ponens, $\bar{S} \vdash t \to u$, and (by the same consistency-and-maximality argument) $t \to u \in \bar{S}$, so $v(t \to u) = 1$. In both cases $v(t \to u) = 1$. Combining, $v(t \to u) = 1$ iff $v(t) \leq v(u)$, which is exactly the truth-table definition of implication in a valuation. Therefore $v$ is a valuation. By construction, $v(t) = 1$ for every $t \in \bar{S}$, so $v \models \bar{S}$. Since $S \subseteq \bar{S}$, $v \models S$, completing the proof. [guided] A **valuation** is a function $v: L(P) \to \{0, 1\}$ satisfying the truth-table clauses for the connectives: $v(\bot) = 0$ and $v(t \to u) = 1$ iff $v(t) = 0$ or $v(u) = 1$. (All other connectives $\neg, \land, \lor, \leftrightarrow$ are defined in terms of $\bot$ and $\to$ in the standard setup of propositional logic, so these two clauses suffice.) **Why is the $\bot$ clause automatic?** Because $\bot \in \bar{S}$ would give $\bar{S} \vdash \bot$ (by assumption introduction), contradicting consistency. So $\bot \notin \bar{S}$, and $v(\bot) = 0$. **Why does the implication clause hold?** The forward direction ($t \to u \in \bar{S}$ and $t \in \bar{S}$ imply $u \in \bar{S}$) is modus ponens applied inside $\bar{S}$, combined with the standard fact that maximal consistent sets are closed under provability: if $\bar{S} \vdash \varphi$, then $\varphi \in \bar{S}$ (otherwise maximality forces $\bar{S} \cup \{\varphi\}$ to be inconsistent, but a derivation of $\bot$ from $\bar{S} \cup \{\varphi\}$ combined with the derivation of $\varphi$ from $\bar{S}$ would give $\bar{S} \vdash \bot$). The reverse direction breaks into two cases: - *If $u \in \bar{S}$:* then $t \to u \in \bar{S}$ using the tautology $u \to (t \to u)$ (the "vacuous $t$" axiom of implication). - *If $u \notin \bar{S}$ and $t \notin \bar{S}$:* then by completeness $\neg t \in \bar{S}$, and the tautology $\neg t \to (t \to u)$ (ex falso quodlibet, modulo the defining equation $\neg t = t \to \bot$) gives $t \to u \in \bar{S}$. Both tautologies are standard axioms or easy consequences in any Hilbert-style or natural-deduction system for propositional logic. With these two clauses verified, $v$ is a bona fide valuation. By definition $v(t) = 1 \iff t \in \bar{S}$, so $v$ satisfies every sentence in $\bar{S}$. In particular, since $S \subseteq \bar{S}$, $v$ satisfies every sentence in $S$. So $v$ is a model of $S$, as required. **What made the uncountable case different from the countable case?** In the countable case, one often enumerates all sentences $t_1, t_2, \ldots$ and recursively decides them one at a time, producing a maximal consistent $\bar{S}$ without invoking Zorn. In the uncountable case, there is no such enumeration — the set $L(P)$ can have arbitrarily large cardinality when $P$ is uncountable — and Zorn's Lemma supplies the needed transfinite selection. The rest of the argument (completeness of $\bar{S}$, extraction of the valuation) is then identical to the countable case. [/guided] [/step]