Introduction to Logic

The Limits of Propositional Calculus

All men are mortal.
Socrates is a man.
Therefore, Socrates is mortal.

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.

Answer

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

Answer

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."

∀x[Px→Qx].

 

Question

What are those square brackets doing around Px→Qx?

Answer

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.

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.

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

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 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)², our statement can be written like this:

∀x[∀y[(NxNy)→~{(x+y)²<0}]].

Rather than write "x["y[ . . . ]] we often write

∀x,y[(NxNy)→~{(x+y)²<0}].

If we prefer not to have the negation, we could write

∀x,y[(NxNy)→{(x+y)²≥0}].

Once more, we could be lazy and write

∀x,y[(x+y)²≥0].

Existential Quantifier

∃x[PxHx].

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[PyB(x,y)])].

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.

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.