Section 1.4 Predicate Logic
61
The effect of the restriction on existential instantiation is that you should look
at all your hypotheses and, if you plan to use ei on any of them, do it first.
Universal Generalization
Universal generalization allows a universal quantifier to be inserted. This must
be done pretty carefully, however. If we know that P(x) is true and that the x is
absolutely arbitrary, i.e., that x could be any element of the domain, then we can
conclude (4x)P(x). But if x is supposed to represent some specific element of the
domain that has property P, then we can’t generalize that every element of the
domain has property P.
There are two restrictions on universal generalization. Without the first restriction, the sequence
1. P(x)
hyp
2. (4x)P(x) 1, incorrect ug; x was free in the hypothesis.
would be a proof of the wff P(x) S (4x)P(x), but this is not a valid wff. Element x
of the domain may have property P, but that does not mean that every element of
the domain has property P. In the hypothesis, x is naming some fixed if unspecified element of the domain. For instance, in the interpretation where the domain
consists of automobiles and P(x) means “x is yellow,” some particular car may be
yellow but it is certainly not true that all cars are yellow.
Without the second restriction, the sequence
1. (4x)(E y)Q(x, y) hyp
2. (E y)Q(x, y)
1, ui
3. Q(x, a)
2, ei
4. (4x)Q(x, a)
3, incorrect ug; Q(x, a) was deduced by ei from the wff
in step 2, in which x is free.
eXAMPLe 28
Use predicate logic to prove
(4x)[P(x) S Q(x)] ` (4x)P(x) S (4x)Q(x)
Here is a proof sequence.
1. (4x)[P(x) S Q(x)] hyp
2. (4x)P(x)
hyp
3. P(x) S Q(x)
1, ui
4. P(x)
2, ui Note that there is no restriction on ui about
reusing a name.
5 Q(x)
3, 4, mp
6. (4x)Q(x)
5, ug
The use of universal generalization at step 6 is legitimate because x was not a
free variable in any hypothesis nor was ei used anywhere in the proof. The variable x in steps 3 and 4 is just an arbitrary name, representative of any element
in the domain.
ReMIndeR
Use existential instantiation early in the proof
sequence.
61
The effect of the restriction on existential instantiation is that you should look
at all your hypotheses and, if you plan to use ei on any of them, do it first.
Universal Generalization
Universal generalization allows a universal quantifier to be inserted. This must
be done pretty carefully, however. If we know that P(x) is true and that the x is
absolutely arbitrary, i.e., that x could be any element of the domain, then we can
conclude (4x)P(x). But if x is supposed to represent some specific element of the
domain that has property P, then we can’t generalize that every element of the
domain has property P.
There are two restrictions on universal generalization. Without the first restriction, the sequence
1. P(x)
hyp
2. (4x)P(x) 1, incorrect ug; x was free in the hypothesis.
would be a proof of the wff P(x) S (4x)P(x), but this is not a valid wff. Element x
of the domain may have property P, but that does not mean that every element of
the domain has property P. In the hypothesis, x is naming some fixed if unspecified element of the domain. For instance, in the interpretation where the domain
consists of automobiles and P(x) means “x is yellow,” some particular car may be
yellow but it is certainly not true that all cars are yellow.
Without the second restriction, the sequence
1. (4x)(E y)Q(x, y) hyp
2. (E y)Q(x, y)
1, ui
3. Q(x, a)
2, ei
4. (4x)Q(x, a)
3, incorrect ug; Q(x, a) was deduced by ei from the wff
in step 2, in which x is free.
eXAMPLe 28
Use predicate logic to prove
(4x)[P(x) S Q(x)] ` (4x)P(x) S (4x)Q(x)
Here is a proof sequence.
1. (4x)[P(x) S Q(x)] hyp
2. (4x)P(x)
hyp
3. P(x) S Q(x)
1, ui
4. P(x)
2, ui Note that there is no restriction on ui about
reusing a name.
5 Q(x)
3, 4, mp
6. (4x)Q(x)
5, ug
The use of universal generalization at step 6 is legitimate because x was not a
free variable in any hypothesis nor was ei used anywhere in the proof. The variable x in steps 3 and 4 is just an arbitrary name, representative of any element
in the domain.
ReMIndeR
Use existential instantiation early in the proof
sequence.