The roots of predicate logic lie in the syllogistic logic of Aristotle, which he developed in the fourth century BCE. (See Prior Analytics.)
Aristotle's logic is concerned with the relation of premises to conclusion in arguments. A premise is defined as follows: "A premise then is a sentence affirming or denying one thing of another" (Bk.I, Pt.1). The thing of which something is affirmed or denied is the subject of the sentence, and that which is affirmed or denied of the subject is the predicate. Subject and predicate are both called terms, which we would now call noun-phrases. So if I affirm that all cats are mammals, 'cats' is the subject-term and 'mammals' is the predicate-term. If both the subject and predicate are general (category) terms, the sentences are called categorical.
Syllogisms relate premises to a conclusion. Here is Aristotle's formal definition.
A syllogism is discourse in which, certain things being stated, something other than what is stated follows of necessity from their being so. I mean by the last phrase that they produce the consequence, and by this, that no further term is required from without in order to make the consequence necessary. (Bk. I, Pt.1)What Aristotle had in mind here is a specialized type of what we now call a valid argument. Its chief feature is that the conclusion "follows of necessity" from the premises being as they are "stated," that is, they must be true if the premises are true. (A further feature of Aristotelian syllogisms is that the conclusion states "something other" than what the premise states. This restriction does not hold for all valid arguments.) Of interest here are categorical syllogisms, in which both premises and the conclusion are categorical sentences. These sentences are divided by Aristotle into types. Affirmative sentences assert that the subjects have the predicate, while negative sentences deny this. Universal sentences assert of all the subject that it has or lacks the predicate, while particular sentences assert this of only some of the subject. This yields a four-fold classification of sentences.
For example, consider the following syllogism:
Whenever three terms are so related to one another that the last is contained in the middle as in a whole, and the middle is either contained in, or excluded from, the first as in or from a whole, the extremes must be related by a perfect syllogism. I call that term middle which is itself contained in another and contains another in itself: in position also this comes in the middle. By extremes I mean both that term which is itself contained in another and that in which another is contained. If A is predicated of all B, and B of all C, A must be predicated of all C: we have already explained what we mean by 'predicated of all'. (Bk.1, Pt.4)The validity of the A-A-A form is understood by reference to a relation of containment between terms, and we would now say that containment is a transitive relation (A Modern Formal Language Primer, Chapter 9, Section 2). But Aristotle had no systematic way of dealing with the containment relation. This was left to later logicians.
Showing that arguments with a certain form are valid requires general reasoning that establishes that the truth of any pair of major and minor premises necessitates the conclusion. To show invalidity, all that is needed is a case (counter-example) in which all the premises are true and the conclusion is false. For example, consider the following argument.
William of Shyreswood
The next innovator in predicate logic was an Englishman, William of Shyreswood, who wrote a book entitled Introductiones in Logicam in the first half of the thirteenth century. The most notable feature of the book was the treatment of quantifiers, the logical expressions "all," "no," and "some" on which are based Aristotle's distinction between universal and particular sentences. William recognized the equivalence of various combinations of quantifiers and negation.
William cited a way to keep track of the valid syllogistic forms. Each syllogistic form is represented by the first three vowels in a Latin word. For example, A-A-A is signified by 'barbara,' E-A-E by 'celarent,' etc. (We have left out of discussion other aspects of syllogisms such as "mood," which are also reflected in the choice of words.) William devised a poem representing all the valid forms of syllogism.
Barbara celarent darii ferio baraliptonAlthough students could memorize the poem in order to be able to identify the valid syllogistic forms, there remained no systematic way of determining which ones belong to the list.
Celantes dabitis fapesmo frisesomorum;
Cesare campestres festino baroco; darapti
Felapton disamis datisi bocardo ferison.
Gottfried Willhelm Leibniz
The seventeenth-century German philosopher-scientist-mathematician Leibniz was the first to provide a systematic interpretation of predicate logic. (For a somewhat technical discussion of Leibniz's contribution to logic, see Wolfgang Lenzen's paper "Leibniz's Logic.") Unfortunately, virtually nothing of his groundbreaking discoveries was published during his lifetime, and they were only discovered early in the twentieth century.
Leibniz's insight was that logic can be treated algebraically, on the analogy of addition, subtraction and multiplication. When this is done, it is possible to determine the validity of arguments systematically. Also, logic becomes fully symbolic.
One interesting twist to Leibniz's logic was that it recoginizes that terms can be interpreted in two different ways. They can be understood extensionally, as referring to classes of objects. This is how subsequent logicians would come to interpret Aristotelian logic and modern predicate logic. But Leibniz thought that terms are best understood intensionally, as referring to properties. So 'cats' could be understood either as denoting the class of all cats or as denoting the property of being a cat. On the intensional interpretation, what makes 'All cats are mammals' true is that the property of being a mammal is a component of the property of being a cat. The direction of the relation of intensional containment is the reverse of that of the relation of extensional, where the class of cats is contained in the class of mammals.
Diagrams
The great mathematician Leonhard Euler in 1768 published a way of representing the relations of subject and predicate geometrically. Improvements to Euler's system were made subsequently by the French mathematician J. D. Gergonne some fifty years later, and then by the Englishman John Venn and the American Charles Sanders Peirce in the late nineteenth century. (For an account of these developments, see the Stanford Encyclopedia of Philosophy entry "Diagrams.") These diagrams can be used to determine the validity of arguments and in fact are commonly used in logic texts today.
Boolean Logic
During the nineteenth century, several logicians perfected systems of sentential logic. Prominent among them was George Boole, who made the analogy between sentential or propositional operators and the operators of set-theory. The operators `and,' `or,' and `not' correspond to the set-theoretic operators intersection, union and complement, respectively.
Suppose we have two sentences symbolized by, 'P' and 'Q'. And suppose that P is true in cases a and b, while Q is true in cases b and c. The conjunction is true in just those cases in which both P and Q are true, i.e., case b. We can think of this as the intersection of the two sets of cases. The disjunction is true in all cases where either disjunct is true, i.e., the union of the two sets of cases. The negation of P is true in those cases in which P is not true, which is the complement of the set of cases in which it is true.
One distinctive feature of Boolean logic is the treatment of the conditional, which is not analogous to a set-theoretic operator. That is, it does not correspond to an operation which forms a set from a single set or pair ot sets. Instead, it is tied to a relation between sets, the subset relation. Set A is a subset of set B just in case all the members of A are members of B. The conditional 'If P then Q' is true just in case the class of cases in which the P is true is a subset of the cases in which the Q is true. (For a full account of Boolean logic, see C.I. Lewis and C.H. Langford, Symbolic Logic, Chapters 1 and 2.)
Gottlob Frege
In 1879, the German philosopher Gottlob Frege published Begriffsschrift (roughly, Conceptual Notation), the first comprehensive and fully systematic version of predicate logic. The greatest departure of Frege's system from Aristotle's is its generality. It can handle all combinations of quantifiers and negation, as well as conjunctions, disjunctions, conditonals, and biconditionals. Moreover, it can represent relations, whereas Aristotle's system was limited to predicates applying to a single subject.
Frege's inspiration came from the mathematical conception of a function, such as that of addition. The addition function takes two arguments and yields a value: we write 'x + y,' which whose value is some number z. Frege saw that predicates can take arguments as well, so that we might write: 'x is the father of y.' This formulation behaves like a function, in that we get a sentence when names replace the variables. So just as '1 + 2' indicates the sum of two specific numbers, 'George H. W. Bush is father of George W. Bush' indicates a relation between two specific people. The use of functional notation was a significant break from the past, which Frege defended.
These deviations from what is traditional find their justification in the fact that logic has hithereto always followed ordinary language and grammar too closely. In particular, I believe that the replacement of the concepts subject and predicate by argument and function, respectively, will stand the test of time. (Preface to Begriffsschrift)
The schema given above for a two-place relation can be represented symbolically as 'F(x,y).' As was noted, a sentence can be generated by substituting two names as arguments. But more importantly, the functional approach allows us to apply quantifiers. We would like to be able to say, for example, that all people have some father. This can be done in Frege's system. All x that are persons are such that there is a y such that y is a father of x. This quantificational formulation allows us to express Aristotle's categorical sentences.
The way in which Frege symbolized quantifiers and sentential operators was very graphical and not intuitive at all. Here are the symbolizations for the A, E, I, and O sentence-forms.
| A: All a that are X are P | E: All a that are X are not P | I: Not all a that are X are not P | O: Not all a that are X are P |
| | | |
Using these symbolizations and some simple logical principles, one can in Frege's system derive the valid forms of the Aristotelian syllogism.
Perhaps it was the cumbersome character of his symbolism which kept Frege's work from wide notice in the years immediately following its publication. It was eventually discovered and made famous by Bertrand Russell, who adopted a much more intuitive notation, that of the Italian mathematician Peano, which is still in use today.
Frege's project was very ambitious. He wanted to provide a rigorous proof-procedure based on a few axioms and one rule of inference. In this he is regarded as having been successful. Beyond the systematization of logic inference, Frege wanted to derive from purely logical (and set-theoretic) principles all the truths of arithmetic (a project known as "logicism"). Unfortunately, Russell discovered a paradox that showed that Frege's system was inconsistent.
Bertrand Russell
After considerable struggle, Russell was able to find a solution to the paradox. With this in hand, he turned anew to Frege's project in the monumental Principia Mathematica, co-authored with Alfred North Whitehead (first volume published in 1910). This work pushed predicate logic into the forefront of philosophical research, spawning many important developments.
Even before this, in 1905, Russell had published a paper demonstrating the power of predicate logic as an instrument with which to deal with difficult philosophical problems. In "On Denoting," Russell gave an analysis of definite descriptions, such as "the present King of France." There was a puzzle as to the meaning of a sentence such as "The present King of France is bald." How are we to understand it, given that there is no present King of France? Russell's analysis showed how, given its rendering in predicate logic, the sentence can be taken to be false without allowing the description to refer to anything. Russell's technique will be covered in Chapter 9 of A Modern Formal Language Primer.
Kurt Gödel
One question left open by the systems of Frege and Russell-Whitehead was whether they were complete. Roughly, what we would like to know is whether every theorem that "ought" to be provable can in fact be proved within the system. Of course, showing whether a system is complete depends on what is considered to be obligatory to prove. The logicians at the time thought that what must be proved are "valid" sentences expressible in the logic. Valid sentences are sentences that are invariably true, given a general interpretive scheme. For example, 'P or not P' is true no matter what the value of 'P,' given rules for determining the truth-values of disjunctions and negations.
In his doctoral dissertation in 1930, Kurt Gödel proved that all valid sentences are provable in the system of Russell and Whitehead. Other ways of proving completeness, most notably that of Leon Henkin, have been invented. If you wish to go through the version of the completeness proof in A Modern Formal Language Primer, see Chapter 15.
Alfred Tarski
In the early 1930s, the Polish logician Alfred Tarski provided a formal interpretation of predicate logic. The problem Tarski faced was how to interpret unquantified formulas such as 'F(x,y)' which have not truth-value (in the same way that 'x + y' does not express a specific number). Tarski found a general method, based on a concept of "satisfaction," of interpreting sentences of this kind, so that the truth-values of quantified sentences could be determined. This method will be examined in detail in this class. While there have been other significant results proved about predicate logic, they go beyond the scope of this course, and so we will end this history of predicate logic at this point.