2.6.3: Complete Consistent Sets of Sentences

\(\def\Assign#1#2{ { #1^{\Struct{#2}} } }\)
\(\def\Atom#1#2{ { \mathord{#1}(#2) } }\)
\(\def\Bin{ {\mathbb{B}} }\)
\(\def\cardeq#1#2{ { #1 \approx #2 } }\)
\(\def\cardle#1#2{ { #1 \preceq #2 } }\)
\(\def\cardless#1#2{ { #1 \prec #2 } }\)
\(\def\cardneq#1#2{ { #1 \not\approx #2 } }\)
\(\def\comp#1#2{ { #2 \circ #1 } }\)
\(\def\concat{ { \;\frown\; } }\)
\(\def\Cut{ { \text{Cut} } }\)
\(\def\Discharge#1#2{ { [#1]^#2 } }\)
\(\def\DischargeRule#1#2{ { \RightLabel{#1}\LeftLabel{\scriptsize{#2} } } }\)
\(\def\dom#1{ {\operatorname{dom}(#1)} }\)
\(\def\Domain#1{ {\left| \Struct{#1} \right|} }\)
\(\def\Elim#1{ { {#1}\mathrm{Elim} } }\)
\(\newcommand{\Entails}{\vDash}\)
\(\newcommand{\EntailsN}{\nvDash}\)
\(\def\eq[#1][#2]{ { #1 = #2 } }\)
\(\def\eqN[#1][#2]{ { #1 \neq #2 } }\)
\(\def\equivclass#1#2{ { #1/_{#2} } }\)
\(\def\equivrep#1#2{ { [#1]_{#2} } }\)
\(\def\Exchange{ { \text{X} } }\)
\(\def\False{ { \mathbb{F} } }\)
\(\def\FalseCl{ { \lfalse_C } }\)
\(\def\FalseInt{ { \lfalse_I } }\)
\(\def\fCenter{ { \,\Sequent\, } }\)
\(\def\fdefined{ { \;\downarrow } }\)
\(\def\fn#1{ { \operatorname{#1} } }\)
\(\def\Frm[#1]{ {\operatorname{Frm}(\Lang #1)} }\)
\(\def\fundefined{ { \;\uparrow } }\)
\(\def\funimage#1#2{ { #1[#2] } }\)
\(\def\funrestrictionto#1#2{ { #1 \restriction_{#2} } }\)
\(\newcommand{\ident}{\equiv}\)
\(\newcommand{\indcase}[2]{#1 \ident #2\text{:}}\)
\(\newcommand{\indcaseA}[2]{#1 \text{ is atomic:}}\)
\(\def\indfrm{ { A } }\)
\(\def\indfrmp{ { A } }\)
\(\def\joinrel{\mathrel{\mkern-3mu}}\)
\(\def\lambd[#1][#2]{\lambda #1 . #2}\)
\(\def\Lang#1{ { \mathcal{#1} } }\)
\(\def\LeftR#1{ { {#1}\mathrm{L} } }\)
\(\def\len#1{ {\operatorname{len}(#1)} }\)
\(\def\lexists#1#2{ { \exists #1\, #2 } }\)
\(\def\lfalse{ {\bot} }\)
\(\def\lforall#1#2{ { \forall#1\, #2 } }\)
\(\newcommand{\lif}{\rightarrow}\)
\(\newcommand{\liff}{\leftrightarrow}\)
\(\def\Log#1{ { \mathbf{#1} } }\)
\(\def\ltrue{ {\top} }\)
\(\def\Id#1{ {\operatorname{Id}_#1} }\)
\(\def\Int{ {\mathbb{Z}} }\)
\(\def\Intro#1{ { {#1}\mathrm{Intro} } }\)
\(\def\mModel#1{ { \mathfrak{#1} } }\)
\(\newcommand{\mSat}[3][{}]{\mModel{#2}{#1}\Vdash{#3}}\)
\(\newcommand{\mSatN}[3][{}]{\mModel{#2}{#1}\nVdash{#3}}\)
\(\def\Nat{ {\mathbb{N}} }\)
\(\def\nicefrac#1#2{ {{}^#1/_#2} }\)
\(\def\num#1{ { \overline{#1} } }\)

\(\def\ran#1{ {\operatorname{ran}(#1)} }\)
\(\newcommand{\Obj}[1]{\mathsf{#1}}\)
\(\def\Rat{ {\mathbb{Q}} }\)
\(\def\Real{ {\mathbb{R}} }\)
\(\def\RightR#1{ { {#1}\mathrm{R} } }\)
\(\def\Part#1#2{ { \Atom{\Obj P}{#1, #2} } }\)
\(\def\pto{ { \hspace{0.1 cm}\to\hspace{-0.44 cm}\vcenter{\tiny{\hbox{|}}}\hspace{0.35 cm} } }\)
\(\def\PosInt{ {\mathbb{Z}^+} }\)
\(\def\Pow#1{ {\wp(#1)} }\)
\(\newcommand{\Proves}{\vdash}\)
\(\newcommand{\ProvesN}{\nvdash}\)
\(\def\Relbar{\mathrel{=}}\)
\(\newcommand{\Sat}[3][{}]{\Struct{#2}{#1}\vDash{#3}}\)
\(\newcommand{\SatN}[3][{}]{\Struct{#2}{#1}\nvDash{#3}}\)
\(\newcommand{\Sequent}{\Rightarrow}\)
\(\def\Setabs#1#2{ { \{#1:#2\} } }\)
\(\newcommand{\sFmla}[2]{#1\,#2}\)
\(\def\Struct#1{ {#1} }\)
\(\def\subst#1#2{ { #1/#2 } }\)
\(\def\Subst#1#2#3{ { #1[\subst{#2}{#3}] } }\)
\(\def\TMblank{ { 0 } }\)
\(\newcommand{\TMendtape}{\triangleright}\)
\(\def\TMleft{ { L } }\)
\(\def\TMright{ { R } }\)
\(\def\TMstay{ { N } }\)
\(\def\TMstroke{ { 1 } }\)
\(\def\TMtrans#1#2#3{ { #1,#2,#3 } }\)
\(\def\Trm[#1]{ {\operatorname{Trm}(\Lang #1)} }\)
\(\def\True{ { \mathbb{T} } }\)
\(\newcommand{\TRule}[2]{#2#1}\)
\(\def\tuple#1{ {\langle #1 \rangle} }\)
\(\newcommand{\Value}[3][\,]{\mathrm{Val}_{#1}^{#3}(#2)}\)
\(\def\Var{ { \mathrm{Var} } }\)
\(\newcommand{\varAssign}[3]{#1 \sim_{#3} #2}\)
\(\def\Weakening{ { \text{W} } }\)

Definition \(\PageIndex{1}\): Complete set

A set \(\Gamma\) of sentences is complete iff for any sentence \(A\), either \(A \in \Gamma\) or \(\lnot A \in \Gamma\).

Complete sets of sentences leave no questions unanswered. For any sentence \(A\), \(\Gamma\) “says” if \(A\) is true or false. The importance of complete sets extends beyond the proof of the completeness theorem. A theory which is complete and axiomatizable, for instance, is always decidable.

Complete consistent sets are important in the completeness proof since we can guarantee that every consistent set of sentences \(\Gamma\) is contained in a complete consistent set \(\Gamma^*\). A complete consistent set contains, for each sentence \(A\), either \(A\) or its negation \(\lnot A\), but not both. This is true in particular for atomic sentences, so from a complete consistent set in a language suitably expanded by constant symbols, we can construct a structure where the interpretation of predicate symbols is defined according to which atomic sentences are in \(\Gamma^*\). This structure can then be shown to make all sentences in \(\Gamma^*\) (and hence also all those in \(\Gamma\)) true. The proof of this latter fact requires that \(\lnot A \in \Gamma^*\) iff \(A \notin \Gamma^*\), \((A \lor B) \in \Gamma^*\) iff \(A \in \Gamma^*\) or \(B \in \Gamma^*\), etc.

In what follows, we will often tacitly use the properties of reflexivity, monotonicity, and transitivity of \(\Proves\) (see sections 8.8 and 9.7).

Proposition \(\PageIndex{1}\)

Suppose \(\Gamma\) is complete and consistent. Then:

1. If \(\Gamma \Proves A\), then \(A \in \Gamma\).
2. \(A \land B \in \Gamma\) iff both \(A \in \Gamma\) and \(B \in \Gamma\).
3. \(A \lor B \in \Gamma\) iff either \(A \in \Gamma\) or \(B \in \Gamma\).
4. \(A \lif B \in \Gamma\) iff either \(A \notin \Gamma\) or \(B \in \Gamma\).

Proof. Let us suppose for all of the following that \(\Gamma\) is complete and consistent.

1. If \(\Gamma \Proves A\), then \(A \in \Gamma\).

   Suppose that \(\Gamma \Proves A\). Suppose to the contrary that \(A \notin \Gamma\). Since \(\Gamma\) is complete, \(\lnot A \in \Gamma\). By Propositions 8.9.3 and 9.8.3, \(\Gamma\) is inconsistent. This contradicts the assumption that \(\Gamma\) is consistent. Hence, it cannot be the case that \(A \notin \Gamma\), so \(A \in \Gamma\).

2. Exercise.
3. First we show that if \(A \lor B \in \Gamma\), then either \(A \in \Gamma\) or \(B \in \Gamma\). Suppose \(A \lor B \in \Gamma\) but \(A \notin \Gamma\) and \(B \notin \Gamma\). Since \(\Gamma\) is complete, \(\lnot A \in \Gamma\) and \(\lnot B \in \Gamma\). By Propositions 8.10.2 and 9.9.2, item (1), \(\Gamma\) is inconsistent, a contradiction. Hence, either \(A \in \Gamma\) or \(B \in \Gamma\).

   For the reverse direction, suppose that \(A \in \Gamma\) or \(B \in \Gamma\). By Propositions 8.10.2 and 9.9.2, item (2), \(\Gamma \Proves A \lor B\). By (1), \(A \lor B \in \Gamma\), as required.

4. Exercise.

◻

Problem \(\PageIndex{1}\)

Complete the proof of Proposition \(\PageIndex{1}\).