Textbook on Gödel’s incompleteness theorems and computability theory, based on the Open Logic Project. Covers recursive function theory, arithmetization of syntax, the first and second incompleteness theorem, models of arithmetic, second-order logic, and the lambda calculus.

An introductory textbook on metalogic. It covers naive set theory, first-order logic, sequent calculus and natural deduction, the completeness, compactness, and Löwenheim-Skolem theorems, Turing machines, and the undecidability of the halting problem and of first-order logic. The audience is undergraduate students with some background in formal logic.

I shall elaborate more on the idea of anti-irrationalism proposed by the Polish analytic philosopher Kazimierz Ajdukiewicz, a prominent member of the Lvov-Warsaw School of philosophy and logic. In my reading, anti-irrationalism stands in opposition not only to overt irrationalism, which is made clear by the term itself, but also to all forms of rationalism that tip toward something like worship of reason. Having characterized anti-irrationalism as it originally appeared in Ajdukiewicz’s works, I shall propose a certain reformulation of it, (...) so as to capture a broader philosophical legacy in Poland, primarily, yet not exclusively the Lvov-Warsaw School. (shrink)

Many papers have been devoted to the semantic turn Carnap took in the late 1930s after Tarski had explained to him his method for defining truth and his work on the establishment of scientific semantics. Commentators have often argued that the major turn in Carnap’s approach to languages had already been taken in the Logical Syntax of Language, but they have usually assumed that Carnap was happy to subsequently follow Tarski and adopt Tarskian semantics. In this paper, it is argued (...) that this assumption needs to be qualified and that Carnap was actually far from following Tarski when he decided to complement his syntactic method with a semantic one. Carnap and Tarski had different goals, divergent programs, and dissenting views on truth and semantics. After exploring several possible methods for the explication of logical concepts such as L-truth and L-implication, Carnap opted for definitions based on concepts he had found in Wittgenstein’s Tractatus and Waismann’s work on a logical interpretation of probability. Carnap’s reasons for taking a semantic turn are to be understood in the context of his principle of tolerance. He first hoped he could use Tarski’s technique to recover in the semantic setting the completeness result he had tried to establish in the Logical Syntax. His eventual adoption of non-Tarskian semantics can be accounted for by his program of a logical analysis of science—including empirical science—and his ambition to elaborate a unified logical framework for deductive, inductive, and modal logic, and for explicating analyticity. (shrink)

In his recent article, titled ‘Royaumont Revisited’, Overgaard challenges Dummett's view that one needs to go as far back as the late nineteenth century in order to discover examples of genuine dialogue between ‘analytic’ and ‘continental’ philosophy. Instead, Overgaard argues that in the 1958 Royaumont colloquium, generally judged as a failed attempt at communication between the two camps, one can find some elements which may be utilized towards re-establishing a dialogue between these two sides. Yet, emphasising this image of Royaumont (...) as a kind of battleground between ‘analytic’ and ‘continental’ philosophy obscures the plurality of philosophical approaches involved. Royaumont was the meeting point of more than two philosophical traditions, as can be shown by the divergent interests of its participants. Thus, though the potential for rapprochement between Oxford ‘linguistic philosophy’ and a certain strand of phenomenological thought may indeed be found among the discussions that took place during the colloquium, one should keep in mind that such rapprochement took place in the context of a meeting between, among others: continental ‘analytics’, Anglophone non-‘analytics’, French historians of philosophy, ‘analytic’ opponents of Oxford philosophy, Franciscan phenomenologists, and Oxonians who called their work ‘phenomenology’. (shrink)

Around 1989, a striking letter written in March 1956 from Kurt Gödel to John von Neumann came to light. It poses some problems about the complexity of algorithms; in particular, it asks a question that can be seen as the first formulation of the P=?NP question. This paper discusses some of the background to this letter, including von Neumann's own ideas on complexity theory. Von Neumann had already raised explicit questions about the complexity of Tarski's decision procedure for elementary algebra (...) and geometry in a letter of 1949 to J. C. C. McKinsey. The paper concludes with a discussion of why theoretical computer science did not emerge as a separate discipline until the 1960s. (shrink)

Henry M. Sheffer is well known to logicians for the discovery (or rather, the rediscovery) of the ?Sheffer stroke? of propositional logic. But what else did Sheffer contribute to logic? He published very little, though he is known to have been carrying on a rather mysterious research program in logic; the only substantial result of this research was the unpublished monograph The General Theory of Notational Relativity. The main aim of this paper is to explain, as far as possible (given (...) the scanty evidence), the nature of Sheffer's program, and the reasons for its failure. The paper concludes with a discussion of Sheffer's only true logical descendant, C.H. Langford, and his contributions to model theory. (shrink)

The article describes the background of Roman Ingarden's 1922 review of Leon Chwistek's book Wielość rzeczywistości, and the back-and-forth that followed. Despite the differences, the two shared some interesting similarities. Both authors had important ties to the intellectual happenings outside Poland and were not considerd mainstream at home. In the end, however, it is these connections that allowed them to gain recognition. Ingarden, who had been a student of Husserl, became the leading phenomenologist in the postwar Poland. For Chwistek, a (...) painter, philosopher, and logician interested in Russell’s work, such connections meant that he won the competition for a professorship at the university in Lwów over Alfred Tarski. Until recently, Chwistek’s place in Polish logic remains unclear and Ingarden’s interactions with Polish logic and the Vienna Circle have not been investigated extensively. A deeper look at this intellectual fracas between Ingarden and Chwistek helps one in the study of the complicated mesh of alliances within the Lwów-Warsaw School. The article also identifies the origins of the split between phenomenology and the analytic philosophical tradition in Poland. The article is also accompanied by the translations of the reviews. (shrink)

Once a standard tool in the epistemologist’s kit, the analytic/synthetic distinction was challenged by Quine and others in the mid-twentieth century and remains controversial today. But although the work of a lot contemporary philosophers touches on this distinction – in the sense that it either has consequences for it, or it assumes results about it – few have really focussed on it recently. This has the consequence that a lot has happened that should affect our view of the analytic/synthetic distinction, (...) while little has been done to work out exactly what the effects are. All these features together make the topic ideal for either a survey or research seminar at the graduate level: it can provide an organising theme which justifies a spectrum of classic readings from Locke to Williamson, passing though Kant, Frege, Carnap, Quine and Kripke on the way, but it could also provide an excuse for a much more narrowly construed research seminar which studies the consequences of really contemporary philosophy of language and linguistics for the distinction. (shrink)

Van Heijenoort's main contribution to history and philosophy of modern logic was his distinction between two basic views of logic, first, the absolutist, or universalist, view of the founding fathers, Frege, Peano, and Russell, which dominated the first, classical period of history of modern logic, and, second, the relativist, or model-theoretic, view, inherited from Boole, Schröder, and Löwenheim, which has dominated the second, contemporary period of that history. In my paper, I present the man Jean van Heijenoort (Sect. 1); then (...) I describe his way of arguing for the second view (Sect. 2); and finally I come down in favor of the first view (Sect. 3). There, I specify the version of universalism for which I am prepared to argue (Sect. 3, introduction). Choosing ZFC to play the part of universal, logical (in a nowadays forgotten sense) system, I show, through an example, how the usual model theory can be naturally given its proper place, from the universalist point of view, in the logical framework of ZFC; I outline another, not rival but complementary, semantics for admissible extensions of ZFC in the very same logical framework; I propose a way to get universalism out of the predicaments in which universalists themselves believed it to be (Sect. 3.1). Thus, if universalists of the classical period did not, in fact, construct these semantics, it was not that their universalism forbade them, in principle, to do so. The historical defeat of universalism was not technical in character. Neither was it philosophical. Indeed, it was hardly more than the victory of technicism over the very possibility of a philosophical dispute (Sect. 3.2). (shrink)

Formal semantics is an approach to SEMANTICS1, the study of meaning, with roots in logic, the philosophy of language, and linguistics, and since the 1980’s a core area of linguistic theory. Characteristics of formal semantics to be treated in this article include the following: Formal semanticists treat meaning as mind-independent (though abstract), contrasting with the view of meanings as concepts “in the head” (see I-LANGUAGE AND E-LANGUAGE and MEANING EXTERNALISM AND INTERNALISM); formal semanticists distinguish semantics from knowledge of semantics (Lewis (...) 1975, Cresswell 1978), which has consequences for the notion of semantic COMPETENCE. A central part of the meaning of a sentence on this approach is its TRUTH CONDITIONS, and most although not all formal semantics is model-theoretic, relating linguistic expressions to model-theoretically constructed semantic values cast in terms of truth, REFERENCE, and possible worlds. This sets formal semantics apart from approaches which view semantics as relating a sentence just to a representation on another linguistic “level” (LOGICAL FORM) or a representation in an innate LANGUAGE OF THOUGHT. The formal semanticist could accept such representations as an aspect of semantics but would insist on asking what the model-theoretic semantic interpretation of the given representationlanguage is (Lewis 1970). Formal semantics is centrally concerned with COMPOSITIONALITY at the SYNTAX-SEMANTICS INTERFACE, how the meanings of larger constituents are built up from the meanings of their parts on the basis of their syntactic structure, and with the relation between compositional SENTENCE MEANING and meaning in discourse. (shrink)

Formal semantics and pragmatics as they have developed since the late 1960's have been shaped by fruitful interdisciplinary collaboration among linguists, philosophers, and logicians, among others, and in turn have had noticeable effects on developments in syntax, philosophy of language, computational linguistics, and cognitive science.In this paper I describe the environment in which formal semantics was born and took root, highlighting the differences in ways of thinking about natural language semantics in linguistics and in philosophy and logic. With Montague as (...) a central but not solo player in the story, I reflect on crucial developments in the 1960's and 70's in linguistics and philosophy, and the growth of formal semantics and formal pragmatics from there. I discuss innovations, key players, and leading ideas that shaped the development of formal semantics and its relation to syntax, to pragmatics, and to the philosophy of language in its early years, and some central aspects of its early impact on those fields. (shrink)

The aim of the present study is (1) to show, on the basis of a number of unpublished documents, how Heinrich Scholz supported his Warsaw colleague Jan ?ukasiewicz, the Polish logician, during World War II, and (2) to discuss the efforts he made in order to enable Jan ?ukasiewicz and his wife Regina to move from Warsaw to Münster under life-threatening circumstances. In the first section, we explain how Scholz provided financial help to ?ukasiewicz, and we also adduce evidence of (...) the risks incurred by German scholars who offered assistance to their Polish colleagues. In the second section, we discuss the dramatic circumstances surrounding the ?ukasiewiczes' move to Münster in the summer of 1944. (shrink)

Two unpublished contributions to meetings can be found in the Alfred Tarski Papers, at the University of California, Berkeley. The meetings took place in 1965, in Chicago and London, respectively....

(new version: 10/30/07). Click here to download the companion Mathematica 6 notebook that goes along with this paper.

This is a critical reexamination of several pieces in van Heijenoort’s Selected Essays that are directly or indirectly concerned with the philosophy of logic or the relation of logic to natural language. Among the topics discussed are absolutism and relativism in logic, mass terms, the idea of a rational dictionary, and sense and identity of sense in Frege.

Van Heijenoort’s main contribution to history and philosophy of modern logic was his distinction between two basic views of logic, first, the absolutist, or universalist, view of the founding fathers, Frege, Peano, and Russell, which dominated the first, classical period of history of modern logic, and, second, the relativist, or model-theoretic, view, inherited from Boole, Schröder, and Löwenheim, which has dominated the second, contemporary period of that history. In my paper, I present the man Jean van Heijenoort (Sect. 1); then (...) I describe his way of arguing for the second view (Sect. 2); and finally I come down in favor of the first view (Sect. 3). There, I specify the version of universalism for which I am prepared to argue (Sect. 3, introduction). Choosing ZFC to play the part of universal, logical (in a nowadays forgotten sense) system, I show, through an example, how the usual model theory can be naturally given its proper place, from the universalist point of view, in the logical framework of ZFC; I outline another, not rival but complementary, semantics for admissible extensions of ZFC in the very same logical framework; I propose a way to get universalism out of the predicaments in which universalists themselves believed it to be (Sect. 3.1). Thus, if universalists of the classical period did not, in fact, construct these semantics, it was not that their universalism forbade them, in principle, to do so. The historical defeat of universalism was not technical in character. Neither was it philosophical. Indeed, it was hardly more than the victory of technicism over the very possibility of a philosophical dispute (Sect. 3.2). (shrink)

This expository paper on Aristotle’s prototype underlying logic is intended for a broad audience that includes non-specialists. It requires as background a discussion of Aristotle’s demonstrative logic. Demonstrative logic or apodictics is the study of demonstration as opposed to persuasion. It is the subject of Aristotle’s two-volume Analytics, as its first sentence says. Many of Aristotle’s examples are geometrical. A typical geometrical demonstration requires a theorem that is to be demonstrated, known premises from which the theorem is to be deduced, (...) and a deductive logic by which the steps of the deduction proceed. Every demonstration produces knowledge of its conclusion for every person who comprehends the demonstration. Aristotle presented a general truth-and-consequence theory of demonstration meant to apply to all demonstrations: a demonstration is an extended argumentation that begins with premises known to be truths and that involves a chain of reasoning showing by deductively evident steps that its conclusion is a consequence of its premises. In short, a demonstration is a deduction whose premises are known to be true. Aristotle’s general theory of demonstration required a prior general theory of deduction presented in the Prior Analytics. His general immediate-deduction-chaining theory of deduction was meant to apply to all deductions: any deduction that is not immediately evident is an extended argumentation that involves a chaining of immediately evident steps that shows its final conclusion to follow logically from its premises. His deductions, both direct and indirect, were rule-based and not tautology-based. The idea of tautology-based deduction, which dominated modern logic in the early years of the 1900s, is nowhere to be found in Analytics. Rule-based deduction was rediscovered by modern logicians. To illustrate his general theory of deduction, Aristotle presented a prototype: an ingeniously simple and mathematically precise special case traditionally known as the categorical syllogistic. With reference only to propositions of the four so-called categorical forms, he painstakingly worked out exactly what those immediately evident deductive steps are and how they are chained to complete deductions. In his specialized prototype theory, Aristotle explained how to deduce from a given categorical premise set, no matter how large, any categorical conclusion implied by the given set. He did not extend this treatment to non-categorical deductions, thus setting a program for future logicians. The prototype, categorical syllogistic, was seen by Boole as a “first approximation” to a comprehensive logic. Today, however it appears more as the first of the dozens of logics already created and as the first exemplification of a family that continues to expand. (shrink)

Demonstrative logic, the study of demonstration as opposed to persuasion, is the subject of Aristotle's two-volume Analytics. Many examples are geometrical. Demonstration produces knowledge (of the truth of propositions). Persuasion merely produces opinion. Aristotle presented a general truth-and-consequence conception of demonstration meant to apply to all demonstrations. According to him, a demonstration, which normally proves a conclusion not previously known to be true, is an extended argumentation beginning with premises known to be truths and containing a chain of reasoning showing (...) by deductively evident steps that its conclusion is a consequence of its premises. In particular, a demonstration is a deduction whose premises are known to be true. Aristotle's general theory of demonstration required a prior general theory of deduction presented in the Prior Analytics. His general immediate-deduction-chaining conception of deduction was meant to apply to all deductions. According to him, any deduction that is not immediately evident is an extended argumentation that involves a chaining of intermediate immediately evident steps that shows its final conclusion to follow logically from its premises. To illustrate his general theory of deduction, he presented an ingeniously simple and mathematically precise special case traditionally known as the categorical syllogistic. (shrink)

Here, I offer a rapid overview of the theory of metaphor, in order to situate the contributions to this volume in relation to one another and within the field more generally.

Maria Kokoszyńska-Lutmanowa was one of the most outstanding female representatives of the Lvov-Warsaw School. After achieving her PhD in philosophy under Kazimierz Twardowski’s supervision, she was Kazimierz Ajdukiewicz’s assistant. She was also influenced by Alfred Tarski whose results in semantics she analyzed and popularized. After World War II, she got the chair of logic in University of Wrocław and she organized studies in logic in this academic center. In the 1930s, Kokoszyńska kept in contact with members of the Vienna Circle (...) and became a kind of connecting factor between Polish logicians and the Viennese group. In Poland, she presented the views of members of the Vienna Circle. In Vienna, she emphasized the results of her Polish colleagues. In the present paper, some of Kokoszyńska’s results connected with the matters discussed in the Vienna Circle are presented, namely with the problem of metaphysics, the status of logic and the idea of unity of science. (shrink)

Van Heijenoort’s account of the historical development of modern logic was composed in 1974 and first published in 1992 with an introduction by his former student. What follows is a new edition with a revised and expanded introduction and additional notes.

The aim of the present study is (1) to show, on the basis of a number of unpublished documents, how Heinrich Scholz supported his Warsaw colleague Jan Łukasiewicz, the Polish logician, during World War II, and (2) to discuss the efforts he made in order to enable Jan Łukasiewicz and his wife Regina to move from Warsaw to Münster under life-threatening circumstances. In the first section, we explain how Scholz provided financial help to Łukasiewicz, and we also adduce evidence of (...) the risks incurred by German scholars who offered assistance to their Polish colleagues. In the second section, we discuss the dramatic circumstances surrounding the Łukasiewiczes' move to Münster in the summer of 1944. (shrink)

In the period after the First World War when the various national-ideological “truths” that led to it were not well resolved which resulted in the Second World War, one of the greatest world crises occurs. In those turbulent times, one philosopher renounces his national identity (changes his religion and name), wanting not to save himself from an evil world that is emerging but to join the creation of a completely new world – the world of modern logic. This man is (...) Alfred Tarski, whom many recognize as “the man who defined truth”, linking him to the formulation of the distinction between object and metalanguage. In the paper, I argue with historians of philosophy who claim that this distinction was first set by the logician and philosopher of the Lvov-Warsaw school Stanislaw Leśniewski (whose Tarski was the only doctoral student) accusing Tarski of violating professional laws without attributing the authorship of this distinction to Leśniewski. I show that this is not true and I cite the places where Tarski clearly emphasizes Leśniewski ‘s contribution. (shrink)

Theory and Reality is about the connection between true theories and the world. A mathematical framefork for such connections is given, and it is shown how that framework can be used to infer facts about the structure of reality from facts about the structure of true theories, The book starts with an overview of various approaches to metaphysics. Beginning with Quine's programmatic "On what there is", the first chapter then discusses the perils involved in going from language to metaphysics. It (...) criticises contemporary intuition-driven metaphysics, comments on naturalistic approaches, and then presents the main proposition put forward in the thesis: we should base metaphysics on model theory. In chapters 2 to 5, mathematical treatments are given of concepts that we need: theories, metaphysics, necessitation and semantics. These are used in chapters 6 and 7 to prove that, seen from a certain informative view point, any true theory will give rise to an isomorphism between that theory and the world. This conclusion is similar to Wittgenstein's in the Tractatus, but differs in that it places the structural relationship on the level of whole theories, rather than single propositions. (shrink)