Predicates and Quantified Statements
Set Notation
Universal and Existential Statements
Translating between Formal and Informal Language
Implicit Quantification
Negation of Universal and Existential Statements
Negation of Universal Conditional Statements

Predicates and Quantified Statements top
Given an understanding of the logical analysis of compound statements -those made of simple statements joined by the connectives negation, conjunction, disjunction, conditional, and the biconditional, we have the rudimentary tools. We need only add an ability to quantify statements to extend our understanding of logic to cover many of the everyday and the majority of the mathematical situations. To this end we must learn to analyze and understand the quantities "all" and "some".

What is a predicate? In grammar, the predicate is the part of a sentence that gives information about the subject.

"John is a student at UNCW."

John is the subject and is a student at UNCW is the predicate. In logic we can obtain predicates by removing any nouns from a statement.
Let P stand for the words "is a student at UNCW" and
let Q stand for the words "is a student at."
Then both P and Q are predicate symbols. The sentences

"x is a student at UNCW" and
"x is a student at y"

are symbolized by P(x) and Q(x, y) respectively, where x and y are predicate variables.

Definition
A predicate is a sentence that contains a finite number of variables and becomes a statement when specific values are substituted for the variables. The domain of a predicate variable is the set of all values that may be substituted in place of the variable.

Consider P(x) and Q(x, y) above, what is the size of their domain sets? For P(x), we consider the student population around ten thousand. For Q(x, y) we must further define the domain to say universities in North Carolina, then consider the student populations for all these schools, certainly a much larger domain set than what we have for P(x).

Set Notation top
The sets in which predicate variables take their values are denoted by upper case letters or described by words. The elements of a set are denoted by lower case letters. So the notation x A indicates that x is an element of the set A, or simply x is in A. Some common sets in mathematics are

Symbol

Set

R

set of all real numbers

Q

set of all rational numbers, integer quotients

Z

set of all integers

N

set of nonnegative integers, the natural numbers

Definition
If P(x) is a predicate and x has domain D, the truth set of P(x) is the set of all elements of D that make P(x) true when substituted for x. The truth set of P(x) is denoted

{x D | P(x)}

which is read "the set of all x in D such that P(x)."

Ex. 1
Let D = {0, 1, 2, 3, ...}, and P(x) be "x is a factor of 12". 
Then the truth set P(x) is ...Solution

Notation
Let P(x) and Q(x) be predicates and suppose the common domain of x is D. The notation P(x) Q(x) means that every element in the truth set of P(x) is in the truth set of Q(x). The notation P(x) Q(x) means that P(x) and Q(x) have identical truth sets.

Ex. 2
Let P(x) be "x is a factor of 12," Q(x) be "x is a factor of 4," and R(x) be "x < 5 and x 3," and suppose the domain of x is Z+. Use and to indicate true relationships among P(x), Q(x), and R(x). Solution

Universal and Existential Statements top
Quantifiers are words such as "some" or "all" that can be added to predicates to tell for how many elements a given predicate is true. The symbol " denotes "for all" and is called the universal quantifier.

Definition
Let Q(x) be a predicate and D the domain of x. A universal statement is of the form
"" x D, Q(x)." It is defined to be true if, and only if, Q(x) is true for every x in D. It is defined to be false if, and only if, Q(x) is false for at least one x in D. A value for x for which Q(x) is false is called a counterexample to the universal statement.

Ex.
Let D = {0, 1, 2, 3}, and P(x) be "x2 x." Show that

" x D, P(x)

is true.

Checking each case (method of exhaustion): 02 0, 12 1, 22 2, 32 3, we see that the statement is true.

The symbol $ denotes "there exists" and is called the existential quantifier.

Definition
Let Q(x) be a predicate and D the domain of x. A existential statement is of the form
"$ x D, such that Q(x)." It is defined to be true if, and only if, Q(x) is true for at least one x in D. It is defined to be false if, and only if, Q(x) is false for all x in D.

Ex.
Show the truth of the statement

$ e Z such that e2 = e.

To show that e2 = e is true for at least one integer observe that 12 = 1.

Translating between Formal and Informal Language top
We can only approximate the translating of English sentencs to predicate logic because of the diverse natures of teh two kinds of language. The expressiveness of natural language is much greater, but what a formal language does express is done with precision. The first step is to identify the propositional connectives conjunction, disjunction, negation, conditional, ..., then the quantifiers for all, and there exist. Expressions that can be used in place of for all are

for every, for arbitrary, for any, for each, and given any.

Expression that can be used in place of their exists are

there is a, we can find a, there is at least one, for some, and for at least one.

For particularly difficult cases it may be worth while to rephrase in a semi-formal version being sure to put subject in each sentence fragment. Do not expect the formal version to catch all the subtleties, and while there may be many correct solutions, there are also many incorrect ones. One's effort should be in the minimizing of the incorrect solutions.


As a "rule of thumb", a universal quantifier will generally be followed by , but an existential quantifier by . Consider the two sentences,
  1. "Everyone in the class spoke English or Hungarian."
  2. "Someone in the class spoke either English or Hungarian."
We let
C(x): x is a person in the class,

E(x): x spoke English,

H(x): x spoke Hungarian.
Restating a. in a semi-formal manner: "For all x, if x was a person in the class, then x spoke English or x spoke Hungarian."

" x C(x) (E(x) H(x)).

We would write b. as

$ x C(x) (E(x) H(x)).

Another example reveals how to write equivalent universal statements by condensing the domain to include all values that make the hypothesis of the conditional true. Compare the statements, "" real numbers x, if x is an integer then x is rational." and "" integers x, x is rational." Both mean "All integers are rational." In fact,

" x U, if P(x) then Q(x)

can always be rewritten in the form

" x D, Q(x)

by narrowing U to be the domain D consisting of all values of the variable x that make P(x) true. Conversely, a statement of the form

" x D, Q(x)

can be rewritten as

" x, if x is in D then Q(x).

Implicit Quantification top
Consider the statement

If a number is an integer, then it is a rational number.

What quantifier should we use and what is the clue supporting this as the required quantifier?
From the previous example we know that this is a universal statement. The clue is the indefinite article a. Sometimes there is not even this little clue and the correct quantifier must be supplied by the reader based on experience. Consider the statement

If x > 2 then x2 > 4.

Given in an algebra course this statement is understood to mean

" real numbers x, if x > 2 then x2 > 4.

In the same algebra course you might be asked to solve

(x - 2)2 = 25.

This predicate is existentially quantified as

Show (by finding a value) that $ a real number x such that (x -2)2 = 25.

The quantification, whether universal or existential, determines how the statement can be applied and the method to be used to establish its truth.

Negation of Universal and Existential Statements top
Consider the quantified statement "All fire trucks are red." Which of the following statements more accurately reflects its negation?

  1. No fire trucks are red.
  2. Some fire trucks are not red.

Theorem 2.1.1
The negation of a statement of the form

" x in D, Q(x)

is logically equivalent to a statement of the form

$ x in D such that Q(x).

Symbolically:

(" x D, Q(x)) $ x D such that Q(x).

The negation of the universal statement, "all are," is logically equivalent to the existential statement, "some are not."
Clearly the answer to our fire ruck question is b.

For what statement is "No fire trucks are red." a logical negation? Solution

Theorem 2.1.2
The negation of a statement of the form

$ x in D such that Q(x)

is logically equivalent to a statement of the form

" x in D, Q(x).

Symbolically:

($ x D such that Q(x)) " x D, Q(x).

The negation of the existential statement, "some are not ," is logically equivalent to the universal statement, "all are."

See examples 2.1.10-12 on pp. 84 & 85.

Negation of Universal Conditional Statements top
We have that

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

by Theorem 2.1.1. But the negation of an if-then statement is logically equivalent to an and statement.

(P(x) Q(x)) P(x) Q(x).

So,

(" x, P(x) Q(x)) $ x such that P(x) Q(x).