 # Introduction to Logic

## by Stefan Waner and Steven R. Costenoble ## 7. Predicate Calculus

### The Limits of Propositional Calculus

One of the most famous arguments in logic goes as follows.
All men are mortal.
Socrates is a man.
Therefore, Socrates is mortal.
There is really no good way to express this argument using propositional calculus.

### Question

What are you talking about? These are just three ordinary statements in the propositional calculus:
p: All men are mortal.
q: Socrates is a man.
r: Socrates is mortal.

But then the above argument has the form
 p q  r
and is therefore not a valid argument in the propositional calculus.

### Question

OK. That was a tricky one. I now see that we cannot take those statments as atomic statements, but should write them as compound statements. Now I get it! It is just the transitive rule:
 Something is a man → It is mortal Something is Socrates → It is a man  Something is Socrates → It is mortal

This looks more convincing, but there is another catch: "Something is a man", and "It is a man", while a perfectly good sentences, are not propositions (what, after all, are their truth values?). The same goes for the other "statements" in the argument. No matter how we try to rephrase the argument as a valid argument in propositional calculus, we are doomed to run into some or other technical difficulty.

### Universal Quantifier

We need to go beyond the propositional calculus to the predicate calculus, which allows us to manipulate statements about all or some things, suggested by the above attempt at formulating the argument about Socrates.

We begin by rewording the statment "All men are mortal" a little more slickly than we did above:

"For all x, if x is a man then x is mortal."
The sentence "x is a man" is not a statement in propositional calculus, since it involves an unknown thing x and we can't assign a truth value without knowing what x we're talking about. This sentence can be broken down into its subject, x, and a predicate, "is a man." We say that the sentence is a statement form, since it becomes a statement once we fill in x. Here is how we shall write it symbolically: The subject is already represented by the symbol x, called a term here, and we use the symbol P for the predicate "is a man." We then write Px for the statement form. (It is traditional to write the predicate before the term; this is related to the convention of writing function names before variables in other parts of mathematics.) Similarly, if we use Q to represent the predicate "is mortal" then Qx stands for "x is mortal." We can then write the statement "If x is a man then x is mortal" as Px→Qx. To write our whole statement, "For all x, if x is a man then x is mortal" symbolically, we need symbols for "For all x." We use the symbol ∀ "∀" to stand for the words "for all" or "for every." Thus, we can write our complete statement as
∀x[Px→Qx].
The symbol "∀" is called a quantifier because it describes the number of things we are talking about: all of them. Specifically, it is the universal quantifier because it makes a claim that something happens universally.

### Question

What are those square brackets doing around Px→Qx?

They define what is called the scope of the quantifier ∀x. That is, they surround what it is we are claiming is true for all x.

### Example 0P Practice with the Universal Qantifier

Let
Ex: "x is an earth-like planet."
Lx: "x supports life."
Choose the correct interpretation of each of the following.

 (a) ∀x[Lx → Ex] Select one "Every earth-like planet supports life." "Every life-supporting planet is earth-like." "Some life-supporting planets are not earth-like." "Some earth-like planets do not support life." "All planets support life or are earth-like." (b) ∀x[Ex] ∀x[Lx] Select one "All planets are either earth-like or support life." "Either all planets are earth-like, or all of them support life." "All planets are earth-like and support life." "Some planets are earth-like; others support life. " "A planet is either earth-like or it is not." (c) ∀x[Ex ~Ex] Select one "Some planets are earth-like." "All planets are earth-like." "All planets are earth-like, or all planets are not." "Some planets are earth-like; others are not " "A planet is either earth-like or it is not." (d) ∀x[Ex] ∀x[~Ex] Select one "Some planets are earth-like and some are not." "All planets are earth-like." "All planets are earth-like, or all planets are not." "Some planets are earth-like; others are not " "A planet is either earth-like or it is not." (e) ~(∀x[Ex Lx]) Select one "Some planets are neither earth-like nor support life." "Not all planets are both earth-like and support life" "All planets are neither earth-like nor support life." "All planets are either not earth-like or do not support life." "A planet is either earth-like or supports life." Armed with some of the language of predicate calculus, we are now ready for our first valid argument in predicate calculus:

### Example 1 A Syllogism

Express the argument about Socrates,

All men are mortal.
Socrates is a man.
Therefore, Socrates is mortal.
in symbolic form.

### Solution

We've done most of the work. The statement "Socrates is mortal" uses the predicate P to make a statement about a particular man, Socrates. Let us use the letter s to stand for Socrates. (We shall always use small letters for terms and big letters for predicates.) Then Ps is the statement "Socrates is a man." Similarly, Qs is the statement "Socrates is mortal." The argument now looks like this:

 ∀x[Px → Qx] Ps  Qs

### Before we go on...

This is an example of a classical form of argument known as a syllogism. Roughly, a syllogism is an argument in the predicate calculus with two premises sharing a common term (in this case, the predicate P, "is a man"). In the following section we shall see how to prove that such an argument is valid.

### Note on Negation

Let us go back for a moment to the statement "All men are mortal": ∀x[Px → Qx].

### Question

What does its negation, ~∀x[Px → Qx], say?
Literally, it says: "It is not true that all men are mortal." More succinctly,
"Some men are immortal."
Contrast this with "No men are mortal": ∀x[Px → ~Qx].

### Mathematics and Predicate Calculus

Mathematics is expressed in the language of the predicate calculus. Here's an example of a mathematical statement expressed symbolically.

### Example 2 A Mathematical Statement

Write the following statement symbolically: "If a number is greater than 1 then it is greater than 0."

### Solution

Since this is a statement meant to be true of every number, we need to rephrase it to make the universal quantifier obvious:
"For all x, if x is a number and x is greater than 1, then x is greater than 0."
Let us write N for the predicate "is a number" and use the standard notation ">" for "is greater than." Our statement is then:
∀x[(Nx (x>1)) → (x>0)].
Notice that we put the phrases "x>1" and "x>0" in parentheses to make the meaning clearer.

### Before we go on...

Mathematicians being as lazy as they are, they often don't bother to specify that x is a number, regarding it as understood if they write something like x>1. So, a mathematician might write
∀x[(x>1) → (x>0)].
In fact, we're being a little sloppy even in our original solution. We can run into logical paradoxes if we allow ourselves to let x range over "everything" possible. We should, instead, agree beforehand what universe of things the quantifier "∀x" really refers to. In this example, we might agree that the universe is the set of all real numbers. There is no need to allow x to also refer to, say, an elephant.

### Example 2P Practice with Mathematical Statements

Let Zx: "x is an integer." "The square of every negative integer is positive." ∀x[(Zx (x>0)) → (x2 > 0)] ∀x[(Zx (x<0)) → (x2 > 0)] ∀x[(Zx (x<0)) → (x2 > 0)] ∀x[(Zx (x<0)) (x2 > 0)] "Not every integer is positive." ∀x[~Zx → (x>0)] ∀x[Zx → (x 0)] ∀x[Zx → ~(x>0)] ~∀x[Zx → (x>0)] "No positive integer is negative." ∀x[(Zx (x>0)) → ~(x<0)] ~∀x[(Zx (x>0)) → (x<0)] ∀x[~(Zx (x>0)) → (x<0)] ∀x[(Zx (x>0)) → (x<0)] "All integers are positive or no integers are positive." ∀x[Zx → ((x>0) (x<0))] ∀x[Zx → ((x>0) ~(x>0))] ∀x[Zx → (x>0)] ∀x[Zx → ~(x>0)] ∀x[Zx → (x>0)] ~∀x[Zx → (x>0)] ### Example 3 Another Mathematical Statement

Now write the following statement symbolically: "Given any two numbers, the square of their sum is never negative."

### Solution

Again, we are making a statement about all numbers, in fact, about all pairs of numbers. We can rephrase the statement as follows:
"For all x and all y, if x and y are numbers then the square of their sum is not negative."
Since "the square of their sum" is (x+y)2, our statement can be written like this:
∀x[∀y[(Nx Ny)→~{(x+y)2<0}]].
Rather than write "x["y[ . . . ]] we often write
∀x,y[(Nx Ny)→~{(x+y)2<0}].
If we prefer not to have the negation, we could write
∀x,y[(Nx Ny)→{(x+y)2≥0}].
Once more, we could be lazy and write
∀x,y[(x+y)2≥0].

### Existential Quantifier

There are times when, rather than claim that something is true about all things, we only want to claim that it is true about at least one thing. For example, we might want to make the claim that "some politicians are honest," but we would probably not want to claim this universally. A way that mathematicians often phrase this is "there exists a politician who is honest." Our abbreviation for "there exists" is "∃", which is called the existential quantifier because it claims the existence of something. If we use P for the predicate "is a politician" and H for the predicate "is honest," we can write "some politicians are honest" as
∃x[Px Hx].

### Example 4 Mixing Quantifiers

Write the following statement symbolically: "Every person is better off than someone else."

### Solution

Let's rephrase this statement to get closer to our logical symbolism: "For every person x, there is a person y such that x is better off than y." Now we can see two quantifiers, a universal one and an existential one. We also need some predicates, including P for "is a person," and one more predicate B(x,y) to stand for "x is better off than y." This is a new kind of predicate, taking two terms. Since it relates its two terms, such a 2-place predicate is often called a relation.

Now we can write our statement symbolically, using lots of brackets to make the meaning clear:

∀x[Px→(∃y[Py B(x,y)])].

### Example 4P Practice with Mixing Quantifiers

Let Ax: "x is an astronaut," Px: "x is a planet", and V(x,y) "x will travel to y."  "Every astronaut will travel to at least one planet." ∀x[Ax (∃y[Py V(x,y)])] ∀x[∃y[P(x,y) V(x,y)]] ∀x[Ax (∃y[Py V(x,y)])] ∀x[Ax→(∃y[Py V(x,y)])] "Some astronauts will travel to every planet." ∀x[Ax→(∃y[Py V(x,y)])] ∀x[Ax→(∃y[Py V(x,y)])] ∃x[Ax (∀y[Py V(x,y)])] ∃x[Ax (∀y[Py→V(x,y)])] "Other astronauts will travel to no planets." ∃x[Ax (∀y[Py→~V(x,y)])] ∃x[Ax ~(∀y[Py→V(x,y)])] ~∃x[Ax (∀y[Py→V(x,y)])] ∃x[Ax ~(∀y[Py→V(x,y)])] ∀x[Px→(∃y[Ay V(y,x)])] "Some planets will be visited by every astronaut." "Every planet will be visited by every astronaut." "Every planet will be visited by some astronauts." "Some planets will be visited by some astronauts." ∀x[Px→(∃y[Ay ~V(y,x)])] "Some planets will be visited by no astronauts." "Every planet will be visited by no astronauts." "Not every planet will be visited by some astronauts." "No planet will be visited by all astronauts." Many mathematical definitions are made in terms of quantifiers. An interesting example is the notion of "divisible by." To say that a number x is divisible by 2, for example, is to say that x is 2 times some integer, or that there exists some integer n such that x = 2n. Generalizing a bit and writing symbolically, we can make the following definition.

 Divisible By If x and y are integers, we say that x is divisible by y if ∃n[In (x=yn)]. Here, I is the predicate "is an integer." Note If we agree to restrict our variable to the universe of integers, we don't have to use the predicate I and we get the following simpler version: ∃n[x = yn].

### Example 5 Divisibility

Write the following statement symbolically: "If a number is divisible by 6 then it is divisible by 3 and by 2."

### Solution

To simplify the notation, let us agree that our universe is the set of integers and all variables are therefore integers.

First notice that our statement is a universal one about integers: "For every integer n, if n is divisible by 6 then it is divisible by 3 and by 2." Now, when we want to write "n is divisible by 6" we have to watch out for the fact that we've already used the variable n and can't reuse it as in the definition of "divisible by" above. What we do is pick another letter, say m, and write

∃m[n = 6m]
for "n is divisible by 6." In general, the variable being quantified (the one immediately to the right of the quantifier) is a dummy variable; its name does not matter, as long as the same name is used consistently throughout the statement.

Doing the same with divisibility by 3 and 2, we can write our statement as follows:

∀n[(∃m[n = 6m])→(∃m[n = 3m]) (∃m[n = 2m])].

### Before we go on...

We used m as the dummy variable in all three parts of this statement, but it stands for different numbers in each case. If we wanted to emphasize that the three numbers are different, we could use three different letters, like this:
∀n[(∃m[n = 6m])→(∃i[n = 3i]) (∃j[n = 2j])].
This leads to an interesting question: For a given n, how are i and j related to m? Pondering this question leads to the mathematical proof of the statement.

In this last example we've started to see how mathematics can be translated into symbolic form. It was the hope of mathematicians at the end of the nineteenth century that all of mathematics could be made purely formal and symbolic in this way. The most serious attempt to do this was in Whitehead and Russell's Principia Mathematica (1910), which translated a large part of mathematics into symbolic language. The hope then was that there could be developed a purely formal procedure for checking the truth of mathematical statements and producing proofs. This project was cut short by Gödel's incompleteness theorem (1931), which effectively showed the impossibility of any such procedure. Nonetheless, mathematicians still feel that anything that they do should be expressible in symbolic logic, and the language that they actually use in writing down their work is a somewhat less formal version of the predicate calculus. Last Updated: April, 2004
Copyright © 1996 StefanWaner and Steven R. Costenoble

Top of Page