Predicate Functor Logic - Motivation

Motivation

The source for this section, as well as for much of this entry, is Quine (1976). Quine proposed PFL as a way of algebraizing first-order logic in a manner analogous to how Boolean algebra algebraizes propositional logic. He designed PFL to have exactly the expressive power of first-order logic with identity. Hence the metamathematics of PFL are exactly those of first-order logic with no interpreted predicate letters: both logics are sound, complete, and undecidable. Most work Quine published on logic and mathematics in the last 30 years of his life touched on PFL in some way.

Quine took "functor" from the writings of his friend Rudolf Carnap, the first to employ it in philosophy and mathematical logic, and defined it as follows:

"The word functor, grammatical in import but logical in habitat... is a sign that attaches to one or more expressions of given grammatical kind(s) to produce an expression of a given grammatical kind." (Quine 1982: 129)

Ways other than PFL to algebraize first-order logic include:

• Cylindric algebra by Alfred Tarski and his American students. The simplified cylindric algebra proposed in Bernays (1959) led Quine to write the paper containing the first use of the phrase "predicate functor";
• The polyadic algebra of Paul Halmos. By virtue of its economical primitives and axioms, this algebra most resembles PFL;
• Relation algebra algebraizes the fragment of first-order logic consisting of formulas having no atomic formula lying in the scope of more than three quantifiers. That fragment suffices, however, for Peano arithmetic and the axiomatic set theory ZFC; hence relation algebra, unlike PFL, is incompletable. Most work on relation algebra since about 1920 has been by Tarski and his American students. The power of relation algebra did not become manifest until the monograph Tarski and Givant (1987), published after the three important papers bearing on PFL, namely Bacon (1985), Kuhn (1983), and Quine (1976);
• Combinatory logic builds on combinators, higher order functions whose domain is another combinator or function, and whose range is yet another combinator. Hence combinatory logic goes beyond first-order logic by having the expressive power of set theory, which makes combinatory logic vulnerable to paradoxes. A predicate functor, on the other hand, simply maps predicates (also called terms) into predicates.

PFL is arguably the simplest of these formalisms, yet also the one about which the least has been written.

Quine had a lifelong fascination with combinatory logic, attested to by his (1976) and his introduction to the translation in Van Heijenoort (1967) of the paper by the Russian logician Moses Schönfinkel founding combinatory logic. When Quine began working on PFL in earnest, in 1959, combinatory logic was commonly deemed a failure for the following reasons:

• Until Dana Scott began writing on the model theory of combinatory logic in the late 1960s, nearly all work on that logic had been by Haskell Curry, his students, or by Robert Feys in Belgium;
• Satisfactory axiomatic formulations of combinatory logic were slow in coming. In the 1930s, some formulations of combinatory logic were found to be inconsistent. Curry also discovered the Curry paradox, peculiar to combinatory logic;
• The lambda calculus, with the same expressive power as combinatory logic, was seen as a superior formalism.