4.1 Finite Interpretations and Expansions with One-Place Predicates

finite interpretation

Definition. A FINITE INTERPRETATION for a set of symbolic sentences (containing one-place predicates but no many-place predicates) consists of three components:

universe

A finite set of objects called the UNIVERSE or DOMAIN. The universe must contain at least one object.

predicate extensions

An EXTENSION for each of the predicates in the sentences. Each extension is a subset of the universe containing those objects to which the predicate applies.

truth-value specifications

Truth-value specifications for the sentence letters in the sentences. Each of the sentence letters is paired with the specification True or with the specification False.

Comment. Such an interpretation is finite because its universe is a finite set. In the rest of this section, we will use `interpretation' as shorthand for `finite interpretation'.

evaluation

Comment. Given an interpretation for a set of sentences, it will be possible to determine truth values for the sentences in the set.

Example.
Here is a conditional sentence and an interpretation in which it can be evaluated:

@x(Fx v ~Gx) -> P v $x(Gx & ~Fx)

U: {a,b,c}
F: {a,b}
G: {b}
P is False

In this interpretation the antecedent of the sentence is true since everything in the universe is either F or not G (a and b are both F, c is not G).

The consequent of the conditional is false, since both disjuncts are false. (P is specified false. The existential wff is false because there is nothing in the extension of G that is not also in the extension of F.)

The conditional is, there-fore, false.

Comment. The procedure for determining the truth values of sentences in an interpretation for them is given more precisely in section 4.2.

universal expansion

Definition. The EXPANSION OF A UNIVER- SAL WFF relative to a universe of n elements consists of n conjuncts, where the nth conjunct is an instance of the formula with the name of the nth element in the universe as the instantial name. (We refer to this as a UNIVERSAL EXPANSION for short.)

Comment. Strictly speaking, all conjunctions have exactly two conjuncts. Expressions having the form f & y & ... are unproblematic, however, because of the associativity of & (S30). So, it is acceptable to use the notion of a conjunction with more than two conjuncts in the definition of a universal expansion. Likewise, because of the associativity of v (S31), we use the notion of a disjunct with more than two disjuncts in the definition of an existential expan- sion, below.

Example.
The expansion of
     @x(Fx -> Gx)
in the universe {a} is
     (Fa -> Ga).
In the universe {a,b} its expansion is
     (Fa -> Ga) & (Fb -> Gb).
In the universe {a,b,c} its expansion is
     (Fa -> Ga) & (Fb -> Gb) & (Fc -> Gc),
and so on.

existential expansion

Definition. The EXPANSION OF AN EXISTEN- TIAL WFF relative to a universe of n elements consists of n disjuncts, where the nth disjunct is an instance of the formula with the name of the nth element in the universe as the instantial name. (EXISTENTIAL EXPANSION for short.)

Example.
The existential
$x(Fx & Gx)
expands to
(Fa & Ga) v (Fb & Gb) v...
for the universe {a,b,...}.

overlapping quantifiers

Comment. In cases where quantifiers overlap, ex- pansion may take several steps, starting with the quantifier with the widest scope and then expanding those with narrower scope. Expansion is complete when no quantifiers remain.

Example.
In the universe {a,b},
     $x(Fx -> $yGy)
is first expanded to
     (Fa -> $yGy) & (Fb -> $yGy),
then to
     ((Fa ->(Ga v Gb)) & (Fb -> (Ga v Gb)).

truth values of complex sentences

Comment. The truth values of complex sentences in a given interpretation are determined as follows.

quantifiers

(i)

Construct the expansions of all universal and existential formulas, then assign truth values for the resulting quantifier-free sentences according to steps ii-iv below. The truth value of a quantified sentence is the truth value of its expansion.

sentence letters

(ii)

Sentence letters have the truth values directly assigned to them in the interpretation.

predicates

(iii)

Formulas of the form Fa, where F is a predicate and a is a name, are true if the object a is in the extension of F and false otherwise.

connectives

(iv)

The truth values for the sentential connectives are determined according to the usual truth-functional rules for the connectives.

Exercise 4.1

Give the expansions for the following sentences
(a) for the universe {a},
(b) for the universe {a,b},
(c) for the universe {a,b,c}.

@xFx

ii*

$xFx & P

iii*

@xFx -> $xGx

iv*

@x(Gx <-> P) v @xHx

Ha v $xGx

vi*

$x(Fx v Hx)

vii*

@xFx <-> $x(Fx & ~Hx)

viii*

~@x(Fx & Gx)

ix*

~@xFx & ~@xGx

~(@xGx <-> $x(Hx & ~Fx))

Exercise 4.2

Say whether the sentences in exercise 4.1 are true in the following interpretations:

U: {a}, F: {a}, G: { }, H: { },
P is False

U: {a,b}, F: {a}, G: {a,b}, H: { },
P is True

U: {a,b,c}, F: {a,b,c}, G: {a,b}, H: {b},
P is False

[Prev] [Next]