Multiple Quantifiers in a Single Statement
Negations of Multiply Quantified Statements
Relation among " , $ , Ù , and Ú
Variants of Universal Conditional Statements
Necessary and Sufficient Conditions Revisited

Multiple Quantifiers in a Single Statement top

Rewrite the following statements formally:

  1. Everybody loves somebody.
  2. Somebody loves everybody.

Solution:

  1. " people x, $ a person y such that x loves y.
  2. $ a person x such that " people y, x loves y.

Clearly, reversing the order in which quantifiers are written dramatically changes the meaning of a statement.

Negations of Multiply Quantified Statements top
What is the negation of the following statement?

" people x, $ a person y such that x loves y.

Let Q(x, y): "$ a person y such that x loves y," by Theorem 2.1.1 we can write

$ a person x such that Ø ($ a person y such that x loves y).

By Theorem 2.1.2 we have

$ a person x such that " people y, x does not love y.

Less formally the negation of "Everybody loves somebody" is

There is somebody who does not love anybody.

The negation of

" x, $ y such that P(x, y)

is logically equivalent to

$ x such that " y, Ø P(x, y).

What might one conclude the negation of

$ x such that " y, P(x, y)

to be?

Relation among " , $ , Ù , and Ú top
DeMorgan's laws, the negation of a conjunction is a disjunction and the negation of a disjunction is a conjunction, are analogous to the relationship we see between the negation of universal statement and its counterpart the existential statement. In a sense, universal statements are generalizations of conjunctions while existential statements are generalizations of disjunctions.

Specifically, if Q(x) is a predicate and the domain D of x is the set {x1, x2, …, xn}, then the statements

" x Î D, Q(x)

and

Q(x1) Ù Q(x2) Ù … Ù Q(xn)

are logically equivalent.

Similarly,

$ x Î D such that Q(x)

and

Q(x1) Ú Q(x2) Ú … Ú Q(xn)

are logically equivalent.

 

Variants of Universal Conditional Statements top
We extend the definitions of contrapositive, converse, and inverse to the universal conditional statements.

Definition
Consider a statement of the form

" x Î D, if P(x) then Q(x).

  1. Its contrapositive is the statement

    2. " x Î D, if Ø Q(x) then Ø P(x).

  2. Its converse is the statement

    3. " x Î D, if Q(x) then P(x).

  3. Its inverse is the statement

" x Î D, if Ø P(x) then Ø Q(x).

See example 2.2.6 on p. 93.

Again a "universal conditional" statement and its contrapositive are logically equivalent. But beware of the converse error and the inverse error.

Necessary and Sufficient Conditions Revisited top
We can extend the definitions of necessary and sufficient conditions to apply to universal conditional statements.

Definition

  1. " x, r(x) is a sufficient condition for s(x) means " x, if r(x) then s(x).
  2. " x, r(x) is a necessary condition for s(x) means " x, if Ø r(x) then Ø s(x). Equivalently, " x, if s(x) then r(x).
  3. " x, r(x) only if s(x) means " x, if Ø s(x) then Ø r(x). Equivalently, " x, if r(x) then s(x).