Class Notes
(807,176)

Canada
(492,651)

University of Toronto St. George
(42,781)

Philosophy
(1,512)

PHL245H1
(18)

Victoria Wohl
(1)

Lecture

# Unit 7 2011.pdf

Unlock Document

University of Toronto St. George

Philosophy

PHL245H1

Victoria Wohl

Summer

Description

UNIT 7
INTERPRETATIONS AND MODELS: SEMANTICS FOR PREDICATE LOGIC
7.1 Interpretations
In sentential logic, we can give meaning to symbolic sentences through truth-value analysis. If we know what
makes it true, then we know what it means! By taking the truth-value of an atomic component as its semantic
value, we can determine the truth-value of any complex sentence from the truth-values of its components. The
truth-table provides the truth-value of the sentence on every possible truth-value assignment for a sentence.
Thus, given any particular truth-value assignment, we can determine the truth-value of the sentence. Some
sentences (tautologies) are true on any truth-value assignment. Other sentences (contradictions) are false on any
truth-value assignment. But most sentences were true on some truth-value assignments and false on others
(contingent sentences).
In predicate logic, we are not dealing merely with the truth-valuable relations between atomic sentences – rather
we are concerned with the relation of subsentential components. Truth-tables aren’t sufficient for this. We
need to consider whether predicates are true of the individual members of a potentially infinite universe. In
order to evaluate the truth-value of such sentences we have to consider different interpretations.
The abbreviation schemes that we used when symbolizing sentences can be thought of as interpretations. They
define:
The Universe
The Predicates
Individuals (name letters and operation letters)
Of course, each abbreviation or translation scheme is just one of countless possible interpretations. But, each
abbreviation scheme does tell us how to interpret the sentence.
An abbreviation scheme provides an interpretation for a symbolic sentence or set of symbolic sentences.
It provides an interpretation for each predicate within a non-empty universe.
The extension of the predicate is the set of members of the universe that the predicate picks out (that
satisfy the predicate).
Let’s look at this abbreviation scheme for a universe of natural numbers. I will use ‘natural numbers’ to
refer to the ‘counting numbers’ or positive integers beginning with 1:
U: {1,2,3 …} G : a is odd H : a is negative. L : a is less than b. a: 1
We could use this abbreviation scheme to interpret such sentences as:
x(Gx ~Hx) No odd numbers are negative.
~x(Gx L(xa)) No odd number is less than 1.
x(Gx yL(xy)) Every odd number is less than some number.
xyz(L(xy) L(yz) L(xz)) If one number is less then a second and the second is less
than a third, then the first is less than the third.
PHL 245 Unit 7: Interpretations and Models 1
Niko Scharer Extension and Meaning:
What does ‘dog’ mean?
One way to give the meaning of ‘dog’ is the intension or sense of the word (often the dictionary meaning):
A domesticated carnivorous mammal of the genus, Canis, related to foxes and wolves.
But this is probably not the way that you learned what it meant! Most people learn the meaning of words like
‘dog’ and ‘cat’ through ostensive definitions: having examples pointed out to you.
The extension of the word ‘dog’ is all of those things that you might point at when giving an ostensive
definition (all dogs!) That gives us another way of giving the meaning of a word: dog means…
…
The extension of the word dogs includes all of those types of things!
Indeed, if we want to know whether a dictionary definition is a good one, we can check if it captures the
meaning in the sense of the extension.
Chair: A piece of furniture used for sitting on.
Is this a good definition?
No. It is too broad. It picks out couches, benches and stools. The extension of the word
“chair” does not include such things.
Chair: A piece of furniture used for sitting on, normally for seating one person, with a back, legs
and a seat.
Is this a good definition?
No. Now it is too narrow. The extension of the word “chair” includes things that don’t have
legs – hanging chairs, some rocking chairs, etc.
The relation between the extension of a word and the ‘intension’ or sense of the word (what the dictionary
definition is trying to capture) is more complicated than you might think, and philosophically fascinating!
Philosophers such as Bertrand Russell, Hilary Putnam, Tyler Burge, Saul Kripke have written much about this
part of philosophy of language, as well as its relation to the mind and intentionality.
For us, it is enough to recognize that extension is one central way of understanding meaning. It is an important
part of a semantics for predicate logic.
PHL 245 Unit 7: Interpretations and Models 2
Niko Scharer Determining the Extension of a Predicate:
In order to determine the extension of a predicate, we must consider the interpretation and ask ourselves, on that
interpretation, which members of the universe is the predicate true of – which members of the universe satisfy
the predicate?
Extension of a one-place predicate: the extension of a monadic predicate is the subset of members of the
universe that satisfy the predicate. In other words, it is the set of those members of the universe
that the predicate is true of.
Extension of a two-place predicate: the extension of a dyadic predicate is the set of ordered pairs of
members of the universe that satisfy the predicate. In other words, it is the set of ordered pairs
that the predicate is true of.
Extension of a three-place predicate: the extension of a triadic predicate is the set of ordered triplets of
members of the universe that satisfy the predicate. In other words, it is the set of ordered triplets
that the predicate is true of.
U: natural numbers {1,2,3 …} G : a is odd H : a is negative. L : a is less than b.
a: 1
According to the above interpretation, what is the extension of the predicates?
The extension of G: the extension is the set of odd members of U. On this interpretation, these are the
members of U (natural numbers) that satisfy the predicate, G, ‘is odd’. {1,3,5,7…}
The extension of H: the extension is the set of negative natural numbers. Theses are the members of U
that satisfy the predicate, H, ‘is negative’. On this interpretation, the extension of H is empty since no
natural number is negative and thus satisfies this predicate. { } or
The extension of L: the extension is the set of ordered pairs of members of U such that the first of the
ordered pair is less than the second of the ordered pair. So (1,2), (1,3), (2,3) and (5,100) will all be in
the extension of L, but (2,1), (1,1) and (100,5) will not be. This set is an infinite set.
Determining the truth-value of a sentence:
Whether a sentence is true or false depends on how we interpret it – it may be true on some interpretations and
false on others (just like a sentential logic sentence might be true on some truth-value assignments and false on
others).
Consider this sentence: xyL(xy) Here are two interpretations:
U: people. L : a loans money to b.
2
U: integers. L : a is less than b.
According to the first interpretation, the sentence says: Everybody loans money to somebody. That is false!
According to the second interpretation, the sentence says: Every integer is less than some integer. That’s true!
In order to determine truth-value, we need an interpretation!
PHL 245 Unit 7: Interpretations and Models 3
Niko Scharer 7.2 Determining the Truth-Value of Sentences On An Interpretation
An abbreviation or translation scheme provides an interpretation. It defines:
the universe (must not be empty)
the predicates
the individual constants (zero place operation letters)
truth-values of sentential atomic sentences (zero place predicates)
monadic, dyadic or higher-place operations.
Determining the Truth-Value of Sentences without Quantifiers:
i. Use the interpretation to determine the truth-value of each atomic formula.
ii. Proceed to determine the truth-value of the sentence on the basis of your knowledge of the connectives,
just like we did in sentential logic (truth-tables).
What is the truth value of this sentence according to the following interpretations?
(Fa Fb) (L(ca) L(cb))
U: unrestricted F : a is a building. L : a is taller than b.
a : The Jackman Humanities Building b : The Statue of Liberty. c : The CN Tower
If either The Jackman Humanities Building or The Statue of Liberty is a building then the CN tower is
taller than The Jackman Humanities Building or The CN Tower is taller than The Statue of Liberty.
The sentence is true on this interpretation.
U: integers F : a is prime. L : a is less than b.
a : 3 b : -4 c : -1
If either 3 or -4 is prime then either -1 is less than 3 or -1 is less than -4.
This interpretation makes this sentence true.
U: integers F : a is prime. L : a is larger than b.
a : 4 b : 4 c : 4
If either 4 or 4 is prime then 4 is larger than 4 or 4 is larger than 4.
This interpretation makes this sentence true.
The interpretations on which the sentence is true have something in common: they make the consequent true by
ensuring that (ca) or (cb) is within the extension of L or they make the antecedent false by ensuring that neither
‘a’ nor ‘b’ is within the extension of F.
PHL 245 Unit 7: Interpretations and Models
Niko Scharer 4 But the same sentence will also be false on some interpretations:
(Fa Fb) (L(ca) L(cb))
1 2
U: unrestricted F : a is a building. L : a is shorter than b.
0 0 0
a : The Jackman Humanities Building b : The Statue of Liberty. c : The CN Tower
This sentence is false: “If either The Jackman Humanities Building or The Statue of Liberty is a building
then The CN Tower is shorter than The Jackman Humanities Building or The Statue of Liberty.”
1 2
U: integers F : a is an integer. L : a is greater than b.
a : 2 b : 2 c : 2
This sentence is false: “If either 2 or 2 is an integer then 2 is greater than 2 or 2 is greater than 2.
The interpretations on which the sentence is false have something in common: they make the antecedent true
by ensuring that either a or b is within the extension of F and they make the consequent false by ensuring that
neither (ca) nor (cb) is within the extension of L.
Sentences with Quantifiers:
Determining the truth-value of sentences with quantifiers is not much more difficult. The interpretation defines
the universe, predicates, individual constants (also operation letters.) Now we use both the logical connectives
and the quantifiers to determine the truth-value of the sentence on that interpretation.
α A universally quantified sentence is true if and only if it is true for every single
member of the universe, or for every single ordered pair or triplet (in the case of two
and three place predicates).
α An existentially quantified sentence is true if and only if it is true for at least one
member of the universe, or for at least on ordered pair or triplet (in the case of two and
three place predicates).
i. Use the interpretation to determine the truth-value of any unquantified atomic formulas.
ii. Use the interpretation, the results of (i), and your knowledge of the connectives to determine the truth-
value or partial truth-value of any quantified sentential components.
iii. Use the interpretation, the results of (i) and the results of (ii) to determine the truth-value of the sentence.
PHL 245 Unit 7: Interpretations and Models 5
Niko Scharer 7.2 EG1 On the interpretations below, is the following true or false?
a) ~Fa x(Fx G(xa))
Universe: positive integers F : a is a multiple of 4.
a : 2 G : a is divisible by b
The first conjunct can be interpreted: 2 is not a multiple of 4.
The second conjunct can be interpreted: Every multiple of 4 is divisible by 2.
Since both conjuncts are true, the sentence is true on this interpretation.
b) ~Fa x(Fx G(ax))
Universe: people F : a is Canadian
a : Bill Gates G : a is richer than b
c) ~Fa x(Fx G(ax))
1
Universe: positive integers F : a is odd
0 2
a : 2 G : a is smaller than b
7.2 EG2 On the interpretations below, is the following true or false?
a) x(Fx y(G(xy) H(yx))
Universe: People F1: a is a politician
H2: a believes b G2: a makes a promise to b
Every politician is such that if he or she makes a promise to somebody, then that person
believes the politician.
OR … Everybody believes every politician that makes them a promise.
This sentence is false
b) x(Fx y(G(xy) H(yx))
Universe: Positive Integers F : a is even
H : a is less than or equal to b G : a is a factor of b
c) x(Fx y(G(xy) H(yx))
Universe: positive integers F : a is purple
2 2
G : a is less than b H : a is a multiple of b
PHL 245 Unit 7: Interpretations and Models
Niko Scharer 6 7.3 Interpretations and Properties of Sentences and Arguments
Tautologies, Contradictions and Contingent Sentences:
As we just saw, the truth-value of a symbolic sentence often cannot be determined without taking
interpretations into consideration. Sentences, such as (Fa Fb) (L(ca) L(cb)) or x(Fx y(G(xy)
H(yx)), are true on some interpretations and false on others.
In sentential logic, a sentence that was true on some truth-value assignments and false on others was a
contingent sentence (can be true or false.) These sentences can be true or false depending on the interpretation:
they are contingent!
Some sentences are true on any interpretation. There is no interpretation on which they are false – they are
always true. In sentential logic, a sentence that was true on any truth-value assignment (always true) was a
tautology or a theorem. Likewise, a sentence that is true on any interpretation is a tautology. No matter how
we interpret this sentence, it is true.
(Fa Fb) (~Fa Fb)
1
U: unrestricted. F : a is a building. a: The Jackman Humanities Building. b: the Statue
of Liberty
Either The Jackman Humanities Building or the Statue of Liberty is a building if and only if it’s the case
that if The Jackman Humanities Building is not a building then The Statue of Liberty is a building.
U: integers. F : a is prime. a: 3 b: 4
Either 3 or 4 is prime if and only if it’s the case that if 3 is not prime then 4 is prime.
Some quantified sentences are tautologies: true on every possible interpretation.
xyF(xy) xF(xx)
Universe: people F : a loves b.
If everybody loves everybody then everybody loves him/herself.
Universe: integers F : a is less than b
If every integer is less than all integers then every integer is less than itself.
Try to think up an interpretation that makes it false! If everything stands in the F relation to everything, then
everything must stand in that relation to itself. Even though it is clearly true, we can’t demonstrate it by giving
interpretations – we would have to show that there is no interpretation on which it is false by considering every
possible interpretation (an infinite set).
PHL 245 Unit 7: Interpretations and Models 7
Niko Scharer This is the situation for all tautologies… consider some of the theorems proved in Unit 6!
Consider the following interpretations for: x~Fx ~xFx
1
F : a is purple. Something is not purple if and only if not everything is purple.
1
F : a is a unicorn Something isn’t a unicorn if and only if not all things are unicorns.
F : a is made of matter Something isn’t made of matter if and only if not everything is made of matter.
On every possible interpretation, no matter what property F is, something exists that doesn’t have property F if
and only if not all things do have property F.
Consider the following interpretations for: xy(B(xy) ~B(yx)) ~xF(xx)
B : a is taller than b. If it is the case that if one thing is taller than another, the second is not taller than
itself, then nothing is taller than itself. .
B : a loves b. If it is the case that if one thing loves another, the second does not love the first,
then nothing loves itself.
On every possible interpretation, no matter what relation B is, if B is an asymmetric relation, then B is also
irreflexive.
Contradictions:
Some sentences are false on any interpretation. There is no interpretation on which they are true – they are
always false. In sentential logic, a sentence that was false on any truth-value assignment (always false) was a
contradiction or logical falsehood. Likewise, a sentence that is false on any interpretation is a contradiction.
No matter how we interpret this sentence, it is false.
Fa ~Fa
1
U: unrestricted. F : a is a building. a: The Jackman Humanities Building
The Jackman Humanities Building is a building if and only if it is not a building.
1
U: integers. F : a is prime. a: 3
3 is prime if and only if 3 is not prime.
PHL 245 Unit 7: Interpretations and Models 8
Niko Scharer Likewise, some quantified sentences are contradictions: false on every possible interpretation.
xyF(xy) xy~F(xy)
Universe: people F : a loves b.
2
Universe: integers F : a is smaller than b.
Try to think up an interpretation that makes it true! If everything stands in the F relation to something then it
can’t be the case that something fails to stand in the F relation to everything. Likewise, if something fails to
stand in the F relation to everything, it can’t be the case that everything stands in the F relation to something.
Likewise, a sentence such as: x(Fx Gx) x(Fx ~Gx) will be false no matter what interpretation is
given. After all, if everything with property F also has property G, then it can’t be true that something has
property F but not property G.
Even though the sentence is false on all interpretations, we can’t demonstrate it by giving interpretations – we
would have to show that there is no interpretation on which it is true by considering every possible
interpretation (an infinite set).
We cannot demonstrate that a sentence is a contradiction; however, a single interpretation can show that a
sentence is not a contradiction. Since a contradiction is false on every possible interpretation, a single
interpretation on which a sentence is true will prove that a sentence is not a contradiction.
Contingent Sentences:
Since tautologies are true on any interpretation and contradictions are false on any interpretation, we can’t prove
that the sentences are tautologies or contradictions by providing an interpretation. (We prove a sentence is a
tautology or a contradiction with a derivation.)
BUT, a single interpretation that makes a sentence true can prove that the sentence is NOT a contradiction
(since a contradiction is false for all interpretations) and a single interpretation that makes a sentence false can
prove that the sentence is NOT a tautology (since a tautology is true for all interpretations.)
We can prove a sentence is NOT a tautology by providing an interpretation that makes it false.
We can prove a sentence is NOT a contradiction by providing an interpretation that makes it true.
So, we can prove that a sentence is contingent by providing two interpretations: one that makes it true and one
that makes it false.
S: xy(Fx L(yx))
1 2
Universe: people F : a is female L : a is the parent of b. On this interpretation, S is True
Universe: people F : a is female L : a is the child of b. On this interpretation, S is False
1 2
Universe: positive integers F1: a is even. L :2a is smaller than b On this interpretation, S is True
Universe: positive integers F : a is odd. L : a is smaller than b. On this interpretation, S is False
PHL 245 Unit 7: Interpretations and Models 9
Niko Scharer Some Concepts for Predicate Logic:
Tautology: A sentence P is a tautology if and only if P is true on every interpretation.
Contradiction: A sentence P is a contradiction if and only if P is false on every
interpretation.
Contingent sentence: A sentence P is contingent if and only if P is neither a tautology
or a contradiction (thus it is true on some interpretations and false on some
interpretations).
Interpretations are to predicate logic what truth-value assignments are to sentential logic!
In determining whether a sentence of predicate logic is a tautology, a contradiction or contingent, instead of
considering every possible truth-value assignment, we need to consider every possible interpretation.
A finite set of interpretations cannot show that that a sentence is a tautology or a contradiction.
But we can use a single interpretation to prove that a sentence is not a tautology. One need only provide an
interpretation on which the sentence is false (a counterexample).
Likewise we can show that a sentence is not a contradiction by providing an interpretation on which the
sentence is true (a counterexample).
We can prove that a sentence in predicate logic is a contingent sentence. One need only provide two
interpretations – one on which the sentence is true and one on which the sentence is false. In doing this we are
proving that it is not a contradiction and not a tautology.
Validity and Tautological Implication
Since every valid argument can be transformed into a tautology in which the antecedent is a conjunction of the
premises and the consequent is the conclusion, valid arguments will be much like tautologies. No finite set of
interpretations can show that an argument is valid, but a single interpretation can show that it is invalid.
To show an argument is invalid, provide an interpretation on which all the premises are true and the conclusion
is false.
A single interpretation cannot show that a set of sentences tautologically implies another sentence, . But a
single interpretation can show that a set of sentences doesn’t tautologically imply a further sentence, . To
show this, provide an interpretation on which all the sentences of are true, but the further sentence, , is false.
Validity: An argument in predicate logic of is valid if and only if there is no
interpretation on which every premise is true and the conclusion is false. An argument
of is invalid if and only if the argument is not valid.
Tautological Implication: A set of sentences tautologically implies a sentence if
and only if there is no interpretation on which all the sentences in the set are true and
is false.
PHL 245 Unit 7: Interpretations and Models 10
Niko Scharer Consistency and Equivalency
As we learned in Sentential Logic, a set of sentences is consistent if it is possible for them to all be true. Thus,
we can also show that a set of sentences is consistent by providing an interpretation on which they are all true.
A set of sentences is consistent if and only if there is at least one interpretation on
which all the members of the set are true.
Two sentences are logically equivalent if and only if they have the same truth-value on every possible
interpretation. Thus, we cannot prove that two sentences are logically equivalent, but we can show that two
sentences are not equivalent by providing a single interpretation on which one is true and one is false.
Sentence and are logically equivalent if and only if there is no interpretation on which
and different truth-values. (They are logically equivalent if and only if and have the
same truth-value on every interpretation.)
7.4 Finite Models
Many of these properties of sentences or sets of sentences can be demonstrated with very small, finite models.
A model is just an example – one that you create to demonstrate a particular feature that you are interested in.
A finite model is an example that has a finite universe of discourse (rather than an infinite universe of
discourse) – often a very small finite universe with only a few individuals in it.
Here is a very small finite model, with exactly one thing in the universe.
It can show things such as:
Something is a circle and something is polka dotted.
All circles are polka dotted.
Something is a circle and is polka dotted.
No circles are striped.
Here is another small finite model, with two things in the universe.
It can show things such as:
Something is a circle and something is a triangle.
All triangles are striped.
No circles are striped, but some triangles are.
All circles are beside some triangle.
PHL 245 Unit 7: Interpretations and Models 11
Niko Scharer We can use simple finite models as interpretations – so we can use them to demonstrate that sentences (or sets
of sentences) have certain properties.
U Consider the finite model we looked at with one individual.
We could use it to prove that the following sentence is not a contradiction: xCx xHx
1 1
Universe: U {circle} C : a is a circle H : a is striped.
On this interpretation, the sentence is true, so it is not a contradiction.
We can also use it to prove that the sentence is not a tautology: xCx xHx
1 1
Universe: U {circle} C : a is a circle H : a is polka dotted.
On this interpretation, the sentence is false, so it is not a tautology.
But we cannot use this model to prove that the following argument is invalid: xCx. xHx. x(Cx Hx)
Since there is only one individual in the universe, if both premises are true, then the conclusion has to be
true as well!
Now consider the finite model with two individuals.
U We can use it to show that the argument is invalid:
xCx. xHx. x(Cx Hx)
Universe: U {circle, triangle}
1 1
C : a is a circle H : a is striped.
Something is a circle. Something is striped. But nothing is a striped circle.
We could also use it to show that the following sentence is contingent:
x(Cx y(Dy L(xy))
C : a is a circle D : a is striped. L : a is beside b.
All circles are beside a striped thing. On this interpretation, the sentence is true.
1 1 2
C : a is a circle D : a is polka dotted. L : a is beside b.
All circles are beside a polka dotted thing. On this interpretation, the sentence is false.
PHL 245 Unit 7: Interpretations and Models
Niko Scharer 12 Abstract Finite Models
We can also use a more abstract model to show the same things.
Instead of using a concrete diagram with properties we can see, we can leave the properties undefined, but
simply state whether or not the individuals in the universe have those properties.
A finite model provides an interpretation by taking a non-empty finite class of individuals as the universe. A
sub-class is any subset of the class (including the empty class and including the entire class).
Consider the simplest universe. U: {0} U is defined as a set that has one member: ‘0’
This is like the model with a single circle in it. This model has a universe with just one thing in

More
Less
Related notes for PHL245H1