Transcript Introduction to Quantification

Language, Proof and
Logic
Introduction to Quantification
Chapter 9
9.1
Variables and atomic wffs
Variables --- a new type of basic terms, along with names/constants.
They can be seen as placeholders for names
Atomic wffs (well-formed formulas): Home(x), Taller(max,y),…
Tarski’s World understands the variables u through z;
Fitch understands t,u,v,w,x,y,z with or without subscripts.
9.2
The quantifier symbols: ,
Universal quantifier 
xA(x) is read as:
“for every x, A(x)”
“for all x, A(x)”
“for every object x, A(x)”
etc.
Existential quantifier 
xA(x) is read as:
“for some x, A(x)”
“for at least one x, A(x)”
“there is an object x such that A(x)”
etc.
xHome(x)
x(Doctor(x)Smart(x))
xHome(x)
x(Doctor(x)Smart(x))
9.3.a
Wffs and sentences
Wff: 0. Every atomic wff is a wff
1. If P is a wff, so is P
2. If P1,…,Pn are wffs, so are (P1…Pn) and (P1…Pn)
3. If P and Q are wffs, so are (PQ) and (PQ)
4. If P is a wff and x is a variable, xP and xP are wffs;
every occurrence of x in these wffs is said to be bound.
As always, external parentheses can be omitted.
An occurrence of a variable that is not bound is said to be free.
In other words, x is free iff it is not in the scope of x or x.
A sentence is a wff that has no free occurrences of variables.
9.3.b
Wffs and sentences
Is x free or bound in:
Is the following wff a sentence:
x=0
(0=1)
 (x(x=0))
x=0
 (y(x=0))
x(x=x)
y(x=y)
x(x=y)
x((x=0)(x=y))
x(x=1 y(x+y=1))
(x(x=0))(x=y)
9.4.a
Semantics for the quantifiers
Consider any wff P(x) that has no free occurrences of variables other
than x.
Take any object, and give it a (new) name c if it does not already have
one. We say that this object satisfies P(x) iff P(c) is true.
When evaluating quantified sentences, we always have some nonempty
domain of discourse in mind, i.e. the set of all possible objects in a
given treatment. E.g., in a Tarski’s world, this would be the set of all
objects on the board; in arithmetic, this would be the set of all natural
numbers; etc.
xP(x) is true iff there is an object in the domain that satisfies P(x)
xP(x) is true iff every object of the domain satisfies P(x)
9.4.b
Semantics for the quantifiers
x(x+x=x)
x(x+x=x)
When the domain of
discourse is {0,1,2,…},
then
x(x=1+1)
xP(x) = P(0)P(1)P(2)…
x(x=1+1)
and
x(x+x=xx)
xP(x) = P(0)P(1)P(2)…
x(x1=x)
x(x1=x)
x(x=0(x+x=x))
x(x+x=1)
9.4.c
Semantics for the quantifiers
Game rules for xP(x):
If you commit to the truth, then your opponent chooses an object c,
and the game continues as if you had committed to the truth of P(c).
If you commit to the falsity, then you have to choose an object c, and
the game continues as if you had committed to the falsity of P(c).
Game rules for xP(x):
If you commit to the truth, then you have to choose an object c, and
the game continues as if you had committed to the truth of P(c).
If you commit to the falsity, then your opponent chooses an object c,
and the game continues as if you had committed to the falsity of P(c).
You try it, page 240 [Game World + Game Sentences]
9.5
The four Aristotelian forms
All Ps are Qs
Some Ps are Qs
No Ps are Qs
Some Ps are not Qs
You try it, page 242
9.6
Translating complex noun phrases
Small, Happy, Dog, Home.
Translate “A small happy dog is at home” (existential noun phrase)
Translate “Every small dog that is at home is happy” (universal noun phr.)
True or false?
x[(x>15x<6)  Even(x)]
x(x0x=x)
You try it, p. 248
Dodgson’s sentences + Peano’s world; Pierce’s world