Modal Predicate Logic

Philosophy 244: #9— Modal Predicate Logic Now we turn to modal predicate logic, the result of adding modal operators to firstorder quantification theory. First-order quantification theory is itself the result of making two additions to propositional logic. First, we dig into the structure of atomic sentences, replacing the simple indivisible p with things of the form ϕx1 x2 ....xk that is, a k-ary predicate followed by k variables. Second, we introduce a new way of forming complex sentences from simpler ones, a way that wouldn’t have been available without the aforementioned digging. Whenever you’ve got a formula α(x) with a variable in it, you can stick a quantifier in front. ∀x α(x) ∃xα(x) If flexibility is the property that ϕ(x) attributes to x, then the first of these says that everything is flexible, and the second that something is flexible. The process can be reiterated with different variables, to get things like ∀x∃y ψ(x, y), which if admiration is the relation expressed by ψ, says that everyone admires somebody. And so on indefinitely. Syntax Now let’s give the syntax and semantics formally; that we’ll be taking the universal quantifier ∀ as basic, the existential ∃ will be defined as ¬∀¬. A language L for LPC has as its lexicon Actually you can stick a quantifier in front regardless, but it doesn’t do anything unless you’ve got a corresponding variable. The book’s name for first-order quantification theory is “lower predicate calculus” or LPC. The reason for the “lower” is that we’re quantifying into name-position only, not predicatepositions as in second-order logic (∃X Xmc = Marcus and Kripke have something in common). ”Lower” means the same as ”first-order.” for each n ≥ 1, a denumerably infinite set of n-place predicates ϕ. ψ,...(P, Q,,.....) a denumerably infinite set of individual variables x, y, z,... the three logical symbols ¬,∨, ∀ left and right parentheses The formation rules for wffs are FR1 FR2 FR3 FR4 An n-place predicate followed by n individual variables is an atomic wff If α is a wff so is ¬α If α, β are wffs, so is (α ∨ β) If α is a wff and x a variable then ∀x α is a wff. The definitions of &, ⊃, and ≡ are as before. The existential quantifier is defined by D∃ ∃x α =df ¬∀x¬α The scope of a quantifier in α is the smallest sub-wff of α that contains it. (Examples.) A variable x is called bound or free according to whether it is or isn’t in the scope of an x-quantifier. Note that it is really occurrences of variables that are bound or free, and that bound/free is always relative to an enclosing formula; x is bound in ∃x∀yRxy but free in the bit after the initial quantifier: ∀y Rxy. 1 An exception is made though for the variable immediately after the ∀ or ∃; this is neither bound nor free, it’s considered just part of the quantifier. Semantics The first thing we need for an interpretation of L is a domain D to signal what we are talking about. When we say ∃xα or ∀xα, this means that there is something in the domain which satisfies α, or that everything in the domain satisfies α. The domain can in principle be considered our interpretation of the quantifiers—D = V(∀)—in something like the way that multiplication is our interpretation of conjunction; in that case the model would be determined by V alone. If P is an n-place predicate, V(P) is a set of n-tuples drawn from the domain D. In the language of cross products, it’s a subset of D×...×D (n times). A model M of L is an ordered pair of a domaIn and an interpretation function. Don’t variables have to stand for objects? Yes and no. Names when we get to them will be assigned objects by V. But not variables; they stand for “arbitrary” or “unspecified” objects. The reason is that there are two kinds of wffs. Those with free variables — open wffs – we don’t assign truth-values to, so there’s no need to specify an object to help determine that truth-value. Those whose variables are all bound— closed wffs or sentences of L — we do assign truth-values to, but in a way that relies only on the pattern of variables in the sentence, and so does not require an assignment of particular objects to any of them. Consider ∀xPx. This will be true if V(P) = D, otherwise false. No need for x to stand for any particular entity. As for Px, whether it should be counted true or false depends on what we think of x as standing for. We could let V assign values to variables too, but then we lose this freedom of construing it as standing for whatever we like. Also it is mainly sentences we want to come out true or false in the model, so assigning a fixed value to x would not accomplish much. But again, though we don’t don’t want x to refer to anything in particular in our model , we do want to generalize over all the things it might be taken as referring to. This in order to say, e.g., that ∀xPx is true iff Px is true “whatever we take x to be.” To accomplish this, let a value-assignment µ be a function mapping variables to arbitrary members of the domain; for all variables x, µ(x)D. We write Vµ (α)=1 to mean that α is true in the model when the variables are given the values assigned by µ. This approach enabled in 1930 the first recursive definition of truth for quantified languages. See p.237 for the informalities. Are the cases really analogous? What does this mean for ∀’s status as a logical constant? Kit Fine has a book taking arbitrary objects seriously as a distinctive sort of object An arbitrary D has the properties all Ds have in common, with a few exceptions, e.g., non-arbitrariness. Open wffs will be evaluable only if their universal closures are valid or anti-valid. Tarski called µ a “sequence,” and spoke of satisfaction by a sequence of objects rather than truth of those objects. (Vϕ) Vµ (ϕ(x 1 ....x n ))=1 iff <µ(x 1 )...µ(x n )>εV(ϕ), otherwise 0. (V¬) Vµ (¬α) = 1 iff Vµ (α)=0, otherwise 0 (V∨) Vµ (α∨β) = 1 iff Vµ (α)=1 or Vµ (β)=1 (V∀) Vµ (∀xα)=1 iff Vρ (α) = 1 for every x-alternative ρ to µ, otherwise 0 From this last and the rule for negation it follows that (V∃) Vµ (∃xα)=1 iff Vρ (α)=1 for some x-alternative ρ to µ, otherwise 0. The interesting part of the definition, and the part we most need the valueassignment µ for, comes with the quantifiers. Say that ρ is an x-alternative to µ if ρ agrees with µ on every variable but (possibly) x. Finally the all important notion of Validity α is valid in M = iff Vµ (α)=1 for every variable-assignment µ, and valid (period) iff it’s valid in every model M. Axiomatization This time we’ll state the axiom(s) schematically instead of leaning hard on a a uniform substitution rule. PC Any LPC substitution-instance of a valid PC wff is an axiom of LPC. ∀1 ∀xα ⊃ α[y/x] 2 The precise definition of α[y/x] is complicated, because we don’t want x’s free in α to turn into y’s that are bound in α[y/x]. See The Principle of Replacement on pp.240-241. The rules are MP `α, `α⊃β ⇒ ` β ∀2 `(α⊃β) ⇒ `(α⊃∀xβ) provided x is not free in α. How would we show that every LPC theorem is valid? Some derived rules: UG `α ⇒ `∀xα UG⊃ `(α⊃β) ⇒ `(∀xα⊃∀xβ) UG≡ `(α≡β) ⇒ `(∀xα≡∀xβ) UG is the model for the rule of necessitation: `α ⇒ `α. Eq `α≡β ⇒ `γ[α]≡γ[β] where γ[α] differs from γ[β] only in having α at 0 or more places where γ[β] has β RBV `∀xα≡∀yβ where α differs from β only in having free x where and only where β has free y ∀xα and ∀yβ are “bound alphabetic variants.” Some theorems: LPC1 ∀x(α⊃β)⊃(∀xα⊃∀xβ) LPC2 ∀x(α⊃β)⊃(α ⊃ ∀xβ) provided x is not free in α LPC3 ∃y(α[y/x]⊃∀xα) if y is not free in ∀xα QI ¬∃x¬α≡∀xα — quantifier interchange, generalizes a la LMI Modal LPC The language of modal LPC differs from the language of LPC in having the modal operator  as a lexical item, and in having a slightly amended second formation rule: E.g., ∃y(Fy ⊃ ∀xFx). Why is this valid? Either V(F) = D or not. If V(F) = D then the sentence is true because the conditional’s consequent is true. Otherwise the domain contains a thing not in V(F). ∃y(Fy ⊃ ....) is true because Fy ⊃ ... is true (due to a false antecedent) when y is assigned that thing as its value. FR2’ If α is a wff then so are ¬α and α A model M for modal LPC is a quadruple in which is a frame, D is a domain, and V is a function from n-place predicates to, not n-tuples of domain elements, but n+1-tuples of domain elements and worlds — the idea being that εV(ϕ) iff a and b stand in the relation expressed by ϕ in world w. (Vϕ) Vµ (ϕ(x 1 ....x n ),w)=1 iff < µ(x 1 )...µ(x n ), w >εV(ϕ), otherwise 0. (V¬) Vµ (¬α,w) = 1 iff Vµ (α,w)=0, otherwise 0 (V∨) Vµ (α ∨ β,w) = 1 iff Vµ (α,w)=1 or Vµ (β,w)=1 (V) Vµ (α,w) = 1 iff Vµ (α,u) = 1 for every u that w bears R to (V∀) Vµ (∀xα,w)=1 iff Vρ (α,w)=1 for all x-variants ρ of µ ρ is an x-variant of µ if ρ agrees with µ on every variable but (possibly) x. Finally the all important notion of Validity α is valid in M = iff Vµ (α,w)=1 for all w and µ, and valid on iff it’s valid in every model M based on . Systems of Modal Predicate Logic Suppose S is a normal system of modal propositional logic. Then LPC+S is defined as follows. Axioms: S’ `α whenever α is an LPC substitution instance of an S-theorem, ∀1 `∀xα⊃α[y/x] if α[y/x] is α with a free y replacing every free x 3 ”Normal” = extension of K. Rules: NE `α ⇒ `α MP `(α⊃β), `α ⇒ `β ∀2 `(α ⊃ β) ⇒ `(α ⊃ ∀xβ) provided x is not free in α Another important potential axiom is the following, which concerns interactions between the quantifiers and : BF ` ∀xα⊃∀xα This is the famous Barcan formula, named after Ruth Barcan Marcus. The notation S+BF is used for LPC+S with BF added. Let’s see what the BF can do for us. The converse is important too. BFC ` ∀x α⊃∀xα How do these strike you intuitively? Everything is necessarily material, according to the materialist. Is it necessary that everything be material? Necessarily everything exists. Does it follow we are all like God in necessarily existing? Recall LPC1 ∀x(α⊃β)⊃(∀xα⊃∀xβ). Can we generalize it to ∀x(αJβ)⊃(∀xαJ∀xβ)? Well, in box terms it’s ∀x(α ⊃β) ⊃ (∀xα⊃ ∀x β). To prove this, it’s enough to show that ∀x(α⊃β) ⊃ ∀x(α⊃ β) (since  and ∀ distribute over material implication). But that’s an instance of BF. Which is more plausible, BF or CBF? The converse of the Barcan formula is, interestingly enough, a theorem even of LPC+K: BFC ∀xα⊃∀xα 1 ∀xα ⊃ α ∀1 2 ∀xα ⊃ α (1)xDR1 3 ∀xα ⊃ ∀xα (2)x∀2 How do modalities mix with the “opposite” sort of quantification? ∃xα ⊃ ∃xα is valid, as is ^∀xα ⊃ ∀x^α. Converses of these are not valid. Neither would we want them to be. The converse of the first, ∃xα ⊃ ∃xα, involves exactly the kind of mix-up that Quine complained about in quantified modal logic. An instance would be, Necessarily there is a number of planets only if something necessarily numbers the planets. There are lots of modal systems S such that LPC+S does not have BF as a theorem. It is a theorem, though, if S contains the Brouwer axiom B. Here is why: BF ` ∀xα⊃∀xα 1 ∀xα ⊃ α ∀1 2 ^∀xα ⊃ ^α (1)xDR3 3 ^α ⊃ α B 4 ^∀xα ⊃ α (2),(3)xPC 5 ^∀xα ⊃ ∀xα (4)x∀2 6 ∀xα ⊃ ∀xα (5)xDR2 Next time: different systems of modal predicate logic, types of validity, soundness, essentialism, de re and de dicto necessity. 4 Williamson argues in Modal Logic as Metaphysics that both should be considered valid, because all worlds have the same domain. Recall that α J β — α fishhook β — is equivalent to (α ⊃ β)