III. Predicate Logic and Quantifiers

Predicates

Universal and Existential Quantifiers

Negation of Quantified Predicates

Multiple Quantifiers

Unique Existence

Predicates

Consider the following syllogism.

Premise: All human beings are mortal.

Premise: Socrates is a human being.

Conclusion: Socrates is mortal.

The last statement seems an irrefutable conclusion of the premises, yet the validity of this type of argument lies beyond the rules of sentential logic. The key of the argument is the quantifier "all" that precedes the first premise.

Before we deal with quantifiers let's consider the arithmetic sentence "x + 1 = 2". Here the letter x is called a variable since the symbol "x" apart from its position in the alphabet has no standard interpretation as a definite object. In contrast, the symbols "1", "=", and "2" have specific meanings. The first thing we need to specify for a variable is its Domain or Universe which is the collection of objects (i.e., a set) from which a given variable takes its particular values. In "x + 1 = 2" the most reasonable domain is some set of numbers (more on these in Section V). In the sentence "z was president of the United States in 1955" the domain for z would be a set of human beings.

In instances like the above two examples the variables x and z are said to be "free", in that any member of the domain is allowed to be substituted into the sentence. The sentence "x + 1 = 2" could be represented by the symbol S(x) . The sentence S(3) is the false proposition "3 + 1 = 2", while the sentence S(1) is the true proposition "1 + 1 = 2". A statement like S(x) with free variables is called a predicate or open sentence. Note: the resemblance to function notation is deliberate. The idea is that the truth of the proposition S(x) depends on or is a function of the variable x. Thus, some authors refer to predicates as propositional functions. If you were asked to determine the truth value of S(x), the question would be meaningless. The statement is sometimes true (when x is replaced by 1) and sometimes false (when x is not replaced by 1). The truth of S(x) is an open question until a value for x is specified. Similarly, let P(z) be the predicate "z was president of the United States in 1955". Then P(Dwight David Eisenhower) is true, P(John F. Kennedy) is false, and P(z) is open.

Universal and Existential Quantifiers

When we introduce quantifiers like all, every, some, there exist, etc., in front of a predicate, the variables in the sentence are bound by the quantifier. The two quantifiers we will use are the Universal Quantifier, , commonly read as "for all" or "for every", and the Existential Quantifier, , commonly read as "there exists … such that" or "for some". For example, is interpreted to mean the sentence "there exists z such that z was President of the United States in 1955". This sentence is considered closed, not open. In fact, it is certainly a true statement since Dwight David Eisenhower is just such an individual! If we wanted to be more specific as to the domain of this statement, we could introduce the additional predicate H(x) "x is a human being" into the closed sentence . Again this is a true statement since substituting Dwight David Eisenhower for z makes true.

Note: the predicate H(x) was defined using the variable x rather than z. The choice of variable names in the definition of a predicate or in a quantified closed sentence is usually arbitrary. Such variables are often called "dummy" variables, since the choice of the name used is immaterial to the interpretation of the sentence. Thus, the statements and are equivalent.

The closed sentence is interpreted as "everything is both a human being and president of the United States in 1955". Clearly, for any domain having more members than Dwight David Eisenhower, this is a false statement. Using a similar analysis, is true since x = 1 does the job, while is false since only x = 1 does the job.

The use of quantifiers and predicates is summarized as follows.

1. The closed sentence is true if and only if Q(x) is true for every value in the domain of x.

2. The closed sentence is true if and only if Q(x) is true for at least one value in the domain of x.

Obviously, , but in general the converse is false.

Negation of Quantified Predicates

Let C(x) be the predicate "x is a citizen of the United States" and let T(x) be the predicate "x pays taxes". Then we probably suspect that the closed sentence is false. Not every US citizen pays taxes. This means of course is true. What is the correct interpretation of this negation? It is certainly not the statement , which can be rendered as "everyone is both a US citizen and doesn't pay taxes"! is false if and only if we can find at least one US citizen who doesn't pay taxes. Hence, is true if and only if we can find at least one US citizen who doesn't pay taxes. Thus, we are lead to the following equivalent statements.

It's not the case that every US citizen pays taxes if and only if there is at least one US citizen who doesn't pay taxes.

In general, and by similar reasoning . 

Multiple Quantifiers

Often we need predicates with more than one variable. Consider the closed sentence "Every team wants to win all of its games". Let T(x) be the predicate "x is a team", G(x,y) the predicate "y is a game played by x" and W(x,y) the predicate "x wants to win y". The above sentence can be symbolized as. Note: The sentence , which could be rendered as "In every game played by any team, the team wants to win", is identical in meaning to . In general, for any predicate Q(x,y), .

As a second example, let S(x,y) be the predicate "the sum of x and y is zero". Let the domains of both x and y be the set of integers . Now consider the following four closed sentences. 

1. "The sum of every two integers is zero."

2. "There are two integers whose sum is zero."

3. "There is an integer whose sum with any integer is zero."

4. "Every integer has an opposite."

Statement 2 is true. For example, is such a pair.

Statement 4 is true. For any .

Statement 1 is clearly false. When .

Statement 3 is also false. There is no integer that acts as the opposite for all the integers. Note: The corresponding statement for multiplication,, is true, since is just such an x.

Thus, we see that for any predicate, and .

However, is not equivalent to. In fact, , but the converse need not be true.

For example, consider the predicate M(x,y) "x is a human being, and y is a human being, and y is the mother of x". Then the closed sentence could be rendered as "Everyone has a biological mother". While this statement might not be true due to advances in cloning technology, it is at least plausible. The closed sentence is the absurdity "There is a person who is everyone's biological mother".

The rules of negation for multiple quantifiers follow from repeated application of the rules for negating a single quantifier. The results are stated and paraphrased below.

It's not true that all x, y pairs make Q(x,y) true if and only if you can find at least one x, y pair that makes Q(x,y) false.

It's not true that for every x you can find a y that makes Q(x,y) true if and only if there is at least one x value for which all y values make Q(x,y) false.

It's not true that you can find an x value that for every y value makes Q(x,y) true if and only if for every x value you can find a y value that makes Q(x,y) false.

It's not true that you can find an x, y pair that makes Q(x,y) true if and only if every x, y pair makes Q(x,y) false.

 Unique Existence

A third quantifier often used is unique existence . The sentence is read as "There exists a unique x such that Q(x)". This means that there is one and only one value in the domain of x that makes the predicate Q(x) true. Using the notion of equality, i.e., x = y if and only if x and y are the same object, one has the following equivalence.