100 LOGIC, PART II: THE PREDICATE CALCULUS Chapter 3
[Note: The concepts in (b) are from elementary linear algebra, (f) is from abstract
algebra, whereas (g) would be encountered in advanced calculus or elementary to-
pology. You need not be familiar with these definitions in order to answer the
questions.]
- Frequently, in mathematics, we wish to restrict a quantified variable to a portion
(i.e., subset A) of the domain of discourse U. A familiar example is the epsilon-delta
definition of limit, in which epsilon and delta are both taken to be positive real
numbers. We define (Vx E A)(p(x)) and (3x E A)(p(x)) by the rules:
(a) Prove that -[(Vx E A)(p(x))] o (3x E A)(-Ax)).
(b) Prove that - [(3x E A)(Ax))] * (Vx E A)(-Ax)).
- (Continuation of 7) (a) Consider the special case A = U of the two definitions
in Exercise 7. Explain why (Vx E U)(p(x)) is equivalent to (Vx)(p(x)) and why
(3x E U)(p(x)) is equivalent to (3x)(p(x)).
(6) Consider the (even more) special case A = U = 0 in part (a). Explain why
(Vx)(p(x)) is true whereas (3x)(p(x)) is false in this case. [Note: Theorem 2(c)
precludes this possibility in the case of a nonempty universal set.]
- Frequently, in mathematics, we wish to assert not only that there exists an object
with a certain property (existence), but that there exists only one such object (unique-
ness). We define the statement "there exists a unique x such that Ax)," denoted
(3! mo)) by
Thus a proof of "unique existence" consists of an existence proof [often by produc-
ing a specific object satisfying p(x)] and a uniqueness proof. The latter is often ap-
proached by assuming that two objects both satisfy Ax) and then showing that
those two objects are actually the same object. Or, if existence of a specific object
b, for which p(b) is true, has been proved first, then uniqueness may be proved by
showing that any x satisfying Ax) equals this b. Let U = R and prove:
(a) (3!x)(7x - 5 = *(b) (3!x)(x2 + SX + 16 = 0)
(d) -[(~!x)((x~ - 1)114 = I)]
- (e) (3!x > 0)(x2 - 5x -^36 = 0) (f) -[(3!x)(x2-5x-36=0)]
- (Continuation of 9) Given a subset A of a universal set U, we define a complement
B of A to be any subset B of U satisfying the equations A u B = U and A n B = 0.
Describe precisely what must be proved in order to show that "any set has a unique
complement." (You will be asked to prove this theorem in Article 6.3.)
- In each of (a) through (d), give an informal argument to support the stated theo-
rem of the predicate calculus. Let Ax) and q(x) be predicates over a domain of dis-
course U and let r be a proposition. Then:
