Bridge to Abstract Mathematics: Mathematical Proof and Structures

3.3 THEOREMS ABOUT PREDICATES IN ONE VARIABLE 97

(or forces) that of the second. There are various other ways of expressing this
idea. The second statement cannot be false for predicates h(x) and k(x) for
which the first statement is true, or the second cannot be false unless the first
is false. Recalling language introduced in Article 2.3, we say also that the first
statement form is stronger than the second. We express this idea in symbols

by

This conclusion is consistent with answers you should have gotten in Ex-
ercises 3(e, f) and 5, Article 3.2. Several other theorems of the predicate
calculus, involving implication between pairs of quantified propositional
functions in one variable, can be arrived at in a similar manner. We state
Theorem 2 in a format analogous to that of Theorem 1.

T H E 0 R E M 2 (Implications Involving Quantified Predicates in One Variable)

Let p(x) and q(x) be predicates over a domain of discourse U with truth sets P and

Q. In (c) we assume further that U is nonempty, while in (d) and (e), we assume

that a is a specific element of U. Then:

Stdtement about quantijied Corresponding statement

predicates about truth sets

Stronger - Weaker Stronger Weaker

The converse of each of the statements in Theorem 2 is false; that is, specific

propositional functions p(x) and q(x) can be found for which the weaker

statement form is true, whereas the corresponding stronger one is false.

Recall, for example, Article 3.2, Exercise 3, part (iv)(c, d), and part (i)(e, f).

Theorems 1 and 2 can be used, together with previous results, to establish

other results of the predicate calculus.

EXAMPLE 3 Find a statement equivalent to the logical negation of

(Vx)(p(x) --+ q(x)), in which "negation" is not a main connective.

Solution According to (a) of Theorem 1, -- [(Vx)(p(x) -, q(x))] is equivalent

to (3x)[--(p(x) 4 q(x))J. By Exercise 4(a), Article 3.1, the compound