About this topic
Summary When a mathematical theory is decidable we are able to check in some mechanistic fashion whether some well-formed statement in the language of the theory is a theorem (lemma, corollary, etc.). More precisely, a theory is decidable when the set of theorems (lemmas, corollaries, etc.) is recursive. A theory is undecidable, naturally, when this is not the case. Given that completeness and decidability go hand in hand, when we have found an incomplete theory we have also found an undecidable theory. So, Gödel's incompleteness results yield the further result of showing these incomplete theories also have the feature of not being able to check whether the set of theorems is recursive.
Key works Church (1936a), Gödel (Collected Works), Turing, Mostowski, and Robinson (1953), Davis (1977)
  Show all references
Related categories
Siblings:
8 found
Search inside:
(import / add options)   Sort by:
  1. Sergei Artëmov & Franco Montagna (1994). On First-Order Theories with Provability Operator. Journal of Symbolic Logic 59 (4):1139-1153.
    In this paper the modal operator "x is provable in Peano Arithmetic" is incorporated into first-order theories. A provability extension of a theory is defined. Presburger Arithmetic of addition, Skolem Arithmetic of multiplication, and some first order theories of partial consistency statements are shown to remain decidable after natural provability extensions. It is also shown that natural provability extensions of a decidable theory may be undecidable.
    Remove from this list | Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  2. Michael Beeson (1976). The Unprovability in Intuitionistic Formal Systems of the Continuity of Effective Operations on the Reals. Journal of Symbolic Logic 41 (1):18-24.
  3. John Bell (2008). Incompleteness in a General Setting (Vol 13, Pg 21, 2007). Bulletin of Symbolic Logic 14 (1):21 - 30.
    Full proofs of the Gödel incompleteness theorems are highly intricate affairs. Much of the intricacy lies in the details of setting up and checking the properties of a coding system representing the syntax of an object language (typically, that of arithmetic) within that same language. These details are seldom illuminating and tend to obscure the core of the argument. For this reason a number of efforts have been made to present the essentials of the proofs of Gödel’s theorems without getting (...)
    Remove from this list | Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  4. John L. Bell (2008). Corrigendum to “Incompleteness in a General Setting”. Bulletin of Symbolic Logic 14 (1):122-122.
    Remove from this list | Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  5. Francesco Berto (2009). The Gödel Paradox and Wittgenstein's Reasons. Philosophia Mathematica 17 (2):208-219.
    An interpretation of Wittgenstein’s much criticized remarks on Gödel’s First Incompleteness Theorem is provided in the light of paraconsistent arithmetic: in taking Gödel’s proof as a paradoxical derivation, Wittgenstein was drawing the consequences of his deliberate rejection of the standard distinction between theory and metatheory. The reasoning behind the proof of the truth of the Gödel sentence is then performed within the formal system itself, which turns out to be inconsistent. It is shown that the features of paraconsistent arithmetics match (...)
    Remove from this list | Direct download (13 more)  
     
    My bibliography  
     
    Export citation  
  6. Adrian Heathcote (1990). Unbounded Operators and the Incompleteness of Quantum Mechanics. Philosophy of Science 57 (3):523-534.
    A proof is presented that a form of incompleteness in Quantum Mechanics follows directly from the use of unbounded operators. It is then shown that the problems that arise for such operators are not connected to the non- commutativity of many pairs of operators in Quantum Mechanics and hence are an additional source of incompleteness to that which allegedly flows from the..
    Remove from this list | Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  7. G. Longo (2011). Reflections on Concrete Incompleteness. Philosophia Mathematica 19 (3):255-280.
    How do we prove true but unprovable propositions? Gödel produced a statement whose undecidability derives from its ad hoc construction. Concrete or mathematical incompleteness results are interesting unprovable statements of formal arithmetic. We point out where exactly the unprovability lies in the ordinary ‘mathematical’ proofs of two interesting formally unprovable propositions, the Kruskal-Friedman theorem on trees and Girard's normalization theorem in type theory. Their validity is based on robust cognitive performances, which ground mathematics in our relation to space and time, (...)
    Remove from this list | Direct download (10 more)  
     
    My bibliography  
     
    Export citation  
  8. Matthew W. Parker (2003). Undecidability in Rn: Riddled Basins, the KAM Tori, and the Stability of the Solar System. Philosophy of Science 70 (2):359-382.
    Some have suggested that certain classical physical systems have undecidable long-term behavior, without specifying an appropriate notion of decidability over the reals. We introduce such a notion, decidability in (or d- ) for any measure , which is particularly appropriate for physics and in some ways more intuitive than Ko's (1991) recursive approximability (r.a.). For Lebesgue measure , d- implies r.a. Sets with positive -measure that are sufficiently "riddled" with holes are never d- but are often r.a. This explicates Sommerer (...)
    Remove from this list | Direct download (6 more)  
     
    My bibliography  
     
    Export citation