Church's thesis (constructive mathematics)

In constructive mathematics, Church's thesis (CT) is an axiom stating that all total functions are computable. The axiom takes its name from the Church–Turing thesis,^{[citation needed]} which states that every effectively calculable function is a computable function, but the constructivist version is much stronger, claiming that every function is computable.

The axiom CT is incompatible with classical logic in sufficiently strong systems. For example, Heyting arithmetic (HA) with CT as an addition axiom is able to disprove some instances of the law of the excluded middle. However, Heyting arithmetic is equiconsistent with Peano arithmetic (PA) 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.

Formal statement[]

In first-order theories such as HA, which cannot quantify over functions directly, CT is stated as an axiom schema saying that any definable function is computable, using Kleene's T predicate to define computability. For each formula φ(x,y) of two variables, the schema includes the axiom

${\displaystyle (\forall x\;\exists y\;\varphi (x,y))\to (\exists e\;\forall x\;\exists y,u\;\mathbf {T} (e,x,y,u)\wedge \varphi (x,y))}$

This axiom asserts that, if for every x there is a y satisfying φ then there is in fact an e that is the Gödel number of a general recursive function that will, for every x, produce such a y satisfying the formula, with some u being a Gödel number encoding a verifiable computation bearing witness to the fact that y is in fact the value of that function at x.

In higher-order systems that can quantify over functions directly, CT can be stated as a single axiom saying that every function from the natural numbers to the natural numbers is computable.

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,

${\displaystyle (\forall f)(\exists e)(\forall n)(\exists u)[\mathbf {T} (e,n,f(n),u)],}$

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 ${\displaystyle {\mathsf {RCA}}_{0}}$ is consistent with this single axiom, because ${\displaystyle {\mathsf {RCA}}_{0}}$ 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.

Extended Church's thesis[]

Extended Church's thesis (ECT) extends the claim to functions which are totally defined over a certain type of domain. It is used by the school of constructive mathematics founded by Andrey Markov Jr. It can be formally stated by the schema:

${\displaystyle (\forall x\;\psi (x)\to \exists y\;\varphi (x,y))\to \exists f(\forall x\;\psi (x)\to \exists y,u\;\mathbf {T} (f,x,y,u)\wedge \varphi (x,y))}$

In the above, ${\displaystyle \psi }$ is restricted to be almost-negative. For first-order arithmetic (where the schema is designated ${\displaystyle ECT_{0}}$), this means ${\displaystyle \psi }$ cannot contain any disjunction, and existential quantifiers can only appear in front of ${\displaystyle \Delta _{0}^{0}}$ (decidable) formulas.

This thesis can be characterised as saying that a sentence is true if and only if it is computably realisable. In fact this is captured by the following meta-theoretic equivalences:^[1]

${\displaystyle HA+ECT_{0}\vdash (\varphi \leftrightarrow (\exists n\;n\Vdash \varphi ))}$

${\displaystyle (HA+ECT_{0}\vdash \varphi )\leftrightarrow (HA\vdash \exists n\;(n\Vdash \varphi ))}$

Here, ${\displaystyle n\Vdash \varphi }$ stands for "${\displaystyle n{\text{ realises }}\varphi }$". So, it is provable in ${\displaystyle HA}$ with ${\displaystyle ECT_{0}}$ that a sentence is true iff it is realisable. But also, ${\displaystyle \varphi }$ is provably true in ${\displaystyle HA}$ with ${\displaystyle ECT_{0}}$ iff ${\displaystyle \varphi }$ is provably realisable in ${\displaystyle HA}$ without ${\displaystyle ECT_{0}}$.

The second equivalence can be extended with Markov's principle (M) as follows:

${\displaystyle (HA+ECT_{0}+M\vdash \varphi )\leftrightarrow (\exists n\;PA\vdash ({\bar {n}}\Vdash \varphi ))}$

So, ${\displaystyle \varphi }$ is provably true in ${\displaystyle HA}$ with ${\displaystyle ECT_{0}}$ and ${\displaystyle M}$ iff there is a number n which provably realises ${\displaystyle \varphi }$ in ${\displaystyle PA}$. The existential quantifier has to be outside ${\displaystyle PA}$ in this case, because PA is non-constructive and lacks the existence property.

References[]

• Elliott Mendelson (1990) "Second Thoughts About Church's Thesis and Mathematical Proofs", Journal of Philosophy 87(5): 225–233.