3.4 QUANTIFICATION OF PROPOSITIONAL FUNCTIONS IN SEVERAL VARIABLES 109
(c) In parts (ii) through (v) of (b), indicate, for each existentially quantified variable,
all possible dependencies on universally quantified variables (e.g., in the first part
of (i), z may depend on both x and y, whereas in the second part of (i) z may
depend only on x. Note that you should find fewer dependencies in statements
judged stronger in part (b) than in corresponding weaker statements).
- Let U = Z, the set of all integers. Given two elements m, n E Z, we say that m
divides n if and only if there exists p E Z such that n = mp. Define a propositional
function d on Z x Z by d(m, n): m divides n.
(a) Translate each of the following symbolized statements into a good English
sentence. Label each as either true or false:
(0
(iii)
*(v)
(vii)
(ix)
*(xi)
(xii)
(xiii)
- (ii) d(4, 16)
d( 1694) (iv) W,7)
4-8, 0) (vi) d(7, -7)
4 - 7,7) (viii) (Vm)d(m, m)
(Vn)d( 194 00 (Vm)d(m, 0)
(Vm)(Vn)[d(m, n) + d(n, m)]
(Vm)(Vn)(~~)[(d(m, n) A 44 P)) + d(m, P)]
(Vm)(Vn)[(d(m, n) A d(n, m)) + m = n]
(b) Suppose we now let U = N, the set of all positive integers. We wish to
consider the four statements (Vm)(3n)d(m, n), (3n)(Vm)d(m, n), (Vn)(3m)d(m, n), and
(3m)Pn)d(m, 4.
(i) The statement (Vm)(3n)d(m, n) is true. In particular, for each of the following
given values of m, give back a corresponding value of n for which d(m, n) is true:
(A) m = 2 n =?
(B) m=4 n =?
(C) m = 16 n =?
(D) m = 464 n =?
(E) m=1,000,000 n=?
(ii) Do you think that the statement (3n)(Vm)d(m, n) is true? Explain the connection
between this question and your answers to (i).
(iii) The statement (Vn)(3m)d(m, n) is true. In particular, for each of the following
given values of n, give back a corresponding value of m for which d(m, n) is true:
(A) n = 2 m =?
(B) n=4 m =?
(C) n= 16 - m=?
(D) n = 464 m =?
(E) n = 1,000,000 m =?
(iv) Do you think that the statement (3m)(Vn)d(m, n) is true? Explain the connec-
tion between this question and your answers in (iii).
(c) Reconsider part (ii) of (b) if we let U = Z, rather than U = N.
- (Continuation of Exercises 7 and 8, Article 3.3) Let us consider again the matter
of the restriction of a quantified variable to a subset of the domain of discourse
U. Let p(x, y) be a predicate with domain U, x U,, and let A c U, and B c U,.
