Philosophy 3340
Symbolic Logic II

Second Examination - Review
Spring, 2006

Syntax of First-Order Logic

• A language: automatically contains quantifiers, logical connectives, variables, the identity predicate. We specify a particular language by specifying whatever additional non-logical primitives it contains: constants, function symbols, and predicates.
• You should know the definitions (usually inductive) of: terms, formulas, free variables, sentences.
• If I give you a string of symbols, you should be able to say whether (and why) it is a term, a sentence, etc. (Is f(x) a sentence? A term? A formula? What about F(a,b) & G(b,x)? Etc.)

Semantics of First-Order Logic

• you should know what a structure is. (A structure consists of: a universe, an assignment of an element of the universe to each constant, an assignment of an n-place function (a.k.a. a set of n+1-tuples of elements of the universe) to each n-place function symbol, and an assignment of a set of n-tuples of elements of the universe to every n-place predicate. (Except in the case of one-place predicates we just take a set of elements of the universe instead of a set of singletons.)
• So a structure gives an interpretation of all the primitive nonlogical vocabulary of the language. We extend the semantics to the rest of the language by way of the definitions of denotation and of truth. You should know the def. of denotation and the def. of truth and understand how they allow a structure to determine a truth value for every sentence of its language (and, relative to a variable interpretation, a truth value for every formula of the language).
• You should understand the notation used to express all this stuff.
• You should know what it means to say that a set of sentences Gamma logically implies a sentence F. (It means that every structure that makes all the sentences in Gamma true also makes F true. Another way to say this: every model of Gamma is a model of F.)
• Note that we can prove that F is not a logical consequence of Gamma if we can find an interpretation (any interpretation!) that makes all the sentences in Gamma true and also makes F false.

Models

• know what a model of a sentence, or set of sentences, is.
• Note that if we speak of a model of a sentence or set of sentences without explicit reference to a language, we have in mind an interpretation of the minimal language needed to express those sentences -- i.e. a language that contains, in addition to logical expressions, only the nonlogical expressions that actually occur in the set of sentences. So a model of the sentence F(c) would be an interpretation of the language {F, c} in which F(c) is true.
• Know what is meant by the size of a model. (Answer: the size of the universe of the model.)
• For any positive integer n, you should be able to write a sentence of first-order logic that has only models of size n.
• You should be able to put other constraints on the models of a set of sentences, e.g. you should be able to write sentences whose only model interprets a two-place predicate by a relation that is transitive, or reflexive, or . . .

Deduction

• t/x substitution of an L-formula (of a language L), written (phi)[t/x]. This is defined in terms of the t/x substitution of an L-term, so you should know that too. You don't need to be able to reproduce the formal inductive definition (pp. 128-129), but should know what it does well enough that you can (a) given a formula, specify what the t/x substitution of that formula is; (b) given two formulas, say whether one is the t/x substitution of the other; (c) given a clause of the definition, be able to explain what it does. (The quantifier clauses are a little tricky but interesting; I might give you one and ask you to explain it.)
• know what it is for one term to be substitutable for another an an L-formula. You don't need to be able to reproduce the formal inductive definition on p. 131, but should know what it does well enough that you can, given a formula and two terms, say whether one term is substitutable for the other in the formula. Sample question: Consider the formula Ex (Px & Ay (Qy v Ry)). Is f(y) substitutable for x in this formula? Why or why not?
• Know what an L-sequent is. Understand the relationship between the set D_L of L-sequents, and the relation ⊦_L.
• Understand the definition of deducibility. You don't need to be able to reproduce the formal inductive definition (p. 139), but given a set of formulas Gamma and a formula phi, you should be able to say whether phi is deducible from Gamma (in reasonably simple cases, that is). I might do something like this: give you one of the clauses and a purported application of it, and ask you whether the step is or isn't justified by the clause (and why).

Theorems

• be able to state the Completeness Theorem, the Satisfaction Lemma, the Model Existence Theorem, and the logical relations between them.
• Be able to give an informal sketch of a proof that the SL is equivalent to the Model Existence Theorem, and/or that the SL is equivalent to the Completeness Theorem.
• Know what a theory is.
• know what the canonical structure of a set of sentences is (for both languages without identity and languages with it)
• know what a well-rounded set is.
• know what a negation-complete set is, and how to extend any consistent set to a negation-complete set
• Be able to give a very informal and sketchy sketch of a sketch of a sketch of the general idea of the proof of the Completeness Theorem.
• know what a Henkin constant is, and how to add enough of them to a language
• know what a Henkin axiom is, and how to add enough of them to a consistent set of sentences to construct a Henkin set
• be able to state the Compactness theorem. You should be able to prove the Compactness Theorem on the basis of the Completeness Theorem.

One kind of question I am very likely to ask: I might give you the nonlogical vocabulary of a toy language, and then ask you to play with it in various ways. For example I might ask you to tell me whether specific strings of symbols in the toy language are or are not terms, formulas, or sentences of the language (and why). I might give you a formula phi and ask you to write down (phi)[c/x] for some constant c and variable x. I might ask you to give a model of a set of sentences in the language. More specifically, I might ask you to give the interpretation assigned to a term, function symbol, or predicate by the canonical structure for that set of sentences.