The constructivist principle is however also given, in different theories and incarnations, as a fully formal axiom.
The formalizations depends on the definition of "function" and "computable" of the theory at hand.
as a principle, then for a predicate of the form of a family of existence claims (e.g.
in a computable manner, the contrapositive of the axiom implies that this is then not validated by any total function (i.e. no mapping corresponding to
It thus collapses the possible scope of the notion of function compared to the underlying theory, restricting it to the defined notion of computable function.
In turn, the axiom is incompatible with systems that validate total functional value associations and evaluations that are also proven not to be computable.
This theory disproves some universally closed variants of instances of the principle of the excluded middle.
, at the cost of introducing abbreviating notation involving the sign already used for arithmetic equality.
may be stated as an axiom schema saying that for any definable total relation, which comprises a family of valid existence claims
being a Gödel number encoding a verifiable computation bearing witness to the fact that
Relatedly, implications of this form may instead also be established as constructive meta-theoretical properties of theories.
extends the claim to relations which are defined and total over a certain type of domain.
This may be achieved by allowing to narrowing the scope of the universal quantifier and so can be formally stated by the schema: In the above,
These first-order formulations are fairly strong in that they also constitute a form of function choice: Total relations contain total recursive functions.
The extended Church's thesis is used by the school of constructive mathematics founded by Andrey Markov.
denotes the weaker variant of the principle in which the premise demands unique existence (of
In higher-order systems that can quantify over (total) functions directly, a form of
In terms of the primitive recursive predicates, This postulates that all functions
A total function has a unique return value for every input in its domain.
By inserting a double negation before the index existence claim in the higher order version, it is asserted that there are no non-recursive functions.
A related statement is that any decidable subset of naturals cannot ruled out to be computable in the sense that The contrapositive of this puts any non-computable predicate in violation to excluded middle, so this is still generally anti-classical.
E.g. a principle always granting existence of a total recursive function
, implies the negation of the universally quantified version of the law of the excluded middle for some predicates.
Further assuming Church's thesis one in turn concludes that this is computable - a contradiction.
associated with the halting question, relating any code from an enumeration of Turing machines and values from
Assuming the classical tautology above, this relation can be proven total, i.e. it constitutes a function that returns
can typically be shown to be closed under a Church's rule and the corresponding principle is thus compatible.
This above thesis can be characterized as saying that a sentence is true iff it is computably realisable.
is non-constructive and lacks then existence property, whereas Heyting arithmetic exhibits it: The second equivalence above can be extended with
together with alternative variants of Church's thesis, more such metalogical existence statements have been obtained.