Carol R Karp: Languages with expressions of infinite length
My interest in infinitary logic dates back to a February day in 1956 when I remarked to my thesis supervisor, Professor Leon Henkin, that a particularly vexing problem would be so simple if only I could write a formula that would say x = 0 or x = 1 or x = 2 etc. To my surprise he replied, "Well, go ahead". The problem is now long-forgotten, but that reply has led to this monograph.
Techniques for proving completeness theorems in logic and representation theorems for Boolean algebras combined to yield a completeness theorem: Valid formulas of denumerable length in which only finitely many variables can be quantified at a time are provable in a system very much like the ordinary first-order predicate calculus. It was clear that this system was not adequate for deductions from assumptions and that no formal system with denumerable proofs could be. It was known from representation theory that additional propositional axiom schemes were required to deal with non-denumerable formulas and I suspected that new quantificational rules were needed as well. The more powerful systems that I formulated in 1957 proved to be complete for many of the infinitary languages; I did not, however, have independence proofs for the new quantificational schemes till later.
The development of infinitary languages was encouraged by Professor Alfred Tarski who, with Professor Henkin, organized a seminar on this topic at Berkeley in the fall of 1956. It gave me an invaluable opportunity to report on my work while it was still at an early stage. Professor Tarski's interest in the area led to a series of new developments in set theory that grew out of William Hanf's work on models of infinitary languages, reported in 1960. Dana Scott's incompleteness theorem, appearing here in print for the first time, was announced at about the same time.
My doctoral dissertation, submitted to the University of Southern California in 1958, contained most of the material of Chapters 2-11. However, the results of Tarski, Hanf, and Scott in 1960 gave it a focus that it did not have before. The central problem could now be formulated as, "For which cardinals a, b do there exist definable complete formal systems for formulas of length less than a in which fewer than b variables can be quantified at a time?", a question that is almost completely answered in this monograph.
The present version of the material also owes much to the referee (not known to me) of an article submitted to the Journal of Symbolic Logic in 1962. He suggested a way of using the Boolean algebraic representation theorems to make the completeness proofs clearer; I had only mentioned that such proofs could be given. As a result, the completeness proofs are done syntactically only in the propositional case, the Boolean representation theorems are derived from them as they were in the dissertation, and from that point on, algebraic methods are used freely.
This monograph owes its very existence to Professor Leon Henkin at whose suggestion work was begun on it in 1960. I am grateful to Professor Beth for his cooperation during the unexpectedly long preparation period. The work was partially supported by National Science Foundation.
Carol R Karp
31 March 1963
University of Maryland
College Park, Maryland
JOC/EFR August 2006
The URL of this page is: