Gödel's Completeness Theorem

[Abstract_Logic]

I'm currently reading this book called Set Theory and the Continuum Hypothesis, written by Paul Cohen, which is a model-theoretic investigation of the topics. I'm trying to rediscover the proof of Gödel's Completeness theorem for myself, but I'm kind of stuck on certain details of the proof provided in the book. In the preface, the author mentioned that he did not "polish up" the final draft of the book, so many important details are left out. Although it is written for people with little to no background in propositional logic, the book assumes that one has a background in abstract mathematics, namely in Model theory. I'm only an undergraduate student not yet knowledgeable enough to understand the methods Cohen uses to prove his arguments. So I'm wondering if someone here can help me understand what certain things mean in the proofs.

 

The parts that I've put in red are the parts I'm stuck on. I will quote directly from the book so as to give you a full view of what I'm asking.

 

[math]c_\alpha[/math] and [math]R_\beta[/math] are constant and relation symbols, respectively.

 

Theorem 3. (Completeness of the Propositional Calculus). If [math]S[/math] contains no quantifiers and is consistent, then there is a model [math]M[/math] for [math]S[/math] in which every element of [math]M[/math] is of the form [math]\overline{c}_\alpha[/math] for some [math]c_\alpha[/math] appearing in [math]S[/math].

 

We need one lemma.

 

LEMMA. If [math]T[/math] is a consistent set of statements, [math]A[/math] an arbitrary statement, either [math]T \cup \{A\}[/math] or [math]T \cup \{\neg A\}[/math] is consistent.

 

PROOF. If [math]T \cup \{A\}[/math] is inconsistent, then for some [math]B_i[/math] in [math]T, A \land B_1 \land \cdots \land B_n \rightarrow C \land \neg C[/math] for some [math]C[/math], is valid. If [math]T \cup \{\neg A\}[/math] is inconsistent, then for some [math]B'_i[/math] in [math]T[/math], [math]\neg A \land B'_1 \land \cdots \land B'_m \rightarrow C \land \neg C[/math] is valid. The propositional calculus now implies that [math]B_1 \land \cdots \land B_n \land B'_1 \land \cdots \land B'_m \rightarrow C \land \neg C[/math] is valid, so that [math]T[/math] must be inconsistent.

 

Now to prove Theorem 3. Let [math]S[/math] be well-ordered. This induces a well-ordering on all the constant and relation symbols which appear in [math]S[/math]. This in turn induces a well-ordering of all possible statements of the form [math]c_i = c_j[/math] and [math]R_\beta (c_1,...,c_n)[/math] where [math]c_i[/math] and [math]R_\beta[/math] are constant and relation symbols occurring in [math]S[/math]. Call these statements [math]F_\alpha[/math]. We now define statements [math]G_\alpha[/math] by induction on [math]\alpha[/math]. If [math]F_\alpha[/math] is consistent with [math]S \cup \{G_\beta | \beta < \alpha \}[/math] we put [math]G_\alpha = F_\alpha[/math], otherwise put [math]G_\alpha = \neg F_\alpha[/math]. By our lemma and by induction on [math]\alpha[/math], it follows that [math]S \cup \{G_\beta | \beta \leq \alpha \}[/math] is consistent for all [math]\alpha[/math]. Since any contradiction must be derived from a finite number of statements, we see that [math]H = S \cup \{G_\alpha \}[/math] is a consistent system. For each [math]c_\alpha[/math] occurring in S, define [math]\overline{c}_\alpha = c_\beta[/math] where [math]\beta[/math] is the least index such that [math]c_\alpha = c_\beta[/math] belongs to [math]H[/math]. (There must be some such since [math]c_\alpha = c_\alpha[/math] belongs to [math]H[/math].) Let [math]M[/math] be the set of [math]\overline{c}_\alpha[/math], and define [math]\overline{R}_\beta[/math] as the set of all [math]\langle \overline{c}_\alpha 1 ,..., \overline{c}_\alpha n \rangle[/math] such that [math]R_\beta (c_\alpha ,..., c_\alpha n)[/math] is in [math]H[/math]. Thus our model consists of a subset of the formal symbols [math]c_\alpha[/math]. It is easy to see that every statement in [math]H[/math], or its negation, must be a consequence of the [math]G_\alpha[/math] since every atomic relation occurring in a statement of [math]S[/math] or its negation appears among the [math]G_\alpha[/math]. A negation of a statement in S cannot be such a consequence since in that case [math]H[/math] would not be consistent. Since we have defined [math]M[/math] so that all the [math]G_\alpha[/math] are true, it follows that in [math]M[/math] all the statements of [math]H[/math] and hence of [math]S[/math] are also true. Thus Theorem 3 is proved.

 

I have a very vague idea, but I'm not entirely sure what those parts mean exactly. If someone could help me out here by explaining those parts to me in more detail I would appreciate it. Also, if there are any questions regarding the excerpt from the book I will do my best to answer them.

 

Thank you!

Jeffrey

Edited January 1, 2010 by Abstract_Logic

[liarliarpof]

Regarding Completeness: You may try going to the source. Godel actually published (2) papers: 1) 'On the completeness of the calculus of logic (1929)' ; 2) 'The completeness of the axioms of the functional calculus of logic (1930)'. See 'Kurt Godel COLLECTED WORKS Volume I Publications 1929-1936'. Regarding The Continuum Hypothesis: As the story goes, Godel believed it to be false. In 1947 he published an 'expository essay' showing that the CH cannot be proved false. Curiously, he stopped there. One almost gets the sense that he did not attempt to prove it true, as this would contradict his intuition. Who knows? Cohen, on the other hand, proved that the CH cannot be proved true (1963). Though still debatable, the two results essentially showed the CH to be undecidable. Let me know if this helps. Good Luck! liarliarpof