Search

Emergence refers to the spontaneous formation of higher level (macro) structures or patterns incomplex systems. Attempts to formalize the notion of emergence via algorithmic complexity theoryruns into the problem that the Kolmogorov complexity function is not computable. The reason for thismotivates a closer examination of the link between emergence and universal computation. FollowingWolfram’s pioneering work in the classification of cellular automata behavior, the research programsof Langton and Crutchfield, while incomplete, provide important insights to economists seeking tounderstand the relevance of emergence and universal computation to their discipline. They lead toquestions on the emergence of institutions and the concomitant changes in rule-based behavior on thepart of economic agents. 1. INTRODUCTION The twentieth century is replete with scientific and mathematical discoveriesthat have profoundly changed our world view. In physics, within a merecentury, our view of the cosmos changed from a classical (Newtonian) to arelativistic one following Einstein’s relativity theory in the early 1900s. Inmathematics, Hilbert’s faith in the closure of formal axiom systems fell apartwith Godel’s incompleteness theorem in the 1930s.Out of these ashes of lost deterministic foundations arose the sciences ofcomplex systems, first in the study of non-equilibrium thermodynamics(under the intellectual leadership of Ilya Prigogine in Brussels) and later, inbroader interdisciplinary terms, in New Mexico with the establishment of theSanta Fe Institute. Interestingly, a core element of this new paradigm—thenotion of emergence—reflects the passage of the sciences and mathematics

The Schrodinger’s cat paradox has troubled physicists for many years and many ways to solve it has been provided so far. In this paper I will try to provide a different method of solving the Paradox with the help of logical machine and it will look like a hybrid of Wigner’s no-go theorem and the machine of Godel in his Incompleteness Theorems. And due to the machine the paradox will not require any human intervention to measure the state of the cat, whether it is alive or dead, while the measurement will be made by humans with regard to the statement given out by the machine.

We present an abstract framework in which we give simple proofs for Godel’s First and Second Incompleteness Theorems and obtain, as consequences, Davis’, Chaitin’s and Kritchman-Raz’s Theorems.

A response is given to the paper by A. M. Izmailova (Izmailova A. M. O kritike teoremy K. Gedelya o nepolnote A. V. Bessonovym [On A. V. Bessonov’s criticism of K. Gödel’s incompleteness theorem]. Studencheskii nauchnyi zhurnal “Grani nauki” [Student Scientific Journal "Facets of Science"], 2018, no. 1, p. 7-9. (in Russ.)) allegedly indicating a «serious error» in my analysis of K. Gödel’s second incompleteness theorem. It is shown that her criticism is based on gross logical errors, as well as on a misunderstanding of both the second incompleteness theorem and my results. Such a widespread misinterpretation is based on the inadmissible confusion of the proof of the consistency of formal arithmetic with the proof in it of a formula expressing its consistency. It is argued that Gödel's second theorem is not directly related to the proof of the consistency of formal arithmetic. It is proved that this theorem cannot be used in argumentation against feasibility of D. Hilbert’s finitistic program.

We give a survey of current research on G\"{o}del's incompleteness theorems from the following three aspects: classifications of different proofs of G\"{o}del's incompleteness theorems, the limit of the applicability of G\"{o}del's first incompleteness theorem, and the limit of the applicability of G\"{o}del's second incompleteness theorem., Comment: 54 pages, final accepted version, to appear in The Bulletin of Symbolic Logic

We investigate relationships between versions of derivability conditions for provability predicates. We show several implications and non-implications between the conditions, and we discuss unprovability of consistency statements induced by derivability conditions. First, we classify already known versions of the second incompleteness theorem, and exhibit some new sets of conditions which are sufficient for unprovability of Hilbert--Bernays' consistency statement. Secondly, we improve Buchholz's schematic proof of provable $\Sigma_1$-completeness. Then among other things, we show that Hilbert--Bernays' conditions and L\"ob's conditions are mutually incomparable. We also show that neither Hilbert--Bernays' conditions nor L\"ob's conditions accomplish G\"odel's original statement of the second incompleteness theorem., Comment: 36 pages

The proofs of Gödel (1931), Rosser (1936), Kleene (first 1936 and second 1950), Chaitin (1970), and Boolos (1989) for the first incompleteness theorem are compared with each other, especially from the viewpoint of the second incompleteness theorem. It is shown that Gödel’s (first incompleteness theorem) and Kleene’s first theorems are equivalent with the second incompleteness theorem, Rosser’s and Kleene’s second theorems do deliver the second incompleteness theorem, and Boolos’ theorem is derived from the second incompleteness theorem in the standard way. It is also shown that none of Rosser’s, Kleene’s second, or Boolos’ theorems is equivalent with the second incompleteness theorem, and Chaitin’s incompleteness theorem neither delivers nor is derived from the second incompleteness theorem. We compare (the strength of) these six proofs with one another.

In this article, one presents how some of the most important mathematicians of the early twentieth century – those responsible for organizing mathematics into algebraic, topological and order structures, which one studied in undergraduate courses in mathematics – received the results established by Godel´s Incompleteness Theorem. One understands that the stance taken by Bourbaki group and revealed in his works thus claims how the mathematicians of that time welcomed the incompleteness theorem and handled with its consequences. The attitude assumed by the group was to continue doing Mathematics with the same ideal of complete formalization, although they faced with the proof of the existence of a non-empty set of true and undemonstrable propositions – via mathematical tools for producing this science – and of the incompleteness of any theory that contains Peano axioms. One also presents Wittgenstein's perspective on Godel's Incompleteness Theorem. Finally, one apprehends that this theorem is understood by the mathematical community as a messenger of incompleteness as a characteristic inherent to axiomatization, not as an impediment to the continuation of the activity with formal systems, but as an invigorating result for Mathematics.

A cornerstone of modern mathematical logic is the diagonal lemma of Gödel and Carnap. It is used in, for example, the classical proofs of the theorems of Gödel, Rosser, and Tarski. From its first explication in 1934, just essentially one proof has appeared for the diagonal lemma in the literature; a proof that is so tricky and hard to relate that many authors have tried to avoid the lemma altogether. As a result, some so-called diagonal-free proofs have been given for the above-mentioned fundamental theorems of logic. In this paper, we provide new proofs for the semantic formulation of the diagonal lemma, and for a weak version of the syntactic formulation of it.

We present an abstract development of Gödel’s incompleteness theorems, performed with the help of the Isabelle/HOL proof assistant. We analyze sufficient conditions for the applicability of our theorems to a partially specified logic. In addition to the usual benefits of generality, our abstract perspective enables a comparison between alternative approaches from the literature. These include Rosser’s variation of the first theorem, Jeroslow’s variation of the second theorem, and the Świerczkowski–Paulson semantics-based approach. As part of the validation of our framework, we upgrade Paulson’s Isabelle proof to produce a mechanization of the second theorem that does not assume soundness in the standard model, and in fact does not rely on any notion of model or semantic interpretation.

Informally speaking, the categoricity of an axiom system means that its non-logical symbols have only one possible interpretation that renders the axioms true. Although non-categoricity has become ubiquitous in the second half of the twentieth century whether one looks at number theory, geometry or analysis, the first axiomatizations of such mathematical theories by Dedekind, Hilbert, Huntington, Peano and Veblen were indeed categorical. A common resolution of the difference between the earlier categorical axiomatizations and the more modern non-categorical axiomatizations is that the latter derive their non-categoricity from Skolem's Paradox and Godel's Incompleteness Theorems, while the former, being second order, suffer from a heavy reliance on meta-theory, where the Skolem-Godel phenomenon re-emerges. Using second-order meta-theory to avoid non-categoricity of the meta-theory would only seem to lead to an infinite regress. In this article we maintain that internal categoricity breaks with this traditional picture. It applies to both first- and second-order axiomatizations, although in the first-order case we have so far only examples. It does not depend on the meta-theory in a way that would lead to an infinite regress. It also covers the classical categoricity results of early researchers. In the first-order case it is weaker than categoricity itself, and in the second-order case stronger. We provide arguments to suggest that internal categoricity is the "right" concept of categoricity.

It is quite well-known from Kurt Godel's (1931) ground-breaking result on the Incompleteness Theorem that rudimentary relations (i.e., those definable by bounded formulae) are primitive recursive, and that primitive recursive functions are representable in sufficiently strong arithmetical theories. It is also known, though perhaps not as well-known as the former one, that some primitive recursive relations (and functions) are not rudimentary. We present a simple and elementary proof of this fact in the first part of this paper. In the second part, we review some possible notions of representability of functions studied in the literature, and give a new proof of the equivalence of the weak representability with the (strong) representability of functions in sufficiently strong arithmetical theories. Our results shed some new light on the notions of rudimentary, primitive recursive, and representable functions and relations, and clarify, hopefully, some misunderstandings and confusing errors in the literature.

While Garfinkel’s early work, captured in Studies in Ethnomethodology (Garfinkel 1967), has received a lot of attention and discussion, this has not been the case for his later work since the 1970s (e.g., Garfinkel 1986, 2002). In this paper, we critically examine the aims of Garfinkel’s later ethnomethodological studies of work programme and evaluate key ideas such as the ‘missing what’ in the sociology of work, ‘the unique adequacy requirements of methods’, and the notion of ‘hybrid studies’. We do so through a detailed engagement with a study that has frequently been singled out as exemplary by Garfinkel for his studies of work programme, namely Livingston’s (1986) The Ethnomethodological Foundations of Mathematics. We show how Livingston uses the proof of Godel’s Incompleteness Theorem as a way to exhibit the work involved in understanding mathematical proofs. We then discuss how Livingston uses this example to introduce a distinction between the written ‘proof account’ (or ‘proof description’) and the associated ‘lived work’ of working through that proof, which we argue allows Livingston to provide a powerful critique of a formalist understanding of the objectivity of mathematics. We then discuss three aspects that we find problematic in Livingston’s and Garfinkel’s claims about Livingston’s study. Firstly, we question whether written proofs are best conceived of as descriptions or accounts. Secondly, we interrogate whether an ethnomethodological study could teach mathematicians how to make discoveries. Thirdly, we throw doubt on Garfinkel’s claim that Livingston’s results are results in mathematics. We conclude this paper with a discussion of how Livingston’s study Godel’s proof highlights key tensions in Garfinkel’s later work. Firstly, we argue that there exists an ambiguity in Garfinkel’s treatment of texts as ‘incompetent’. Secondly, we show that Garfinkel’s attempt to extend his idea of classical studies from sociology to other professions and disciplines is problematic. Finally, we question Garfinkel’s proposals to reorient ethnomethodological studies away from sociological audiences and ask whether ethnomethodological studies promise the delivery of a ‘large prize’ or, rather, provide something like ‘helpful therapy’.

The article attempts to provide a rather concise overview of the life and work of Jean van Heijenoort (1912–1986) in the field of the history of logic. Information of a biographical nature is given, in which the scientist’s attitude towards Marxism is noted and his close cooperation with L.D. Trotsky in a certain period; disappointment in the key principles of the Marxist doctrine and especially its practical implementation, but the preservation of the general interest in this political trend. Based on some of the unpublished materials obtained from the American Mathematics Archive in Austin, Texas, van Heijenoort’s works in the field of the history of logic described. It is noted that he received a mathematical education as a geometer and a topologist, but his interests were transferred to logic, which, by the nature of its search for proof and the canons of reasoning, were close to geometry. Particular emphasis placed in the article on the circumstances of the work on the fundamental anthology of the development of logical thought "From Frege to Godel", compiled and commented by van Heijenoort and a number of his colleagues. Attention paid to the fact that the algebraic direction of the development of mathematical logic remains outside the anthology. We describe the works of van Heijenoort relating to the incompleteness theorem, and the first two volumes of the collected works of K. Godel in the early 1980s, interrupted by the death of van Heijenoort. The assessments of his colleagues on van Heijenoort’s legacyin the history of logic provided.

In this paper, we provide a fairly general self-reference-free proof of the second incompleteness theorem from Tarski’s theorem on the undefinability of truth.

An ultimate universal theory – a complete theory that accounts, via few and simple first principles, for all the phenomena already observed and that will ever be observed – has been, and still is, the aspiration of most physicists and scientists. Yet, a basic principle that is embodied in the results of Godel’s incompleteness theorems is that self-referencing leads to logical conflict or failure, as in the liar paradox or Russell’s paradox. In physics theories self-referencing necessarily occurs when it is realized that the observer is also a participant in the experienced phenomena – we, humans, are part of the universe while observing it. Therefore self-referencing, and consequently logical conflicts, are unavoidable, and any theory pretending to be universal is bound to be incomplete.

This is a modification as well as a model theoretic application of my previous paper Sd- Topology over the theory of a Model. The main intention of this article is to proof and visualize the celebrated Gödel’s completeness and incompleteness theorems in a different and lucid approach., AMS -MSC2010 No. 03B99

The chapter starts with an overview of information theory, how information is measured and how it is encoded in messages and transmitted. The ambiguity of coding with numeric alphabets is exposed with an analogy from computer science. An unambiguous coding is shown with reference to Godel’s incompleteness theorem.

In his famous article On formally undecidable propositions of Principia Mathematica and related systems I (1931), Godel established two results that marked a point of no return in the history of logic.

Kurt Gödel’s incompleteness theorems and the limits of knowledge In this paper a presentation is given of Kurt Gödel’s pathbreaking results on the incompleteness of formal arithmetic. Some biographical details are provided but the main focus is on the analysis of the theorems themselves. An intermediate level between informal and formal has been sought that allows the reader to get a sufficient taste of the technicalities involved and not lose sight of the philosophical importance of the results. Connections are established with the work of Alan Turing and Hao Wang to show the present-day relevance of Gödel’s research and how it relates to the limitations of human knowledge, mathematical knowledge in particular.

This chapter is about the ontology and epistemology of mathematical objects. The core problem for an empiricist is that conceiving mathematical objects as existing independently of human thinking makes it impossible to understand how we can have mathematical knowledge, while the alternative, a constructivist conception, resolves the epistemological problem, but entails the identification of truth with provability. That entails that the law of excluded middle must be dismissed as a generally valid logical principle. The identificaiton of truth with provability is furthermore problematic when taking into account Godel’s first incompleteness theorem. The chapter ends with suggesting a modified constructivism, which keeps the distinction between truth and provability, thus avoiding counter arguments based on Godel’s theorem.

This chapter starts with a discussion of the algorithmic concepts of decidability, computability, and enumerability, introduces register machines and their programs as an exact model, and presents the proof of several undecidability results: of the valid first-order sentences, of the first-order sentences valid in finite structures (Trakhtenbrot's Theorem), and of first-order arithmetic. Furthermore, Godel's incompleteness theorems are treated. Finally, the decidability of two theories is proved, of Presburger arithmetic and of the weak monadic theory of successor. For the latter some facts on finite automata are developed as far as needed.

It is a widespread belief that results like Godel’s incompleteness theorems or the intrinsic randomness of quantum mechanics represent fundamental limitations to humanity’s strive for scientific knowledge. As the argument goes, there are truths that we can never uncover with our scientific methods, hence we should be humble and acknowledge a reality beyond our scientific grasp. Here, I argue that this view is wrong. It originates in a naive form of metaphysics that sees the physical and Platonic worlds as a collection of things with definite properties such that all answers to all possible questions exist ontologically somehow, but are epistemically inaccessible. This view is not only a priori philosophically questionable, but also at odds with modern physics. Hence, I argue to replace this perspective by a worldview in which a structural notion of ‘real patterns’, not ‘things’ are regarded as fundamental. Instead of a limitation of what we can know, undecidability and unpredictability then become mere statements of undifferentiation of structure. This gives us a notion of realism that is better informed by modern physics, and an optimistic outlook on what we can achieve: we can know what there is to know, despite the apparent barriers of undecidability results.

Although there does not seem to be a direct influence of utilitarianism on David Hilbert and his School, there are some pragmatic aspects in the foundational investigations of the father of modern axiomatics and of some of his scholars that can be read in utilitarian terms. In this article, I detail these aspects, focusing on the foundational research of Hilbert throughout his career and the later methodological reflections of John von Neumann on the mathematical sciences. As for research on Hilbert, much attention is paid to the role played by the notion of success as an alternative epistemological criterion for the introduction of powerful conceptual tools within axiomatic theories, as well as for the justification of these theories in the case where consistency proofs were not available. Ironically, after the discovery of Gödel’s incompleteness theorems, success became a plain epistemological criterion for the justification of axiomatized sciences, together with all the conceptual tools contained therein. In his later foundational reflections, von Neumann, in particular, a former mathematician of Hilbert’s School, subscribed to an opportunistic methodology of science, i.e. a methodology that tried to coherently develop Hilbert’s thought on success, as well as his axiomatic reform of mathematical sciences. There seems to be, therefore, a clear evolutionary line that can be traced from Hilbert to von Neumann, which also reveals utilitarian aspects (broadly conceived) not only in science, but in axiomatics as well. Bien qu’il ne semble pas y avoir d’influence directe de l’utilitarisme sur Hilbert et son École, dans la recherche fondamentale du père de l’axiomatique moderne, comme dans celles de certains de ses élèves, il y a des aspects pragmatiques qui peuvent être lus en termes utilitaires. Dans cet article, je considère ces aspects en m’attardant sur toute la recherche fondamentale de Hilbert et sur les réflexions méthodologiques ultérieures de von Neumann sur les sciences mathématiques. Quant à Hilbert, je me concentre, en particulier, sur le rôle que la notion de succès a joué dans sa pensée comme critère épistémologique alternatif pour l’introduction d’outils conceptuels très puissants au sein de théories scientifiques construites axiomatiquement et pour la justification de ces mêmes théories dans le cas où des preuves de cohérence appropriées ne seraient pas disponibles. Étonnamment, après la découverte par Gödel des théorèmes d’incomplétude, le succès est devenu en fait un critère épistémologique pour la justification des sciences construites de manière axiomatique et des outils conceptuels qu’elles contiennent. Dans ses dernières considérations fondamentales, von Neumann, l’un des mathématiciens ayant appartenu à l’École de Hilbert dans sa jeunesse, a adopté une méthodologie opportuniste explicite de la science: une méthodologie de la science, c’est-à-dire qui cherchait à développer de manière cohérente les considérations de Hilbert sur le succès et en même temps proposer une réforme axiomatique des sciences mathématiques. Il semble donc y avoir une ligne évolutive claire qui peut être tracée de Hilbert à von Neumann et qui révèle des aspects utilitaires (au sens large) présents non seulement dans la science, mais aussi dans l’axiomatique lui-même. Sebbene non sembri esserci un’influenza diretta dell’utilitarismo su Hilbert e sulla sua Scuola, nelle ricerche fondazionali del padre dell’assiomatica moderna, come pure in quelle di alcuni suoi allievi, sono presenti aspetti pragmatici che è possibile leggere in termini utilitaristici. Nell’articolo considero questi aspetti soffermandomi sull’intera indagine fondazionale di Hilbert e sulle riflessioni metodologiche più tarde di von Neumann relativamente alle scienze matematiche. Quanto ad Hilbert, mi concentro, in particolare, sul ruolo che nel suo pensiero la nozione di successo svolgeva in quanto criterio epistemologico alternativo per l’introduzione di strumenti concettuali molto potenti all’interno di teorie scientifiche costruite in modo assiomatico e per la giustificazione di queste stesse teorie nel caso in cui non fossero state disponibili opportune dimostrazioni di coerenza. Sorprendentemente, dopo la scoperta dei teoremi di incompletezza da parte di Gödel, il successo divenne a tutti gli effetti un criterio epistemologico per la giustificazione delle scienze costruite in modo assiomatico e degli strumenti concettuali contenuti al loro interno. Nelle sue tarde considerazioni fondazionali, von Neumann, uno dei matematici che in gioventù fece parte della scuola di Hilbert, sposò un’esplicita metodologia opportunistica della scienza: una metodologia della scienza, cioè, che cercava di sviluppare in modo coerente le considerazioni di Hilbert sul successo e che proponeva nel contempo una riforma assiomatica delle scienze matematiche. Sembra così esserci una chiara linea evolutiva che può essere tracciata da Hilbert a von Neumann e che rivela aspetti utilitaristici (intesi in senso ampio) presenti non solo nella scienza, ma anche nella stessa assiomatica.

Is it possible to encompass the full extent of the universe within a theory based on a finite set of first principles and inference rules? The r\^{o}le of observers and observations in physics theories is considered here in the light of G\"{o}del's incompleteness theorem. Physics theories are the sum-total that we -- humans, scientists, physicists -- can make in interpreting our observations of the universe. We are integral part of the universe, together with our observations, therefore acts of observation are also observables and should become part of the phenomena considered by the theory, especially in view of the fact that arbitrarily chosen modes of observations may essentially determine empirical results. Incompleteness arises in G\"{o}del's theorem with self-referential propositions. Observations and interpretations are acts of referencing, and self-referencing occurs in physics whenever the observer is recognized as being part of the observed system. If self-reference appears in physics in simile to G\"{o}del's theorem, then incompleteness seems unavoidable in physics. The article discusses observers and observations as referencing in physics, culminating with the understanding that they are hierarchically inter-related so that a universal physics theory cannot be complete., Comment: 16 pages, 3 figures

The mathematical foundations of machine learning play a key role in the development of the field. They improve our understanding and provide tools for designing new learning paradigms. The advantages of mathematics, however, sometimes come with a cost. Godel and Cohen showed, in a nutshell, that not everything is provable. Here we show that machine learning shares this fate. We describe simple scenarios where learnability cannot be proved nor refuted using the standard axioms of mathematics. Our proof is based on the fact the continuum hypothesis cannot be proved nor refuted. We show that, in some cases, a solution to the ‘estimating the maximum’ problem is equivalent to the continuum hypothesis. The main idea is to prove an equivalence between learnability and compression. Not all mathematical questions can be resolved, according to Godel’s famous incompleteness theorems. It turns out that machine learning can be vulnerable to undecidability too, as is illustrated with an example problem where learnability cannot be proved nor refuted.

Este volumen de Metatheoria incluye traducciones al castellano de los tres famosos trabajos sobre las escuelas de fundamentos de la matemática, el logicismo, el intuicionismo y el formalismo, expuestos en el Simposio de Königsberg sobre Fundamentos de la Matemática en septiembre de 1930, y que fueron finalmente publicados en la revista Erkenntnis en 1931. Los tres constituyeron un hito en la filosofía de la matemática del siglo pasado. En esta introducción a las traducciones, los compiladores del volumen esbozan el contexto histórico en el cual se concibieron los trabajos originales e incluyen detalles de su publicación original. También ponen de relieve el papel decisivo que tuvieron en la filosofía de la matemática del siglo pasado. Se hace un resumen de sus contenidos, y se discuten las ideas subyacentes del Círculo de Viena acerca de la naturaleza de la matemática y el impacto de los teoremas de Gödel en los programas de fundamentos. Además, se hace una breve introducción a las contribuciones originales que siguen en el volumen a las traducciones., This volume of Metatheoria includes translations into Spanish of the three famous papers on the schools in foundations of mathematics, logicism, intuitionism and formalism, presented at the Konigsberg’s Symposium on Foundations of Mathematics in September 1930 and finally published in the journal Erkenntnis in 1931. The three papers constituted a milestone in the Philosophy of Mathematics of the last century. In this introduction to the translations, the editors of the volume outline the historical context in which the original papers were conceived and they include some details concerning their original publication. They also stress the decisive role played by the papers in the philosophy of mathematics in the last century. A summary of them is provided and the underlying ideas of the Vienna Circle on the nature of mathematics and the impact of Godel theorems in the foundations programs are discussed. Moreover, they briefly introduce the original contributions to the volume that follow the translations., Facultad de Humanidades y Ciencias de la Educación

espanolEn este trabajo se presentan algunos elementos relacionados con el enfoque o filosofia de la complejidad y su integracion con la matematica. Se describen las particularidades de los sistemas dinamicos no-lineales como sistemas complejos, hecho raiz de la nocion de ver a las matematicas como una disciplina unificadora de la ciencia: una disciplina transdisciplinar. Ademas, se entiende el Teorema de Incompletud de Kurt Godel, como una de las mas significativas razones que puede argumentar la insuficiencia teorica de la logica clasica a partir de fundamentos matematicos, ajustandose a la nocion de indecidibilidad de Murray Gell-Man, y asi, abrir las puertas a las logicas no clasicas, en particular, a la logica del tercero incluido como la logica de la complejidad. EnglishIn this paper some elements related with the focus or philosophy of the Complexity and it's integration with mathematics. Are presented particularities of the non-lineal dynamic systems as complex systems are described, that took us to the idea of seeing mathematics as a unifying discipline is science: an interdisciplinary discipline. Moreover, Kurt Godels incompleteness theorem was understood as one of the most significant reasons that we can use to talk about the theoretical insufitiencies of classical logic starting from mathematical fundaments, reaching the undecidability motion from Murray Gell-Man, to then talk about the non-classical logics, particularly the third included logic like the complexity logic.

Incompleteness theorems of Gödel, Turing, Chaitin, and Algorithmic Information Theory have profound epistemological implications. Incompleteness limits the ability of evolutionary processes to find optimal solutions.

The proofs of Kleene, Chaitin and Boolos for G\"odel's First Incompleteness Theorem are studied from the perspectives of constructivity and the Rosser property. A proof of the incompleteness theorem has the Rosser property when the independence of the true but unprovable sentence can be shown by assuming only the (simple) consistency of the theory. It is known that G\"odel's own proof for his incompleteness theorem does not have the Rosser property, and we show that neither do Kleene's or Boolos' proofs. However, we show that a variant of Chaitin's proof can have the Rosser property. The proofs of G\"odel, Rosser and Kleene are constructive in the sense that they explicitly construct, by algorithmic ways, the independent sentence(s) from the theory. We show that the proofs of Chaitin and Boolos are not constructive, and they prove only the mere existence of the independent sentences., Comment: 12 pages -- to appear in the Annals of Pure and Applied Logic

Self-reference has played a prominent role in the development of metamathematics in the past century, starting with Gödel’s first incompleteness theorem. Given the nature of this and other results in the area, the informal understanding of self-reference in arithmetic has sufficed so far. Recently, however, it has been argued that for other related issues in metamathematics and philosophical logic a precise notion of self-reference and, more generally, reference is actually required. These notions have been so far elusive and are surrounded by an aura of scepticism that has kept most philosophers away. In this paper I suggest we shouldn’t give up all hope. First, I introduce the reader to these issues. Second, I discuss the conditions a good notion of reference in arithmetic must satisfy. Accordingly, I then introduce adequate notions of reference for the language of first-order arithmetic, which I show to be fruitful for addressing the aforementioned issues in metamathematics.

In this article I am going to argue for the possibility of a transcendental source of logic based on a phenomenologically motivated approach. My aim will be essentially carried out in two succeeding steps of reduction: the first one will be the indication of existence of an inherent temporal factor conditioning formal predicative discourse and the second one, based on a supplementary reduction of objective temporality, will be a recourse to a time-constituting origin which has to be assumed as a non-temporal, transcendental subjectivity and for that reason as possibly the ultimate transcendental root of pure logic. In the development of the argumentation and taking into account W.V. Quine’s views in his well-known Word and Object, a special emphasis will be given to the fundamentally temporal character of universal and existential predicative forms, to their status in logical theories in general, and to their underlying role in generating an inherently non-finitistic character reflected, for instance, in the undecidability of certain infinity statements in formal mathematical theories. This is shown also to concern metatheorems of such vital importance as Godel’s incompleteness theorems in mathematical foundations. Moreover in the course of the discussion the quest for the ultimate limits of predication will lead to the notions of separation and intentional correlation between an ‘observing’ subject and the object of ‘observation’ as well as to the notion of syntactical individuals taken as the irreducible non-analytic nuclei-forms within analytical discourse.

The subject matter of this research is Kant’s apriorism underlying Hilbert’s formalism in the philosophical grounding of mathematics as a self-sufficing system. The research aim is the invention of such a logically formalized axiomatic epistemology system, in which it is possible to construct formal deductive inferences of formulae—modeling the formalism ideal of Hilbert—from the assumption of Kant’s apriorism in relation to mathematical knowledge. The research method is hypothetical–deductive (axiomatic). The research results and their scientific novelty are based on a logically formalized axiomatic system of epistemology called Σ + C, constructed here for the first time. In comparison with the already published formal epistemology systems Ξ and Σ, some of the axiom schemes here are generalized in Σ + C, and a new symbol is included in the object-language alphabet of Σ + C, namely, the symbol representing the perfection modality, C: “it is consistent that…”. The meaning of this modality is defined by the system of axiom schemes of Σ + C. A deductive proof of the consistency of Σ + C is submitted. For the first time, by means of Σ + C, it is deductively demonstrated that, from the conjunction of Σ + C and either the first or second version of Gödel’s theorem of incompleteness of a formal arithmetic system, the formal arithmetic investigated by Gödel is a representation of an empirical knowledge system. Thus, Kant’s view of mathematics as a self-sufficient, pure, a priori knowledge system is falsified.

The paper examines Husserl’s interactions with logicians in the 1930s in order to assess Husserl’s awareness of Gödel’s incompleteness theorems. While there is no mention about the results in Husserl’s known exchanges with Hilbert, Weyl, or Zermelo, the most likely source about them for Husserl is Felix Kaufmann (1895–1949). Husserl’s interactions with Kaufmann show that Husserl may have learned about the results from him, but not necessarily so. Ultimately Husserl’s reading marks on Friedrich Waismann’s Einführung in das mathematische Denken: die Begriffsbildung der modernen Mathematik, 1936, show that he knew about them before his death in 1938.

Gödel introduced the original provability predicate in the proofs of Gödel’s incompleteness theorems, and Rosser defined a new one. They are equivalent in the standard model ${\mathbb N}$ of arithmetic or any nonstandard model of ${\rm PA} + {\rm Con_{PA}} $, but the behavior of Rosser’s provability predicate is different from the original one in nonstandard models of ${\rm PA} + \neg {\rm Con_{PA}} $. In this paper, we investigate several properties of the derivability conditions for Rosser provability predicates, and prove the existence of a Rosser provability predicate with which we can define any consistent complete extension of ${\rm PA}$ in some nonstandard model of ${\rm PA} + \neg {\rm Con_{PA}} $. We call it a universal Rosser predicate. It follows from the theorem that the true arithmetic ${\rm TA}$ can be defined as the set of theorems of ${\rm PA}$ in terms of a universal Rosser predicate in some nonstandard model of ${\rm PA} + \neg {\rm Con_{PA}} $. By using this theorem, we also give a new proof of a theorem that there is a nonstandard model M of ${\rm PA} + \neg {\rm Con_{PA}} $ such that if N is an initial segment of M which is a model of ${\rm PA} + {\rm Con_{PA}} $ then every theorem of ${\rm PA}$ in N is a theorem of $\rm PA$ in ${\mathbb N}$. In addition, we prove that there is a Rosser provability predicate such that the set of theorems of $\rm PA$ in terms of the Rosser provability predicate is inconsistent in any nonstandard model of ${\rm PA} + \neg {\rm Con_{PA}} $.

The aim of this paper is to review some basic ideas, concepts, and questions of today's theoretical biology and stimulate reflection on them. Possible sources of misunderstanding, confusion, and disagreement in the discussion of the foundation of biology are outlined. Major attention is given to different interpretations (and implications) of the term “explanation” and “living system.” It is argued that the concepts of present day's physics are not general enough to describe biology. As examples of possible new concepts “complexity” and “creativity” are discussed. Different definitions of “living systems” and their flaws are reviewed. It is concluded that an explanation of a living system involves both, an understanding of its parts and of the organization of these parts. This leads to a discussion of the role of quantum mechanics and non-equilibrium statistical thermodynamics in biology. Finally, the implications of some philosophical points of view and the role of Godel's incompleteness theorem in a basic theory of biology are discussed.

Historically, mathematics has often been regarded as a role model for all of science—a paragon of abstraction, logical precision, and objectivity. The 19th and early 20th centuries saw tremendous progress. The great mathematician David Hilbert proposed a sweeping program whereby the entire panorama of higher mathematical abstractions would be justified objectively and logically, in terms of finite processes. But then in 1931 the great logician Kurt Godel published his famous incompleteness theorems, leading to an era of confusion and skepticism. In this talk I show how modern foundational research has opened a new path toward objectivity and optimism in mathematics.1

It follows from Godel's Completeness Theorem that a theory is consistent if and only if it has a model. In particular, the consistency of Peano Arithmetic follows from \(\mathbb{N} \models \mathbf{PA}\).

This short and informal article shows that, although Godel's theorem is valid using classical logic, there exists some four-valued logical system that is able to prove that arithmetic is both sound and complete. This article also describes a four-valued Prolog in some informal, brief and intuitive manner.

This paper surveys the interactions between Russell and Gödel, both personal and intellectual. After a description of Russell’s influence on Gödel, it concludes with a discussion of Russell’s reaction to the incompleteness theorems.

Series of attempts have been made to find a sufficient account of the nature of mental states. Functionalism took up the baton and Putnam attempted to use a computational means as a potent analogy to describing the nature of the nature of mental states as a physical component of the world. Putnam discovered that to be consistent on the question, an equivalent relation between a functional state and a corresponding environmental evidence is necessary. But he concludes that no intelligent or non-intelligent agent could discover this. This is because of the conflicting and innumerable nature of the possible environmental evidences. However, even if it were possible, there is the Godel’s Incompleteness Theorem. That is to be able to justify every other proposition in the universe, there must remain some proposition which is not justified. Therefore, computation becomes arbitrary and trivial because there is no means of establishing the equivalent relation and even to justify it. In all of these, the potent question remains; what is the nature of mental states?Keywords: Physicalism, Functionalism, Equivalent Relation, Mental states, Machine States

An idea attributable to Russell serves to extend Zermelo's theory of systems of infinitely long propositions to infinitary relations. Specifically, relations over a given domain $${\mathfrak{D}}$$D of individuals will now be identified with propositions over an auxiliary domain $${\mathfrak{D}^{\mathord{\ast}}}$$D* subsuming $${\mathfrak{D}}$$D. Three applications of the resulting theory of infinitary relations are presented. First, it is used to reconstruct Zermelo's original theory of urelements and sets in a manner that achieves most, if not all, of his early aims. Second, the new account of infinitary relations makes possible a concise characterization of parametric definability with respect to a purely relational structure. Finally, based on his foundational philosophy of the primacy of the infinite, Zermelo rejected Godel's First Incompleteness Theorem; it is shown that the new theory of infinitary relations can be brought to bear, positively, in that connection as well.

On Three Appearances of Difference in Mathematics. This article proposes to examine three types of relations between man and equality, as they are embodied in the relation to the minimal condition of the mathematical: the sentence of identity: I=I. Starting our examination from the current common conception of science and mechanism, we aim to reveal that behind the dominating logic of identity there are two other systems of logic, which have arisen during the history of humanity and that of mathematics. Following Serres, the first one might be revealed during the passage from the Babylonian mathematics to the interaction between Thales and the Greek gnomon. The Babylonian epoch marks an era, in which the logic of sameness operates; logic which offers a place for the mathematician. This era is followed by a science, working under the second logic: the logic of identity, which consecrates an axiomatic definition-based approach, at the expense of the human being. The third logic looms after the discovery of Godel's incompleteness theorems: that an undecidable statement can be derived within every arithmetical system. Under this logic, the roles of man and the allegedly mathematical automatic machine become even more intertwined: the newly found logic promises instability not only for man, but also for the machinic-mathematics.

In a note appended to the translation of “On consistency and completeness” (1967), Godel reexamined the problem of the unprovability of consistency. Godel here focuses on an alternative means of expressing the consistency of a formal system, in terms of what would now be called a ‘reflection principle’, roughly, the assertion that a formula of a certain class is provable in the system only if it is true. Godel suggests that it is this alternative means of expressing consistency that we should be interested in from a foundational point of view, and he gives a result that shows certain reflection principles to be underivable in extensions of elementary number theory under conditions significantly weaker than the Hilbert-Bernays derivability conditions. In this paper I shall discuss the background to Godel's result and the foundational significance he claims for it. Along the way, I shall present a new proof of the result which places it in an even more general context than the one considered by Godel in the 1960s.