# Predicate Logic

© 2011 By Paul Herrick

## A Survey of the Main Branches of Logic

Predicate logic was invented in 1879 by a then-unknown German logician and mathematician, Gottlob Frege, as phase one of a lifelong project: Frege spent much of his career trying to prove that mathematics, in the final analysis, reduces to pure logic. The proof of his thesis (known as “logicism” in math and logic), which he spent so many years trying to construct, was to be an axiomatic proof starting with statements of pure logical theory alone and nothing else. After a series of deductively valid inferences, the proof would (hopefully) arrive at the principles of pure number theory (arithmetic), eventually reaching all the principles of mathematics.

However, as he worked on his massive logical-mathematical proof, Frege discovered that the languages of both math and logic then in use were not powerful enough to express the ideas he had in mind; they were not precise enough either. In addition, the standard theory of proof was insufficient. Consequently, Frege invented a new system of logical notation (the first fully “formal” language for logical theory) and used this to formulate a new system of logical principles encompassing and going beyond (a) the categorical logic of Aristotle, (b) the truth-functional logic of the Stoics, and (c) the existing theory of logical and mathematical proof.

Frege’s new theory went beyond all existing theories by generalizing upon them in such a way that the new system could be used to prove all currently provable logical propositions, and it could also be used to prove new propositions in domains never before brought within the fold of logical theory. In the process, Frege single-handedly invented modern logic. Today he is universally considered the founder of modern logic.

You will also hear modern logic called “symbolic logic” and “mathematical logic.” These terms have arisen because modern logic, thanks to Frege, is expressed in symbols and formulas resembling those of mathematics and uses mathematical techniques that take it beyond the reach of the traditional logic that existed prior to the introduction of the modern system invented by Frege in 1879.

We have space for only a few of the details. In order to generalize and then go beyond both categorical and truth-functional logic, Frege invented a brand new system of logical notation, the first “formal” language for logic theory—a complete language with its own syntax and semantics. The entire apparatus is much too big to explain here, but I will try to provide a hint of its expressiveness and power. In modern predicate logic, the following symbols replace the quantifiers (*All*, *None*, and *Some*) of Aristotelian logic:

In place of the universal quantifier All: (x)

In place of the existential quantifier Some: (∃x)

In each of these formulas, the x is a variable ranging over anything in the universe, the expression “(x)” is read, “For all x,” and the expression “(∃X)” is read “For some x.”

Next, in place of the subject and predicate terms of categorical logic, modern predicate logic uses a combination of two additional symbols:

- An individual constant. This is a small case letter standing for an individual thing identified by proper name or by definite description.
- A predicate constant. This is a capital letter standing for a predicate phrase.

Using these, a subject or predicate term is expressed by applying a predicate constant to an individual constant, as in the formula: Ob, where O represents the predicate phrase “is old” and b stands for the individual named Bob. Ob simply says, “Bob is old.”

Using all of this, plus some of the machinery of truth-functional logic, Aristotle’s four basic forms of categorical sentence may now be stated in the notation of modern predicate logic as follows:

(x)( Ax > Bx)

This reads: “For all x, if x is A, then x is B.”

(x)( Ax >~Bx)

This reads: “For all x, if x is A, then x is not B.”

(3x)(Ax & Bx)

This reads: “For some x, x is A and x is B.”

(3x)( Ax & ∼Bx)

This reads: “For some x, x is A and x is not B.”

Finally, here is a sentence that cannot be accurately expressed within the logic of Aristotle alone, or within the logic of truth-functions alone. Neither system alone captures all the logical properties of the sentence:

Everyone is older than someone.

However, the logical properties can be brought out once the sentence is accurately translated into modern predicate logic. In addition, the system originated by Frege can handle arguments composed of sentences such as this one; the other two systems cannot. In modern terms, the formula looks like this, assuming the variables x and y range over a universal domain:

(x) (3y) [(Px & Py) > Oxy]

This is just a sample, of course. As I said for truth-functional logic, the complete system is so precise; it forms such a lovely whole.

Incidentally, the great German logician **Kurt Gödel** (1906-1978), one of the greatest logicians of the 20th century, used the rules of predicate logic to prove one of the most famous mathematical theorems in history. Gödel proved that mathematics is *incomplete*. By “incomplete,” logicians mean something very exact: they mean (in this case) that there are truths of mathematics that cannot be proved true in any axiom system strong enough to prove the elementary truths of arithmetic. Gödel’s “incompleteness theorem” is one of the most famous discoveries in the history of logic or mathematics. For his discovery, Gödel was awarded the first Albert Einstein Award, in a ceremony in 1951 at Princeton University. The award was presented by Einstein himself. The two had become best friends while working at the Institute for Advanced Studies during the 1930s.

My favorite book on Gödel is Rebecca Goldstein’s marvelous intellectual biography: *Incompleteness: The Proof and Paradox of Kurt Gödel* (W. W. Norton & Company, New York).

See the Useful Links for more on Gödel and his famous theorem.