Transcript Methods of Proof for Quantifiers

Language, Proof and
Logic
Methods of Proof for
Quantifiers
Chapter 12
12.1
Valid quantifier steps
Universal elimination (instantiation):
From xP(x) infer P(c)
Existential introduction (generalization):
From P(c) infer xP(x)
1. x[Cube(x)Large(x)]
2. x[Large(x)LeftOf(x,b)]
3. Cube(d)
4. x[Large(x)LeftOf(x,b)]
where c is the name
of some object of the
domain of discourse
3 says that d is a cube. And
1 says that all cubes are large.
Thus, d is large. But 2 says
that every large object is to
the left of b. So, d is to the
left of b. To summarize,
d is large and is to the left of b.
Thus, there is a large object to
the left of b.
Let us think about whether there is any similarity with -elim and -intro.
12.2
The method of existential instantiation
Existential instantiation (elimination): Once you have proven xP(x)
(or have it as a premise), you can select a “neutral” (not used elsewhere)
name d and use P(d) as a valid assumption.
1. x[Cube(x)Large(x)]
2. x[Large(x)LeftOf(x,b)]
3. xCube(x)
4. x[Large(x)LeftOf(x,b)]
Important: If we had selected
d=b, we would have been able to
“prove” xLeftOf(x,x)!
3 says that there is a cube. Let d
be such a cube, i.e. assume
Cube(d) (is true).
1 says that all cubes are large.
Thus, d is large. But 2 says
that every large object is to
the left of b. So, d is to the
left of b. To summarize,
d is large and is to the left of b.
Thus, there is a large object to
the left of b.
Let us think about whether there is any similarity with -elim.
12.3.a
The method of general conditional proof
Universal generalization (introduction): Once you have proven P(d) for
some “neutral” (not used elsewhere) name d (denoting a “totally
arbitrary” object), you can conclude xP(x).
1. xLarge(x)
2. x[Large(x)SameRow(x,b)]
3. xSameRow(x,b)
Important: The “arbitrary” object
d indeed has to be arbitrary. Things
will go wrong if you select d=b here
Consider any object d. By 1, d is
large. But, by 2, every large
object is in the same row as b. So,
d is in the same row as b. As d
was arbitrary, we conclude that
every object is in the same row
as b.
1. Cube(b)
2. x[Cube(x)Large(x)]
3. xLarge(x)
Let us think about whether there is any similarity with -intro.
12.3.b
The method of general conditional proof
General conditional proof: Once you have proven Q(d) from the
assumption P(d) for some “neutral” (not used elsewhere) name d
(denoting a “totally arbitrary” object), you can conclude x[P(x)Q(x)].
1. x[Cube(x)SameRow(x,b)]
2. x[SameRow(x,b)Small(x)]
3. x[Cube(x)Small(x)]
Consider any object d, and assume d
is a cube. 1 says that every cube is in
the same row as b. So, d is in the same
row as b. But, by 2, everything in the
same row as b is small. So, d is small.
As d was arbitrary, we conclude that
every cube is small.
Let us think about why universal generalization in fact makes this rule redundant.
12.4.a
Proofs involving mixed quantifiers
1. y[Girl(y)  x(Boy(x)  Likes(x,y))]
2. x[Boy(x)  y(Girl(y)  Likes(x,y))]
Consider an arbitrary boy d. By 1, there is a girl who is liked by every
boy. Let c be such a girl. So, d likes c. That is, d likes some girl. As
d was arbitrary, we conclude that every boy likes some girl.
1. x[Boy(x)  y(Girl(y)  Likes(x,y))]
2. y[Girl(y)  x(Boy(x)  Likes(x,y))]
Pseudo-proof: Consider an arbitrary boy d. By 1, d likes some girl. Let
c be such a girl. Thus, d likes c. Since d was arbitrary, we conclude that
every boy likes c. So, there is a girl (specifically, c) who is liked
by every boy.
12.4.b
Proofs involving mixed quantifiers
REMEMBER
Let P(x), Q(x) be wffs.
1. Existential Instantiation: If you have proven xP(x) then you may
choose a new constant symbol c to stand for any object satisfying
P(x) and so you may assume P(c).
2. General Conditional Proof: If you want to prove x[P(x)Q(x)]
then you may choose a new constant symbol c, assume P(c), and
prove Q(c), making sure that Q does not contain any names
introduced by existential instantiation after the assumption of P(c).
3. Universal Generalization: If you want to prove xQ(x) then you
may choose a new constant symbol c and prove Q(c), making sure
that Q does not contain any names introduced by existential
instantiation after the introduction of c.
12.4.c
Proofs involving mixed quantifiers
Euclid’s Theorem: xy[yx  Prime(y)]
Proof. Consider an arbitrary natural number n. Our goal is to show that
y[yn  Prime(y)], from which Euclid’s theorem follows by universal
generalization.
Let k be the product of all the prime numbers less than n. Thus each
prime with <n divides k without remainder. Now let m=k+1. Each
prime less than n divides m with remainder 1. But we know that m can
be factored into primes. Let p be one of those primes. Clearly, by the
earlier observation, pn. Hence, by existential generalization, there
is a prime (specifically, p) greater or equal to n.
As n was arbitrary, we conclude that xy[yx  Prime(y)].
12.4.d
Proofs involving mixed quantifiers
The Barber Paradox:
xy [Shave(x,y)  Shave(y,y)]
The domain of discourse is the set of all men in a small village.
Proof. Assume, for a contradiction, that
1. xy [Shave(x,y)  Shave(y,y)]
Let b be a man (barber) such that
2. y [Shave(b,y)  Shave(y,y)]
is true. By universal instantiation from 2,
3. Shave(b,b)  Shave(b,b).
But this is (indeed) a contradiction.