In constructive mathematics, Church's thesis is an axiom stating that all total functions are computable functions. thus restricts the class of functions to computable ones and consequently is incompatible with classical logic in sufficiently strong systems. For example, Heyting arithmetic with as an addition axiom is able to disprove some instances of variants of the law of the excluded middle. However, Heyting arithmetic is equiconsistent with Peano arithmetic as well as with Heyting arithmetic plus Church's thesis. That is, adding either the law of the excluded middle or Church's thesis does not make Heyting arithmetic inconsistent, but adding both does.
Attributes | Values |
---|
rdfs:label
| - Church's thesis (constructive mathematics) (en)
|
rdfs:comment
| - In constructive mathematics, Church's thesis is an axiom stating that all total functions are computable functions. thus restricts the class of functions to computable ones and consequently is incompatible with classical logic in sufficiently strong systems. For example, Heyting arithmetic with as an addition axiom is able to disprove some instances of variants of the law of the excluded middle. However, Heyting arithmetic is equiconsistent with Peano arithmetic as well as with Heyting arithmetic plus Church's thesis. That is, adding either the law of the excluded middle or Church's thesis does not make Heyting arithmetic inconsistent, but adding both does. (en)
|
dcterms:subject
| |
Wikipage page ID
| |
Wikipage revision ID
| |
Link from a Wikipage to another Wikipage
| |
sameAs
| |
dbp:wikiPageUsesTemplate
| |
has abstract
| - In constructive mathematics, Church's thesis is an axiom stating that all total functions are computable functions. thus restricts the class of functions to computable ones and consequently is incompatible with classical logic in sufficiently strong systems. For example, Heyting arithmetic with as an addition axiom is able to disprove some instances of variants of the law of the excluded middle. However, Heyting arithmetic is equiconsistent with Peano arithmetic as well as with Heyting arithmetic plus Church's thesis. That is, adding either the law of the excluded middle or Church's thesis does not make Heyting arithmetic inconsistent, but adding both does. The Church–Turing thesis states that every effectively calculable function is a computable function. The constructivist version, , is much stronger, in the sense that with it every function is computable. (en)
|
gold:hypernym
| |
prov:wasDerivedFrom
| |
page length (characters) of wiki page
| |
foaf:isPrimaryTopicOf
| |
is Link from a Wikipage to another Wikipage
of | |
is Wikipage redirect
of | |
is Wikipage disambiguates
of | |
is foaf:primaryTopic
of | |