Philosophy 3340
Symbolic Logic II

Final Examination - Review
Spring, 2004

Compactness

Should be able to explain why compactness follows from completeness and soundness. (I'll give you a handout about this.)

Completeness of Propositional Logic

• know what completeness of propositional logic is (namely that if S is a tautological consequence of T, then S is derivable from T using only the propositional rules)
• understand the reformulations of this thesis that lead to its equivalence with the claim that for any set of sentences T, if you can't derive a contradiction from T (i.e. T is formally consistent), then T is tt-satisfiable. (Remember, to say T is truth-table satisfiable is to say that there is a truth assignment h that can be extended to a function ĥ that assigns the value True to every sentence in T.)
• know what a truth assignment h is
• know how to extend a truth assignment for a language to a function ĥ that assigns a truth value to every sentence in the language
• understand the notions of formal consistency and formal completeness (a theory is formally consistent if and only if it is not possible to give a proof of ⊥ from sentences in the set. It is formally complete if and if, for every sentence S in the language, there is either a proof of S or a proof of ~S from sentences in the set.)
• recall that we first prove that for any formally complete set T, if T is formally consistent, then it is tt-satisfiable.
• then we complete the proof by showing that any formally consistent set of sentences can be extended to a set that is both formally consistent and formally complete.
• I won't ask you to actually prove the Completeness Theorem, but I might ask you to prove some of the fairly straightforward lemmas along the way. Here are some things I might ask you to prove:

• prove that S is a tautological consequence of a set T if and only if T ∪ {~S} is not tt-satisfiable. (Keep in mind that this is a biconditional, so proving it requires proving two conditionals.) 
• Prove that ⊥ is derivable from T ∪ {~S} using the propositional rules if and only if S is derivable from T using the propositional rules.
• Prove that if T is a set of sentences of L such that for every atomic sentence A of L, either T ⊢ A or T ⊢ ~A, and R and S are atomic sentences of L, then either T ⊢ (R ∨ S) or T ⊢ ~(R ∨ S). (Or, similarly, that either T ⊢ (R ∧ S) or T ⊢ ~(R ∧ S); that either T ⊢ R → S or T ⊢ ~(R → S); etc.) (Remember that these were part of the lemma that shows that if from T you can derive either A or ~A for every atomic sentence A, then T is formally complete.)

Completeness of First-Order Logic

• know what completeness of FO logic is! (Namely that if T ⊨ S then T ⊢ S).
• understand the basic idea of how to use completeness of propositional logic in order to derive completeness of FO logic
• We do this in three basic stages. Stage 1: Show that if T ⊨ S, then T ∪ H ⊨_T S. That is, if S is a FO consequence of T, then S is a tautological consequence of T together with H, where H is the Henkin set.
• So, of course, you need to know what's in the Henkin set and what it's used for in the proof! Basically the idea is that the Henkin set includes sentences that convert any FO consequence into a tautological consequence -- roughly, a consequence you could establish using only truth tables. 
• more specifically, you should know what a witnessing constant is, and how they are added to our language in (an infinite number of) stages.
• Stage 2: Show that if T ∪ H ⊨_T S, then T ∪ H ⊢_T S (that is, that if S is a FO consequence of T ∪ H, then S is derivable from T ∪ H using only the propositional rules. But this is simply an instance of the completeness theorem for propositional logic!
• Stage 3: show that if T ∪ H ⊢_T S, then T ⊢ S -- that is, show that if S is a tautological consequence of T ∪ H, then it is a FO consequence of T all by itself.
• This last step requires the Elimination Theorem. Know what this is and be able to explain informally why it's true.

Arithmetization

• Goedel numbers
• be able to say (roughly) why, given an appropriate Goedel numbering, there are recursive functions on the natural numbers that correspond to things like: the set of formulas of a language; the set of sentences; the concatenation operation; the function that takes a sentence and produces its negation; the function that takes two sentences and produces their conjunction; etc.
• recall that, given an appropriate Goedel numbering, the set of deductions is a recursive set; the property of being a deduction of a sentence S from a set of sentences Gamma is recursive; and so on.

Representability

• any recursive function is definable in the language of arithmetic (perhaps supplemented by a function symbol for exponentiation)
• know what definability in L* means
• know what minimal arithmetic is
• you don't need to memorize all the Q axioms, but should know a few and have a feel for what they're for
• know what is meant by a theory
• know what the theory Q is (namely a set of sentences that is closed under logical implication, that is, a set of sentences such that every FO consequence of elements of the set is also an element of the set)
• be able to explain why it is important (for Goedel's purposes) that Q is a weak theory
• not only is every recursive function (as well as recursive sets and relations) definable in L*, every recursive function is also representable in Q. You should know what this means. (Very roughly, it means that not only can you "translate" the recursive function into L*, but you can also do so in such a way that whenever f(a) = b, the "translation" into L* is provable from the axioms of minimal arithmetic, and therefore is in the set Q.

Gödel's First Incompleteness Theorem

• you should have a good informal understanding of what the theorem says (namely, that for any set of axioms stronger than minimal arithmetic, there is a sentence in the language of arithmetic that is true in the standard interpretation but is not provable from the axioms)
• you should be able to give a very informal description of the reasoning that leads to the theorem (starting from the point that the Gödel sentence G can be understood roughly as saying "The sentence with Gödel number g is not provable," where it turns out that g is the GN of that very sentence).
• know what the Diagonal Lemma is. Namely: for every formula B of L*, and every theory T that extends Q, there is a sentence G with Gödel numeral g such that T ⊢ G ↔ B(g).
• Use the Diagonal Lemma to prove that there is no formula InT(x) that is satisfied by all and only the Gödel numbers of sentences in T (where T is any theory that extends Q). Do this by assuming that there is such a formula and deriving a contradiction. (Note: from the assumption that there is such a formula InT(x) together with the Diagonal Lemma, we get the result that T ⊢ G ↔ InT(g). If you think through the consequences of this carefully, you should be able to derive a contradiction!)
• I might ask questions like the following. You should be able to give a yes or no answer, and also explain why your answer is correct (informally). (a) The set of sentences Q is a set of sentences of L* that are true in the standard interpretation. It is also a recursive set (which is to say, its characteristic function is a recursive function). Give an informal proof that Q is recursive. (Remember that any finite set is recursive, and that logical consequence is a recursive relation.) (b) Consider the set T of all the sentences of L* that are true in the standard interpretation. Is it a recursive set? Give an informal proof of your answer. (c) Consider again the set T. Is there a decision procedure for determining whether a given sentence is in T? Why or why not? (Explain how Church's Thesis is relevant to your answer.)