18
$\begingroup$

This came up in a question on the xkcd forums. Is it possible to have a nonconstructive metaproof, i.e. a proof that there exists a proof in some formal system which does not construct said proof? Are there any known examples, preferably with some well-known formal system like PA?

Conversely, is it possible to prove a meta-metatheorem saying that any metaproof can be used to find a proof?

$\endgroup$
6
  • 7
    $\begingroup$ Sure. Metatheorem: any question I get on my homework has a proof. Metaproof: suppose otherwise. Then it would not be on my homework. $\endgroup$ Jun 8, 2011 at 16:01
  • $\begingroup$ Isn't there a story where a famous mathematician was assigned an open problem as homework by a devious professor, and ended up solving it? $\endgroup$ Jun 8, 2011 at 16:03
  • 7
    $\begingroup$ @Qiaochu: you are very optimistic about the infallibility of your teacher. $\endgroup$ Jun 8, 2011 at 16:03
  • $\begingroup$ Isn't there some question on how to show intuitionistically that Kripke models are complete for first-order intuitionistic (single-sorted) theories. Isn't the usual proof classical? $\endgroup$ Jun 8, 2011 at 16:34
  • 1
    $\begingroup$ Another example is completeness of Grothendieck toposes for higher-order intiotionistic logic. I think the proof is classical, and it's not clear how to make it intuitionistic. $\endgroup$ Jun 8, 2011 at 16:35

3 Answers 3

24
$\begingroup$

In theory, David’s answer is correct. Nevertheless, in practice it is perfectly possible to prove the existence of a proof non-constructively (such as by manipulating models and then appealing to the completeness theorem) where no one has a clue how to actually find the proof.

One example which springs to mind is Jacobson’s theorem: if $R$ is a ring such that for every $a\in R$ there exists an integer $n > 1$ such that $a=a^n$, then $R$ is commutative. By completeness of equational logic, this implies that for any $n > 1$, there exists an equational derivation of $xy=yx$ from the axioms of rings and $x^n=x$. Already finding such derivation for $n=3$ is a nontrivial exercise; explicit derivations are known for some $n$, but not in general.

$\endgroup$
3
  • $\begingroup$ Great answer. But I would still be interested in more examples, if anyone has some more. $\endgroup$ Jun 8, 2011 at 19:19
  • 2
    $\begingroup$ Do you have your quantifiers in the right order in that statement? There are two closely related theorems of Jacobson that look like this and I'm not sure which one you mean. $\endgroup$ Jun 8, 2011 at 21:49
  • 2
    $\begingroup$ The quantifiers in the assumption of Jacobson’s theorem I have in mind are $\forall a\in R\,\exists n > 1\,a^n=a$. However, in order to express this in equational logic, the exponent has to be fixed, hence we only consider the corollary of the theorem with the stronger assumption $\exists n\,\forall a\,a^n=a$ (more precisely, for each particular constant $n$, we consider the theorem with assumption $\forall a\,a^n=a$). $\endgroup$ Jun 9, 2011 at 10:21
5
$\begingroup$

If the proof system is recursively axiomatizable, this situation cannot occur.

If there exists a proof of $\Theta$, there exists an algorithm to find that proof. Namely, search the recursively enumerable set of deductions until you find a proof of $\Theta$. This must terminate, as we have proved that $\Theta$ is provable.

If the proof system is NOT recursive, then this may be possible. Consider the following set of axioms $\Sigma$ in the signature of arithmetic. Let $A$ be an infinite set which does not contain any infinite r.e. set. Define $$ \Sigma = \{ (\bar k = \bar k) \wedge \sigma \mid k \in A, k > \ulcorner \sigma \urcorner, \mathfrak N \models \sigma \} $$

Now, note that any sentence provable in $Th(\cal N)$ is provable is in $\Sigma$. However, there is no algorithm to transform produce such proofs from $\Sigma$. To do so would require enumerating arbitrarily large elements of $A$, which is impossible

$\endgroup$
4
  • $\begingroup$ This can hardly be seen as a constructive proof, as the "constructive" part is entirely divorced from the "proof" part. $\endgroup$ Jun 8, 2011 at 16:05
  • $\begingroup$ You are implicitly using Markov principle, I think. $\endgroup$ Jun 8, 2011 at 16:33
  • 1
    $\begingroup$ I don't know that this addresses the spirit of the question. This algorithm guarantees that it can find a proof but it does not guarantee that this will happen before I die or that the proof can be made short enough for me to finish reading it before I die, yet it is still possible that I can prove by other means that a proof exists in perhaps 10 minutes. $\endgroup$ Jun 8, 2011 at 16:47
  • 2
    $\begingroup$ There's a stronger form of this assertion. If the proof system is recursive, the statement "T proves $\phi$" is itself a $\Sigma_1$ statement, so if the non-constructive proof itself takes place in a "reasonable" system, it is possible to extract an explicit witness, which would be a direct proof. $\endgroup$ Jun 8, 2011 at 17:58
0
$\begingroup$

What about examples from nonstandard analysis? By the transfer principle, given a proof of $\phi$ in nonstandard analysis, we know there exists a proof of $\phi$ using only standard techniques; but there is in general no nice way to extract the standard proof from the nonstandard proof, and if I recall correctly there are theorems which have a known nonstandard proof with no known standard proof. Would this count as a non-constructive metaproof?

$\endgroup$
2
  • 1
    $\begingroup$ One can go from nonstandard proof to standard proof using ultrapowers. It is just that such a proof may not be as "elegant". $\endgroup$ Jun 8, 2011 at 16:28
  • $\begingroup$ If we're talking about proofs in formal systems of nonstandard analysis, there are general methods for extracting the standard proof from it. For instance, "Weak theories of nonstandard arithmetic and analysis" by Jeremy Avigad. $\endgroup$ Jun 8, 2011 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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