Undecidability and intuitionistic incompleteness (Q1815411): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/bf00257386 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1988967089 / rank | |||
Normal rank |
Latest revision as of 11:36, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Undecidability and intuitionistic incompleteness |
scientific article |
Statements
Undecidability and intuitionistic incompleteness (English)
0 references
12 November 1996
0 references
It is proved that the many-one completeness of S-derivability (for a deductive system S) and its completeness w.r.t. a class of structures K imply Markov's Principle MP (under some simple assumptions on S and K). This result yields as immediate corollary that weak completeness for classical predicate logic and strong completeness for sentential logic imply MP. Hence the corresponding completeness theorems for (the negative fragment of) intuitionistic logic (w.r.t. Beth and Kripke models) imply MP, too (and these completeness theorems are unprovable in second-order Heyting arithmetic HAS).
0 references
Beth models
0 references
classical logic
0 references
Markov's principle
0 references
completeness
0 references
intuitionistic logic
0 references
Kripke models
0 references