The paper is devoted to the discussion of some philosophical and historical problems connected with the theorem on the undefinability of the notion of truth. In particular the problem of the priority of proving this theorem will be considered. It is claimed that Tarski obtained this theorem independently though he made clear his indebtedness to Gödel’s methods. On the other hand, Gödel was aware of the formal undefinability of truth in 1931, but he did not publish this (...) result. Reasons for that are also considered. (shrink)

This paper describes Tarski’s project of rehabilitating the notion of truth, previously considered dubious by many philosophers. The project was realized by providing a formal truth definition, which does not employ any problematic concept.

We prove the equivalence of the semantic version of Tarski’s theorem on the undefinability of truth with the semantic version of the diagonal lemma and also show the equivalence of a syntactic version of Tarski’s undefinability theorem with a weak syntactic diagonal lemma. We outline two seemingly diagonal-free proofs for these theorems from the literature and show that the syntactic version of Tarski’s theorem can deliver Gödel–Rosser’s incompleteness theorem.

Tarski’s Convention T—presenting his notion of adequate definition of truth (sic)—contains two conditions: alpha and beta. Alpha requires that all instances of a certain T Schema be provable. Beta requires in effect the provability of ‘every truth is a sentence’. Beta formally recognizes the fact, repeatedly emphasized by Tarski, that sentences (devoid of free variable occurrences)—as opposed to pre-sentences (having free occurrences of variables)—exhaust the range of significance of is true. In Tarski’s preferred usage, it is part (...) of the meaning of true that attribution of being true to a given thing presupposes the thing is a sentence. Beta’s importance is further highlighted by the fact that alpha can be satisfied using the recursively definable concept of being satisfied by every infinite sequence, which Tarski explicitly rejects. Moreover, in Definition 23, the famous truth-definition, Tarski supplements “being satisfied by every infinite sequence” by adding the condition “being a sentence”. Even where truth is undefinable and treated by Tarski axiomatically, he adds as an explicit axiom a sentence to the effect that every truth is a sentence. Surprisingly, the sentence just before the presentation of Convention T seems to imply that alpha alone might be sufficient. Even more surprising is the sentence just after Convention T saying beta “is not essential”. Why include a condition if it is not essential? Tarski says nothing about this dissonance. Considering the broader context, the Polish original, the German translation from which the English was derived, and other sources, we attempt to determine what Tarski might have intended by the two troubling sentences which, as they stand, are contrary to the spirit, if not the letter, of several other passages in Tarski’s corpus. (shrink)

Among the main theorems obtained in mathematical logic in this century are the so called limitation theorems, i.e., the Löwenheim-Skolem theorem on the cardinality of models of first-order theories, Gödel’s incompleteness theorems and Tarski’s theorem on the undefinability of truth. Problems connected with the latter are the subject of this paper. In Section 1 we shall consider Tarski’s theorem. In particular the original formulation of it as well as some specifications will be provided. Next various meanings of (...) the notion of a satisfaction predicate will be studied. In Section 2 the problem of definability of the notion of truth, in particular of the notion of truth for the language of Peano arithmetic PA, will be discussed. It will be explicitly shown that the notion of satisfaction for the language of PA can be defined in a certain weak fragment of the second order arithmetic. Finally the axiomatic characterization of satisfaction and truth as well and its mathematical and philosophical meaning will be discussed. (shrink)

We discuss Robinson's model theoretic proof of Tarski's theorem on undefinability of truth. We present two other “diagonal-free” proofs of Tarski's theorem, and we compare undefinability of truth to other forms of undefinability in nonstandard models of arithmetic.

The fact that Gödel's famous incompleteness theorem and the archetype of all logical paradoxes, that of the Liar, are related closely is, of course, not only well known, but is a part of the common knowledge of the community of logicians. Indeed, almost every more or less formal treatment of the theorem makes a reference to this connection. Gödel himself remarked in the paper announcing his celebrated result :The analogy between this result and Richard's antinomy leaps to the eye;there is (...) also a close relationship with the ‘liar’ antinomy, since … we are… confronted with a proposition which asserts its own unprovability.In the light of the fact that the existence of this connection is commonplace it is all the more surprising that very little can be learnt about its exact nature except perhaps that it is some kind of similarity or analogy. There is, however, a lot more to it than that. Indeed, as we shall try to show below, the general ideas underlying the three central theorems concerning internal limitations of formal deductive systems can be taken as different ways to resolve the Liar paradox. More precisely, it will turn out that an abstract formal variant of the Liar paradox, which can almost straightforwardly inferred from its original ordinary language version, is a possible common generalization of Gödel's incompleteness theorem, the theorem of Tarski on the undefinability of truth, and that of Church concerning the undecidability of provability. (shrink)

A teaching document I've used in my courses on truth and on incompleteness. Aimed at students who have a good grasp of basic logic, and decent math skills, it attempts to give them the background they need to understand a proper statement of the classic results due to Gödel and Tarski, and sketches their proofs. Topics covered include the notions of language and theory, the basics of formal syntax and arithmetization, formal arithmetic (Q and PA), representability, diagonalization, and the (...) incompleteness and undefinability theorems. (shrink)

We transform the proof of the second incompleteness theorem given in [3] to a proof-theoretic version, avoiding the use of the arithmetized completeness theorem. We give also new proofs of old results: The Arithmetical Hierarchy Theorem and Tarski's Theorem on undefinability of truth; the proofs in which the construction of a sentence by means of diagonalization lemma is not needed.

Tarski's Undefinability of Truth Theorem comes in two versions: that no consistent theory which interprets Robinson's Arithmetic (Q) can prove all instances of the T-Scheme and hence define truth; and that no such theory, if sound, can even express truth. In this note, I prove corresponding limitative results for validity. While Peano Arithmetic already has the resources to define a predicate expressing logical validity, as Jeff Ketland has recently pointed out (2012, Validity as a primitive. Analysis 72: 421-30), (...) no theory which interprets Q closed under the standard structural rules can define nor express validity, on pain of triviality. The results put pressure on the widespread view that there is an asymmetry between truth and validity, viz. that while the former cannot be defined within the language, the latter can. I argue that Vann McGee's and Hartry Field's arguments for the asymmetry view are problematic. (shrink)

Interesting as they are by themselves in philosophy and mathematics, paradoxes can be made even more fascinating when turned into proofs and theorems. For example, Russell’s paradox, which overthrew Frege’s logical edifice, is now a classical theorem in set theory, to the effect that no set contains all sets. Paradoxes can be used in proofs of some other theorems—thus Liar’s paradox has been used in the classical proof of Tarski’s theorem on the undefinability of truth in sufficiently rich (...) languages. This paradox (as well as Richard’s paradox) appears implicitly in Gödel’s proof of his celebrated first incompleteness theorem. In this paper, we study Yablo’s paradox from the viewpoint of first- and second-order logics. We prove that a formalization of Yablo’s paradox (which is second order in nature) is non-first-orderizable in the sense of George Boolos (1984). (shrink)

This is a free book, 165 pages. It is for anyone who has had a solid introductory logic course and wants more. Topics covered include soundness and completeness for first-order logic, Tarski's theorem on the undefinability of truth, Gödel's incompleteness theorems, the undecidability of first-order logic, a smattering of second-order logic, and modal logic (both propositional and quantificational). I wrote it for use in my own course, because I thought I could present the most important results and concepts (...) more clearly than the available textbooks. (shrink)

Frege famously claimed that logic is the science of truth: “To discover truths is the task of all science; it falls to logic to discern the laws of truth” (Frege, 1956, p. 289). But just like the other foundational concept of set, truth at that time was intimately associated with paradox; in the case of truth, the Liar paradox. The set-theoretical paradoxes had their teeth drawn by being recognised as reductio proofs of assumptions that had seemed too obvious to warrant (...) stating explicitly, but were now seen to be substantive, and more importantly inconsistent. Tarski includes the Liar paradox in his classic discussion of the concept of truth (Tarski, 1956), and developed it, in the form of his famous theorem on the undefinability of truth, as a reductio of the assumption that a language could be semantically closed, in the sense of being able to contain its own truth-predicate.Frege famously claimed that logic is the science of truth: “To discover truths is the task of all science; it falls to logic to discern the laws of truth” (Frege, 1956, p. 289). But just like the other foundational concept of set, truth at that time was intimately associated with paradox; in the case of truth, the Liar paradox. The set-theoretical paradoxes had their teeth drawn by being recognised as reductio proofs of assumptions that had seemed too obvious to warrant stating explicitly, but were now seen to be substantive, and more importantly inconsistent. Tarski includes the Liar paradox in his classic discussion of the concept of truth (Tarski, 1956), and developed it, in the form of his famous theorem on the undefinability of truth, as a reductio of the assumption that a language could be semantically closed, in the sense of being able to contain its own truth-predicate. (shrink)

There is a well-known gap between metamathematical theorems and their philosophical interpretations. Take Tarski’s Theorem. According to its prevalent interpretation, the collection of all arithmetical truths is not arithmetically definable. However, the underlying metamathematical theorem merely establishes the arithmetical undefinability of a set of specific Gödel codes of certain artefactual entities, such as infix strings, which are true in the standard model. That is, as opposed to its philosophical reading, the metamathematical theorem is formulated (and proved) relative to (...) a specific choice of the Gödel numbering and the notation system. A similar observation applies to Gödel’s and Church’s theorems, which are commonly taken to impose severe limitations on what can be proved and computed using the resources of certain formalisms. The philosophical force of these limitative results heavily relies on the belief that these theorems do not depend on contingencies regarding the underlying formalisation choices. The main aim of this paper is to provide metamathematical facts which support this belief. While employing a fixed notation system, I showed in previous work (_Review of Symbolic Logic_, 2021, 14(1):51–84) how to abstract away from the choice of the Gödel numbering. In the present paper, I extend this work by establishing versions of Tarski’s, Gödel’s and Church’s theorems which are invariant regarding _both_ the notation system and the numbering. This paper thus provides a further step towards absolute versions of metamathematical results which do not rely on contingent formalisation choices. (shrink)

It is shown by Parsons [2] that the first-order fragment of Frege's logical system in the Grundgesetze der Arithmetic is consistent. In this note we formulate and prove a stronger version of this result for arbitrary first-order theories. We also show that a natural attempt to further strengthen our result runs afoul of Tarski's theorem on the undefinability of truth.

Frege famously claimed that logic is the science of truth: “To discover truths is the task of all science; it falls to logic to discern the laws of truth”. But just like the other foundational concept of set, truth at that time was intimately associated with paradox; in the case of truth, the Liar paradox. The set-theoretical paradoxes had their teeth drawn by being recognised as reductio proofs of assumptions that had seemed too obvious to warrant stating explicitly, but were (...) now seen to be substantive, and more importantly inconsistent. Tarski includes the Liar paradox in his classic discussion of the concept of truth, and developed it, in the form of his famous theorem on the undefinability of truth, as a reductio of the assumption that a language could be semantically closed, in the sense of being able to contain its own truth-predicate.Frege famously claimed that logic is the science of truth: “To discover truths is the task of all science; it falls to logic to discern the laws of truth”. But just like the other foundational concept of set, truth at that time was intimately associated with paradox; in the case of truth, the Liar paradox. The set-theoretical paradoxes had their teeth drawn by being recognised as reductio proofs of assumptions that had seemed too obvious to warrant stating explicitly, but were now seen to be substantive, and more importantly inconsistent. Tarski includes the Liar paradox in his classic discussion of the concept of truth, and developed it, in the form of his famous theorem on the undefinability of truth, as a reductio of the assumption that a language could be semantically closed, in the sense of being able to contain its own truth-predicate. (shrink)

This paper proposes a formal framework for the cognitive relation understood as an ordered pair with the cognitive subject and object of cognition as its members. The cognitive subject is represented as consisting of a language, conequence relation and a stock of accepted theories, and the object as a model of those theories. This language allows a simple formulation of the realism/anti-realism controversy. In particular, Tarski’s undefinability theorem gives a philosophical argument for realism in epistemology.

According to Peter Aczel, the inconsistency of Frege’s system in Grundgesetze is due, not to the introduction of sets, as is usually thought, but to the introduction of the Horizontal. His argument is that the principles governing sets are intuitively correct and therefore consistent, while the scheme introducing the Horizontal amounts to an internal definition of truth conflicting with Tarski’s classic result on the undefinability of truth in the object language. The aim of this paper is to show (...) that the Horizontal is innocent: Aczel’s diagnosis is based on a mistaken view of the structure underlying Frege’s ideal language. (shrink)

The prospects and limitations of defining truth in a finite model in the same language whose truth one is considering are thoroughly examined. It is shown that in contradistinction to Tarski's undefinability theorem for arithmetic, it is in a definite sense possible in this case to define truth in the very language whose truth is in question.

The paper presents four open problems concerning recursively saturated models of Peano Arithmetic. One problems concerns a possible converse to Tarski's undefinability of truth theorem. The other concern elementary cuts in countable recursively saturated models, extending automorphisms of countable recursively saturated models, and Jonsson models of PA. Some partial answers are given.

In various theories of truth, people have set forth many definitions to clarify in what sense a set of sentences is paradoxical. But what, exactly, is _a_ paradox per se? It has not yet been realized that there is a gap between ‘being paradoxical’ and ‘being a paradox’. This paper proposes that a paradox is a minimally paradoxical set meeting some closure property. Along this line of thought, we give five tentative definitions based upon the folk notion of paradoxicality implied (...) in Tarski’s undefinability theorem of truth and the dependence relation proposed by Leitgeb (J Philos Log 34(2):155–192, 2005). A definition of ‘being a paradox’ is acceptable if its extension must be sufficiently comprehensive to include all known paradoxes on the one hand, and its standard must also be high enough to exclude those that are evidently not paradoxes on the other hand. It turns out that only the last attempt is acceptable: a set of sentences is a paradox if it is paradoxical and self-dependent, and at the same time, it and any of its paradoxical and self-dependent subsets bisimulate each other. In this way, we articulate in what sense a set of sentences is a paradox, and so establish a connection between the notion of a paradox and the notion of paradoxicality. (shrink)

This paper is an edited form of a letter written by the two authors (in the name of Tarski) to Wolfram Schwabhäuser around 1978. It contains extended remarks about Tarski's system of foundations for Euclidean geometry, in particular its distinctive features, its historical evolution, the history of specific axioms, the questions of independence of axioms and primitive notions, and versions of the system suitable for the development of 1-dimensional geometry.

This article presents Tarski's Address at the Princeton Bicentennial Conference on Problems of Mathematics, together with a separate summary. Two accounts of the discussion which followed are also included. The central topic of the Address and of the discussion is decision problems. The introductory note gives information about the Conference, about the background of the subjects discussed in the Address, and about subsequent developments to these subjects.

We provide for the first time an exact translation into English of the Polish version of Alfred Tarski's classic 1936 paper, whose title we translate as ?On the Concept of Following Logically?. We also provide in footnotes an exact translation of all respects in which the German version, used as the basis of the previously published and rather inexact English translation, differs from the Polish. Although the two versions are basically identical, to an extent that is even uncanny, we (...) note more than 400 differences. Several dozen of these are substantive differences due to revisions by Tarski to the Polish version which he did not incorporate in the German version. With respect to these revisions the Polish version should be regarded as more authoritative than the German. Hence scholars limited to an English translation should use ours. (shrink)

This article presents Tarski's Address at the Princeton Bicentennial Conference on Problems of Mathematics, together with a separate summary. Two accounts of the discussion which followed are also included. The central topic of the Address and of the discussion is decision problems. The introductory note gives information about the Conference, about the background of the subjects discussed in the Address, and about subsequent developments to these subjects.

In this manuscript, published here for the first time, Tarski explores the concept of logical notion. He draws on Klein's Erlanger Programm to locate the logical notions of ordinary geometry as those invariant under all transformations of space. Generalizing, he explicates the concept of logical notion of an arbitrary discipline.

We are in the midst of a fundamental shift, as more enterprises start to use services enabled by cloud technologies. This will heavily impact IT services providers, who must now consider strategies for coping with profound changes in the marketplace or risk being left behind. This research will be of interest to IT services vendors, as well as consumers of IT services.

I ON THE PRIMITIVE TERM OF LOGISTICf IN this article I propose to establish a theorem belonging to logistic concerning some connexions, not widely known, ...

Published with the aid of a grant from the National Endowment for the Humanities. Contains the only complete English-language text of The Concept of Truth in Formalized Languages. Tarski made extensive corrections and revisions of the original translations for this edition, along with new historical remarks. It includes a new preface and a new analytical index for use by philosophers and linguists as well as by historians of mathematics and philosophy.

This book is well known for its proof that many mathematical systems - including lattice theory and closure algebras - are undecidable. It consists of three treatises from one of the greatest logicians of all time: "A General Method in Proofs of Undecidability," "Undecidability and Essential Undecidability in Mathematics," and "Undecidability of the Elementary Theory of Groups.".

Published with the aid of a grant from the National Endowment for the Humanities. Contains the only complete English-language text of The Concept of Truth in Formalized Languages. Tarski made extensive corrections and revisions of the original translations for this edition, along with new historical remarks. It includes a new preface and a new analytical index for use by philosophers and linguists as well as by historians of mathematics and philosophy.

This classic undergraduate treatment examines the deductive method in its first part and explores applications of logic and methodology in constructing mathematical theories in its second part. Exercises appear throughout.

In our current era, a new rapidly spreading pandemic disease called coronavirus disease, caused by a virus identified as a novel coronavirus, is becoming a crucial threat for the whole world. Currently, the number of patients infected by the virus is expanding exponentially, but there is no commercially available COVID-19 medication for this pandemic. However, numerous antiviral drugs are utilized for the treatment of the COVID-19 disease. Identification of the appropriate antivirus medicine to treat the infection of COVID-19 is still (...) a complicated and uncertain decision. This study’s key objective is to develop a novel approach called _q_-rung orthopair probabilistic hesitant fuzzy rough set, which incorporates the _q_-rung orthopair fuzzy set, probabilistic hesitant fuzzy set, and rough set structures. New _q_-ROPHFR aggregation operators have been established: the _q_-ROPHFR Einstein weighted averaging operator and the _q_-ROPHFR Einstein weighted geometric operator. In this study, we explored some basic features of the developed operators. Afterward, to demonstrate the viability and feasibility of the established decision-making approach in real-world applications, a case study related to selecting drugs for COVID-19 pandemic is addressed. Furthermore, a comprehensive comparison with the _q_-rung orthopair probabilistic hesitant fuzzy rough TOPSIS technique is also presented to illustrate the benefits of the new framework. The obtained results confirm the reliability and effectiveness of the proposed approach for finding uncertainty in real-world decision-making. (shrink)

Now in its fourth edition, this classic work clearly and concisely introduces the subject of logic and its applications. The first part of the book explains the basic concepts and principles which make up the elements of logic. The author demonstrates that these ideas are found in all branches of mathematics, and that logical laws are constantly applied in mathematical reasoning. The second part of the book shows the applications of logic in mathematical theory building with concrete examples that draw (...) upon the concepts and principles presented in the first section. Numerous exercises and an introduction to the theory of real numbers are also presented. Students, teachers and general readers interested in logic and mathematics will find this book to be an invaluable introduction to the subject. (shrink)

The logical theory which is called thecalculus of (binary) relations, and which will constitute the subject of this paper, has had a strange and rather capricious line of historical development. Although some scattered remarks regarding the concept of relations are to be found already in the writings of medieval logicians, it is only within the last hundred years that this topic has become the subject of systematic investigation. The first beginnings of the contemporary theory of relations are to be found (...) in the writings of A. De Morgan, who carried out extensive investigations in this domain in the fifties of the Nineteenth Century. De Morgan clearly realized the inadequacy of traditional logic for the expression and justification, not merely of the more intricate arguments of mathematics and the sciences, but even of simple arguments occurring in every-day life; witness his famous aphorism, that all the logic of Aristotle does not permit us, from the fact that a horse is an animal, to conclude that the head of a horse is the head of an animal. In his effort to break the bonds of traditional logic and to expand the limits of logical inquiry, he directed his attention to the general concept of relations and fully recognized its significance. Nevertheless, De Morgan cannot be regarded as the creator of the modern theory of relations, since he did not possess an adequate apparatus for treating the subject in which he was interested, and was apparently unable to create such an apparatus. His investigations on relations show a lack of clarity and rigor which perhaps accounts for the neglect into which they fell in the following years. (shrink)

We provide for the first time an exact translation into English of the Polish version of Alfred Tarski's classic 1936 paper, whose title we translate as ‘On the Concept of Following Logically’. We also provide in footnotes an exact translation of all respects in which the German version, used as the basis of the previously published and rather inexact English translation, differs from the Polish. Although the two versions are basically identical, to an extent that is even uncanny, we (...) note more than 400 differences. Several dozen of these are substantive differences due to revisions by Tarski to the Polish version which he did not incorporate in the German version. With respect to these revisions the Polish version should be regarded as more authoritative than the German. Hence scholars limited to an English translation should use ours. (shrink)