Agnes Scott College

Carol R. Karp

Languages with Expressions of Infinite Length
Studies in Logic and the Foundations of Mathematics, North-Holland Publishing Co., 1964

Karp cover

Preface

My interest in infinitary logic dates back to a February day in 1956 when I remarked to my thesis supervisor, Professor Leon Jenkin, 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 Tarske 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 state. 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.

Table of Contents

  1. Introduction
  2. Infinitary Concatenation
  3. Algebras of Terms of Infinite Length
  4. Infinitary Propositional Languages
  5. Infinitary Propositional Logic
  6. Representation Theory for Boolean Algebras
  7. Non-Deducibility in Infinitary Propositional Logic
  8. Systems of Formulas of Infinite Length
  9. Substitution
  10. Infinitary Predicate Languages
  11. Infinitary Predicate Logic
  12. Non-Deducibility in infinitary Predicate Logic
  13. The Definability of the Infinitary Formals Systems
  14. Incompleteness in infinitary Predicate Logic