Results for 'Undecidability'

858 found
Order:
See also
  1. The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions.Martin Davis (ed.) - 1965 - Hewlett, NY, USA: Dover Publication.
    "A valuable collection both for original source material as well as historical formulations of current problems."-- The Review of Metaphysics "Much more than a mere collection of papers . . . a valuable addition to the literature."-- Mathematics of Computation An anthology of fundamental papers on undecidability and unsolvability by major figures in the field, this classic reference opens with Godel's landmark 1931 paper demonstrating that systems of logic cannot admit proofs of all true assertions of arithmetic. Subsequent papers (...)
    Direct download  
     
    Export citation  
     
    Bookmark   99 citations  
  2.  53
    Undecidable Theories.Alfred Tarski - 1953 - Amsterdam: North-Holland Pub. Co..
    This book is well known for its proof that many mathematical systems - including lattice theory and closure algebras - are undecidable. It consists of three treatises from one of the greatest logicians of all time: "A General Method in Proofs of Undecidability," "Undecidability and Essential Undecidability in Mathematics," and "Undecidability of the Elementary Theory of Groups.".
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   84 citations  
  3.  9
    Creatively Undecided: Toward a History and Philosophy of Scientific Agency.Menachem Fisch - 2017 - Chicago: University of Chicago Press.
    For many, the two key thinkers about science in the twentieth century are Thomas Kuhn and Karl Popper, and one of the key questions in contemplating science is how to make sense of theory change. In Creatively Undecided, philosopher Menachem Fisch defends a new way to make sense of the rationality of scientific revolutions. He argues, loosely following Kuhn, for a strong notion of the framework dependency of all scientific practice, while at the same time he shows how such frameworks (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   12 citations  
  4. The Undecidability of Monadic Modal Quantification Theory.Saul A. Kripke - 1962 - Mathematical Logic Quarterly 8 (2):113-116.
  5.  14
    21 Undecidability and Intractability in Theoretical Physics.Stephen Wolfram - 2013 - Emergence: Contemporary Readings in Philosophy and Science.
    This chapter explores some fundamental consequences of the correspondence between physical process and computations. Most physical questions may be answerable only through irreducible amounts of computation. Those that concern idealized limits of infinite time, volume, or numerical precision can require arbitrarily long computations, and so be considered formally undecidable. The behavior of a physical system may always be calculated by simulating explicitly each step in its evolution. Much of theoretical physics has, however, been concerned with devising shorter methods of calculation (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   21 citations  
  6.  92
    Undecidability Without Arithmetization.Andrzej Grzegorczyk - 2005 - Studia Logica 79 (2):163-230.
    In the present paper the well-known Gödels – Churchs argument concerning the undecidability of logic (of the first order functional calculus) is exhibited in a way which seems to be philosophically interestingfi The natural numbers are not used. (Neither Chinese Theorem nor other specifically mathematical tricks are applied.) Only elementary logic and very simple set-theoretical constructions are put into the proof. Instead of the arithmetization I use the theory of concatenation (formalized by Alfred Tarski). This theory proves to be (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   27 citations  
  7.  73
    Undecidability and the Problem of Outcomes in Quantum Measurements.Rodolfo Gambini, Luis Pedro Garcia Pintos & Jorge Pullin - forthcoming - Foundations of Physics:93-115.
    We argue that it is fundamentally impossible to recover information about quantum superpositions when a quantum system has interacted with a sufficiently large number of degrees of freedom of the environment. This is due to the fact that gravity imposes fundamental limitations on how accurate measurements can be. This leads to the notion of undecidability: there is no way to tell, due to fundamental limitations, if a quantum system evolved unitarily or suffered wavefunction collapse. This in turn provides a (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  8. Undecidable Theories.Alfred Tarski, Andrzej Mostowski & Raphael M. Robinson - 1953 - Philosophy 30 (114):278-279.
    No categories
     
    Export citation  
     
    Bookmark   82 citations  
  9.  39
    Sentences Undecidable in Formalized Arithmetic: An Exposition of the Theory of Kurt Gödel.Andrzej Mostowski - 1952 - Amsterdam, Netherlands: Greenwood Press.
    The famous theory of undecidable sentences created by Kurt Godel in 1931 is presented as clearly and as rigorously as possible. Introductory explanations beginning with the necessary facts of arithmetic of integers and progressing to the theory of representability of arithmetical functions and relations in the system (S) prepare the reader for the systematic exposition of the theory of Godel which is taken up in the final chapter and the appendix.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   11 citations  
  10.  7
    The Undecidability of K-Provability.Samuel R. Buss - 1991 - Annals of Pure and Applied Logic 53 (1):75-102.
    Buss, S.R., The undecidability of k-provability, Annals of Pure and Applied Logic 53 75-102. The k-provability problem is, given a first-order formula ø and an integer k, to determine if ø has a proof consisting of k or fewer lines . This paper shows that the k-provability problem for the sequent calculus is undecidable. Indeed, for every r.e. set X there is a formula ø and an integer k such that for all n,ø has a proof of k sequents (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   13 citations  
  11. Algorithmic Information Theory and Undecidability.Panu Raatikainen - 2000 - Synthese 123 (2):217-225.
    Chaitin’s incompleteness result related to random reals and the halting probability has been advertised as the ultimate and the strongest possible version of the incompleteness and undecidability theorems. It is argued that such claims are exaggerations.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  12.  24
    The Undecidability of Quantified Announcements.T. Ågotnes, H. van Ditmarsch & T. French - 2016 - Studia Logica 104 (4):597-640.
    This paper demonstrates the undecidability of a number of logics with quantification over public announcements: arbitrary public announcement logic, group announcement logic, and coalition announcement logic. In APAL we consider the informative consequences of any announcement, in GAL we consider the informative consequences of a group of agents all of which are simultaneously making known announcements. So this is more restrictive than APAL. Finally, CAL is as GAL except that we now quantify over anything the agents not in that (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  13.  34
    Undecidability and the Problem of Outcomes in Quantum Measurements.Rodolfo Gambini, Luis Pedro García Pintos & Jorge Pullin - 2009 - Foundations of Physics 40 (1):93-115.
    We argue that it is fundamentally impossible to recover information about quantum superpositions when a quantum system has interacted with a sufficiently large number of degrees of freedom of the environment. This is due to the fact that gravity imposes fundamental limitations on how accurate measurements can be. This leads to the notion of undecidability: there is no way to tell, due to fundamental limitations, if a quantum system evolved unitarily or suffered wavefunction collapse. This in turn provides a (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  14.  98
    The Undecidability of Propositional Adaptive Logic.Leon Horsten & Philip Welch - 2007 - Synthese 158 (1):41-60.
    We investigate and classify the notion of final derivability of two basic inconsistency-adaptive logics. Specifically, the maximal complexity of the set of final consequences of decidable sets of premises formulated in the language of propositional logic is described. Our results show that taking the consequences of a decidable propositional theory is a complicated operation. The set of final consequences according to either the Reliability Calculus or the Minimal Abnormality Calculus of a decidable propositional premise set is in general undecidable, and (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   12 citations  
  15. Undecidable Theories.Alfred Tarski - 1959 - British Journal for the Philosophy of Science 9 (36):321-327.
     
    Export citation  
     
    Bookmark   30 citations  
  16.  54
    The Undecidability of Grisin's Set Theory.Andrea Cantini - 2003 - Studia Logica 74 (3):345 - 368.
    We investigate a contractionless naive set theory, due to Grisin [11]. We prove that the theory is undecidable.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   15 citations  
  17.  75
    Which Undecidable Mathematical Sentences Have Determinate Truth Values.Hartry Field - 1998 - In H. G. Dales & Gianluigi Oliveri (eds.), Truth in Mathematics. Oxford University Press, Usa. pp. 291--310.
    Direct download  
     
    Export citation  
     
    Bookmark   23 citations  
  18. What is Absolute Undecidability?†.Justin Clarke-Doane - 2013 - Noûs 47 (3):467-481.
    It is often alleged that, unlike typical axioms of mathematics, the Continuum Hypothesis (CH) is indeterminate. This position is normally defended on the ground that the CH is undecidable in a way that typical axioms are not. Call this kind of undecidability “absolute undecidability”. In this paper, I seek to understand what absolute undecidability could be such that one might hope to establish that (a) CH is absolutely undecidable, (b) typical axioms are not absolutely undecidable, and (c) (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   11 citations  
  19. Undecidability in the Imitation Game.Y. Sato & T. Ikegami - 2004 - Minds and Machines 14 (2):133-43.
    This paper considers undecidability in the imitation game, the so-called Turing Test. In the Turing Test, a human, a machine, and an interrogator are the players of the game. In our model of the Turing Test, the machine and the interrogator are formalized as Turing machines, allowing us to derive several impossibility results concerning the capabilities of the interrogator. The key issue is that the validity of the Turing test is not attributed to the capability of human or machine, (...)
    Direct download (16 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  20.  51
    Undecidability in the Spatialized Prisoner's Dilemma.Patrick Grim - 1997 - Theory and Decision 42:53-80.
    n the spatialized Prisoner’s Dilemma, players compete against their immediate neighbors and adopt a neighbor’s strategy should it prove locally superior. Fields of strategies evolve in the manner of cellular automata (Nowak and May, 1993; Mar and St. Denis, 1993a,b; Grim 1995, 1996). Often a question arises as to what the eventual outcome of an initial spatial configuration of strategies will be: Will a single strategy prove triumphant in the sense of progressively conquering more and more territory without opposition, or (...)
    Direct download  
     
    Export citation  
     
    Bookmark   2 citations  
  21. Alethic Undecidability Doesn’T Solve the Liar.Mark Jago - 2016 - Analysis 76 (3):278-283.
    Stephen Barker presents a novel approach to solving semantic paradoxes, including the Liar and its variants and Curry’s paradox. His approach is based around the concept of alethic undecidability. His approach, if successful, renders futile all attempts to assign semantic properties to the paradoxical sentences, whilst leaving classical logic fully intact. And, according to Barker, even the T-scheme remains valid, for validity is not undermined by undecidable instances. Barker’s approach is innovative and worthy of further consideration, particularly by those (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  22.  5
    The Undecidability of Quantified Announcements.T. French, H. Ditmarsch & T. Ågotnes - 2016 - Studia Logica 104 (4):597-640.
    This paper demonstrates the undecidability of a number of logics with quantification over public announcements: arbitrary public announcement logic, group announcement logic, and coalition announcement logic. In APAL we consider the informative consequences of any announcement, in GAL we consider the informative consequences of a group of agents all of which are simultaneously making known announcements. So this is more restrictive than APAL. Finally, CAL is as GAL except that we now quantify over anything the agents not in that (...)
    Direct download  
     
    Export citation  
     
    Bookmark   3 citations  
  23.  21
    The Undecidability of Iterated Modal Relativization.Joseph S. Miller & Lawrence S. Moss - 2005 - Studia Logica 79 (3):373-407.
    In dynamic epistemic logic and other fields, it is natural to consider relativization as an operator taking sentences to sentences. When using the ideas and methods of dynamic logic, one would like to iterate operators. This leads to iterated relativization. We are also concerned with the transitive closure operation, due to its connection to common knowledge. We show that for three fragments of the logic of iterated relativization and transitive closure, the satisfiability problems are fi1 11–complete. Two of these fragments (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   22 citations  
  24.  7
    The Undecidability of Grisin's Set Theory.Andrea Cantini - 2003 - Studia Logica 74 (3):345-368.
    We investigate a contractionless naive set theory, due to Gris̆in [11]. We prove that the theory is undecidable.
    Direct download  
     
    Export citation  
     
    Bookmark   16 citations  
  25.  19
    Undecidability and 1-Types in the Recursively Enumerable Degrees.Klaus Ambos-Spies & Richard A. Shore - 1993 - Annals of Pure and Applied Logic 63 (1):3-37.
    Ambos-Spies, K. and R.A. Shore, Undecidability and 1-types in the recursively enumerable degrees, Annals of Pure and Applied Logic 63 3–37. We show that the theory of the partial ordering of recursively enumerable Turing degrees is undecidable and has uncountably many 1-types. In contrast to the original proof of the former which used a very complicated O''' argument our proof proceeds by a much simpler infinite injury argument. Moreover, it combines with the permitting technique to get similar results for (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  26.  35
    The Undecidability of the First-Order Theory of Diagonalizable Algebras.Franco Montagna - 1980 - Studia Logica 39 (4):355 - 359.
    The undecidability of the first-order theory of diagonalizable algebras is shown here.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  27.  23
    Undecidability Results on Two-Variable Logics.Erich Grädel, Martin Otto & Eric Rosen - 1999 - Archive for Mathematical Logic 38 (4-5):313-354.
    It is a classical result of Mortimer that $L^2$ , first-order logic with two variables, is decidable for satisfiability. We show that going beyond $L^2$ by adding any one of the following leads to an undecidable logic:– very weak forms of recursion, viz.¶(i) transitive closure operations¶(ii) (restricted) monadic fixed-point operations¶– weak access to cardinalities, through the Härtig (or equicardinality) quantifier¶– a choice construct known as Hilbert's $\epsilon$ -operator.In fact all these extensions of $L^2$ prove to be undecidable both for satisfiability, (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  28.  33
    Undecidability of First-Order Intuitionistic and Modal Logics with Two Variables.Roman Kontchakov, Agi Kurucz & Michael Zakharyaschev - 2005 - Bulletin of Symbolic Logic 11 (3):428-438.
    We prove that the two-variable fragment of first-order intuitionistic logic is undecidable, even without constants and equality. We also show that the two-variable fragment of a quantified modal logic L with expanding first-order domains is undecidable whenever there is a Kripke frame for L with a point having infinitely many successors (such are, in particular, the first-order extensions of practically all standard modal logics like K, K4, GL, S4, S5, K4.1, S4.2, GL.3, etc.). For many quantified modal logics, including those (...)
    Direct download (11 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  29.  26
    The Undecidability of Entailment and Relevant Implication.Alasdair Urquhart - 1984 - Journal of Symbolic Logic 49 (4):1059-1073.
  30.  16
    Undecidability of First-Order Modal and Intuitionistic Logics with Two Variables and One Monadic Predicate Letter.Mikhail Rybakov & Dmitry Shkatov - 2018 - Studia Logica 107 (4):695-717.
    We prove that the positive fragment of first-order intuitionistic logic in the language with two individual variables and a single monadic predicate letter, without functional symbols, constants, and equality, is undecidable. This holds true regardless of whether we consider semantics with expanding or constant domains. We then generalise this result to intervals \ and \, where QKC is the logic of the weak law of the excluded middle and QBL and QFL are first-order counterparts of Visser’s basic and formal logics, (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  31.  74
    The Undecidability of the Spatialized Prisoner's Dilemma.Patrick Grim - 1997 - Theory and Decision 42 (1):53-80.
    In the spatialized Prisoner's Dilemma, players compete against their immediate neighbors and adopt a neighbor's strategy should it prove locally superior. Fields of strategies evolve in the manner of cellular automata (Nowak and May, 1993; Mar and St. Denis, 1993a,b; Grim 1995, 1996). Often a question arises as to what the eventual outcome of an initial spatial configuration of strategies will be: Will a single strategy prove triumphant in the sense of progressively conquering more and more territory without opposition, or (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  32.  28
    Undecidability of the Problem of Recognizing Axiomatizations of Superintuitionistic Propositional Calculi.Evgeny Zolin - 2014 - Studia Logica 102 (5):1021-1039.
    We give a new proof of the following result : it is undecidable whether a given calculus, that is a finite set of propositional formulas together with the rules of modus ponens and substitution, axiomatizes the classical logic. Moreover, we prove the same for every superintuitionistic calculus. As a corollary, it is undecidable whether a given calculus is consistent, whether it is superintuitionistic, whether two given calculi have the same theorems, whether a given formula is derivable in a given calculus. (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  33.  6
    Undecidability of the Spectral Gap: An Epistemological Look.Emiliano Ippoliti & Sergio Caprara - 2021 - Journal for General Philosophy of Science / Zeitschrift für Allgemeine Wissenschaftstheorie 52 (1):157-170.
    The results of Cubitt et al. on the spectral gap problem add a new chapter to the issue of undecidability in physics, as they show that it is impossible to decide whether the Hamiltonian of a quantum many-body system is gapped or gapless. This implies, amongst other things, that a reductionist viewpoint would be untenable. In this paper, we examine their proof and a few philosophical implications, in particular ones regarding models and limitative results. In more detail, we examine (...)
    Direct download (3 more)  
    Translate
     
     
    Export citation  
     
    Bookmark   1 citation  
  34.  55
    On Undecidable Statements in Enlarged Systems of Logic and the Concept of Truth.Alfred Tarski - 1939 - Journal of Symbolic Logic 4 (3):105-112.
  35. Undecidability in Diagonalizable Algebras.V. Yu Shavrukov - 1997 - Journal of Symbolic Logic 62 (1):79-116.
    If a formal theory T is able to reason about its own syntax, then the diagonalizable algebra of T is defined as its Lindenbaum sentence algebra endowed with a unary operator □ which sends a sentence φ to the sentence □φ asserting the provability of φ in T. We prove that the first order theories of diagonalizable algebras of a wide class of theories are undecidable and establish some related results.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  36.  82
    Undecidability in Anti-Realism.Sanford Shieh - 1998 - Philosophia Mathematica 6 (3):324-333.
    In this paper I attempt to clarify a relatively little-studied aspect of Michael Dummett's argument for intuitionism: its use of the notion of ‘undecidable’ sentence. I give a new analysis of this concept in epistemic terms, with which I resolve some puzzles and questions about how it works in the anti-realist critique of classical logic.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  37.  41
    Hereditary Undecidability of Some Theories of Finite Structures.Ross Willard - 1994 - Journal of Symbolic Logic 59 (4):1254-1262.
    Using a result of Gurevich and Lewis on the word problem for finite semigroups, we give short proofs that the following theories are hereditarily undecidable: (1) finite graphs of vertex-degree at most 3; (2) finite nonvoid sets with two distinguished permutations; (3) finite-dimensional vector spaces over a finite field with two distinguished endomorphisms.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  38.  86
    The Undecidability of the Disjunction Property of Propositional Logics and Other Related Problems.Alexander Chagrov & Michael Zakharyaschev - 1993 - Journal of Symbolic Logic 58 (3):967-1002.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   12 citations  
  39.  18
    Undecidable Long-Term Behavior in Classical Physics: Foundations, Results, and Interpretation.Matthew W. Parker - 2005 - Dissertation, University of Chicago
    The behavior of some systems is non-computable in a precise new sense. One infamous problem is that of the stability of the solar system: Given the initial positions and velocities of several mutually gravitating bodies, will any eventually collide or be thrown off to infinity? Many have made vague suggestions that this and similar problems are undecidable: no finite procedure can reliably determine whether a given configuration will eventually prove unstable. But taken in the most natural way, this is trivial. (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  40.  59
    An Undecidable Problem in Correspondence Theory.L. A. Chagrova - 1991 - Journal of Symbolic Logic 56 (4):1261-1272.
  41.  28
    Extremely Undecidable Sentences.George Boolos - 1982 - Journal of Symbolic Logic 47 (1):191-196.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  42.  42
    The Undecidability of the II4 Theory for the R. E. Wtt and Turing Degrees.Steffen Lempp & André Nies - 1995 - Journal of Symbolic Logic 60 (4):1118 - 1136.
    We show that the Π 4 -theory of the partial order of recursively enumerable weak truth-table degrees is undecidable, and give a new proof of the similar fact for r.e. T-degrees. This is accomplished by introducing a new coding scheme which consists in defining the class of finite bipartite graphs with parameters.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  43. Undecidability in Rn: Riddled Basins, the KAM Tori, and the Stability of the Solar System.Matthew W. Parker - 2003 - 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 (...)
    Direct download (11 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  44.  38
    The Undecidability of the II$^_4$ Theory for the R. E. Wtt and Turing Degrees.Steffen Lempp & André Nies - 1995 - Journal of Symbolic Logic 60 (4):1118-1136.
    We show that the $\Pi_4$-theory of the partial order of recursively enumerable weak truth-table degrees is undecidable, and give a new proof of the similar fact for r.e. T-degrees. This is accomplished by introducing a new coding scheme which consists in defining the class of finite bipartite graphs with parameters.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  45.  74
    Some Undecidable Problems Involving Elementary Functions of a Real Variable.Daniel Richardson - 1968 - Journal of Symbolic Logic 33 (4):514-520.
  46.  24
    Undecidable Semiassociative Relation Algebras.Roger D. Maddux - 1994 - Journal of Symbolic Logic 59 (2):398-418.
    If K is a class of semiassociative relation algebras and K contains the relation algebra of all binary relations on a denumerable set, then the word problem for the free algebra over K on one generator is unsolvable. This result implies that the set of sentences which are provable in the formalism Lwx is an undecidable theory. A stronger algebraic result shows that the set of logically valid sentences in Lwx forms a hereditarily undecidable theory in Lwx. These results generalize (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  47.  7
    Undecidability of the Real-Algebraic Structure of Scott's Model.Miklós Erdélyi-Szabó - 1998 - Mathematical Logic Quarterly 44 (3):344-348.
    We show that true first-order arithmetic of the positive integers is interpretable over the real-algebraic structure of Scott's topological model for intuitionistic analysis. From this the undecidability of the structure follows.
    Direct download  
     
    Export citation  
     
    Bookmark   2 citations  
  48.  18
    Undecidability of Some Topological Theories.Andrzej Grzegorczyk - 1953 - Journal of Symbolic Logic 18 (1):73-74.
    Direct download  
     
    Export citation  
     
    Bookmark   7 citations  
  49.  38
    Undecidable Sentences Generated by Semantic Paradoxes.Hao Wang - 1955 - Journal of Symbolic Logic 20 (1):31-43.
  50.  34
    Undecidability and Intuitionistic Incompleteness.D. C. McCarty - 1996 - Journal of Philosophical Logic 25 (5):559 - 565.
    Let S be a deductive system such that S-derivability (⊦s) is arithmetic and sound with respect to structures of class K. From simple conditions on K and ⊦s, it follows constructively that the K-completeness of ⊦s implies MP(S), a form of Markov's Principle. If ⊦s is undecidable then MP(S) is independent of first-order Heyting arithmetic. Also, if ⊦s is undecidable and the S proof relation is decidable, then MP(S) is independent of second-order Heyting arithmetic, HAS. Lastly, when ⊦s is many-one (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
1 — 50 / 858