true

in

M9

relative to

every

assignment for

M9

. Thus is

true

in

M9

.

But the reasoning generalizes to any other assignment for

M9

.

The reason being that while the ordered pair < Silver Lake, Los Feliz > is in in the extension of

F

in

M4

, Los Feliz is in the extension of

G

in

M4

. So, ¬

Gx

is

not true

in M4 relative to

f[x/Los Feliz]

.

Since the factory is

not

a member of the set { }, we conclude that the second premise is

true

in

M1

as well.

C

is interpreted by the model to apply to the members of the set

B

is interpreted by the model to apply to the members of the set

**SEMANTICS**

**Predicate Logic**

At this point, we have specified the

vocabulary

and

grammar

of the language of Predicate Logic, which allowed us, in turn, to provide a formal characterization of the concept of a

formula

.

We now undertake a different task:

We will explain how to

interpret

the language of Predicate Logic.

Much like we did for Propositional Logic, we will specify a range of interpretations for the language of Predicate Logic.

logical truth

for sentences of Predicate Logic;

logical equivalence

for pairs of sentences of Predicate Logic;

consistency

for sets of sentences of Predicate Logic; and

validity

for arguments given in the language of Predicate Logic.

Models for the Language of Predicate Logic

We know how to interpret the

propositional connectives

of Predicate Logic;

we need an

interpretation

of the language of Predicate Logic to tell us how to interpret other expressions that occur in the vocabulary of Predicate Logic.

An interpretation for the language of Predicate Logic is a

model

. A model consists of three main ingredients:

(1) A

domain of discourse

,

The

domain of discourse

is the

set of objects

over which the quantifiers range, according to the model.

The

denotation

of a constant

in a model is

the object

to which the constant is supposed to refer according to the model.

The

extension

of a predicate

in a model is the

set of objects

to which the predicate is supposed to apply according to the model.

(2) A specification of a

denotation

for each constant in the language of Predicate Logic, and

(3) A specification of an

extension

for each predicate of the language of Predicate Logic.

1.1 How to Evaluate a Closed Formula in a Model

Consider the following argument in the language of Predicate Logic:

(1)

A model for the language of Predicate Logic will at the very least specify:

(i) a

domain of discourse

for the quantifiers to range over,

(ii) a

denotation

for the constants

a

and

b

, and

(iii)

extensions

for the monadic predicates

A

,

B

, and

C

.

(2)

(3)

Let the

domain of discourse

of

M1

be two buildings (eg. the factory and the bank).

We can write this as a

set

with two

members

:

(1)

A model must also specify a set of things from the domain for

each

predicate

letter.

(2)

(3)

To interpret a monadic predicate

B

to apply to the members of the set { } is roughly to say:

The predicate applies to an object in the domain

iff

the object is a member of the set.

We can, very roughly at this point, evaluate each of the premises of the argument we specified at the outset with respect to this sample model:

(1) is true in

M1

if and only if

Aa

is true in

M1

and

Ba

is true in

M1

.

Since the bank is a member of both sets, we conclude that the first premise is

true

in

M1

.

(2) is true in

M1

if and only if it is

not

the case that

Cb

is true in

M1

.

The conclusion requires special attention.

The

domain of discourse

of the model

M1

consists only of the bank and the factory, which are, respectively, the denotations of the constants

a

and

b

.

So, as a first approximation, we may take the conclusion (3) to be true in

M1

just in case:

In other words, the conclusions is true in

M1

if and only if

either

:

is true in

M1

,

or

Since the bank is a member of the set ,

Ca

is true in M, which means that

neither nor

is true in

M1

.

Likewise, since the factory is not a member of the set , we have that

neither nor

is true in

M1

.

We conclude that the conclusion of the argument is

not true

in the model

M1

we have just specified.

Notice that the evaluation of the existentially quantified formula in the model relied on the fact that we had a

name

for

every member of the domain

.

Unfortunately, we cannot make the same assumption for every model, and we will later introduce a

different way

of evaluating the truth value of a quantified formula with respect to a model.

There are no restrictions on the sorts of objects and sets thereof we may employ in the specification of a model for the language of Predicate Logic.

Two Clarifications

We will then use them in order to define

key concepts

:

1.2 Using Diagrams

A model may let the set of two buildings in the diagram above be the domain of discourse,

D.

It may identify one of the buildings as the denotation of the constant

a

, and as the denotation of the constant

b.

(1)

(2)

(3)

Consider, for example:

It may also specify the sets of objects in the domain

{

o in D

:

o is enclosed by a circle

}

{

o in D: o is enclosed by a square

} and

{

o in D

:

o is enclosed by a triangle

}

as the extensions of

A

,

B

, and

C

, respectively.

Models and Two-Place Predicates

The argument in the previous examples contains only monadic predicates.

Consider the following argument in the language of Predicate Logic:

1.

2.

3.

Much like before, a model for the language of Predicate Logic will at the very least specify:

(i) a

domain of discourse

for the quantifiers to range over,

(ii) a

denotation

for the constants

a

and

b

,and

(iii)

extensions

for the predicates F and G.

But notice since

F

is a

two-place

predicate

, the

extension

assigned by the model will now be a set of

ordered pairs

of objects

in the domain (rather than simply a set of objects).

To claim that an

ordered pair

<

p

,

q

>

M4

may perhaps specify Silver Lake as the

denotation

of the constant

a

, and Los Feliz as the

denotation

of the constant

b

.

Finally,

M4

may specify a

set of neighborhoods

in the domain for each

monadic predicate letter

, and a

set of ordered pairs

of neighborhoods in the domain for each

two-place predicate letter

.

M4

may specify the extension of the monadic predicate

G

to be the set {Los Feliz, Silver Lake}

and may specify the the extension of the two-place predicate

F

to be:

a

is interpreted by

M4

to denote Silver Lake.

b

is interpreted by

M4

to denote Los Feliz.

F

is interpreted by

M4

to apply to an

ordered pair

, <

p

,

q

>, of objects in the

domain

if, and only if,

p

is adjacent to

q

.

So:

The

domain of discourse

of

M4

is the set of neighborhoods in Los Angeles.

So the extension of

F

is the set {< Los Feliz, Silver Lake >, < Silver Lake, Los Feliz >}.

G

is interpreted by

M4

to apply to the members of the set {Los Feliz, Silver Lake}.

Let us assume that each neighborhood in the domain is, in

M4

, the denotation of some constant of the language.

For example, let Beverly Hills be the denotation of

c

according to

M4

.

As as a first approximation, we may take (3) to be true just in case

there is some neighborhood in the domain

such that

We may, if we like, help ourselves to a diagram for the specification of a model for Predicate Logic.

Consider, for example:

p

1

p

2

p

3

We can, very roughly at this point, evaluate each of the premises of the argument we specified above (in Example 4) with respect to this model:

(1)

(2)

(3)

1.2. Evaluating an Open Formula at a Model

Thus far we have informally discussed the evaluation of various sentences of the language of Predicate Logic with respect to a model, but you may wonder what happens when we attempt to evaluate an

open

formula in a model.

Consider

M1

again:

Since models remain silent on this point, we need to supplement them with

another

parameter for the evaluation of an open formula:

An

assignment

of values to the variables of the language

An

assignment of values to the variables

,

f

, for a model

M

is a function mapping each variable of the language of Predicate Logic an element in the domain of discourse of

M

.

An assignment,

f

, for

M1

maps variables into members of the set .

An assignment,

f

, for

M4

maps variables into neighborhoods of Los Angeles in the set {Beverly Hills, Los Feliz, Silver Lake}.

An assignment,

f

, for

M5

maps variables into the members of the set of points {

p1

,

p2

,

p3

}.

In order to check whether an open formula like

is true in the model

M1

with respect to an assignment

f

of values to the variables, we need to know what

value

has been assigned to ‘

x

’ and ‘

y

’ by

f

.

Compare, for example, the following assignments:

f1

is an assignment for

M1

which maps the variable

x

to , the variable

y

to , the variable

z

to , etc.

. . . x y z . . .

f2

is an assignment for

M1

which maps the variable

x

to , the variable

y

to , the variable

z

to , etc.

. . . x y z . . .

Then:

is true in

M1

relative to

f1

if, and only if,

Ax

is true

in

M1

relative to

f1

and

By

is true in

M1

relative to

f1

.

Ax

is true in

M1

relative to

f1

if, and only if,

(the bank) is in the extension of

A

in

M1

.

By

is true in

M1

relative to

f1

if, and only if,

(the factory) is in the extension of

B

in

M1

.

Ax

is true in

M1

relative to

f1

if, and only if, the bank is a member of the set .

By

is true in

M1

relative to

f1

if, and only if,

the factory is a member of the set .

Since

is

in , but is

not

in , we

conclude that is

not true

in

M1

relative to

f1

.

1.3. How to Evaluate a Quantified Formula at a Model

We are now in a position to revisit the evaluation of quantified formulas.

Until now, we have relied on the assumption that every member of the domain is, in M1, the

denotation of some constant

.

We have taken to be true in

M1

if there is some building in the domain

named by some constant

such that the formula obtained by dropping the quantifier and

replacing the variable with the constant

denoting that building is true in

M1

.

We have, in effect, reduced the truth of in the model to the truth of

one of the instances

Aa

or

Ab

in the model.

Now that we are in a position to handle the evaluation of

an open formula

like

Ax

in

M1

relative to an assignment

f

for

M1

, we will proceed differently.

is true in

M1

relative to an assignment

f

if, and only if, there is some object

p

in the domain such that the formula

Ax

is true in

M1

relative to

f

[

x

/

p

].

So, is true in

M1

relative to an assignment

f

iff some object

p

in the domain is such that

the open formula

Ax

is true in

M1

relative to some assignment

just like

f

except possibly for

assigning

p

to the variable

x

.

To provide a different illustration,

let us return to

M4:

Consider the evaluation of an existentially quantified formula like:

in

M4

with respect to an assignment

f

for

M4

on which:

. . . x y z . . .

Beverly Hills Los Feliz Silver Lake

is true in

M4

relative to an assignment

f

if, and only if, there is some

p

in the domain such that is true in

M4

relative to

f

[

x

/

p

].

Recall

that

f

[

x

/

p

] is an assignment just like

f

except perhaps for assigning

p

to the variable

x

.

If

f

already assigns

p

to

x

, then

f

[

x

/

p

]

just is

f.

Otherwise,

f[x/p]

is an assignment differing from the assignment

f

only

in what it assigns to

x

.

The question at this point is whether any one of Beverly Hills, Los Feliz, or Silver Lake can be assigned to

x

(by an assignment that will otherwise be just like

f

) in such a way as to make the open formula:

true in

M4

relative to the assignment in question.

There are three assignments to consider:

f

[

x

/

Beverly Hills

]

assigns Beverly Hills to

x

and otherwise remains like

f

.

is

not true

in

M4

relative to

f

[

x

/

Beverly Hills

]

.

f

[

x

/

Los Feliz

]

assigns Los Feliz to

x

and otherwise remains like

f

.

is

not true

in

M4

relative to

f

[

x

/

Los Feliz

]

.

The reason being that the ordered pair < Silver Lake, Beverly Hills > is not in the extension of

F

in

M4

.

f

[

x

/

Silver Lake

]

assigns Silver Lake to

x

and otherwise remains like

f

.

is

not true

in M4 relative to

f

[

x

/

Silver Lake

]

.

The reason being that the ordered pair < Silver Lake, Silver Lake > is not in the extension of

F

in

M4

.

We conclude that the existentially quantified formula is

not true

in

M4

relative to the original assignment

f

.

1.4. From

Truth Relative to an Assignment

to

Truth

The procedure we have just outlined helps us to evaluate an existentially quantified formula in a model

M

relative to an assignment

f

.

But we will often be interested whether a closed formula is

true in a model

M

as opposed to whether the formula is merely

true in M relative to an assignment

f

.

when we discussed the question of whether is true in

M4

relative to assignment

f

for

M4

, we did not have to rely on information concerning what

f

assigns to

x --

or to any other variable!

In fact, a little thought reveals that, for the very same reason that the formula is true in

M4

with respect to

f ,

the formula will be true in

M4

with respect to

any other assignment

g

for M.

Quite generally, then,

1.5 Formal Definitions

The time has come for a formal statement of the semantics for the language of Predicate Logic.

A

model

M

for the language of Predicate Logic is an ordered pair <

D

,

I

>, where:

D

is a set of objects, and

I

is an interpretation function, which maps:

> every constant of the language into a member of

D

, and

> every

n

-place predicate into a set of n -tuples of objects in

D

.

A 2-tuple is an ordered pair, <

p

,

q

>, of objects

p

and

q

, a 3-tuple is an ordered triple, <

p

,

q

,

r

> of objects

p

,

q

, and

r

. Etc.

An

assignment

f

for a model

M

is a function from variables of the Language of Predicate Logic to members of

D

.

A formula is

true in a model

M

relative to an assignment

f

for

M

if, and only if:

A formula of Predicate Logic is

true in a model

M

if, and only if, is true in

M

relative to every assignment of values to variables for

M

.

We can illustrate the preceding definitions by means of an example.

Example 6

Consider a model

M6

based on the following diagram:

p1

p3

p2

p4

Strictly speaking,

M6

is an

ordered pair

<

D

,

I

>, where:

D

= {

p1

,

p2

,

p3

,

p4

}, and

I

is an

interpretation function

, which maps:

I

(

a

) =

p1

,

I

(

b

) =

p2

, . . .

I

(

R

) = {<

p1

,

p3

>, <

p3

,

p1

>, <

p2

,

p1

>, <

p4

,

p1

>, <

p4, p4

>},

Consider two different assignments for

M6

:

f1

is an assignment on which:

. . . x y z x' y' z' . . .

. . . p1 p2 p3 p1 p1 p4 . . .

f2

is an assignment on which:

. . . x y z x' y' z' . . .

. . . p3 p2 p4 p4 p2 p2 . . .

Let us now illustrate the definitions by evaluating the truth of different formulas in

M6

relative to each assignment:

is

true

in

M6

relative to

f1

:

Since

p1

is enclosed by a square,

p1

lies in the extension of the predicate

G1

in

M6

.

is

not

true

in

M6

relative to

f2

:

Since

p3

is not enclosed by a square,

p3

does not lie in the extension of the predicate

G1

in

M6

.

Some more examples:

is

true

in

M6

relative to

f1

:

The denotation of

y

in

M6

relative to

f1

is

p2

and the denotation of

x

in

M6

relative to

f1

is

p1

.

Since an arrow points from

p2

to

p1

, the ordered pair <

p2

,

p1

> lies in the extension of the two-place predicate

R2

in

M6

.

is

not

true

in

M6

relative to

f2

:

The denotation of

y

in

M6

relative to

f2

is

p2

and the denotation of

x

in

M6

relative to

f2

is

p3

.

Since no arrow points from

p2

to

p3

, the ordered pair <

p2

,

p3

> does not lie in the extension of the two-place predicate

R2

in

M6

.

is

true

in

M6

relative to

f1

:

The denotation of

x

in

M6

relative to

f1

is

p1

and the denotation of

y

in

M6

relative to

f1

is

p2

.

Since no arrow points from

p1

to

p2

in the diagram, we know that

Rxy

is

not true

in

M6

relative to

f1

.

So, since the antecedent of the conditional is not true in

M6

relative to

f1

, we conclude that the conditional itself is

true

in

M6

relative to

f1

.

is

true

in

M6

relative to

f2

:

The denotation of

x

in

M6

relative to

f2

is

p3

and the denotation of

y

in

M6

relative to

f2

is

p2

.

Since no arrow points from

p3

to

p2

in the diagram, we know that

Rxy

is

not true

in

M6

relative to

f2

.

So, since the antecedent of the conditional is not true in

M6

relative to

f2

, we conclude that the conditional itself is

true

in

M6

relative to

f2

.

is

true

in

M6

relative to

f1

:

The denotation of

x

in

M6

relative to

f1

is

p1

.

We need to check whether some value can be assigned to

y

without making any other change in

f1

in such a way that

Ryx

comes out true in

M6

relative to the new assignment.

That is, we need to check whether there is some

p

in

D

such that

Ryx

is true in

M6

relative to

f1

[

y

/

p

].

Now, since an arrow points from

p3

to

p1

, we need not look further than

p3

.

Since

Ryx

is

true

in

M6

relative to

f1

[

y

/

p3

], we conclude that is

true

in

M6

relative to

f1

.

is

not true

in

M6

relative to

f2

:

We need to check whether some value can be assigned to

y

without making any other change in

f2

in such a way that

Ryx

comes out true in

M6

relative to the new assignment.

That is, we need to check whether there is some

p

in

D

such that

Ryx

is true in

M6

relative to

f2

[

y

/

p

].

Now, since no arrow points from any node in the domain to

p3

, there is no such point

p

in the domain of

M6

.

Therefore, we conclude that is

not true

in

M6

relative to

f2

.

is

true

in

M6

relative to

f1

:

We need to check whether comes out true no matter what value one assigns to ‘

x

’ without making any other change in

f1

.

That is, we need to check whether for every

p

in the domain, is true in

M6

relative to

f1

[

x

/

p

].

We need to consider four different assignments:

1. Consider the assignment

f1

[

x

/

p1

]:

Rxx

is

not true

in

M6

relative to

f1

[

x

/

p1

] because no arrow points from

p1

to

p1

.

So, the conditional is

true

in

M6

relative to

f1

[

x

/

p1

].

2. Consider the assignment

f1

[

x

/

p2

]:

Rxx

is

not true

in

M6

relative to

f1

[

x

/

p2

] because no arrow points from

p2

to

p2

.

So, the conditional is

true

in

M6

relative to

f1

[

x

/

p2

].

3. Consider the assignment

f1

[

x

/

p3

]:

Rxx

is

not true

in

M6

relative to

f1

[

x

/

p3

] because no arrow points from

p3

to

p3

.

So, the conditional is

true

in

M6

relative to

f1

[

x

/

p3

].

4. Consider the assignment

f1

[

x

/

p4

]:

Rxx

is

true

in

M6

relative to

f1

[

x

/

p4

] because an arrow points from

p4

to

p4

.

However,

Fx

is

also true

in

M6

relative to

f1

[

x

/

p4

] because

p4

is enclosed by a circle.

So, the conditional is

true

in

M6

relative to

f1

[

x

/

p4

].

Now, since is true in

M6

relative to every assignment just like

f1

except possibly for the value assigned to the variable

x

, we conclude that is

true

in

M6

relative to

f1

.

is

true

in

M6

relative to

f2

:

Notice that the justification for this claim is completely parallel to the justification given in the previous example.

is

true

in M6 relative to every assignment for

M6

.

A little reflection on the preceding two points shows that the justification can be generalized to cover

every

assignment, and so we have that the closed formula is true in

M6

relative to every assignment for

M6

.

is

true

in

M6

.

By definition, a closed formula like is true in

M6

if, and only if, it is true relative to every assignment for

M6.

and Validity

We are now in a position to define

a series

of important concepts for Predicate

Logic.

A

sentence

of the language of Predicate Logic is a

logical truth

if, and only if, is true in every model.

Two

sentences

and of the language of Predicate Logic are

logically equivalent

if, and only if, and are true in exactly the same models.

A

set of sentences

of the language of Predicate Logic is

consistent

if, and only if, there is a model in which all of them are true.

An

argument

formulated in the language of Predicate Logic is

valid

if, and only if, every model in which the premises are true is one in which the conclusion is true as well.

We now know what it is for a sentence to be a

logical truth

, namely, to be true in

all models

.

But how can one show that a given sentence

is

, or

is

not

, a logical truth?

In the case of

Propositional Logic

, we managed to specify an

algorithm

, which enabled us to determine whether a sentence of the language is or not a logical truth in a

finite

number of steps.

We needed only to construct a truth table for the sentence and check whether or not the sentence comes out true in each of the rows of the table.

One reason the method worked well for us is because there were only

finitely many

different kinds of

assignments

we needed to check in order to convince us that a sentence of

Propositional Logic

, say, was a tautology.

In Predicate Logic, however, the situation is more complicated.

Since there is

no limit

to how many objects we can have in a domain of discourse, there are

infinitely many domains of discourse

we can consider. As a consequence, there is an

infinite number of models

that are relevant for the question of whether a sentence of

Predicate Logic

is a logical truth.

Since there are

infinitely many models

one can devise for the language of Predicate Logic, there is

no hope

we can survey them all in a

finite number of steps

in order to come to a conclusive answer to the question of whether a given sentence is a logical truth.

So, proving that there is

no model

in which the sentence fails to be true is generally a rather involved task.

A simpler and more elegant method will be introduced in the next unit, when we extend the

deductive systems

we developed for Propositional Logic to the case of Predicate Logic.

It is a different matter to establish the negative claim, for example, that a sentence is

not

a

logical truth

.

If a sentence is not a logical truth, then all we need to do is to supply a single model

M

in which the sentence is

not true

.

Likewise for the claim that two sentences are

not

logically equivalent

, and, crucially, the claim that a given argument is

not

valid

.

To show that a sentence is not logically equivalent to a sentence , we need only supply a single model in which one is true while the other is false.

To show that a given argument is not valid, we need only supply a model in which the premises are true and the conclusion is false.

Consider the sentence:

This sentence is

not

a

logical truth

.

We may reason as follows. Since the sentence is a conditional, to make it false in a model

M

, we need the model

M

to make the antecedent true and the consequent false.

To keep matters simple, we may want to keep the number of objects in the domain at a

minimum

. However, notice that we need more than one:

If the

only

object in the domain,

p

, is the denotation of

a

in the model and <

p

,

p

> is in the extension of

R

in the model (making the antecedent true), then the consequent will

trivially be true

in the model.

Consider a model

M7

described by the following diagram:

p1

p2

To check that

M7

is a counterexample to the claim that

is true in all models, we need only verify that there is an assignment

f

for

M7

such that is true in M7 relative to

f

even though is not true in M7 relative to

f

:

Fix an assignment

f

for

M7

:

1. is

true

in

M7

relative to

f

:

Since the denotation of

a

in

M7

is

p1

, and the ordered pair <

p1

,

p1

> is in the extension of the predicate

R

in

M7

, is true in

M7

relative to

f

.

2. is

not true

in M7 relative to f :

We need to check whether is true in

M7

relative to every assignment

f

[

x

/

p

], where

p

is a member of the domain.

But now, consider

f

[

x

/

p2

] :

Since the ordered pair <

p1

,

p2

> is not in the extension of

R

in

M7

, we have that is not true in

M7

relative to

f

[

x

/

p2

].

So, is

not true

in

M7

relative to every assignment just like

f

except perhaps for the value it assigns to

x

.

It follows that the formula is

not true

in

M7

relative to

f

.

3. is

not true

in M7 relative to f :

This is a straightforward consequence of 1 and 2.

So, since is

not

true in

M7

relative to

every

assignment for

M7

, we conclude:

is

not true

in M7 .

Since is

not

true in

all

models, is

not

a logical truth.

Consider the sentence and the sentence .

These two sentences are

not

logically equivalent.

We may reason as follows. Not every model in which the second sentence is true is a model in which the first sentence is true.

To make this point, we need a model

M

in which is

true

and

is nevertheless

false

.

Consider a model

M8

described by the following diagram:

p1

p2

Example 2.

F

is interpreted by

M8

to apply to members of the set {

p in D

:

p is enclosed by a circle

}.

G

is interpreted by

M8

to apply to members of the set {

p in D

:

p is enclosed by a square

} .

To check that

M8

is a counterexample to the claim that the two sentences and are logically equivalent,

we need to verify that is

true

in M8 even though

is

not true

in M8 .

1. is

true

in

M8

Fix an assignment

f

for

M8

. We need to show that the conjunction

is true in

M8

relative to

f

:

is

true

in

M8

relative to

f

.

This is because

Fx

is true in

M8

relative to

f

[

x

/

p1

] since

p1

is in the extension of

F

in

M8

.

is

true

in

M8

relativeto

f

.

This is because

Gx

is true in

M8

relative to

f

[

x

/

p2

] since

p2

is in the extension of

G

in

M8

.

So, the conjunction is

true

in

M8

relative to

f

.

But a similar reasoning applies to any other assignment for

M8

.

Therefore, is

true

in

M8

relative to all assignments for

M8

, which means that is

true

in

M8

.

2. is

not true

in

M8

.

Fix an assignment

f

for

M8

. We now need to show that the existentially quantified formula is

not true

in

M8

relative to

f

.

The reason for this is that the conjunction

is not true in

M8

relative to any assignment differing from

f

at most in what it assigns to the variable

x

.

Since there are only two objects in the domain, we need only consider two cases:

Consider the assignment

f

[

x

/

p1

].

Fx

is

true

in

M8

relative to

f

[

x

/

p1

] but

Gx

is

not true

in

M8

relative to

f

[

x

/

p1

].

So, the conjunction is

not true

in

M8

relative to

f

[

x

/

p1

].

Consider the assignment

f

[

x

/

p2

].

Fx

is

not true

in

M8

relative to

f

[

x

/

p2

] even though

Gx

is

true

in

M8

relative to

f

[

x

/

p2

].

So, the conjunction

is

not true

in

M8

relative to

f

[

x

/

p2

].

So, is

not true

in

M8

relative to

f

, and more generally, it is

not

true in

M8

relative to

all

assignments for

M8

.

We conclude that is

not true

in

M8

.

Example 3

Consider the following argument in the language of Predicate Logic:

1.

2.

3.

Think of the premise as the translation of the English sentence ‘

someone likes someone

’ relative to a suitable dictionary,

and think of the sentences and , respectively, as the translations of the English sentences ‘

no one likes anyone or everyone likes someone

’, on the one hand,

and ‘

someone is liked by everyone

’, on the other.

So the English argument would take us from ‘someone likes someone’ and ‘no one likes anyone or everyone likes someone’ to ‘someone is liked by everyone’.

We need to provide a model

M

such that:

(i) the premise is

true

in

M

, and

(ii) the premise is

true

in

M

,

and, nevertheless,

(iii) the conclusion is

not true

in

M

.

Consider a model

M9

described by the following diagram:

p1

p2

We now verify that this is a model in which both premises are

true

and the conclusion is

false

.

1. is

true

in

M9

.

Fix an assignment

f

for

M9

. We need to check that is

true

in

M9

relative to

f

.

The intuitive reason for this is that there are two points in the domain, e.g.,

p1

and

p2

, whose ordered pair, <

p1

,

p2

>, is in the extension of

R

in

M9

.

More formally, is

true

in

M9

relative to

f

[

x

/

p1

]. This is because

Rxy

is true in

M9

relative to

f

[

x

/

p1

][

y

/

p2

] .

We can conclude that is

true

in

M9

relative to

f

.

2. is

true

in

M9

.

Fix an assignment

f

for

M9

. Since the formula is a disjunction, it will be enough to show that one of the disjuncts,

is

true

in

M9

relative to

f

.

Intuitively, the reason for this is that an arrow points from every object in the domain to some other object.

More formally, we need to see that is true in

M9

relative to every assignment of the form

f

[

x

/

p

] where

p

is a member of the domain.

First consider the assignment

f

[

x

/

p1

]:

We need to check that

Rxy

is true in

M9

relative to some assignment

f

[

x

/

p1

][

y

/

q

] for some member of the domain

q

.

But now consider

f

[

x

/

p1

][

y

/

p2

]. Since <

p1

,

p2

> is in the extension of

R

in

M9

, we conclude that the formula

Rxy

is true in

M9

relative to

f

[

x

/

p1

][

y

/

p2

].

So, is

true

in

M9

relative to

f

[

x

/

p1

].

Consider now the assignment

f

[

x

/

p2

]:

We now check that

Rxy

is true in

M9

relative to some assignment

f

[

x

/

p2

][

y

/

q

] for some member of the domain

q

.

But now consider

f

[

x

/

p2

][

y

/

p1

]. Since <

p2

,

p1

> is in the extension of

R

in

M9

, we conclude that the formula

Rxy

is

true

in

M9

relative to

f

[

x

/

p2

][

y

/

p1

].

So, is

true

in

M9

relative to

f

[

x

/

p2

].

This means that is

true

in

M9

relative to

f

[

x

/

p1

] and

true

in

M9

relative to

f

[

x

/

p2

].

And since

p1

and

p2

are the only objects in the domain, is

true

in

M9

relative to

f

.

It follows that the disjunction is

true

in

M9

relative to

f

.

Since the reasoning generalizes to any assignment for

M9

, we conclude that is

true

in

M9

relative to

all

assignments for

M9

.

So, finally, we are in a position to conclude that the disjunction is

true

in

M9

.

3. is

not true

in

M9

.

Fix an assignment

f

for

M9

. We show that the conclusion is

not true

in

M9

relative to

f

.

The intuitive reason for this is that no point in the domain is such that an arrow points from every other object to it.

More formally, we need to check that is

not true

relative to any assignment

f

[

y

/

p

] where

p

is a member of the domain.

Consider the assignment

f

[

y

/

p1

]:

We check that

Rxy

is

not true

in

M9

relative to every assignment

f

[

y

/

p1

][

x

/

q

] where

q

is a member of the domain.

But let

q

be

p1

.

Since <

p1

,

p1

> is

not

in the extension of

R

in

M9

, we conclude that the formula

Rxy

is

not true

in

M9

relative to

f

[

y

/

p1

][

x

/

p1

].

So, is

not true

in

M9

relative to

f

[

y

/

p1

].

Consider now the assignment

f

[

y

/

p2

]:

We check that

Rxy

is

not true

in

M9

relative to every assignment

f

[

y

/

p2

][

x

/

q

] where

q

is a member of the domain.

But let

q

be

p2

.

Since <

p2

,

p2

> is

not

in the extension of

R

in

M9

, we conclude that the formula

Rxy

is

not true

in

M9

relative to

f

[

y

/

p2

][

x

/

p2

] .

So, is

not true

in

M9

relative to

f

[

y

/

p2

].

It follows that is

not true

in

M9

relative to

f

.

Therefore, is

not

true in

M9

relative to

all

assignments for

M9

, and, therefore, is

not true

in

M9

.

This completes the justification of the claim that there is a model in which the two premises are

true

and the conclusion is

false

. It follows that the original argument is

invalid

.

Defining a Model (

M1)

D=

A

:

B

:

C

:

For example,

M1

might specify a set of buildings as the

extension

of each predicate as follows:

What does this mean?

A

is interpreted by

M1

to apply to the members of the set

B

is interpreted by

M1

to apply to the members of the set

C

is interpreted by

M1

to apply to the members of the set

M1

may perhaps specify the bank as the

denotation

of the constant

a

and the factory as the

denotation

of the constant

b

.

( )

a

:

b

:

Evaluating With Respect to

M1

M1

is a member of the set .

is

a member of the set .

Some

building in the domain is such that

the formula that results

when we drop the initial existential quantifier and replace every free occurrence of the variable

x

with an occurrence of the constant denoting that building

is true in

M1

.

1

0

We aren't done yet. We still need our model to specify a denotation for the two constants that appear in the argument:

a

and

b

.

is true in

M1.

{ , }

{ , }

{ }

{ }

{ , }

{ }

{ }

D=

A

:

B

:

C

:

a

:

b

:

{ , }

{ , }

{ }

{ }

M1

D=

A

:

B

:

C

:

a

:

b

:

{ , }

{ , }

{ }

{ }

{ , }

{ }

Ba

is true in

M1

if and only if

Aa

is true in

M1

if and only if

M1

D=

A

:

B

:

C

:

a

:

b

:

{ , }

{ , }

{ }

{ }

M1

D=

A

:

B

:

C

:

a

:

b

:

{ , }

{ , }

{ }

{ }

{ }

{ }

M1

D=

A

:

B

:

C

:

a

:

b

:

{ , }

{ , }

{ }

{ }

We might also use a diagram in order to provide a model for the language of Predicate Logic.

{ , }

A

is interpreted by the model to apply to the members of the set

Thus, the diagram tells us:

{ , }

{ , }

{ }

{ }

We can now evaluate the premises of the first argument

almost

exactly as before, except this time with the aid of the diagram.

The conclusion requires that we check whether there is some thing in the domain of the model which is enclosed by

both

a

square

and a

triangle

, but

not

by a

circle

. Since the diagram tells us that there is

no such object

in the domain, we conclude that this sentence is

false

in the model.

Very informally:

Since the object denoted by

a

( ) is enclosed by both a circle and the square, we see that the first premise is again true in this model.

The object denoted by

b

( ) is not enclosed by a triangle, so the second premise is again true in this model.

is a member of the set .

{ }

Cb

is true in

M1

if and only if

of objects

p

and

q

is in the extension of

F

in a model

M

is to interpret the two-place predicate

F

as applying to

p

and

q

, in that order.

(1)

(2)

(3)

We can, very roughly at this point, evaluate each of the premises of the argument we specified at the outset with respect to this sample model:

So, the first premise is

true

in

M1

.

Defining a Model (

M4)

{Los Feliz, Silver Lake}

D:

F

:

G

:

Evaluating With Respect to

M4

is true in

M1.

Cb

is true in

M1

if and only if

A model

M4

may, for example, let the

domain of discourse

be given by a set of neighborhoods in Los Angeles:

Beverly Hills, Los Feliz, and Silver Lake

{Beverly Hills, Los Feliz, Silver Lake}

a

: Silver Lake

b

: Los Feliz

the set of ordered pairs, <

p

,

q

>, of neighborhoods in the domain such that

p

is adjacent to

q.

Thus, < Los Feliz, Silver Lake > and < Silver Lake, Los Feliz > will be in the extension of F.

{< Los Feliz, Silver Lake >, < Silver Lake, Los Feliz >}

D

: {Beverly Hills, Los Feliz, Silver Lake}

a

: Silver Lake

b

: Los Feliz

F: {<Los Feliz, Silver Lake> , <Silver Lake, Los Feliz>}

G: {Los Feliz, Silver Lake}

(M4)

Again, the conclusion requires special attention.

D

: {Beverly Hills, Los Feliz, Silver Lake}

a

: Silver Lake

b

: Los Feliz

F: {<Los Feliz, Silver Lake> , <Silver Lake, Los Feliz>}

G: {Los Feliz, Silver Lake}

(M4)

So, the second premise is true in

M4

.

The extension of

B

is the set {Los Feliz, Silver Lake}, so Los Feliz is in the extension of

B

.

Bb

is true in

M4

if and only if Los Feliz is a member of the extension of

B

.

Since Silver Lake is adjacent to Los Feliz, the ordered pair <Silver Lake, Los Feliz> is indeed a member of the extension of

F.

Fab

is true in

M4

if and only if the ordered pair <Silver Lake, Los Feliz> is a member of the extension of

F.

D

: {Beverly Hills, Los Feliz, Silver Lake}

a

: Silver Lake

b

: Los Feliz

F: {<Los Feliz, Silver Lake> , <Silver Lake, Los Feliz>}

G: {Los Feliz, Silver Lake}

(M4)

c: Beverly Hills

*

the formula we obtain by dropping the initial existential quantifier

In this case, we need not look further than

b

, since:

Recall our premises!

So, the conclusion is true in

M4

.

with an occurrence of the constant designating that neigborhood

is true in

M4

.

b b

a a

c

c

is

true

in

M4

.

and replacing every free occurrence of

x

Another Example

(M5)

And now an

extension

for each predicate:

{<

p

,

q

> in

D

x

D

: an arrow points from

p

to

q

} is the same as

{<

p

1

,

p

2

>, <

p

3

,

p

3

>}

so the extension of 'F' is {<

p

1

,

p

2

>, <

p

3

,

p

3

>}.

A model

M5

may let the set of

points

shown in the diagram above

{

p

1

,

p

2

,

p

3

}

be the

domain

D

of discourse.

M1

D=

A

:

B

:

C

:

a

:

b

:

{ , }

{ , }

{ }

{ }

A

is interpreted by

M1

to apply to the members of the set

B

is interpreted by

M1

to apply to the members of the set

C

is interpreted by

M1

to apply to the members of the set

M1

specifies the bank as the

denotation

of the constant

a

and the factory as the

denotation

of the constant

b

.

{ , }

{ }

{ }

The

domain

of discourse of M1 is two buildings; the factory and the bank.

REMINDER

One difficulty with this question is that while

M1

is supposed to provide us with denotations for each constant, the model remains silent as to how to interpret a variable like

x

or

y

.

How should we evaluate an

open formula

like

in the model

M1

?

A

domain of discourse

,

A specification of a

denotation

for each constant in the language of Predicate Logic, and

A specification of an

extension

for each predicate of the language of Predicate Logic.

Unlike a constant, a variable does not denote an object in the domain, but it may temporarily stand for one. Think of a variable, if you like, as a

temporary label

for an object in the domain.

Thus, in order to be able to evaluate a formula like

with respect to M1 we need to be told which object in the domain is temporarily labeled by x and which object is being temporarily labeled by y.

{ , }

Eg.

Now,

we can say what we need more clearly:

{ , }

{ }

M1

D=

A

:

B

:

C

:

a

:

b

:

{ , }

{ , }

{ }

{ }

f1

is an assignment for

M1

which maps the variable

x

to , the variable

y

to , the variable

z

to , etc.

. . . x y z . . .

f2

is an assignment for

M1

which maps the variable

x

to , the variable

y

to , the variable

z

to , etc.

. . . x y z . . .

Likewise:

is true in

M1

relative to

f2

if, and only if,

Ax

is true

in

M1

relative to

f2

and

By

is true in

M1

relative to

f2

.

M1

D=

A

:

B

:

C

:

a

:

b

:

{ , }

{ , }

{ }

{ }

By

is true in

M1

relative to

f2

if, and only if,

(the bank) is in the extension of

B

in

M1

.

Ax

is true in

M1

relative to

f2

if, and only if,

(the factory) is in the extension of

A

in

M1

.

Ax

is true in

M1

relative to

f2

if, and only if, the factory is a member of the set .

{ , }

By

is true in

M1

relative to

f2

if, and only if,

the bank is a member of the set .

{ }

{ , }

{ }

Since

is

in , and

is

in , we

conclude that is

true

in

M1

relative to

f2

.

{ , }

{ }

Compare, for example, the following assignments:

For example, consider the evaluation of the following existentially quantified formula in

M1:

M1

D=

A

:

B

:

C

:

a

:

b

:

{ , }

{ , }

{ }

{ }

A

a

A

b

Ax

In what follows,

If

p

is an object in the domain of a model M and

f

is an assignment for M, we will write

f [x/p]

to name an assignment just like

f

except possibly for assigning the object

p

to

x

.

NOTATION

We can now state new truth conditions for :

D

: {Beverly Hills, Los Feliz, Silver Lake}

a

: Silver Lake

b

: Los Feliz

F: {<Los Feliz, Silver Lake> , <Silver Lake, Los Feliz>}

G: {Los Feliz, Silver Lake}

(M4)

So,

. . . x y z . . .

Beverly Hills Los Feliz Silver Lake

f:

. . . x y z . . .

Beverly Hills

Los Feliz Silver Lake

. . . x y z . . .

Los Feliz

Los Feliz Silver Lake

. . . x y z . . .

Silver Lake

Los Feliz Silver Lake

Notice that

A formula is

true in a model M

iff it is

true in M relative to

every

assignment f

for M.

The domain of discourse

D

of

M6

is the set of points {

p1

,

p2

,

p3

,

p4

}.

a

is interpreted by

M6

to denote

p1

.

b

is interpreted by

M6

to denote

p2

.

R

is interpreted by

M6

to apply to ordered pairs <

p

,

q

> in the set {<

p

,

q

>

in

D

x

D

:

an arrow points from p to q

}, i.e.:

{<

p1

,

p3

>, <

p3

,

p1

>, <

p2

,

p1

>, <

p4

,

p1

>, <

p4

,

p4

>}

F

is interpreted by

M6

to apply to the members of the set {

p in D

:

p is enclosed by a circle

} , i.e., {

p2

,

p4

}.

G

is interpreted by

M6

to apply to the members of the set {

p is in D

:

p is enclosed by a square

}, i.e., {

p1

}.

D: {

p1

,

p2

,

p3

,

p4

}

a

:

p1

b

:

p2

R

:

{<

p1

,

p3

>, <

p3

,

p1

>, <

p2

,

p1

>, <

p4

,

p1

>, <

p4

,

p4

>}

F

: {

p2

,

p4

}

G

: {

p1

}

(M6)

D: {

p1

,

p2

,

p3

,

p4

}

a

:

p1

b

:

p2

R

:

{<

p1

,

p3

>, <

p3

,

p1

>, <

p2

,

p1

>, <

p4

,

p1

>, <

p4

,

p4

>}

F

: {

p2

,

p4

}

G

: {

p1

}

(M6)

I

(

F

) = {

p2

,

p4

},

I

(

G

) = {

p1

}, . . .

{

p1

p3

p2

p4

The

denotation

of

x

in

M6

relative to

f1

is

p1

.

The

denotation

of

x

in

M6

relative to

f2

is

p3

.

Consider two different assignments for

M6

:

f1

is an assignment on which:

. . . x y z x' y' z' . . .

. . . p1 p2 p3 p1 p1 p4 . . .

f2

is an assignment on which:

. . . x y z x' y' z' . . .

. . . p3 p2 p4 p4 p2 p2 . . .

p1

p3

p2

p4

Consider two different assignments for

M6

:

f1

is an assignment on which:

. . . x y z x' y' z' . . .

. . . p1 p2 p3 p1 p1 p4 . . .

f2

is an assignment on which:

. . . x y z x' y' z' . . .

. . . p3 p2 p4 p4 p2 p2 . . .

p1

p3

p2

p4

Consider two different assignments for

M6

:

f1

is an assignment on which:

. . . x y z x' y' z' . . .

. . . p1 p2 p3 p1 p1 p4 . . .

f2

is an assignment on which:

. . . x y z x' y' z' . . .

. . . p3 p2 p4 p4 p2 p2 . . .

p1

p3

p2

p4

Consider two different assignments for

M6

:

f1

is an assignment on which:

. . . x y z x' y' z' . . .

. . . p1 p2 p3 p1 p1 p4 . . .

f2

is an assignment on which:

. . . x y z x' y' z' . . .

. . . p3 p2 p4 p4 p2 p2 . . .

p1

p3

p2

p4

The denotation of

x

in

M6

relative to

f2

is

p3

.

Consider two different assignments for

M6

:

f1

is an assignment on which:

. . . x y z x' y' z' . . .

. . . p1 p2 p3 p1 p1 p4 . . .

f2

is an assignment on which:

. . . x y z x' y' z' . . .

. . . p3 p2 p4 p4 p2 p2 . . .

p1

p3

p2

p4

Consider two different assignments for

M6

:

f1

is an assignment on which:

. . . x y z x' y' z' . . .

. . . p1 p2 p3 p1 p1 p4 . . .

f2

is an assignment on which:

. . . x y z x' y' z' . . .

. . . p3 p2 p4 p4 p2 p2 . . .

p1

p3

p2

p4

Logical Truth,

Logical Equivalence,

Consistency,

What follows is an illustration of the method for establishing negative claims such as the claim that a given sentence is

not a logical truth

, the claim that two sentences are

not logically equivalent

, or, finally, the claim that an argument is

not valid

in Predicate Logic.

Example 1.

We need to specify a model M such that (i) is true in

M

, and (ii) is not true in

M

.

( )

M7

D: {

p1, p2

}

R: {<

p1, p1

>, <

p2, p1

>}

a

:

p1

M8

D: {

p1, p2

}

F: {

p1

}

G: {

p2

}

or

But how can we show that the argument couched in the language of Predicate Logic is itself

invalid

?

It seems clear that the latter is

not

a logical consequence of the former sentence in English.

M9

D: {

p1, p2

}

R: {<

p1, p2> , <p2,p1>

}

M9

D: {

p1, p2

}

R: {<

p1, p2> , <p2,p1>

}

M9

D: {

p1, p2

}

R: {<

p1, p2> , <p2,p1>

}

M9

D: {

p1, p2

}

R: {<

p1, p2> , <p2,p1>

}

M9

D: {

p1, p2

}

R: {<

p1, p2> , <p2,p1>

}

p

1

p

2

p

3

(M5)

M5

may identify one of the points,

p

1

, as the

denotation

of the constant ‘

a

’ and

p

2

as the

denotation

of the constant ‘

b

’.

M5

may specify the set of points in the diagram, which belong to

{

p is in D: p is enclosed by a square

}

as the extension of the monadic predicate ‘

G

’.

i.e. {

p

2

,

p

3

}

M5

may specify the set of ordered pairs of points in the diagram

{<

p

,

q

> in

D

x

D

: an arrow points from

p

to

q

}

as the extension of the two-place predicate '

F

'.

Note:

D

x

D

is just the set of all

ordered pairs

of objects in

D

D

x

D

(1) is true in

M5

if and only if the ordered pair <

p

1,

p

2 > is a member of the extension of

F

.

(2) is true in

M5

if and only if

p

2 is a member of the extension of

G

, which is the set {

p is in D

:

p is enclosed by a square

}.

Since an arrow points from

p

1 to

p

2 in the diagram, the ordered pair <

p

1,

p

2 > is itself a member of {<

p

,

q

>

in D

x

D

:

an arrow points from p to q

}.

Since

p

2 is indeed enclosed by a square in the diagram, the point is a member of the extension of

G

.

So the premises and the conclusion are all true in

M5

.

is

true

in

M4

.

In this case, we need not look further than b again, since:

As as a first approximation, we may take a sentence like (3) to be true just in case there is a point in the diagram designated by some constant such that the formula that results when we

drop the initial existential quantifier

and

replace

every

occurrence of

x

with an

occurrence of that constant

is true in

M5

.

Let us assume that each point in the diagram is, in

M5

, the denotation of a constant of the language. In particular, assume that

p

3 is the

denotation

in

M5

of the constant

c

.

The Search for Counterexample Method