4.1: Finite Interpretations

Finite interpretations play the same role for predicate logic that truth tables did for sentential logic: they give us a way to talk about truth and falsehood for wffs. A finite interpretation is always a finite interpretation for some set of sentences. We need three basic notions:

UNIVERSE: A finite set of objects (also called the DOMAIN of the interpretation). It must contain at least one object.

The universe for an interpretation can be absolutely any set of objects whatever, so long as it contains at least one thing and only finitely many things. Examples:

  1. The set of all states in the United States.
  2. Chicago, the planet Uranus, the Atlantic Ocean, and my cat Mungo.
  3. The set of all living US Presidents and former presidents (which is the same set as the set containing Barack Obama, George W. Bush, Bill Clinton, George H. W. Bush, and Jimmy Carter).
  4. The set of all positive integers less than 100.

To indicate a set, we will use curly braces "{}" and list the members of the set within them.

PREDICATE EXTENSIONS: For each predicate F found in the sentences, the extension of F is the set of those things in the universe to which F applies.

Strictly speaking, this is the definition of the extension of a one-place predicate. We can define the extensions of two-place, three-place, etc., predicates, but it requires a more complicated definition. For the moment we will pass over this.

Example: Suppose that the universe is the set of all living US Presidents and former Presidents. Then the extension of 'Democrat' is {Jimmy Carter, Bill Clinton}, and the extension of 'Republican' is {Gerald Ford, George H. W. Bush, George W. Bush}.

Example: Suppose that the universe is the set of all positive integers less than 10. Then the extension of 'odd' is {1,3,5,7,9}.

TRUTH VALUE SPECIFICATIONS: The finite interpretation must assign a truth value (either true or false) to each sentence letter in the set of sentences. (If the set of sentences does not contain any sentence letters, then there will not be any truth value assignments.

In practice, we will give finite interpretations for sets of well-formed formulas by using lists of names. So, the universe for an interpretation might consist of the set {a, b, c}, that is, the three names a, b, and c. For convenience, we will use "U" for the universe and state this as follows:

U: {a, b, c}

We will use a similar notation for indicating the extensions of predicates. Consider for example this sentence:

x(Fx v ~Gx) → x(Gx & ~Fx)

This contains two predicates, F and G, and no sentence letters. An interpretation of it must then give a universe and the extensions of F and G in that universe. Here is an example:

U: {a, b, c}
F: {a,b}
G: {b,c}

How did we determine what the universe was and what the extensions of F and G are? Easy--we just made them up. All an interpretation is is some universe or other with some extensions assigned to the predicates in that universe. There are plenty of others. For example, here's another one for this sentence using the same universe:

U: {a, b, c}
F: {a}
G: {c}

And here's another one, with a different universe:

U: {a}
F: {a}
G: {a}

And here's yet another one, with another universe:

U: {a,b}
F: {a}
G: {}

Notice that in the last example, the extension of G is empty, that is, there is nothing in it. This is perfectly acceptable in an interpretation: we don't require that every predicate actually apply to anything.

Once we have set up an interpretation for a set of sentences, we can then determine the truth value for every sentence in that set in that interpretation. The procedure rests on the following rules:

1. The truth value of a predication 'Fa' in an interpretation is true if and only if a is in the extension of F. Otherwise, it is false.
2. The truth value of a universal wff xΦ is true in an interpretation if and only if Φ is true in that interpretation when every member of the universe is substituted for x in it.
3. The truth value of an existential wff xΦ is true in an interpretation if and only if there is at least one member of the universe that makes Φ true in that interpretation when it is substituted for x in it.
4. The truth values of conjunctions, disjunctions, conditionals, biconditionals, and negations are determines on the basis of the truth values of their constitutents, just as in sentential logic.

As an example, consider the sentence x(Fx v ~Gx) → x(Gx & ~Fx) above and the interpretation U: {a, b, c}, F: {a, b}, G: {b}. We determine its truth value as follows.

1. This sentence is a conditional. So, we must evaluate its antecedent and its consequent. We'll begin with the antecedent x(Fx v ~Gx)

2. This sentence is true if and only if the result of substituting, in turn, each of the names in the universe for the variable 'x' in 'Fx v ~Gx' is true. Here are those substitutions:

For a: Fa v ~Ga
For b: Fb v ~Gb
For c: Fc v ~Gc

3. Start with the first of these, 'Fa v ~Ga'. We can start out here by determining the truth values of 'Fa' and 'Ga':

For Fa: the extension of F is {a, b}, so 'Fa' is T.
For Ga: the extension of G is { b}, so 'Ga' is F.

4. So, the truth value of 'Fa v ~Ga' will be given by '(T) v ~(F)' = '(T) v (T)' = T. We can do this for all the other elements of the universe. The results are in the following table:

xFxGx~GxFx v ~Gx
aTFTT
bTTFT
cFFTT

5. Since the value of 'Fx v ~Gx' is true for every member of the universe, 'x(Fx v ~Gx)' is true in this interpretation.

Exercise 4.1.1

i. ∀xFx

ii. ∃xFx&P

iii. ∀xFx→∃xGx

iv. ∀x(Gx↔P)∨∀xHx