Search

In this paper, we study the metamathematics of consistent arithmetical theories |$T$| (containing |$\textsf {I}\varSigma _{1}$|⁠); we investigate numerical properties based on proof predicates that depend on numerations of the axioms. Numeral Completeness. For every true (in |$\mathbb {N}$|⁠) sentence |$\vec {Q}\vec {x}.\varphi (\vec {x})$|⁠ , with |$\varphi (\vec {x})$| a |$\varSigma _{1}(\textsf {I}\varSigma _1)$| -formula, there is a numeration |$\tau $| of the axioms of |$T$| such that |$\textsf {I}\varSigma _1\vdash \vec {Q}\vec {x}. \texttt {Pr}_{\tau }(\ulcorner \varphi (\overset {\text{.} }{\vec {x}})\urcorner)$|⁠ , where |$\texttt {Pr}_{\tau }$| is the provability predicate for the numeration |$\tau $|⁠. Numeral Consistency. If |$T$| is consistent, there is a |$\varSigma _{1}(\textsf {I}\varSigma _1)$| -numeration |$\tau $| of the axioms of |$\textsf {I}\varSigma _{1}$| such that |$\textsf {I}\varSigma _1\vdash \forall\, x. \texttt {Pr}_{\tau }(\ulcorner \neg \textit {Prf}(\ulcorner \perp \urcorner , \overset {\text{.}}{x})\urcorner)$|⁠ , where |$\textit {Prf}(x,y)$| denotes a |$\varDelta _{1}(\textsf {I}\varSigma _1)$| -definition of ' |$y$| is a |$T$| -proof of |$x$| '. Finitist consistency is addressed by generalizing a result of Artemov: Partial finitism. If |$T$| is consistent, there is a primitive recursive function |$f$| such that, for all |$n\in \mathbb {N}$|⁠ , |$f(n)$| is the code of an |$\textsf {I}\varSigma _{1}$| -proof of |$\neg\, \textit{Prf}(\ulcorner \perp \urcorner ,\overline {n})$|⁠. These results are not in conflict with Gödel's Incompleteness Theorems. Rather, they allow to extend their usual interpretation and show a deep connection to reflections in Hilbert's last papers of 1931. [ABSTRACT FROM AUTHOR]

The basic axioms or formal conditions of decision theory, especially the ordering condition put on preferences and the axioms underlying the expected utility (EU) formula, are subject to a number of counter-examples, some of which can be endowed with normative value and thus fall within the ambit of a philosophical reflection on practical rationality. Against such counter-examples, a defensive strategy has been developed which consists in redescribing the outcomes of the available options in such a way that the threatened axioms or conditions continue to hold. We examine how this strategy performs in three major cases: Sen's counterexamples to the binariness property of preferences, the Allais paradox of EU theory under risk, and the Ellsberg paradox of EU theory under uncertainty. We find that the strategy typically proves to be lacking in several major respects, suffering from logical triviality, incompleteness, and theoretical insularity (i.e., being cut off from the methods and results of decision theory). To give the strategy more structure, philosophers have developed "principles of individuation"; but we observe that these do not address the aforementioned defects. Instead, we propose the method of checking whether the strategy can overcome its typical defects once it is given a proper theoretical expansion (i.e., it is duly developed using the available tools of decision theory). We find that the strategy passes the test imperfectly in Sen's case and not at all in Allais's. In Ellsberg's case, however, it comes close to meeting our requirement. But even the analysis of this more promising application suggests that the strategy ought to address the decision problem as a whole, rather than just the outcomes, and that it should extend its revision process to the very statements it is meant to protect. Thus, by and large, the same cautionary tale against redescription practices runs through the analysis of all three cases. A more general lesson, simply put, is that there is no easy way out from the paradoxes of decision theory. [ABSTRACT FROM AUTHOR]

Copyright of Procesos de Mercado is the property of Procesos de Mercado. Revista Europea de Economia Politica and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Why is it that even strong formal theories of truth fail to prove their own consistency? Although Field (Mind, 115, 459, 2006) has addressed this question for many theories of truth, I argue that there is an important and attractive class of theories of truth that he omitted in his analysis. Such theories cannot prove that all their axioms are true, though unlike many of the cases Field considers, they do not prove that any of their axioms are false or that any of their rules of inference are not truth preserving. I argue that it is the fact that such theories are not finitely axiomatizable that stops them from proving their own consistency. [ABSTRACT FROM AUTHOR]

This paper brings up some important points about logic, e.g., mathematical logic, and also an inconsistence in logic as per Gödel's incompleteness theorems which state that there are mathematical truths that are not decidable or provable. These incompleteness theorems have shaken the solid foundation of mathematics where innumerable proofs and theorems have a place of pride. The great mathematician David Hilbert had been much disturbed by them. There are much long unsolved famous conjectures in mathematics, e.g., the twin primes conjecture, the Goldbach conjecture, the Riemann hypothesis, etc. Perhaps, by Gödel's incompleteness theorems the proofs for these famous conjectures will not be possible and the numerous mathematicians attempting to find the solutions for these conjectures are simply banging their heads against the metaphorical wall. Besides mathematics, Gödel's incompleteness theorems will have ramifications in other areas involving logic. This paper looks at the ramifications of the incompleteness theorems, which pose the serious problem of inconsistency, and offers a solution to this dilemma. The paper also looks into the apparent inconsistence of the axiomatic method in mathematics. [ABSTRACT FROM AUTHOR]

By a well-known result of Kotlarski et al. (1981), first-order Peano arithmetic P A can be conservatively extended to the theory C T - [ PA ] of a truth predicate satisfying compositional axioms, i.e., axioms stating that the truth predicate is correct on atomic formulae and commutes with all the propositional connectives and quantifiers. This result motivates the general question of determining natural axioms concerning the truth predicate that can be added to C T - [ PA ] while maintaining conservativity over P A . Our main result shows that conservativity fails even for the extension of C T - [ PA ] obtained by the seemingly weak axiom of disjunctive correctness D C that asserts that the truth predicate commutes with disjunctions of arbitrary finite size. In particular, C T - [ PA ] + DC implies Con (PA) . Our main result states that the theory C T - [ PA ] + DC coincides with the theory C T 0 [ PA ] obtained by adding Δ 0 -induction in the language with the truth predicate. This result strengthens earlier work by Kotlarski (1986) and Cieśliński (2010). For our proof we develop a new general form of Visser's theorem on non-existence of infinite descending chains of truth definitions and prove it by reduction to (Löb's version of) Gödel's second incompleteness theorem, rather than by using the Visser–Yablo paradox, as in Visser's original proof (1989). [ABSTRACT FROM AUTHOR]

In Gödel’s Incompleteness Theorems, for every mathematical system there are correct statements that cannot be proven to be correct within that system. We here extend this to address the question of axiomatic statements that are perceived (or known) to be correct but which mathematics, as presently constituted, cannot prove. We refer to these as perceptual axioms. [ABSTRACT FROM AUTHOR]

Motivated by the problem of finding finite versions of classical incompleteness theorems, we present some conjectures that go beyond NP ≠ coNP. These conjectures formally connect computational complexity with the difficulty of proving some sentences, which means that high computational complexity of a problem associated with a sentence implies that the sentence is not provable in a weak theory, or requires a long proof. Another reason for putting forward these conjectures is that some results in proof complexity seem to be special cases of such general statements and we want to formalize and fully understand these statements. Roughly speaking, we are trying to connect syntactic complexity, by which we mean the complexity of sentences and strengths of the theories in which they are provable, with the semantic concept of complexity of the computational problems represented by these sentences. We have introduced the most fundamental conjectures in our earlier works [27, 33–35]. Our aim in this article is to present them in a more systematic way, along with several new conjectures, and prove new connections between them and some other statements studied before. [ABSTRACT FROM AUTHOR]

Big data have revealed unexpected and statistically significant correlations along with intractable propositions. In order to address this development, an algorithm is introduced that is consistent with Ramsey's theorem for pairs and G¨odel's incompleteness theorem. The algorithm assigns one of three truth values to a fuzzy proposition in order to update automatic theorem proving. A unique feature of the algorithm is an AI module that selects the multiple axiom sets needed for a proof. A metric for the AI module is the probability that the database of axiom sets is inadequate for the context. The importance of context is illustrated by a simple analog electrical circuit applied to Fermat's last theorem as contrasted with a similar exponential equation having positive real numbers for bases. Another algorithm or decision tree is introduced to differentiate risk factors from necessary conditions. A failure to recognize this distinction has impaired the public health sector for centuries and continues to do so. The second algorithm introduced here represents an effort to conserve science in general. The risk that big data pose for science is the misuse of positive, statistically significant correlations to infer causality when the correlations actually reflect risk factors or even rare coincidences. [ABSTRACT FROM AUTHOR]

In set theory, a maximality principle is a principle that asserts some maximality property of the universe of sets or some part thereof. Set theorists have formulated a variety of maximality principles in order to settle statements left undecided by current standard set theory. In addition, philosophers of mathematics have explored maximality principles whilst attempting to prove categoricity theorems for set theory or providing criteria for selecting foundational theories. This article reviews recent work concerned with the formulation, investigation and justification of maximality principles. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

We prove that the generalized cancellation axiom for incomplete comparative probability relations introduced by Ríos Insua (Theory Decis 33:83-100, ) and Alon and Lehrer (J Econ Theory 151:476-492, ) is stronger than the standard cancellation axiom for complete comparative probability relations introduced by Scott (J Math Psychol 1:233-247, ), relative to their other axioms for comparative probability in both the finite and infinite cases. This result has been suggested but not proved in the previous literature. [ABSTRACT FROM AUTHOR]

The famous Gödel incompleteness theorem states that for every consistent, recursive, and sufficiently rich formal theory T there exist true statements that are unprovable in T. Such statements would be natural candidates for being added as axioms, but how can we obtain them? One classical (and well studied) approach is to add to some theory T an axiom that claims the consistency of T. In this paper we discuss another approach motivated by Chaitin's version of Gödel's theorem where axioms claiming the randomness (or incompressibility) of some strings are probabilistically added, and show that it is not really useful, in the sense that this does not help us prove new interesting theorems. This result answers a question recently asked by Lipton. The situation changes if we take into account the size of the proofs: randomly chosen axioms may help making proofs much shorter (unless ). We then study the axiomatic power of the statements of type “the Kolmogorov complexity of x exceeds n” (where x is some string, and n is some integer) in general. They are (universally quantified) statements of Peano arithmetic. We show that by adding all true statements of this type, we obtain a theory that proves all true -statements, and also provide a more detailed classification. In particular, as Theorem 7 shows, to derive all true -statements it is enough to add one statement of this type for each n (or even for infinitely many n) if strings are chosen in a special way. On the other hand, one may add statements of this type for most x of length n (for every n) and still obtain a weak theory. We also study other logical questions related to “random axioms”. Finally, we consider a theory that claims Martin-Löf randomness of a given infinite binary sequence. This claim can be formalized in different ways. We show that different formalizations are closely related but not equivalent, and study their properties. [ABSTRACT FROM AUTHOR]

I argue that three main interpretations of the aim of Russell's early logicism in The Principles of Mathematics (1903) are mistaken, and propose a new interpretation. According to this new interpretation, the aim of Russell's logicism is to show, in opposition to Kant, that mathematical propositions have a certain sort of complete generality which entails that their truth is independent of space and time. I argue that on this interpretation two often-heard objections to Russell's logicism, deriving from Gödel's incompleteness theorem and from the non-logical character of some of the axioms of Principia Mathematica respectively, can be seen to be inconclusive. I then proceed to identify two challenges that Russell's logicism, as presently construed, faces, but argue that these challenges do not appear unanswerable. [ABSTRACT FROM AUTHOR]

In this article, the article discusses an example using Collatzfunction showing that there are some arithmetic statements which are true but not provable. He informs about the Incompleteness Theorem by Godel which shows that no consistent system of axioms can prove every true arithmetical statement. He also mentions that the same techniques are applied to the Four-Color Theorem and Goldbach's Conjecture in which every even number greater than 2 is the sum of two primes.

Is it possible to give a coordinate-free formulation of the Second Incompleteness Theorem? We pursue one possible approach to this question. We show that (i) cutfree consistency for finitely axiomatized theories can be uniquely characterized modulo EA-provable equivalence and (ii) consistency for finitely axiomatized sequential theories can be uniquely characterized modulo EA-provable equivalence. The case of infinitely axiomatized RE theories is more delicate. We carefully discuss this in the article. [ABSTRACT FROM PUBLISHER]

Abstract: In 1981, Paris and Wilkie indicated it was an open question whether I would satisfy the Second Incompleteness Theorem for Herbrand deduction. We will show that some specially formulated axiomizations for I can evade the Herbrandized version of the Second Incompleteness Theorem. [Copyright &y& Elsevier]

Abstract: Gödel initiated the program of finding and justifying axioms that effect a significant reduction in incompleteness and he drew a fundamental distinction between intrinsic and extrinsic justifications. Reflection principles are the most promising candidates for new axioms that are intrinsically justified. Taking as our starting point Tait’s work on general reflection principles, we prove a series of limitative results concerning this approach. These results collectively show that general reflection principles are either weak (in that they are consistent relative to the Erdös cardinal ) or inconsistent. The philosophical significance of these results is discussed. [Copyright &y& Elsevier]

Elementary Recursive Nonstandard Analysis, in short ERNA, is a constructive system of nonstandard analysis proposed around 1995 by Patrick Suppes and Richard Sommer, who also proved its consistency inside PRA. It is based on an earlier system developed by Rolando Chuaqui and Patrick Suppes, of which Michal Rössler and Emil Jeřábek have recently proposed a weakened version. We add a Π1-transfer principle to ERNA and prove the consistency of the extended theory inside PRA. In this extension of ERNA a Σ1-supremum principle 'up-to-infinitesimals', and some well-known calculus results for sequences are deduced. Finally, we prove that transfer is 'too strong' for finitism by reconsidering Rössler and Jeřábek's conclusions. [ABSTRACT FROM AUTHOR]

It is well understood and appreciated that Gödel’s Incompleteness Theorems apply to sufficiently strong, formal deductive systems. In particular, the theorems apply to systems which are adequate for conventional number theory. Less well known is that there exist algorithms which can be applied to such a system to generate a gödel-sentence for that system. Although the generation of a sentence is not equivalent to proving its truth, the present paper argues that the existence of these algorithms, when conjoined with Gödel’s results and accepted theorems of recursion theory, does provide the basis for an apparent paradox. The difficulty arises when such an algorithm is embedded within a computer program of sufficient arithmetic power. The required computer program (an AI system) is described herein, and the paradox is derived. A solution to the paradox is proposed, which, it is argued, illuminates the truth status of axioms in formal models of programs and Turing machines. [ABSTRACT FROM AUTHOR]

Gödel's Second Incompleteness Theorem states axiom systems of sufficient strength are unable to verify their own consistency. We will show that axiomatizations for a computer's floating point arithmetic can recognize their cut-free consistency in a stronger respect than is feasible under integer arithmetics. This paper will include both new generalizations of the Second Incompleteness Theorem and techniques for evading it. [ABSTRACT FROM AUTHOR]

This is a critical analysis of the first part of Gödel's 1951 Gibbs lecture on certain philosophical consequences of the incompleteness theorems. Gödel's discussion is framed in terms of a distinction between objective mathematics and subjective mathematics, according to which the former consists of the truths of mathematics in an absolute sense, and the latter consists of all humanly demonstrable truths. The question is whether these coincide; if they do, no formal axiomatic system (or Turing machine) can comprehend the mathematizing potentialities of human thought, and, if not, there are absolutely unsolvable mathematical problems of diophantine form. [ABSTRACT FROM AUTHOR]