Relationship To Classical Logic
The schema form of CT shown above, when added to constructive systems such as HA, implies the negation of the law of the excluded middle. As an example, it is a classical tautology that every Turing machine either halts or does not halt on a given input. Assuming this tautology, in sufficiently strong systems such as HA it is possible to form a function h that takes a code for a Turing machine and returns 1 if the machine halts and 0 if it does not halt. Then, from Church's Thesis one would conclude that this function is itself computable, but this is known to be false, because the Halting problem is not computably solvable. Thus HA and CT disproves some consequence of the law of the excluded middle.
The "single axiom" form of CT mentioned above,
- ,
quantifies over functions and says that every function f is computable (with an index e). This axiom is consistent with some weak classical systems that do not have the strength to form functions such as the function f of the previous paragraph. For example, the weak classical system is consistent with this single axiom, because has a model in which every function is computable. However, the single-axiom form becomes inconsistent with the law of the excluded middle in any system that has sufficient axioms to construct functions such as the function h in the previous paragraph.
Read more about this topic: Church's Thesis (constructive Mathematics)
Famous quotes containing the words relationship to, relationship, classical and/or logic:
“Whatever may be our just grievances in the southern states, it is fitting that we acknowledge that, considering their poverty and past relationship to the Negro race, they have done remarkably well for the cause of education among us. That the whole South should commit itself to the principle that the colored people have a right to be educated is an immense acquisition to the cause of popular education.”
—Fannie Barrier Williams (1855–1944)
“Christianity as an organized religion has not always had a harmonious relationship with the family. Unlike Judaism, it kept almost no rituals that took place in private homes. The esteem that monasticism and priestly celibacy enjoyed implied a denigration of marriage and parenthood.”
—Beatrice Gottlieb, U.S. historian. The Family in the Western World from the Black Death to the Industrial Age, ch. 12, Oxford University Press (1993)
“Et in Arcadia ego.
[I too am in Arcadia.]”
—Anonymous, Anonymous.
Tomb inscription, appearing in classical paintings by Guercino and Poussin, among others. The words probably mean that even the most ideal earthly lives are mortal. Arcadia, a mountainous region in the central Peloponnese, Greece, was the rustic abode of Pan, depicted in literature and art as a land of innocence and ease, and was the title of Sir Philip Sidney’s pastoral romance (1590)
“...some sort of false logic has crept into our schools, for the people whom I have seen doing housework or cooking know nothing of botany or chemistry, and the people who know botany and chemistry do not cook or sweep. The conclusion seems to be, if one knows chemistry she must not cook or do housework.”
—Ellen Henrietta Swallow Richards (1842–1911)