Modelling quantifiers More about first order logic

Since the language of first order quantification theory is so much richer than that of the purely propositional fragment, the definition of truth has to be correspondingly more complicated. This section is the most technical in the Logic Notes (except for parts of Chapter 7) but this is mainly because of the level of detail required. Logic remains the science of the obvious, even if spelling out the obvious with the necessary degree of formal rigour is not entirely simple.

The exposition below makes use of some basic concepts concerning sets. We do not need to go into axiomatic set theory in this course, but you do need the idea of a set as a collection of its members, of one set being a subset of another, of a finite sequence of n things (also known as an n-tuple, and of a function mapping objects from one set to objects in another. The first section of Chapter 7 below contains all the basics you need for the present chapter.

For the sake of clarity, the definitions are given here only for unrestricted (unary) quantifiers. The extension to deal with binary ones is not conceptually very difficult, but it adds another layer of intricacy, with the main effect of obscuring the ideas.

An interpretation of propositional logic is just an assignment of truth values (0 and 1, or false and true) to the atomic formulae (p, q, r, ....), and there is an associated story about how the values of compound formulae are determined by those of their constituent atoms. The first order case is more of the same, except that we pay attention to the inner structure of atomic formulae and we need extra clauses saying how to manage quantifiers and variables.

:   Interpreting names and predicate symbols over a domain: 'Fa' is true and 'Fb' is false.

An atomic formula consists of a predicate symbol applied to appropriately many names. The job of an interpretation I is to determine which such atoms are true and which are false. To do this, it needs to assign a value to each of the names and a value of some kind to each predicate symbol. Before it can do that, it needs to specify what we are talking about: that is, it must determine a set of objects over which the variables are to range. This is called the domain of the interpretation, and can be any non-empty set. In a particular interpretation, the domain could be, for instance, the set of real numbers, the set of chemical elements, the set of words of a language or the finite set {Bob, Carol, Ted, Alice}. In general we allow it to be absolutely any set other than the empty set ∅.

Names are supposed to name things, so the value of a name on a particular interpretation is the object it refers to when interpreted that way. That is, for any name m, I(m) is an object in the domain of I. So far so good. Now a predicate symbol, also known as a relation symbol, ought to be interpreted as a relation between the things in the domain, and so it is. For any n-tuple ⟨α₁ ,..., α_n⟩ of things in the domain, either those things in that order are related by the relation in question or they are not. In set-talk, we identify an n-adic relation with the set of n-tuples it relates. For example, the binary relation '<' on the domain of natural numbers is the set of all number pairs ⟨a, b⟩ where a is less than b (e.g. the ordered pair ⟨16, 38⟩ is in that set, while the pair ⟨38, 16⟩ is not). We therefore take I(F_n) to be some set of sequences each of the form ⟨α₁ ,..., α_n⟩ where all of the  α_i  are in the domain of I. In the limiting case where n = 1 the "relation" is just a (monadic) property, and we may think of I(F) in that case as a subset of the domain, as in picture.

All this is to say that an atomic formula Fm₁ ... m_n is true on interpretation I if and only if the objects I(m₁), ..., I(m_n) in that order constitute one of the sequences in I(F). This, despite the unfamiliar notation and set-theoretic dressing-up, should be obviously the right condition.

Function symbols may be added to the mix in the expected way: where f is an n-adic function symbol, I(f) is a function of n arguments. Each term denotes a member of the domain, again in the obvious way: where f is interpreted as a function φ and terms t₁, ..., t_n denote objects α₁ ,..., α_n respectively, the compound term f(t₁, ..., t_n) denotes the object φ(α₁ ,..., α_n). Compound terms then behave just like names, since, like names, they serve to pick out objects.

The clauses for evaluating formulae built up using connectives are exactly the same as in the propositional case. That is, they follow the truth tables. Quantifiers, however, require some further apparatus. Variables are to substitute for names, but unlike names they should range over all possible individuals from the domain rather than referring to just one. How is this to be done?

The key is to consider not just single interpretations but related sets of them. Where m is a name, we say that two interpretations are m-variants of each other if they agree about everything except perhaps the value of m. As a limiting case, every interpretation is an m-variant of itself. While on any one interpretation m denotes something, just like any other name, over a set of m-variants it behaves like a variable denoting ambiguously while everything else stays the same.

Now the interpretation clauses for quantifiers can be stated. Recall that for quantified formulae ALLvB and SOMEvB to be well-formed, B must be of the form A^v_mfor some name m and v must be a variable not in A. The interpretation clauses follow this construction: ALLvA^v_mis true for interpretation I iff A is true for every m-variant of I, while SOMEvA^v_mis true iff A is true for at least one m-variant of I. Again these are intuitively the right conditions: 'Everything [resp. something] is F' is true if and only if Fa is true for all [resp. some] possible values of a.

It is convenient to adopt a little more notation for m-variants. Where I is an interpretation and α is a member of the domain, let  I_{[m ← α]}  be the m-variant J such that  J(m) = α. Clearly,  I_{[m ← α]}(m) = α, while for every other name n,  I_{[m ← α]}(n) = I(n), and moreover  I_{[m ← α]}(F) = I(F)  for every predicate symbol F and  I_{[m ← α]}(f) = I(f)  for every function symbol f of arity greater than 0.

To illustrate, consider the formula  ALLx (Fx IMP Gx).   For this to be true for an interpretation I, it is necessary and sufficient that  Fa IMP Ga  be true for all a-variants of I. That means that for any element α in the domain of I, if a were to refer to α then  Fa IMP Ga  would come out true, which, by the truth table for IMP, is to say if  Fa  would be true then  Ga  would be true. In symbols: for all elements α in the domain,  Fa IMP Ga  is true for  I_{[a ← α]}, meaning that if Fa is true for  I_{[a ← α]}  then so is Ga. By the evaluation condition for atomic formulae, this means that if  I_{[a ← α]}(a) ∈ I_{[a ← α]}(F)  then  I_{[a ← α]}(a) ∈ I_{[a ← α]}(G). But  I_{[a ← α]}(a) is just α, and  I_{[a ← α]}  agrees with I about predicate symbols. So  ALLx(Fx IMP Gx)  is true for I if and only iff for every object α in the domain, if  α ∈ I(F)  then  α ∈ I(G), which is just to say that I(F) is a subset of I(G). Since  ALLx (Fx IMP Gx)  is used to express the claim that all Fs are Gs, this modelling condition looks right.

As another illustration, consider the formula  ALLx SOMEy Rxy  in an interpretation I whose domain is the natural numbers 0, 1, 2, ... where I(R) is the numerical ordering relation <.  ALLx SOMEy Rxy  then says that there is no biggest number, which should come out true of course. And so it does. Take any two names; they could be the numerals 3 and 7, for instance, but it will be less confusing to let them be arbitrary names like a and b. Perhaps I(a) = 3 and I(b) = 7 anyway, but this is of no significance. Note that the expression  Rxy  is  Ray^x_aand that  Ray  is  Rab^y_b. Consider any a-variant of I: say, the one that assigns a the number 42. Let's call that interpretation J. What is the value of  SOMEy Ray  on interpretation J? Well, let interpretation K be just the same as J except that it assigns b a larger number—say, 50. Of course 42 < 50, so  Rab  is true for K. Therefore there exists a b-variant of J for which  Rab  is true, so  SOMEy Ray  is true for J. Clearly a similar argument will work for any other a-variant of I, so by the interpretation clause for universal quantifiers,  ALLx SOMEy Rxy  is true for I.