MacTutor
Carol R Karp: Languages with expressions of infinite length
Carol Ruth Karp published Languages with expressions of infinite length in 1964. The publisher was the North-Holland Publishing Company, Amsterdam. E Engeler writes:-
The objects studied are languages... which arise by generalization from first-order languages by allowing infinite conjunction and disjunction of fewer than [a fixed cardinal number of] formulas and simultaneous existential or universal quantification of fewer than [a fixed cardinal number of] variables. This is the first connected and detailed report of the important work done by the author, Tarski, Hanf and Scott on these languages. ... The monograph is carefully and lucidly written and should make this field of logic accessible to a wider circle of logicians.
We give below the Preface to the work:-Preface
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 or or 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 do there exist definable complete formal systems for formulas of length less than in which fewer than 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
Last Updated August 2006