Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

That old MSE question discusses the notion of “constructive proof”, and the answers explain that there is no one definition of what "constructive" or "non-constructive" means.

Recently, I thought of the following definition : let us say a theory $T$ (at least as strong as Peano arithmetic, say) is “constructive” if whenever a nonconstructive proof about integers exists, then there is a constructive equivalent, i.e. whenever $T$ proves (“non-constructively”) that $\exists \ \text{integer } n,\ \phi(n)$ for some predicate $\phi$, then there is an integer $n_0$ such that $T$ proves $\phi(n_0)$.

There is a connection between this notion and $\omega$-consistency : if $T$ is consistent but $\omega$-inconsistent, then T is not “constructive”. But (unless I missed something), if we only know $T$ is $\omega$-consistent, we cannot know in advance if $T$ will be constructive or not.

Is it known whether PA,ZF or ZFC are “constructive” in this sense ?

share|improve this question

2 Answers 2

up vote 3 down vote accepted

PA is not constructive in this sense. For note

$PA \vdash \exists x(\varphi(x) \lor \forall y\neg\varphi(y))$.

Now take the case where $\varphi(x)$ is $T(e,e,x)$, which expresses the relation which holds when $x$ codes the steps in a halting computation by Turing machine number $e$ run on input $e$. This Kleene relation is decidable, and indeed is expressible in the language of $PA$. If, for given $e$, there were always a number $n$ such that

$PA \vdash (T(e, e, n) \lor \forall y\neg T(e, e, y))$,

then we could do a terminating search for $n$ given $e$ by enumerating $PA$ proofs, and by then deciding whether $T(e,e,n)$ it would be decided whether Turing machine $e$ halts on input $e$, assuming $PA$ is sound. But we know the halting problem is undecidable.

share|improve this answer
    
I don't know who should get credit for that cute proof. And I don't know either if there is some other nice proof which takes a rather different route to bringing out this fundamental difference between Heyting Arithmetic and Peano Arithmetic. –  Peter Smith Dec 8 '13 at 14:34
2  
There are also ways to do this that do not require the halting problem. For example, for every sentence $\phi$, just classical logic and $(\exists n)[n \not = 0]$ proves $(\exists n)[(n = 0 \land \phi) \lor (n \not = 0 \land \lnot \phi)]$. However, proving that a particular value works for $n$ requires either proving $\phi$ or proving $\lnot \phi$. –  Carl Mummert Dec 10 '13 at 12:44
    
@CarlMummert Thank you Carl, I prefer your version. –  Ewan Delanoy Dec 11 '13 at 8:12
    
And so do I :-) –  Peter Smith Dec 11 '13 at 9:26

This property is called the "numerical existence property". It is common in constructive systems and rare in systems with classical logic. There is an article on Wikipedia that lists several references.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.