Introduction to This LectureQuantified Modal LogicLecture Notes onFirst-Order Modal Logic15-816: Modal LogicAndr´e PlatzerLecture 12February 25, 20101 Introduction to This LectureIn this lecture, we will introduce first-order modal logic and start consider-ing its relationship to classical first-order logic.2 Quantified Modal LogicIn this section, we define the syntax and semantics of quantified modallogic [Car46, Kri63]. An excellent source on first-order modal logic, its var-ious variations and pitfalls is the book by Fitting and Mendelsohn [FM99].We fix a set Σ of function symbols and predicate symbols, with aritiesassociated (number of arguments) and a set of logical variables. Terms aredefined as in first-order logic. The syntax of classical first-order modal logicis defined as follows:Definition 1 (First-order modal formulas) The set FmlFOML(Σ) of formulasof classical quantified modal logic a.k.a. first-order modal logic is the small-est set with:• If p ∈ Σ is a predicate symbol of arity n and θ1, . . . , θnare terms thenp(θ1, . . . , θn) ∈ FmlFOML(Σ).• If φ, ψ ∈ FmlFOML(Σ), then ¬φ, (φ∧ψ), (φ∨ψ), (φ → ψ) ∈ FmlFOML(Σ).• If φ ∈ FmlFOML(Σ) and x is a logical variable, then (∀x φ) ∈ FmlFOML(Σ)and (∃x φ) ∈ FmlFOML(Σ).LECTURE NOTES FEBRUARY 25, 2010L12.2 First-Order Modal Logic• If φ ∈ FmlFOML(Σ) and x ∈ V , then ( φ), (♦φ) ∈ FmlFOML(Σ).There are several variations for the definition of semantics for quanti-fied modal logic. Here is one variant:Definition 2 (Kripke structure) A Kripke structure K = (W, ρ, M) consistsof Kripke frame (W, ρ) and a mapping M that assigns first-order structures M(s)to each world s such that, for each s, t ∈ W with sρt, the structure M(s) is asubstructure of M(t), i.e.:• the universe of M (s) is a subset of the universe of M (t) (monotonicity), and• the structures M(s) and M (t) agree on the interpretation of all functionsymbols on the (smaller) universe of M(s).Another common case in the semantics is that of constant domain, where allworlds in a Kripke structure are required to share the same universe.Definition 3 (Interpretation of quantified modal formulas) Given a Kripkestructure K = (W, ρ, M), the interpretation |= of modal formulas in a world s isdefined as1. K, s |= p(θ1, . . . , θn) iff M(s) |= p(θ1, . . . , θn).2. K, s |= φ ∧ ψ iff K, s |= φ and K, s |= ψ.3. K, s |= φ ∨ ψ iff K, s |= φ or K, s |= ψ.4. K, s |= ¬φ iff it is not the case that K, s |= φ.5. K, s |= ∀x φ(x) iff K, s |= φ(d) for all d in the universe of s6. K, s |= ∃x φ(x) iff K, s |= φ(d) for some d in the universe of s7. K, s |= φ iff K, t |= φ for all worlds t with sρt.8. K, s |= ♦φ iff K, t |= φ for some world t with sρt.When K is clear from the context, we sometimes abbreviate K, s |= φ by s |= φ.In constant domain semantics, quantifiers refer to the same set of objectsin all worlds. In varying domain semantics, quantifiers may possibly referto a different set of objects, depending on the world.LECTURE NOTES FEBRUARY 25, 2010First-Order Modal Logic L12.3ExercisesExercise 1 Recall Definition 3 of interpretation of quantified modal formulas. Thedefinition is imprecise at some points. What is the problem, why is it a problem,and what can be done to fix it?LECTURE NOTES FEBRUARY 25, 2010L12.4 First-Order Modal LogicReferences[Car46] Rudolf Carnap. Modalities and quantification. J. Symb. Log.,11(2):33–64, 1946.[FM99] Melvin Fitting and Richard L. Mendelsohn. First-Order ModalLogic. Kluwer, Norwell, MA, USA, 1999.[Kri63] Saul A. Kripke. Semantical considerations on modal logic. ActaPhilosophica Fennica, 16:83–94, 1963.LECTURE NOTES FEBRUARY 25,