Logic, Meaning and Computation Essays in Memory of Alonzo Church

This volume began as a remembrance of Alonzo Church while he was still with us and is now finally complete. It contains papers by many well-known scholars, most of whom have been directly influenced by Church's own work. Often the emphasis is on foundational issues in logic, mathematics, computation, and philosophy - as was the case with Church's contributions, now universally recognized as having been of profound fundamental significance in those areas. The volume will be of interest to logicians, computer scientists, philosophers, and linguists. The contributions concern classical first-order logic, higher-order logic, non-classical theories of implication, set theories with universal sets, the logical and semantical paradoxes, the lambda-calculus, especially as it is used in computation, philosophical issues about meaning and ontology in the abstract sciences and in natural language, and much else. The material will be accessible to specialists in these areas and to advanced graduate students in the respective fields.

Logic, truth and number: The elementary genesis of arithmetic.- Second-order logic.- A representation of relation algebras using Routley-Meyer frames.- Church’s set theory with a universal set.- Axioms of infinity in Church’s type theory.- Logical objects.- The lambda calculus and adjoint functors.- Atomic Boolean algebras and classical propositional logic.- Improved decision procedures for pure relevant logic.- The “triumph” of first-order languages.- Equivalence relations and groups.- Discriminating coded lambda terms.- ?-calculus as a foundation for mathematics.- Peano’s lambda calculus: The functional abstraction implicit in arithmetic.- The undecidability of ?-definability.- A construction of the provable wellorderings of the theory of species.- Semantics for first and higher order realizability.- Language and equality theory in logic programming.- Alternative (1*): A criterion of identity for intensional entities.- Nominalist paraphrase and ontological commitment.- Peace, justice and computation: Leibniz’ program and the moral and political significance of Church’s theorem.- Tarski’s theorem and NFU.- Church’s theorem and randomness.- Russellian type theory and semantical paradoxes.- The logic of sense and denotation: Extensions and applications.- Analysis, synonymy and sense.- The very possibility of language.