Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Tutorial 8. Predicate Logic: Semantics

No description
by

USC Logic Web

on 22 December 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Tutorial 8. Predicate Logic: Semantics

So, we have that is
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
Full transcript