
handle: 11577/136994
AbstractIn this paper we show that the usual intuitionistic characterization of the decidability of the propositional function B(x) prop [x : A], i. e. to require that the predicate (∀x ∈ A) (B(x) ∨ ¬ B(x)) is provable, is equivalent, when working within the framework of Martin‐Löf's Intuitionistic Type Theory, to require that there exists a decision function ψ: A → Boole such that (∀x ∈ A) ((ψ(x) = Boole true) ↔ B(x)). Since we will also show that the proposition x = Boole true [x: Boole] is decidable, we can alternatively say that the main result of this paper is a proof that the decidability of the predicate B(x) prop [x : A] can be effectively reduced by a function ψ A → Boole to the decidability of the predicate ψ(x) = Boole true [x : A]. All the proofs are carried out within the Intuitionistic Type Theory and hence the decision function ψ, together with a proof of its correctness, is effectively constructed as a function of the proof of (∀x ∈ A)(B(x) ∨ ¬ B(x)).Mathematics Subject Classification: 03B15, 03B20.
Decidability of theories and sets of sentences, intuitionistic decidable predicates, decision function, Martin-Löf's intuitionistic type theory, Intuitionistic mathematics, constructive mathematics; Intuitionistic Type Theory; decidability, Second- and higher-order arithmetic and fragments
Decidability of theories and sets of sentences, intuitionistic decidable predicates, decision function, Martin-Löf's intuitionistic type theory, Intuitionistic mathematics, constructive mathematics; Intuitionistic Type Theory; decidability, Second- and higher-order arithmetic and fragments
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
