Ling 726: Mathematical Linguistics, Lecture 9 Model Theory V. Borschev and B. Partee, October 17-19, 2006 p. 1 Lecture 9. Model theory. Consistency, independence, completeness, categoricity of axiom systems. Expanded with algebraic view. CONTENTS 0. Syntax and semantics; proof theory and model theory.............................................................................................. 1 1. Syntactic provability and semantic entailment.......................................................................................................... 2 1.1. Semantic entailment and validity. ...................................................................................................................... 3 1.2. Soundness and completeness of a logic.............................................................................................................. 3 2. Consistency, completeness, independence, and other notions. ................................................................................ 4 2.1. Some syntactic concepts..................................................................................................................................... 4 2.2. Some semantic concepts..................................................................................................................................... 5 2.3. Soundness and completeness again.................................................................................................................... 5 2.4. Independence...................................................................................................................................................... 5 2.5. Categoricity........................................................................................................................................................ 6 3. An algebraic view on provability and on the notions discussed above ..................................................................... 6 3.1. Closure systems.................................................................................................................................................. 6 3.2. Galois connection............................................................................................................................................... 7 4. Morphisms for models; categoricity........................................................................................................................ 8 Appendix: An axiomatization of statement logic.......................................................................................................... 9 Appendix: Note on model-theoretic vs. proof-theoretic syntax .................................................................................... 9 Homework 9, due Oct 24. ........................................................................................................................................... 10 Reading: Chapter 5, Chapter 8: 8.1- 8.5, of PtMW, pp. 87-96, 179-217. Good supplementary reading: Fred Landman (1991) Structures for Semantics. Chapter 1, Sections 1.1 and 1.3., which we draw on heavily here. Another nice resource (thanks to Luis Alonso-Ovalle for the suggestion) is Gary Hardegree’s online in-progress textbook Introduction to Metalogic : http://people.umass.edu/gmhwww/513/text.htm . (Ch 5: the semantic characterization of logic, with notions of consistency, etc.; Ch 14: the semantics of classical first-order logic.) The notation is slightly different from ours and it may be hard to read those chapters in isolation, especially Ch 14, since the book is cumulative. Anyone who has a chance to take Hardegree’s Mathematical Logic course would get a thorough grounding in all the notions we are discussing here and more. 0. Syntax and semantics; proof theory and model theory Starting out informally (see Chapter 5 of PtMW), we can say that the distinction between syntax and semantics in logic and formal systems is the distinction between talking about properties of expressions of the logic or formal system itself, such as its primitives, axioms, rules of inference or rewrite rules, and theorems, vs. talking about relations between the system and its models or interpretations. Examples: Syntactic activity: Constructing a proof from premises or axioms according to specified rules of inference or rewrite rules. (Proof theory is about this.) Semantic activity: Demonstrating that a certain set of axioms is consistent by showing that it has a model (see Section 2 below, or Ch. 8 in PtMW.) (Model theory is about such things.) Syntactic notions: Well-formedness, well-formedness rules, derivations, proofs, other notions definable in terms of the forms of expressions.Ling 726: Mathematical Linguistics, Lecture 9 Model Theory V. Borschev and B. Partee, October 17-19, 2006 p. 2 Semantic notions: truth, reference, valuation, satisfaction, assignment function, semantic entailment, and various other properties that relate expressions to models or interpretations. “The program of studying only the syntax of a system without making any appeal, explicit or tacit, to its meaning constitutes the formalist research program, which is known as Hilbert’s program in the foundations of mathematics, and, stretching the concept perhaps, as Chomsky’s program of studying syntax autonomously in the theory of generative grammar.” (PtMW p. 92) Irony: The term “formal semantics” refers to the model-theoretic semantics tradition that grew in part out of logician’s model-theoretic approach to the study of the semantics of the formal languages of logic; that tradition is not formalist in Hilbert’s sense, but is simply formal rather than informal. (The book of Montague’s collected works is called Formal Philosophy; and cf. the use of ‘formal’ in linguistics also to signal something like theoretical/explicit as opposed to practical/informal/descriptive.) We have already looked at the syntax and the semantics of statement logic and first-order predicate logic. Note that the syntax is in each case autonomous in the sense that it is fully described independently of the semantics, and the semantics is inherently relational, involving a compositional mapping from syntactic expressions to objects that belong to a model structure. 1. Syntactic provability and semantic entailment Proof theory: When we presented first order logic in earlier lectures, we specified only