Philosophy 3349
Topics in Logic

Curtis Brown
Spring, 2002

Questions for the Midterm Examination

revised March 5, 2002
no further revisions (unless I catch a horrible mistake)

Some possible questions for the midterm examination. I will probably ask you to write short paragraphs on about eight of the short-answer questions, have you do two or three of the exercises, and ask you to write on one of the essay questions.

Part I: short answer

• naive set theory
• singleton
• axiom of comprehension
• axiom of extensionality
• Russell's paradox
• set-theoretic definition of relation
• set-theoretic definition of function
• first-order language
• term
• formula
• sentence
• structure
• universe
• variable assignment function
• model
• satisfaction
• difference in meaning between double turnstile with a structure on the left, and with a set of sentences on the left
• logical implication (be able to give a formal definition)
• nonstandard model
• logical axioms
• "nonlogical axioms"
• rules of inference (be able to give a formal definition)
• deduction (be able to give a formal definition)
• soundness
• completeness
• Henkin axioms
• maximal consistent set of sentences
• compactness
• Skolem-Loewenheim theorems (downward, upward)
• Skolem paradox
• arbitrary objects

Part II: applications and exercises

• given a language and a sentence, say whether the sentence is included in the language. For instance, given the language {f₁, f₂, R₁} -- for simplicity, let's say that all relation symbols are two-place and all function symbols are one-place -- is the sentence R₁(f(a), b) included in the language? A: No, because the language doesn't contain the constants a, b.
• given a formula, you should be able to write down the result of substituting one term for another into the formula.
• given a formula, you should be able to determine whether it is a sentence or not
• given a string of symbols, you should be able to determine whether it is a formula or not. If our language contains the one-place function symbol f and the constant a, is f(a) a formula?
• (I might specify a language and then ask a series of T/F questions like the above (is this string a term, formula, sentence, etc.))
• construct simple predicate logic proofs in Leary's system. (If I ask a question like this, I will list the axioms and rules of inference.)
• given a language and one or more sentences, construct interpretations (structures) that make the sentences come out true or false. (Note that to actually specify an interpretation you need to say what items of the universe are denoted by the constants, and what functions and relations are expressed by the function symbols and relation symbols. The easiest way to do this (at least for a small universe) is to construct tables, where the entries for relations will be T or F and the entries for functions will be objects from the universe of the structure) One example of this kind of question would be the homework problem asking you to construct a structure in which the axioms of number theory are true, but it is not true that for all x, ~(x < x). If I asked a question like this, I would list the axioms you are to make true. I would also strip down the problem a bit by simplifying the language and considering only a subset of the axioms -- for example, I might eliminate the E and * functions and corresponding axioms.

Part III: essays

• explain the general strategy behind the proof of soundness
• ditto for the completeness proof
• . . . and the compactness proof (actually this one is easy enough that you should be able to actually demonstrate it on the exam, making use of the Soundness and Completeness Theorems)
• What is the Skolem paradox? Why isn't it really a paradox? How does Putnam argue that there is a more troubling analog of the Skolem paradox for natural languages? Evaluate Putnam's argument and conclusions.
• The Completeness Theorem states that, for any set of sentences Sigma, if Sigma logically implies phi, then there is a deduction of phi from Sigma. However, the main part of the proof consists of showing that if Sigma is consistent (i.e. it is not possible to derive a contradiction from Sigma), then there is a model of Sigma. Explain why showing this suffices to prove Completeness. (Note: it would be best to do this in two stages. First, show why the Completeness Theorem is equivalent to the claim that if Sigma logically implies contradiction, then there is a deduction of contradiction from Sigma. Then show that this in turn is equivalent to the claim that if Sigma is consistent, then it has a model.
• Fine, in his defense of arbitrary objects, considers the following principle which purports to specify which properties an arbitrary object has:   phi(a) if and only if for all i, phi(i). Show that this principle leads to contradictions, and give a brief explanation of the alternative Fine proposes.