Search

We prove the equivalence of the semantic version of Tarski's theorem on the undefinability of truth with a semantic version of the Diagonal Lemma, and also show the equivalence of syntactic 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 syntactic Tarski's theorem can deliver G\"odel-Rosser's Incompleteness Theorem., Comment: 8 pages

The work seeks to elucidate and understand relevant aspects in the structure of paradoxical undecidable sentences in consistent formal systems that contain Dedekind-Peano Arithmetic. The first chapter exposes the investigations and advances in Mathematics and Logic associated and the philosophical conceptions that culminated in Kurt Gödel's First Incompleteness Theorem, published in his article Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I, in 1931. We will make a historical and conceptual approach to Mathematics from the second half of the 19th century to the first half of the 20th century with its main lines of thought, indicating the mathematical elements and instruments developed to solve certain problems, as well as philosophical assumptions and commitments that accompanied the activities aimed at the formalization and foundation of contemporary Mathematical Logic that helped Gödel to elaborate his demonstration and to explain limitations of such formal systems. The second chapter aims to analyze the components and expose or elaborate formalized undecidable sentences based on paradoxes considered epistemic or semantic. Will be discussed paradoxes expressed implicitly and explicitly in the structure of undecidable sentences. We approaching similarities and distinctions of both finite and infinite undecidable sentences, seeking to understand the proofs and phenomena that lead to the incompleteness of formal systems that contains Dedekind- Peano Arithmetic. Soon after, the third chapter will focus on the application of Algorithmic Information Theory developed by Gregory Chaitin to demonstrate a discussed version of incompleteness of formal systems based on Berry's Paradox. The critical literature on this information-theoretic version will be resumed, as well as an analysis based on the sentences seen above, carrying out a scrutiny of the justifications and definitions used in Chaitin's proof. At the end, we open a discussion about the nature of incompleteness associated with the notion of computability and the limits of finite mechanical processes. O trabalho busca elucidar e compreender aspectos relevantes na estrutura das sentenças indecidíveis paradoxais em sistemas formais consistentes que contenham a Aritmética de Dedekind-Peano. O primeiro capítulo expõe as investigações e avanços na Matemática e na Lógica associadas às concepções filosóficas que culminaram no Primeiro Teorema da Incompletude de Kurt Gödel, publicado em seu artigo Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I, em 1931. Para isso, faremos uma abordagem histórica e conceitual da Matemática da segunda metade do século XIX até a primeira metade do século XX com suas linhas de pensamento principais, indicando os elementos e instrumentos matemáticos desenvolvidos para solução de certos problemas, assim como pressupostos e compromissos filosóficos que acompanharam as atividades voltadas à formalização e fundamentação da Lógica Matemática contemporânea que auxiliaram Gödel a elaborar sua demonstração e explicitar as limitações de tais sistemas formais. O segundo capítulo tem como objetivo analisar os componentes e expor ou elaborar sentenças indecidíveis formalizadas baseadas em paradoxos considerados epistêmicos ou semânticos. Serão discutidos paradoxos expressos de forma implícita e explícita na estrutura das sentenças indecidíveis, abordando semelhanças e distinções tanto de sentenças indecidíveis finitárias quanto infinitárias, procurando entender as provas e fenômenos que levam a incompletude de sistemas que contêm a Aritmética de Dedekind-Peano. Logo após, o terceiro capítulo terá foco na aplicação da Teoria Algorítmica da Informação desenvolvida por Gregory Chaitin para demonstrar uma discutida versão da incompletude de sistemas formais baseada no Paradoxo de Berry. Será retomada a literatura crítica a tal versão teorético-informacional, bem como feita uma análise com base nas sentenças vistas anteriormente, realizando-se um escrutínio acerca das justificativas e definições utilizadas na prova de Chaitin. Ao final, abrimos uma discussão acerca da natureza da incompletude associada a incomputabilidade e os limites de processos computáveis finitos.

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 study the computational power of randomized computations on infinite objects, such as real numbers. In particular, we introduce the concept of a Las Vegas computable multi-valued function, which is a function that can be computed on a probabilistic Turing machine that receives a random binary sequence as auxiliary input. The machine can take advantage of this random sequence, but it always has to produce a correct result or to stop the computation after finite time if the random advice is not successful. With positive probability the random advice has to be successful. We characterize the class of Las Vegas computable functions in the Weihrauch lattice with the help of probabilistic choice principles and Weak Weak K\H{o}nig's Lemma. Among other things we prove an Independent Choice Theorem that implies that Las Vegas computable functions are closed under composition. In a case study we show that Nash equilibria are Las Vegas computable, while zeros of continuous functions with sign changes cannot be computed on Las Vegas machines. However, we show that the latter problem admits randomized algorithms with weaker failure recognition mechanisms. The last mentioned results can be interpreted such that the Intermediate Value Theorem is reducible to the jump of Weak Weak K\H{o}nig's Lemma, but not to Weak Weak K\H{o}nig's Lemma itself. These examples also demonstrate that Las Vegas computable functions form a proper superclass of the class of computable functions and a proper subclass of the class of non-deterministically computable functions. We also study the impact of specific lower bounds on the success probabilities, which leads to a strict hierarchy of classes. In particular, the classical technique of probability amplification fails for computations on infinite objects. We also investigate the dependency on the underlying probability space., Comment: Information and Computation (accepted for publication)

In this paper we study the behavior of computable series of computable partial functions with varying domains (but each domain containing all computable points), and prove that the sum of the series exists and is computable exactly on the intersection of the domains when a certain computable Cauchyness criterion is met. In our point-free approach, we name points via nested sequences of basic open sets, and thus our functions from a topological space into the reals are generated by functions from basic open sets to basic open sets. The construction of a function that produces the sum of a series requires working with an infinite array of pairs of basic open sets, and reconciling the varying domains. We introduce a general technique for using such an array to produce a set function that generates a well-defined point function and apply the technique to a series to establish our main result. Finally, we use the main finding to construct a computable, and thus continuous, function whose domain is of Lebesgue measure zero and which is nonextendible to a continuous function whose domain properly includes the original domain. (We had established existence of such functions with domains of measure less than e for any ɛ>0, in an earlier paper.)

We prove in a uniform way that the following lattices have no computable presentations: the lattice of all computable order theoretic automorphisms of the rational numbers; the lattice of the computable functions from the rational numbers to the rational numbers having continuous extensions to functions on the real numbers; and the lattice of the monotonic functions on the natural numbers. Nevertheless, we prove that the lattice of all computable mappings from the rational numbers to the rational numbers has a computable presentation.

We solve a longstanding question of Rosenstein, and make progress toward solving a long-standing open problem in the area of computable linear orderings by showing that every computable η-like linear ordering without an infinite strongly η-like interval has a computable copy without nontrivial computable self-embedding.The precise characterization of those computable linear orderings which have computable copies without nontrivial computable self-embedding remains open.

We study computable linear orders with computable neighborhood and block predicates. In particular, it is proved that there exists a computable linear order with a computable neighborhood predicate, having a Π 1 0 -initial segment which is isomorphic to no computable order with a computable neighborhood predicate. On the other hand, every Σ 1 0 -initial segment of such an order has a computable copy enjoying a computable neighborhood predicate. Similar results are stated for computable linear orders with a computable block predicate replacing a neighborhood relation. Moreover, using the results obtained, we give a simpler proof for the Coles–Downey–Khoussainov theorem on the existence of a computable linear order with Π 2 0 -initial segment, not having a computable copy.

In the general context of computable metric spaces and computable measures we prove a kind of constructive Borel–Cantelli lemma: given a sequence (constructive in some way) of sets Ai with effectively summable measures, there are computable points which are not contained in infinitely many Ai.As a consequence of this we obtain the existence of computable points which follow the typical statistical behavior of a dynamical system (they satisfy the Birkhoff theorem) for a large class of systems, having computable invariant measure and a certain “logarithmic” speed of convergence of Birkhoff averages over Lipschitz observables. This is applied to uniformly hyperbolic systems, piecewise expanding maps, systems on the interval with an indifferent fixed point and it directly implies the existence of computable numbers which are normal with respect to any base.

In the representation approach (TTE) to computable analysis, the representations of an algebraic or topological structure for which the basic predicates and functions become computable are of particular interest. There are, however, many predicates (like equality of real numbers) and functions that areabsolutely non-computable, that is, not computable for any representation. Many of these results can be deduced from a simple lemma. In this article we prove this lemma for multi-representations and apply it to a number of examples. As applications, we show that various predicates and functions on computable measure spaces are absolutely non-computable. Since all the arguments are topological, we prove that the predicates are not relatively open and the functions are not relatively continuous for any multi-representation.

We introduce and study the notions of computable formal context and computable formal concept. We give some examples of computable formal contexts in which the computable formal concepts fail to form a lattice and study the complexity aspects of formal concepts in computable contexts. In particular, we give some sufficient conditions under which the computability or noncomputability of a formal concept could be recognized from its lattice-theoretic properties. We prove the density theorem showing that in a Cantor-like topology every formal concept can be approximated by computable ones. We also show that not all formal concepts have lattice-theoretic approximations as suprema or infima of families of computable formal concepts.

P. Hertling [Lecture Notes in Computer Science, vol. 2380, Springer, Berlin, 2002, pp. 962–972; Ann. Pure Appl. Logic 132 (2005) 227–246] showed that there exists a sequentially computable function mapping all computable real numbers to computable real numbers that is not effectively continuous. Here, that result is strengthened: a sequentially computable function on the computable real numbers is constructed that is not effectively continuous at any point.

We study computable Boolean algebras with distinguished ideals (I-algebras for short). We prove that the isomorphism problem for computable I-algebras is Σ 1 1 -complete and show that the computable isomorphism problem and the computable categoricity problem for computable I-algebras are Σ 3 0 -complete.

We give some information about new proofs of the incompleteness theorems, found in 1990s. Some of them do not require the diagonal lemma as a method of construction of an independent statement.

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.

is a theorem of Robinson's Arithmetic. It has been argued, for example by Maitzen (1998), that the Knower should be resolved by giving up epistemic closure.3 For our formulation of the Knower, this would mean giving up K3. In Cross 2001a I introduced a new version of the Paradox of the Knower, namely the Paradox of the Knowledge-Plus Knower, and I used this new paradox to argue that the Knower does not constitute a cogent argument against epistemic closure. The Paradox of the Knowledge-Plus Knower is based on an application of the Diagonal Lemma to a predicate K' defined as follows in terms of the knowledge predicate K

We investigate the effects of adding uniformity requirements to concepts in computable structure theory such as computable categoricity (of a structure) and intrinsic computability (of a relation on a computable structure). We consider and compare two different notions of uniformity, previously studied by Kudinov and by Ventsov. We discuss some of their results and establish new ones, while also exploring the connections with the relative computable structure theory of Ash, Knight, Manasse, and Slaman and Chisholm and with previous work of Ash, Knight, and Slaman on uniformity in a general computable structure-theoretical setting.

In effective analysis, various classes of real numbers are discussed. For example, the classes of computable, semi-computable, weakly computable, recursively approximable real numbers, etc. All these classes correspond to some kind of (weak) computability of the real numbers. In this paper we discuss mathematical closure properties of these classes under the limit, effective limit and computable function. Among others, we show that the class of weakly computable real numbers is not closed under effective limit and partial computable functions while the class of recursively approximable real numbers is closed under effective limit and partial computable functions.

In many classes of structures, each computable structure has computable dimension 1 or $\omega$. Nevertheless, Goncharov showed that for each $n < \omega$, there exists a computable structure with computable dimension $n$. In this paper we show that, under one natural definition of relativized computable dimension, no computable structure has finite relativized computable dimension greater than 1.

A nonconstructive proof can be used to prove the existence of an object with some properties without providing an explicit example of such an object. A special case is a probabilistic proof where we show that an object with required properties appears with some positive probability in some random process. Can we use such arguments to prove the existence of a computable infinite object? Sometimes yes: following [8], we show how the notion of a layerwise computable mapping can be used to prove a computable version of Lov\'asz local lemma. (A survey of Moser-Tardos proof is included to make the paper self-contained.), Comment: 10 pages. arXiv admin note: substantial text overlap with arXiv:1012.0557

In this paper we introduce the notion of relative computability for continuous real valued functions. It combines the notion of relative recursiveness for number theoretic functions with the theory of computability for continuous real valued functions. Most of the space is devoted to investigating the degrees of unsolvability of those mathematical operations which lead from the computable to the noncomputable. The paper concludes with Theorem 5, which asserts that the derivatives of computable C1 functions on compact intervals are at most semi-computable.

We prove that any 1-closed (see def 1.1) model of the Π2 consequences of PA satisfies ¬Cons PA which gives a proof of the second Gödel incompleteness theorem without the use of the Gödel diagonal lemma. We prove a few other theorems by the same method.

In a lecture manuscript written around 1961 (Gödel *1961/?), Gödel describes a philosophical path from the incompleteness theorems to Husserl's phenomenology. It is known that Gödel began to study Husserl's work in 1959 and that he continued to do so for many years. During the 1960s, for example, he recommended the sixth investigation of Husserl's Logical Investigations to several logicians for its treatment of categorial intuition (Wang 1997, p. 164). While Gödel may not have been satisfied with what he was able to obtain from philosophy and Husserl's phenomenology, he nonetheless continued to recommend Husserl's work to logicians as late as the 1970s. In this paper I present and discuss the kinds of arguments that led Gödel to the work of Husserl. Among other things, this should help to shed additional light on Gödel's philosophical and scientific ideas and to show to what extent these ideas can be viewed as part of a unified philosophical outlook. Some of the arguments that led Gödel to Husserl's work are only hinted at in Gödel's 1961 paper, but they are developed in much more detail in Gödel's earlier philosophical papers (see especially 1934, *193?, 1944, 1947, *1951, *1953/59). In particular, I focus on arguments concerning Hilbert's program and an early version of Carnap's program.§1. Some ideas from phenomenology. Since Husserl's work is not generally known to mathematical logicians, it may be helpful to mention briefly a few details about his background.

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.

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 Godel’s methods. On the other hand, Godel was aware of the formal undefinability of truth in 1931, but he did not publish this result. Reasons for that are also considered

Theorem 6.3, our first shot at an incompleteness theorem, applies to sound theories. But we have already remarked in Section 1.2 that Godel's arguments show that we don't need to assume soundness to prove incompleteness. In this chapter we see how to argue from consistency to incompleteness. But if we are going to weaken one assumption (from soundness to mere consistency) we'll need to strengthen another assumption: we'll now consider theories that don't just express enough but which can capture , i.e. prove , enough. Starting in Chapter 10, we'll begin examining various formal theories of arithmetic ‘from the bottom up’, in the sense of first setting down the axioms of the theories and then exploring what the different theories are capable of proving. For the moment, however, we are continuing to proceed the other way about. In the previous chapter, we considered theories that have sufficiently expressive languages, and so can express what we'd like any arithmetic to be able to express. Now we introduce the companion concept of a sufficiently strong theory, which is one that by definition can prove what we'd like any moderately competent theory of arithmetic to be able to prove about decidable properties of numbers. We then establish some easy but deep results about such theories. The idea of a ‘sufficiently strong’ theory Suppose that P is some effectively decidable property of numbers, i.e. one for which there is an algorithmic procedure for deciding, given a natural number n , whether n has property P or not.

When can a model of a physical system be regarded as computable? We provide the definition of a computable physical model to answer this question. The connection between our definition and Kreisel's notion of a mechanistic theory is discussed, and several examples of computable physical models are given, including models which feature discrete motion, a model which features non-discrete continuous motion, and probabilistic models such as radioactive decay. We show how computable physical models on effective topological spaces can be formulated using the theory of type-two effectivity (TTE). Various common operations on computable physical models are described, such as the operation of coarse-graining and the formation of statistical ensembles. The definition of a computable physical model also allows for a precise formalization of the computable universe hypothesis--the claim that all the laws of physics are computable.

We study closed choice principles for different spaces. Given information about what does not constitute a solution, closed choice determines a solution. We show that with closed choice one can characterize several models of hypercomputation in a uniform framework using Weihrauch reducibility. The classes of functions which are reducible to closed choice of the singleton space, the natural numbers, Cantor space and Baire space correspond to the class of computable functions, functions computable with finitely many mind changes, weakly computable functions and effectively Borel measurable functions, respectively. We also prove that all these classes correspond to classes of non-deterministically computable functions with the respective spaces as advice spaces. The class of limit computable functions can be characterized with parallelized choice of natural numbers. On top of these results we provide further insights into algebraic properties of closed choice. In particular, we prove that closed choice on Euclidean space can be considered as “locally compact choice” and it is obtained as product of closed choice on the natural numbers and on Cantor space. We also prove a Quotient Theorem for compact choice which shows that single-valued functions can be “divided” by compact choice in a certain sense. Another result is the Independent Choice Theorem, which provides a uniform proof that many choice principles are closed under composition. Finally, we also study the related class of low computable functions, which contains the class of weakly computable functions as well as the class of functions computable with finitely many mind changes. As a main result we prove a uniform version of the Low Basis Theorem that states that closed choice on Cantor space (and the Euclidean space) is low computable. We close with some related observations on the Turing jump operation and its initial topology.

So far we have considered only finite sets of clauses. But as we will see in the second part of this course, infinite sets play an important role. Therefore we extend the notion of satisfiability as follows: Satisfaction of an infinite set of clauses. Let S be a (finite or infinite) set of clauses. Let V ar (S) denote the set of variables that occur in the clauses of S. Then an assignment α is suitable for S if the domain of α contains V ar (S). We say that α satisfies S, and write $$\alpha \vDash S,$$ if it satisfies each clause of S; S is unsatisfiable if no assignment satisfies it.

The determinism-free will debate is perhaps as old as philosophy itself and has been engaged in from a great variety of points of view including those of scientific, theological, and logical character. This chapter focuses on two arguments from logic. First, there is an argument in support of determinism that dates back to Aristotle, if not farther. It rests on acceptance of the Law of Excluded Middle, according to which every proposition is either true or false, no matter whether the proposition is about the past, present or future. In particular, the argument goes, whatever one does or does not do in the future is determined in the present by the truth or falsity of the corresponding proposition. The second argument coming from logic is much more modern and appeals to Gödel's incompleteness theorems to make the case against determinism and in favour of free will, insofar as that applies to the mathematical potentialities of human beings. The claim more precisely is that as a consequence of the incompleteness theorems, those potentialities cannot be exactly circumscribed by the output of any computing machine even allowing unlimited time and space for its work. The chapter concludes with some new considerations that may be in favour of a partial mechanist account of the mathematical mind.