# Applications of nonconstructive mathematics

What are good/interesting examples of theorems than can be proven classically, but not constructively, and have applications in e.g. physics?

-
Which sort of "constructively" are you referring to? Errett Bishop's constructivism, for example, or just avoiding the use of the Axiom of Choice? – Robert Israel May 14 '12 at 16:06
@Robert Israel: The former. – Ruud Koot May 14 '12 at 16:16

In general it is very difficult to be sure that a theorem cannot be constructivised in some form that preserves its applicability. As you will notice most of the answers offered have comments attesting this fact.

One reason for this is that many non-constructive theorems in analysis become constructive when they are relaxed a little bit. A typical example is the mean value theorem. It does not hold constructively as usually stated, but it its $\epsilon$ version does: if $f$ is continuous and $f(0) < 0 < f(1)$ then for every $\epsilon > 0$ there is $x \in [0,1]$ such that $|f(x)| < \epsilon$. Many other theorems can be relaxed in this way: Hahn-Banach, Brouwer fixed-point, etc. Moreover, such relaxed versions often make more sense in applications than their exact versions, for example because we need to take into account noise, errors, or bounded numerical precision.

Another reason is that for applications we typically do not need a theorem in its full generality because we have extra information, which allows for a specialized constructive version. For example, while the general mean value theorem fails constructively, it holds for locally non-constant maps. Special versions of Hahn-Banach holds constructively, and they will typically suffice in concrete situations.

There is a third reason why it is difficult to find classical theorems with applications that cannot be constructivized. Most applications belong to the fields of physics and computer science, which are both very naturally constructive. Physics is constructive by its very nature because "everything is continuous" in the real world, while in computer science "everything is computable". These are two main motivations for intuitionistic mathematics (namely Brouwerian continuity principles or sheaf-theoretic models, and computable interpretations of intuitionistic mathematics).

Lastly, there remains the simple fact that one has to perform an exhaustive literature search to be sure that a theorem has not been constructivized. A lot more has been constructivized than one would think, and the only obstacle seems to be lack of man power.

-
We may summarize, in the words of the Rolling Stones: You can't always get what you want, but if you try sometimes you might find you get what you need. – Gerry Myerson May 16 '12 at 5:33

I would assume that the Hahn-Banach theorem would have to be close to the top of any list.

-
Bishop-ists might counter that in the cases they (and hence, by inference, all right-minded people) care about, one can do Hahn-Banach constructively. (I say this as someone who uses HB non-constructively all the time.) – Yemon Choi May 14 '12 at 17:34
Almost. There is a constructive Hahn-Banach, see blms.oxfordjournals.org/content/21/1/79.abstract and cs.math.ist.utl.pt/ftp/pub/CederquistJ/98-CCN-hahnbanach.pdf. – Andrej Bauer May 14 '12 at 21:08
@Andrej: Are these the same normed spaces as mentioned obliquely by @Yemon? – Igor Rivin May 15 '12 at 0:13
Well, I can't read Yemon's mind, but I think so, yes. Ishihara's paper would certainly count as episcopal. (There is an ubounded potential for silly jokes based on the last name "Bishop".) – Andrej Bauer May 15 '12 at 8:54
Are you sure the paper would not count as Erratic? Two can play at this game... – Igor Rivin May 15 '12 at 11:44

The mean and pointwise ergodic theorems are non-constructive, and I understand they were originally developed for applications to thermodynamics.

-
Jeremy Avigad has recenty done some proof-mining work which extracts constructive meaning from ergodic theorems, see andrew.cmu.edu/user/avigad/Papers/ergodic.pdf – Andrej Bauer May 14 '12 at 21:10
Bishop gave a constructive interpretation as well, by giving an upcrossing proof similar to Doob's proof of martingale convergence. It is interesting because Bishop's result is still used to get numerical bounds on Ergodic convergence. (Also, the paper @Andrej cited of Avigad's was a summary of work Avigad did with Philipp Gerhardy, Ksenija Simic, and Henry Towsner. Some of it was based on Bishop's work. Many of the results are analogous to the martingale and differentiability results I mentioned in my answer.) – Jason Rute May 14 '12 at 21:37

One of the simplest is the monotone convergence principle, that every bounded increasing sequence of rationals is convergent.

Along with Henry Towsner's example of the Ergodic theorem there is Doob's martingale convergence theorem and Lebesgue's theorem that every function of bounded variation is differentiable a.e.

However, if more information is known then this non-constructivity can be overcome. For example, with a martingale, if the limit is computable in the $L^1$ norm and the $L^1$-bound is computable, then the rate of convergence is computable (both convergence in measure and a.e. convergence). (I assume the proof is constructive, but I haven't worked that out. However, computable rates of convergence are one of the most important consequences of constructive proofs.)

Similarly, the Lebesgue differentiation theorem has computable rates of convergence ($L^1$ convergence and a.e. convergence) since the limit is known (it is the function itself) and the Hardy-Littlewood maximal lemma controls the maximal amount of deviation from the limit.

-

Sard's Theorem, which is foundational, may be an example of a theorem of the sort you are looking for when the differentiability class of the function is low. Let's recall its classical statement:

Sard's Theorem: Let $f\colon\, \mathbb{R}^n\to\mathbb{R}^m$ be a $k$ times continuously differentiable function, where $k\geq \text{max}(n-m+1,1)$. Let $X$ be the critical set of $f$. Then $f(X)$ has Lebesgue measure $0$ in $\mathbb{R}^m$.

A constructivist version was proven by Yuen-Kwok Chan in 1971:

Chan, Yuen-kwok, A constructive proof of Sard's theorem. Pacific J. Math. 36, 291–301 (1971; MR0276988).

The constructivist version relaxes the statement of Sard's theorem in a benign way ("critical points" are replaced by "almost critical points") and in at least one less benign way:

The function $f$ is taken to be a $k$ times continuously differentiable function, where $k\geq 2+\frac{1}{2}(n-m)(n-m+1)$.

I can imagine this being a real issue, because the function actually given to you might be $C^k$ only for $\text{max}(n-m+1,1)\leq k< 2+\frac{1}{2}(n-m)(n-m+1)$. John Milnor on Mathematical Reviews asks whether the bound on $k$ can be tightened, and so does the author at the end of the paper. If not, then Sard's Theorem for small $k$ seems to me to be a genuinely important result which can be proved classically, but not constructively.

-
I'm confused -- wouldn't replacing critical points by "almost critical points" make the statement stronger? Because then you'd be asserting that an even larger set still has measure 0. – Harry Altman May 16 '12 at 7:15
The statement of the constructive version isn't that the set is of measure zero, but that it is "measure epsilon", thus the statement is not stronger. – Daniel Moskovich May 16 '12 at 8:38

The Knuth-Bendix completion algorithm is used in computer algebra. Its proof of correctness relies on Kruskal's tree theorem, if I understand correctly. The proof of Kruskal's tree theorem is very nonconstructive: http://en.wikipedia.org/wiki/Kruskal%27s_tree_theorem

-
I'm not sure Kruskal's tree theorem is nonconstructive. I recall seeing several approaches to constructive proofs, though the only one I can find quickly is Wim Veldman's "An intuitionistic proof of Kruskal's Theorem". – Henry Towsner May 14 '12 at 17:46
Really? The proof I know relies on Dickson's lemma, en.wikipedia.org/wiki/Dickson's_lemma, which is non-constructive. But as far as I remember, the lemma is needed only to show termination. So, if you believe in Markov Principle, as some constructivists do, then that would count as a constructive theorem. – Andrej Bauer May 14 '12 at 20:57
I was discussing Dickson's lemma with some colleagues last year. As far as I can tell, the statement becomes constructive if we weaken the statement to say that any non-empty subset is a contained in a union of finite many quarter planes. I don't know if this weaker version is sufficient for the Knuth-Bendix completion. ... BTW also any empty subset also works, so we can constructively prove that any empty or non-empty subset is contained in a union of finite many quarter planes. – Russell O'Connor May 22 '12 at 7:08

A famous Martin Gardner mathematical games column had a number of April Fool items, one of which was about a guy getting rich by duplicating gold spheres using the Banach-Tarski theorem. I guess that doesn't count as a real application, but it's surely nonconstructive and I can't resist mentioning it.

-

Well, the Brouwer Fixed Point Theorem comes to mind. An example of an application: http://physicsoffinance.blogspot.com/2011/09/brouwers-fixed-point-theoremwhy.html

-
The standard proof (using Sperner's lemma) is quite constructive, I think. – Igor Rivin May 14 '12 at 16:06
Yes, you are right. I was thinking of the original proof... – Felix Goldberg May 14 '12 at 16:11
Thanks, but Brouwer Fixed point theorem fails in the effective topos, therefore it cannot have a constructive proof. Of course, the approximate version is constructive. The link pointed to in the answer is not a serious application, it is just popular math. – Andrej Bauer May 14 '12 at 21:01
@Igor: arxiv.org/abs/0804.3199 – Andrej Bauer May 15 '12 at 5:10
The jstor paper referenced above is "constructive" in the sense that it is "explicit". The paper is written in classical logic, it seems. – Andrej Bauer May 15 '12 at 8:57