This paper is dedicated to Alonzo Church, who died in August 1995 after a long life devoted to logic. To Church we owe lambda calculus, the thesis bearing his name and the solution to the Entscheidungsproblem.His well-known book Introduction to Mathematical LogicI, defined the subject matter of mathematical logic, the approach to be taken and the basic topics addressed. Church was the creator of the Journal of Symbolic Logicthe best-known journal of the area, which he edited for several decades This (...) paper is in three sections. The first is written in journalistic style:the story of the life of AlonzoChurch is told, including some of the many anecdotes I have collected from different sources. The secondpart is devoted to his work, but is far from being exhaustive. The last part is more original; in it I attempto show that Church’s great discovery was lambda calculus and that his remaining contributions weremainly inspired afterthoughts in the sense that most of his contributions as well as some of his pupils derivefrom that initial achievement. Included are Kleene’s Recursion Theory and the completeness proof ofHenkin. I have added an appendix in which is presented the typed lambda calculus and a proof of theundecidability of first-order logic. (shrink)

Though regarded today as one of the most important results in logic, the compactness theorem was largely ignored until nearly two decades after its discovery. This paper describes the vicissitudes of its evolution and transformation during the period 1930-1970, with special attention to the roles of Kurt Gödel, A. I. Maltsev, Leon Henkin, Abraham Robinson, and Alfred Tarski.

Each science has its own domain of investigation, but one and the same science can be formalized in different languages with different universes of discourse. The concept of the domain of a science and the concept of the universe of discourse of a formalization of a science are distinct, although they often coincide in extension. In order to analyse the presuppositions and implications of choices of domain and universe, this article discusses the treatment of omega arguments in three very different (...) formalizations of arithmetic. In Peano's formalization the domain is a restricted class of individuals, while the universe of discourse is the unrestricted class of all individuals. In Gödel's formalization the domain is a restricted class of individuals as in Peano's formalization, but the universe of discourse coincides with the domain. In Whitehead-Russell's formalization the domain is a class of logical notions in Tarski's sense, that are necessarily not individuals, whereas the universe of discourse is the unrestricted class of individuals as in Peano's formalization. The present approach emphasizes the viewpoint that the universe of discourse of a given discourse is important in determining which propositions are expressed by which sentences. (shrink)

Steve Awodey and Erich H. Reck. Completeness and Categoricity: 19th Century Axiomatics to 21st Century Senatics.

SummaryLeśniewski presented his logical systems in a way which conformed to his nominalism, so the question arises whether Leśniewski's logic can be given a natural formal semantics which, unlike current versions, avoids commitment to abstract entities. Building on hints in Wittgenstein's Tractatus, I develop the idea of a way of meaning which is the basis for what I call combinatorial semantics. I then consider whether this commits us to abstract objects or an intensional metalogic.

In this paper we investigate strong logics of first and second order that have certain absoluteness properties. We begin with an investigation of first order logic and the strong logics ω-logic and β-logic, isolating two facets of absoluteness, namely, generic invariance and faithfulness. It turns out that absoluteness is relative in the sense that stronger background assumptions secure greater degrees of absoluteness. Our aim is to investigate the hierarchies of strong logics of first and second order that are generically invariant (...) and faithful against the backdrop of the strongest large cardinal hypotheses. We show that there is a close correspondence between the two hierarchies and we characterize the strongest logic in each hierarchy. On the first-order side, this leads to a new presentation of Woodin's Ω-logic. On the second-order side, we compare the strongest logic with full second-order logic and argue that the comparison lends support to Quine's claim that second-order logic is really set theory in sheep's clothing. (shrink)

Frege has proposed to consider names as denoting objects, predicates as standing for concepts and sentences as denoting truth values. He was, however, aware that such denotation does not exhaust all what is to be said about meaning. Therefore he has urged that in addition to such denotation (Bedeutung) an expression has sense (Sinn). The sense is the "way of presentation" of denotation; hence the expressions Morning Star and Evening Star have identical denotations, but different senses. Carnap has proposed to (...) replace Frege's distinction between Sinn and Bedeutung by the distinction between intension and extension. Extension is, according to Carnap, what is shared by every two expressions which can be truthfully declared equivalent; where equivalence means a bit different things for different grammatical categories. In the formalism of the classical logic, the equivalence of two terms T1 and T2 is expressed by the formula T1=T2, that of two sentences ↔ ↔ S1 and S2 is by the formula S1↔ ↔S2, and that of two unary predicates P1 and P2 by the formula.. (shrink)

This volume presents mathematical game theory as an interface between logic and philosophy.

Sobocinski in his paper on Leśniewski's solution to Russell's paradox (1949b) argued that Leśniewski has succeeded in explaining it away. The general strategy of this alleged explanation is presented. The key element of this attempt is the distinction between the collective (mereological) and the distributive (set-theoretic) understanding of the set. The mereological part of the solution, although correct, is likely to fall short of providing foundations of mathematics. I argue that the remaining part of the solution which suggests a specific (...) reading of the distributive interpretation is unacceptable. It follows from it that every individual is an element of every individual. Finally, another Leśniewskian-style approach which uses so-called higher-order epsilon connectives is used and its weakness is indicated. (shrink)

The history of building automated theorem provers for higher-order logic is almost as old as the field of deduction systems itself. The first successful attempts to mechanize and implement higher-order logic were those of Huet [13] and Jensen and Pietrzykowski [17]. They combine the resolution principle for higher-order logic (first studied in [1]) with higher-order unification. The unification problem in typed λ-calculi is much more complex than that for first-order terms, since it has to take the theory of αβη-equality into (...) account. As a consequence, the higher-order unification problem is undecidable and sets of solutions need not even always have most general elements that represent them. Thus the mentioned calculi for higher-order logic have take special measures to circumvent the problems posed by the theoretical complexity of higher-order unification. In this paper, we will exemplify the methods and proof- and model-theoretic tools needed for extending first-order automated theorem proving to higherorder logic. For the sake of simplicity take the tableau method as a basis (for a general introduction to first-order tableaux see part I.1) and discuss the higherorder tableau calculi HT and HTE first presented in [19]. The methods in this paper also apply to higher-order resolution calculi [1, 13, 6] or the higher-order matings method of Peter [3], which extend their first-order counterparts in much the same way. Since higher-order calculi cannot be complete for the standard semantics by Gödel’s incompleteness theorem [11], only the weaker notion of Henkin models [12] leads to a meaningful notion of completeness in higher-order logic. It turns out that the calculi in [1, 13, 3, 19] are not Henkin-complete, since they fail to capture the extensionality principles of higher-order logic. We will characterize the deductive power of our calculus HT (which is roughly equivalent to these calculi) by the semantics of functional Σ-models. To arrive at a calculus that is complete with respect to Henkin models, we build on ideas from [6] and augment HT with tableau construction rules that use the extensionality principles in a goal-oriented way.. (shrink)

The period in the foundations of mathematics that started in 1879 with the publication of Frege's Begriffsschrift and ended in 1931 with Gödel's Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I can reasonably be called the classical period. It saw the development of three major foundational programmes: the logicism of Frege, Russell and Whitehead, the intuitionism of Brouwer, and Hilbert's formalist and proof-theoretic programme. In this period, there were also lively exchanges between the various schools culminating in (...) the famous Hilbert-Brouwer controversy in the 1920s. -/- The purpose of this anthology is to review the programmes in the foundations of mathematics from the classical period and to assess their possible relevance for contemporary philosophy of mathematics. What can we say, in retrospect, about the various foundational programmes of the classical period and the disputes that took place between them? To what extent do the classical programmes of logicism, intuitionism and formalism represent options that are still alive today? These questions are addressed in this volume by leading mathematical logicians and philosophers of mathematics. (shrink)

We take a fresh look at the logics of informational dependence and independence of Hintikka and Sandu and Väänänen, and their compositional semantics due to Hodges. We show how Hodges’ semantics can be seen as a special case of a general construction, which provides a context for a useful completeness theorem with respect to a wider class of models. We shed some new light on each aspect of the logic. We show that the natural propositional logic carried by the semantics (...) is the logic of Bunched Implications due to Pym and O’Hearn, which combines intuitionistic and multiplicative connectives. This introduces several new connectives not previously considered in logics of informational dependence, but which we show play a very natural rôle, most notably intuitionistic implication. As regards the quantifiers, we show that their interpretation in the Hodges semantics is forced, in that they are the image under the general construction of the usual Tarski semantics; this implies that they are adjoints to substitution, and hence uniquely determined. As for the dependence predicate, we show that this is definable from a simpler predicate, of constancy or dependence on nothing. This makes essential use of the intuitionistic implication. The Armstrong axioms for functional dependence are then recovered as a standard set of axioms for intuitionistic implication. We also prove a full abstraction result in the style of Hodges, in which the intuitionistic implication plays a very natural rôle. (shrink)

Tarskian model theory is almost universally understood as a formal counterpart of the preformal notion of semantics, of the “linkage between words and things”. The wide-spread opinion is that to account for the semantics of natural language is to furnish its settheoretic interpretation in a suitable model structure; as exemplified by Montague 1974.

Thus, despite the di culty of higher-order automated theorem proving, which has to deal with problems like the undecidability of higher-order uni - cation (HOU) and the need for primitive substitution, there are proof problems which lie beyond the capabilities of rst-order theorem provers, but instead can be solved easily by an higher-order theorem prover (HOATP) like Leo. This is due to the expressiveness of higher-order Logic and, in the special case of Leo, due to an appropriate handling of the (...) extensionality principles (functional extensionality and extensionality on truth values). (shrink)

This paper develops a semantics for a fragment of English that is based on the idea of `impossible possible worlds'. This idea has earlier been formulated by authors such as Montague, Cresswell, Hintikka, and Rantala, but the present set-up shows how it can be formalized in a completely unproblematic logic---the ordinary classical theory of types. The theory is put to use in an account of propositional attitudes that is `hyperfine-grained', i.e. that does not suffer from the well-known problems involved with (...) replacing expressions by logical equivalents. (shrink)

In the tradition of Denotational Semantics one usually lets program constructs take their denotations in reflexive domains, i.e. in domains where self-application is possible. For the bulk of programming constructs, however, working with reflexive domains is an unnecessary complication. In this paper we shall use the domains of ordinary classical type logic to provide the semantics of a simple programming language containing choice and recursion. We prove that the rule of {\em Scott Induction\/} holds in this new setting, prove soundness (...) of a Hoare calculus relative to our semantics, give a direct calculus ${\cal C}$ on programs, and prove that the denotation of any program $P$ in our semantics is equal to the union of the denotations of all those programs $L$ such that $P$ follows from $L$ in our calculus and $L$ does not contain recursion or choice. (shrink)

This paper is the second in a two-part series in which we discuss several notions of completeness for systems of mathematical axioms, with special focus on their interrelations and historical origins in the development of the axiomatic method. We argue that, both from historical and logical points of view, higher-order logic is an appropriate framework for considering such notions, and we consider some open questions in higher-order axiomatics. In addition, we indicate how one can fruitfully extend the usual set-theoretic semantics (...) so as to shed new light on the relevant strengths and limits of higher-order logic. (shrink)

Henry Leonard and Karel Lambert first introduced so-called presupposition-free (or just simply: free) logics in the 1950’s in order to provide a logical framework allowing for non-denoting singular terms (be they descriptions or constants) such as “the largest prime” or “Pegasus” (see Leonard [1956] and Lambert [1960]). Of course, ever since Russell’s paradigmatic treatment of definite descriptions (Russell [1905]), philosophers have had a way to deal with such terms. A sentence such as “the..

A formal theory of quantity T Q is presented which is realist, Platonist, and syntactically second-order (while logically elementary), in contrast with the existing formal theories of quantity developed within the theory of measurement, which are empiricist, nominalist, and syntactically first-order (while logically non-elementary). T Q is shown to be formally and empirically adequate as a theory of quantity, and is argued to be scientifically superior to the existing first-order theories of quantity in that it does not depend upon empirically (...) unsupported assumptions concerning existence of physical objects (e.g. that any two actual objects have an actual sum). The theory T Q supports and illustrates a form of naturalistic Platonism, for which claims concerning the existence and properties of universals form part of natural science, and the distinction between accidental generalizations and laws of nature has a basis in the second-order structure of the world. (shrink)

In 1887 Georg Cantor gave an influential but cryptic proof of theimpossibility of infinitesimals. I first give a reconstruction ofCantor's argument which relies mainly on traditional assumptions fromEuclidean geometry, together with elementary results of Cantor's ownset theory. I then apply the reconstructed argument to theinfinitesimals of Abraham Robinson's nonstandard analysis. Thisbrings out the importance for the argument of an assumption I call theChain Thesis. Doubts about the Chain Thesis are seen to render thereconstructed argument inconclusive as an attack on the (...) infinitelysmall. (shrink)

We critically investigate and refine Dunn's relevant predication, his formalisation of the notion of a real property. We argue that Dunn's original dialectical moves presuppose some interpretation of relevant identity, though none is given. We then re-motivate the proposal in a broader context, considering the prospects for a classical formalisation of real properties, particularly of Geach's implicit distinction between real and ''Cambridge'' properties. After arguing against these prospects, we turn to relevance logic, re-motivating relevant predication with Geach's distinction in mind. (...) Finally we draw out some consequences of Dunn's proposal for the theory of identity in relevance logic. (shrink)

Carnap's philosophy is examined from new viewpoints, including three important distinctions: (i) language as calculus vs language as universal medium; (ii) different senses of completeness: (iii) standard vs nonstandard interpretations of (higher-order) logic. (i) Carnap favored in 1930-34 the "formal mode of speech," a corollary to the universality assumption. He later gave it up partially but retained some of its ingredients, e.g., the one-domain assumption. (ii) Carnap's project of creating a universal self-referential language is encouraged by (ii) and by the (...) author's recent work. (iii) Carnap was aware of (iii) and occasionally used the standard interpretation, but was not entirely clear of the nature of the contrast. (shrink)

We explore the better known paradoxes of Zeno including modern variants based on infinite processes, from the point of view of standard, classical analysis, from which there is still much to learn (especially concerning the paradox of division), and then from the viewpoints of non-standard and non-classical analysis (the logic of the latter being intuitionist).The standard, classical or Cantorian notion of the continuum, modeled on the real number line, is well known, as is the definition of motion as the time (...) derivative of distance (we are not concerned with position and motion in more than one dimension, since Zeno wasn't). The real number line consists of its points, the distance between distinct points being positive and finite. The standard, classical derivative relies on the classical notion of limit, which does not use infinitesimals. (shrink)

First, the paper argues that Tarski's theory of language levels is best understood not only as a method for avoiding semantic paradoxes by rigidly restricting the expressive power of a language, but as a natural expression of an epistemological process of reflection which is more adequately understood as a process and not by its result. Second, it is argued that the apparent philosophical controversy between materialism and idealism dissolves whithin this process of reflection. If one has raised above the lowest (...) level, one always is a materialist as well as an idealist; however, one is so in relation to different levels. (shrink)

A ground-motive for this study of some historical and metaphysical implications of the diagonal lemmas of Cantor and Gödel is Cantor's insightful remark to Dedekind in 1899 that the Inbegriff alles Denkbaren (aggregate of everything thinkable) might, like some class-theoretic entities, be inkonsistent. In the essay's opening sections, I trace some recent antecedents of Cantor's observation in logical writings of Bolzano and Dedekind (more remote counterparts of his language appear in the First Critique), then attempt to relativize the notion of (...) Inkonsistenz to self-sufficient theories T which interpret themselves. In effect, I argue that Gödel's diagonal lemma suggests a sense in which metatheoretic notions of proof, well-foundeness and satisfaction are object-theoretically inkonsistent. With respect to Cantor's Inbegriff, for example, the lemma yields that any object-theoretic reconstruction of thinkability generates an antidiagonal sentence , which one can paraphrase asSelf-referential application of the assertion that. (shrink)

This paper examines the connection between model-theoretic truth and necessary truth. It is argued that though the model-theoretic truths of some standard languages are demonstrably ''''necessary'''' (in a precise sense), the widespread view of model-theoretic truth as providing a general guarantee of necessity is mistaken. Several arguments to the contrary are criticized.

Gabbay has gathered an enormous amount of results; some of them important and novel, others important but already known, many rather routine, however. The organization of this material shows grave defects, both in the exposition and in its logical structure. Intensional logic appears as a vast collection of (often duplicated) loosely connected results. This may be a true reflection of the present state of the subject, but it does not contribute to a better understanding of it, let alone advance it.

A logic is called higher order if it allows for quantification over higher order objects, such as functions of individuals, relations between individuals, functions of functions, relations between functions, etc. Higher order logic began with Frege, was formalized in Russell [46] and Whitehead and Russell [52] early in the previous century, and received its canonical formulation in Church [14].1 While classical type theory has since long been overshadowed by set theory as a foundation of mathematics, recent decades have shown remarkable (...) comebacks in the fields of mechanized reasoning (see, e.g., Benzm¨. (shrink)

In this paper we define intensional models for the classical theory of types, thus arriving at an intensional type logic ITL. Intensional models generalize Henkin's general models and have a natural definition. As a class they do not validate the axiom of Extensionality. We give a cut-free sequent calculus for type theory and show completeness of this calculus with respect to the class of intensional models via a model existence theorem. After this we turn our attention to applications. Firstly, it (...) is argued that, since ITL is truly intensional, it can be used to model ascriptions of propositional attitude without predicting logical omniscience. In order to illustrate this a small fragment of English is defined and provided with an ITL semantics. Secondly, it is shown that ITL models contain certain objects that can be identified with possible worlds. Essential elements of modal logic become available within classical type theory once the axiom of Extensionality is given up. (shrink)

This paper develops an inference system for natural language within the ‘Natural Logic’ paradigm as advocated by van Benthem, Sánchez and others. The system that we propose is based on the Lambek calculus and works directly on the Curry-Howard counterparts for syntactic representations of natural language, with no intermediate translation to logical formulae. The Lambek -based system we propose extends the system by Fyodorov et~al., which is based on the Ajdukiewicz/Bar-Hillel calculus Bar Hillel,. This enables the system to deal with (...) new kinds of inferences, involving relative clauses, non-constituent coordination, and meaning postulates that involve complex expressions. Basing the system on the Lambek calculus leads to problems with non-normalized proof terms, which are treated by using normalization axioms. (shrink)

Inscrutability arguments threaten to reduce interpretationist metasemantic theories to absurdity. Can we find some way to block the arguments? A highly influential proposal in this regard is David Lewis’ ‘ eligibility ’ response: some theories are better than others, not because they fit the data better, but because they are framed in terms of more natural properties. The purposes of this paper are to outline the nature of the eligibility proposal, making the case that it is not ad hoc, but (...) instead flows naturally from three independently motivated elements; and to show that severe limitations afflict the proposal. In conclusion, I pick out the element of the eligibility response that is responsible for the limitations: future work in this area should therefore concentrate on amending this aspect of the overall theory. (shrink)

We discuss the differences between first-order set theory and second-order logic as a foundation for mathematics. We analyse these languages in terms of two levels of formalization. The analysis shows that if second-order logic is understood in its full semantics capable of characterizing categorically central mathematical concepts, it relies entirely on informal reasoning. On the other hand, if it is given a weak semantics, it loses its power in expressing concepts categorically. First-order set theory and second-order logic are not radically (...) different: the latter is a major fragment of the former. (shrink)

In the paper we present completeness theorems for hybrid logics, discuss the problem of finite axiomatization and study term rewriting and unification for the variety of distributive lattices and the variety of groups of exponent 2.

The main result of this paper belongs to the field of the comparative study of program verification methods as well as to the field called nonstandard logics of programs. We compare the program verifying powers of various well-known temporal logics of programs, one of which is the Intermittent Assertions Method, denoted as Bur. Bur is based on one of the simplest modal logics called S5 or sometime-logic. We will see that the minor change in this background modal logic increases the (...) program verifying power of Bur. The change can be described either technically as replacing the reflexive version of S5 with an irreflexive version, or intuitively as using the modality some-other-time instead of sometime. Some insights into the nature of computational induction and its variants are also obtained. (shrink)

This paper developes a relational---as opposed to a functional---theory of types. The theory is based on Hilbert and Bernays' eta operator plus the identity symbol, from which Church's lambda and the other usual operators are then defined. The logic is intended for use in the semantics of natural language.