51
$\begingroup$

I wanted to give an easy example of a non-constructive proof, or, more precisely, of a proof which states that an object exists, but gives no obvious recipe to create/find it.

Euclid's proof of the infinitude of primes came to mind, however there is an obvious way to "fix" it: just try all the numbers between the biggest prime and the constructed number, and you'll find a prime in a finite number of steps.

Are there good examples of simple non-constructive proofs which would require a substantial change to be made constructive? (Or better yet, can't be made constructive at all).

$\endgroup$
  • 3
    $\begingroup$ The existence of an Hamel Basis for every vector space (based on Zorn's lemma). More specific: the existence of a basis for $\mathbb{R}$ as a vector space over $\mathbb{Q}$. $\endgroup$ – Emilio Novati Jan 25 '15 at 13:14
  • $\begingroup$ When you say simple, do you mean that you want the proof to be relatively short, or that the proof requires relatively little "technology" (or both)? $\endgroup$ – Max Jan 26 '15 at 8:28
  • $\begingroup$ Both! I want to give an explanation understandable for people interested, but not educated mathematically $\endgroup$ – Valentin Golev Jan 27 '15 at 19:40
  • $\begingroup$ I love most of the answers, but I hesitate to pick the "right" one - I hope it's fine to leave them as they are $\endgroup$ – Valentin Golev Jan 27 '15 at 19:41

14 Answers 14

77
$\begingroup$

Some digit occurs infinitely often in the decimal expansion of $\pi$.

$\endgroup$
  • 48
    $\begingroup$ @GFauxPas: perhaps you are thinking of the statement that every digit occurs infinitely often, which is probably open. The fact that some digit occurs infinitely often is (nonconstructively) obvious, because otherwise there would only be finitely many digits altogether. $\endgroup$ – Neil Strickland Jan 25 '15 at 18:57
  • 4
    $\begingroup$ @goblin: no, I think it is not a theorem intuitionistically. An intuitionistic existence proof would produce a witness. Which digit do you think occurs infinitely often? $\endgroup$ – Neil Strickland Jan 26 '15 at 6:47
  • 5
    $\begingroup$ @goblin: Maybe the point is that intuitionistically one has to distinguish between A: 'Some digit occurs infinitely often' and B: 'It is not the case that every digit occurs only a finite number of times.' In classical logic, these are equivalent, while intuitionistically, we have that A implies B and B is constructively valid, but we don't know about A. $\endgroup$ – Hanno Jan 26 '15 at 7:52
  • 27
    $\begingroup$ Actually that must be the case for at least two different digits, since if it was true for only one digit, then it would be a rational number. $\endgroup$ – kasperd Jan 26 '15 at 23:14
  • 6
    $\begingroup$ Note that it is rather easy in intuitionistic logic to prove: for each number $n$, there is a number $k$, such that there exists a digit $d$ that occurs more than $n$ times in the first $k$ digits of $\pi$. It's "passing to the limit" that is difficult, i.e. going from $\forall n\exists d$ to $\exists d\forall n$. $\endgroup$ – cody Jan 29 '15 at 19:10
64
$\begingroup$

Claim: There exist irrational $x,y$ such that $x^y$ is rational.

Proof: If $\sqrt2^{\sqrt2}$ is rational, take $x=y=\sqrt 2$. Otherwise take $x=\sqrt2^{\sqrt2}, y=\sqrt2$, so that $x^y=2$.

$\endgroup$
  • 6
    $\begingroup$ You beat me to it! Let me just add the following: in fact, the existence of such $x$ and $y$ can be proved constructively using different witnesses, e.g., $x = e$ and $y = \ln 2$. But determining whether $\sqrt{2}^{\sqrt{2}}$ is irrational is a more difficult problem - see math.stackexchange.com/questions/446647/… $\endgroup$ – Rob Arthan Jan 25 '15 at 13:36
  • $\begingroup$ @RobArthan: Can you prove to me in one line that $\ln 2$ is irrational? $\endgroup$ – TonyK Jan 25 '15 at 13:52
  • 13
    $\begingroup$ @TonyK: not on one line! A better example would be $x = \sqrt{2}$ and $y = 2 \log_2 3$. $\endgroup$ – Rob Arthan Jan 25 '15 at 15:00
  • 2
    $\begingroup$ Note that verifying the irrationality of $2 \log_2 3$ is even slightly easier than verifying the irrationality of $\sqrt{2}$. $\endgroup$ – Ingo Blechschmidt Feb 25 '15 at 8:41
  • $\begingroup$ @IngoBlechschmidt: Thanks! I hadn't realised that. But of course you are right. $\endgroup$ – TonyK Feb 25 '15 at 9:15
26
$\begingroup$

There is a standard kind of example here. Let $T$ be any open question that requires substantial work to resolve. Consider:

There is a natural number $n$ such that $n = 0$ if and only if $T$.

That statement is clearly true, via a "simple" non-constructive proof: if $n = 0$ is not an example, then $n = 1$ is an example. But if we could produce an explicit example, then we would know whether $T$ holds.

A key point is that the proof does not require the axiom of choice, advanced mathematics, or anything other than ordinary classical logic. The nonconstructivity in classical mathematics is a direct consequence of the classical logic that is used. In constructive mathematics, the property that explicit examples can be constructed for provable existential theorems is called the witness property.

It is common for people to point out examples of "nonconstructive" consequences of Zorn's lemma or the axiom of choice, but classical set theory without the axiom of choice is equally nonconstructive.

$\endgroup$
  • 1
    $\begingroup$ There are some references in the linked Wikipedia article to the work of Myhill and Rathjen on (versions of) IZF and CZF. But this is common in most formalized constructive systems: the systems themselves don't directly tell you how to get the witness property, but by using metatheoretical techniques (e.g. realizability), we are able to show how to construct witnesses. The most recent thorough reference for that is Applied Proof Theory by Kohlenbach. $\endgroup$ – Carl Mummert Jan 25 '15 at 13:27
  • $\begingroup$ Mh I'm sorry, now I had already deleted the comment after your edit. Thanks for elaborating and for the reference to Kohlenbach's book! So far I only had a quick look at Foundations of Constructive Mathematics by Beeson, but I found it a tough read. $\endgroup$ – Hanno Jan 25 '15 at 13:29
  • 1
    $\begingroup$ All the books in this area are difficult to read, unfortunately. They all assume a significant amount of background. $\endgroup$ – Carl Mummert Jan 25 '15 at 13:32
  • 3
    $\begingroup$ I've actually seen a very similar thing used in computability. You define some set-valued function which is obviously uncomputable (e.g. "f(P,I) for program P and input I is: if P doesn't halt on I, the empty set; if P does halt on I in k steps, the set of programs that halt on I in at most k steps"). However, while f is uncomputable, f(P,I) is decidable for any given P and I (either P doesn't halt, in which case f(P,I) is the empty set, or P halts in k steps for some k, in which case we can tell if $Q\in f(P,I)$ by running Q on I for k steps and seeing if it halts). $\endgroup$ – cpast Jan 25 '15 at 23:59
  • 1
    $\begingroup$ @PrinceM, it's frankly nonsense. It just says that either T is true or false. Don't strain yourself trying to understand it; it's literally non sensical. But it is good for one thing: it exemplifies perfectly the objections that constructivists have to non-constructive proofs. I'll try to make it clearer, though: we conditionally define $n$ to be $0$ if T is true and $1$ otherwise. But $1$ is chosen arbitrarily. So we say that "there exists" some $n$ which has the property that it is equal to $0$ if and only if T is true. But we don't know what number $n$ is because we don't know T. $\endgroup$ – Wildcard Aug 12 '17 at 4:30
18
$\begingroup$

The intermediate value theorem, in the form that for a continuous function on $f:[a,b]\to\Bbb R$ with $f(a)<0<f(b)$ there exists $x\in(a,b)$ with $f(x)=0$, is not valid constructively.

See for instance here or here. The fundamental difficulty with the obvious classical proof of the IVT is that one cannot prove constructively that for $c\in(a,b)$ either $f(c)\geq0$ or $f(c)\leq0$ holds, whence one cannot decide whether to concentrate on $[a,c]$ or on $[c,b]$ in trying to localise the search for$~x$ with $f(x)=0$, and therefore no sequence of numbers converging to such an $x$ can be constructed.

$\endgroup$
  • 1
    $\begingroup$ +1. Indeed the fact that you cannot constructively decide whether a real number is zero or not also causes other classically elementary theorems to fail. For example, you cannot prove the existence of the Jordan normal form by constructive means, for if you could, you could decide whether a real $x$ is zero or not by looking at the Jordan normal form of $\tiny\begin{pmatrix} 0 & x \\ 0 & 0 \end{pmatrix}$. $\endgroup$ – Hanno Jan 26 '15 at 15:00
  • 2
    $\begingroup$ @Hanno: What you mention is an instance of the more general fact that discontinuous functions of the real numbers cannot even be defined constructively (the sign function, or the integral part, or in your example Jordan type of rank of that matrix being examples). But I don't think the statement of the IVT suffers from requiring anything discontinuous; it makes perfect sense, but just in not true constructively. $\endgroup$ – Marc van Leeuwen Jan 27 '15 at 10:52
  • $\begingroup$ In this case, the discontinuity is at a bit higher level. We can't constructively partition the reals without some extra effort. Even the partition given above, $f(c) \geq 0$ and $f(c) \leq 0$, may not be enough: since the function may need to have higher derivatives as well to be valid. In some topoi, like directed graphs, the reals might be incredibly connected. $\endgroup$ – Jason Carr Aug 5 '18 at 20:35
13
$\begingroup$

Definition: A real number $x$ is called normal if for every $b>1$ the digits $0,1,2,...,b-1$ are equally distributed in the $b$-adic expansion of $x$.

Theorem: Normal numbers exist.

The standard proof is non-constructive as it proceeds by showing that the set of non-normal numbers has Lebesgue-measure zero, hence must have non-empty complement.

I don't know if the existence of a computable normal number can be proved, and if yes, if that proof can be made constructive in the sense that one can explicitly write down an algorithm for the construction of a normal number. I'd be most interested in hearing about such a thing in case anyone knows more about it. Until then, I'm not convinced that normal numbers exist in a real sense, but only that they are unavoidable artefacts in a certain logical and set theoretical framework for the real numbers.

$\endgroup$
  • 8
    $\begingroup$ It seems the question you asked is answered by "An example of a computable absolutely normal number", Veronica Becher and Santiago Figueira, Theoretical Computer Science 270, 2002, glyc.dc.uba.ar/santiago/papers/absnor.pdf $\endgroup$ – Carl Mummert Jan 25 '15 at 13:11
  • $\begingroup$ @Carl Mummert: Thank you! $\endgroup$ – Hanno Jan 25 '15 at 13:17
  • $\begingroup$ @CarlMummert At some intuitive level, I would say that Becher and Figueira give a non-constructive proof of a constructable normal number. At least in the following sense - if I asked them what the hundredth digit of their example is, I think it would take an extremely long time to compute it. $\endgroup$ – Stephen Montgomery-Smith Jan 27 '15 at 22:29
  • 4
    $\begingroup$ @Stephen Montgomery-Smith: the normal terminology used to talk about constructive mathematics does not worry about computational complexity. So for example every natural number is "constructive" even if it cannot be written in the physical universe. But your point is valid in that they indeed don't worry about efficiency. (At the same time, $\pi$ is also a constructive real, and I have no idea what the 100th digit of $\pi$ is or how to easily compute it.) $\endgroup$ – Carl Mummert Jan 28 '15 at 0:33
9
$\begingroup$

Many existence theorems related to algebraically closed fields are inherently non-constructive.

1) Every field has an algebraic closure. Try to make this explicit for $\mathbf C(x)$ or for $\mathbf Q_p$.

2) Any two algebraically closed fields with the same characteristic and uncountable cardinality are isomorphic as fields. To take a special case, any algebraically closed field of characteristic $0$ with the same cardinality as $\mathbf C$ is isomorphic to $\mathbf C$ as a field. This comes up in number theory, where the algebraic closure of $\mathbf Q_p$ is isomorphic to $\mathbf C$. Good luck constructing the isomorphism.

3) The field automorphism of $\mathbf Q(\sqrt{2})$ that sends $\sqrt{2}$ to $-\sqrt{2}$ extends (in many ways) to a field automorphism of $\overline{\mathbf Q}$. The problem is that the only explicit automorphisms of $\overline{\mathbf Q}$ that can be written down are the identity and complex conjugation, neither of which has the desired effect on $\sqrt{2}$.

$\endgroup$
9
$\begingroup$

Baire's category theorem can be used to establish non-constructive existence proofs in a parsimonious and elegant way.

Theorem (Baire)$\phantom{---}$No complete metric space is a union of countably many nowhere dense subsets.

As Folland (1999, p. 162) puts it, “[Baire's] category theorem is often used to prove existence results: One shows that objects having a certain property exist by showing that the set of objects not having the property (within a suitable complete metric space) is [a countable union of nowhere dense sets]. For example, one can prove the existence of nowhere differentiable continuous functions in this way.”

In some instances, Baire's category theorem helps establish non-existence results. For example, it implies that the dimension of every Banach space is either finite or uncountable. That is, there exist no Banach spaces of countably infinite dimension.

$\endgroup$
  • 3
    $\begingroup$ FYI, quite often proofs making use of the Baire category theorem are constructive, in the same sense that the Cantor diagonal argument gives rise to a constructive construction of a transcendental number (discussed in the comments to Stephen Montgomery-Sm's answer below). See my comments here. $\endgroup$ – Dave L. Renfro Feb 9 '15 at 21:31
8
$\begingroup$

You can recognize any minor-closed graph class in cubic time (Robertson–Seymour theorem), but it might be undecidable to actually find such an algorithm.

Since the minor-ordering is a wqo, any minor-closed graph class $\mathcal{G}$ has a finite set of forbidden minors $\mathcal{H}$. Hence, if we want to check whether a graph $G$ is in $\mathcal{G}$, we simply check for every graph $H \in \mathcal{H}$ whether $H$ is a minor of $G$. This can be done in cubic time. However, finding $\mathcal{H}$ may not be possible.

Some graph classes that can be recognized in cubic time: Graphs of bounded genus, graphs with bounded treewidth, pathwidth and treedepth.

$\endgroup$
  • $\begingroup$ Very interesting, thank you! $\endgroup$ – Hanno Jan 26 '15 at 10:34
6
$\begingroup$

In cryptography there are many times when I wish to prove that I have some private key, but need to make it impossible (or really difficult) for you to construct that key yourself.

Take factoring, the basis of RSA.

Claim: There exist integers P and Q such that P * Q = 651041

Proof:

  1. If 651041 is prime, then 2^651040 mod 651041 = 1
  2. 2^651040 mod 651041 = 436566
  3. Thus 651041 is composite.

Certainly you could construct P and Q by trial division, but it could take you a while (by hand). Do you measure the difficulty of a constructive proof in terms of the amount of space it takes to write down, or the length of time it would take to run it?

Do you allow for probabilistic proofs? If so, you might also consider looking at the idea of Zero Knowledge Proofs: http://en.wikipedia.org/wiki/Zero-knowledge_proof

The zero knowledge proof I remember best deals with graph coloring.

I claim that a particular graph G has a valid k-coloring.

Steps:

  1. (Before making my claim) I generate graph G and its coloring myself in such a way as to guarantee that it has a valid k-coloring.
  2. I claim to you that G has a valid k-coloring.
  3. I randomly shuffle the colors in my coloring (Ex. All red nodes become blue, all blue nodes become green and so forth).
  4. I send you the shuffled colors of all the nodes of the graph, but I encrypt each node's color with a separate key.
  5. You pick a single edge of the graph, and I send you the keys to decrypt the colors on the two nodes of that edge.
  6. When you decrypt the colors, you can verify that my coloring is correct by seeing that the decrypted colors don't match.

We repeat steps 3-6 until you believe that I really do have a valid coloring of the graph. Thus I have proved that there exists a valid coloring of graph G without getting you any closer to constructing a valid coloring yourself.

$\endgroup$
  • 10
    $\begingroup$ There is a fundamental difference between being constructively provable and having an efficient construction. In the purely finite domain dealt with in cryptography everything that exists does so constructively, by trivial brute force constructions. In other words this answer is not an answer to the question. $\endgroup$ – Marc van Leeuwen Jan 27 '15 at 11:14
2
$\begingroup$

Uncountability of the real numbers. Since the set of all finitely-describable numbers (in any formal language) is countable, by definition uncountability implies the existence of numbers that are not finitely describable.

To illustrate my point, here are some examples of finitely-describable numbers:

  • Any natural number or integer
  • Any rational number
  • Any algebraic number, defined for this purpose as a solution to an arbitrary polynomial equation with rational coefficients
  • Any computable number
  • Any number which can be defined by an infinite series of finite terms, such as pi, e, etc
  • Any number definable as a complement or arbitrary Boolean combination of computable sets, eg the sequence of digits representing the halting set, or Chaitin's constant
  • Any solution to an arbitrary finite first-order predicate
  • Any solution to a finitely-generated infinite list of first-order predicates
  • etc

So, any number we can describe using a finite number of symbols is (by definition) a member of a well-defined countable subset of the reals (the set of numbers definable in the language being used). So, even though there are infinitely more "undefinable" than "definable" reals, we cannot construct an "undefinable" real.

$\endgroup$
  • 8
    $\begingroup$ There's a perfectly constructive interpretation of Cantor's theorem: 'given any (constructively) countable list of real numbers there is a procedure for constructing a real number not on that list'. The glitch is that the set of 'finitely describable' (to use your phrase) numbers is countable, but it's not constructively countable; you cannot exhibit a mapping from this set to $\omega$. $\endgroup$ – Steven Stadnicki Jan 25 '15 at 18:44
  • 1
    $\begingroup$ @StevenStadnicki: While it is probably still true constructively that for any countable list of real numbers a real number not on that list can be produced, I do think Cantor's argument needs some modification constructively, because one cannot contruct decimals for arbitrary real numbers (that being a discontinuous operation). Cantor's argument does apply without much change to the more basic form: for any countable list of sets of natural numbers, a set of natural numbers not on that list can be produced. $\endgroup$ – Marc van Leeuwen Jan 27 '15 at 11:07
  • 1
    $\begingroup$ @MarcvanLeeuwen I suppose it depends on what one thinks of as 'Cantor's argument'. The traditional presentation certainly uses decimals, but that presentation is already awkward for any number of reasons, and the fact that decimals are such a miserable representation for real numbers (particularly for constructivist purposes) just makes it that much worse. But I don't think of Cantor's argument as being the decimals; I think of it as being the diagonalization itself, and that can be done on e.g. continued fraction expansions or the like. $\endgroup$ – Steven Stadnicki Jan 27 '15 at 19:16
  • $\begingroup$ @StevenStadnicki: I agree. But continued fractions are just as discontinuous as decimals are, of course. $\endgroup$ – Marc van Leeuwen Jan 28 '15 at 6:05
2
$\begingroup$

I think that there are different kinds of examples, some cited in the other answers. To see the difference I give three examples.

1) The number $a$ so defined: $a=1$ if Goldbach's Conjecture ($G$) is provable in ZFC, $a=0$ if $\neg G$ is provable in ZFC, a=2 if $G$ is undecidable in ZFC. The value of this number is not known today, but it can eventually become known when someone solves the conjecture.

2) Chaitin's constant is an example of a number that is well defined but not computable so nobody will never know it.

3) Let $\gamma$ be a real number defined as, say: $\gamma= 12.23873560031\cdots$ and define: $c=3*10^2+3*10^5+3*10^{10}+\cdots$ where we have chosen the digit $3$, but it could be any digit, and the exponents of $10$ are the positions of this digit in the decimal expansion. Then $c$ may be a number or not, depending on whether this expansion has a finite number of $3$s in its expansion. If we chose $ \gamma= \zeta(5)$ (the Riemann zeta function), we don't know today if it has a finite number of digits $3$ (so far as I know), so we don't know if $c$ is a number or not. If someone proves that $\zeta(5)$ actually has a finite number of $3$ in its expansion then we will have two possibilities: The proof is not be constructive, i.e. we cannot find the position of the last $3$, and $c$ is really an integer number, so it is computable but we can never find it. Or the proof is constructive and we know the position of the last $3$ and we can actually find the number $c$.

$\endgroup$
2
$\begingroup$

There are reasonably-natural games (two player, perfect information) which we can prove are won by Player $1$, but for which no winning strategy is known; or, at least, for which it is not obvious how to transform the classical proof that Player $1$ wins into a constructive proof.

The classic example is Chomp: we start with an $m\times n$ square grid. On each turn, a player removes some tile, along with every tile below and to the left of that tile. The player who takes the top-right square loses.

Since this is a finite game, one player or the other must have a winning strategy. And player $2$ can't have a winning strategy, by a strategy stealing argument: Imagine player $1$ ate the bottom-left square, and player $2$'s winning response was to eat square $\alpha$. Then player $1$ could have just eaten square $\alpha$, and then pretended for the rest of the game that they were player $2$, and force the real player $2$ to lose by playing their own strategy against them.

Although this is perfectly valid classically, it's highly non-constructive.


Actually, determinacy statements in general might push the bounds of constructivity. The usual proof of open determinacy is to assume Open has no winning strategy, and have Closed simply play to preserve Open's lack of a winning strategy. This is impredicative, though (and this is backed up by the fact that computable open games need not have hyperarithmetic winning strategies), and I suspect open determinacy is not true in most constructive theories. (But I could very easily be wrong.)

$\endgroup$
1
$\begingroup$

My favourite one: $[0, 1]$ is compact, i.e. every open cover of $[0, 1]$ has a finite subcover.

Proof: Suppose for a contradiction that there is an open cover $\mathcal{U}$ which does not admit any finite subcover. Thus, either $\left[ 0, \frac{1}{2} \right]$ or $\left[ \frac{1}{2}, 1 \right]$ cannot be covered with a finite number of sets from $\mathcal{U}$ - name it $I_1$. Again, one of the two $I_1$'s subintervals of length $\frac{1}{4}$ can't be covered with a finite number of sets from $\mathcal{U}$. Continuing, we get a descending sequence of intervals $I_n$ of length $\frac{1}{2^n}$ each, every of which cannot be finitely covered.

By the Cantor Intersection Theorem,

$$\bigcap_{n=1}^{\infty} I_n = \{ x \}$$

for some $x \in [0, 1].$ But there is such $U \in \mathcal{U}$ that $x \in U$ and so $I_n \subseteq U$ for some sufficiently large $n$. That's a contradiction.

But given an arbitrary cover $\mathcal{U}$, I think finding a finite subcover may be a somewhat tedious task. :p

P.S. There actually comes a procedure from the proof above:

  1. See if $[0, 1]$ itself is covered by one set from $\mathcal{U}$.
  2. If so, we're done. If not, execute step 1. for $\left[ 0, \frac{1}{2} \right]$ and $\left[ \frac{1}{2}, 1 \right]$ to get their finite subcovers, then unite them.

The proof guarantees you will eventually find a finite subcover (i.e. you'll never end up going downwards infinitely), but you cannot tell how long it will take. So it is not as constructive as one would expect.

$\endgroup$
1
$\begingroup$

How about Cantor's proof that transcendental numbers exist? (Because the set of algebraic numbers is countable, and the set of real numbers is uncountable.) If I remember correctly, this proof appeared only soon after Liouville had provided an explicit construction (namely $\sum 10^{-n!}$).

I know this example is hinted by other answers given, but I think it is worth stating explicitly.

$\endgroup$
  • 3
    $\begingroup$ I'm afraid that proof is constructive! Building an explicit enumeration of the algebraic numbers isn't terribly hard, and Cantor's diagonalization argument explicitly gives a process to compute each digit of the non-algebraic number. $\endgroup$ – cody Jan 29 '15 at 19:25
  • $\begingroup$ @cody Agreed. But it's a bit like the construction of normal numbers (discussed in the comments to another answer to this question). At some intuitive level, the construction is far less constructive than $\sum 10^{-n!}$. $\endgroup$ – Stephen Montgomery-Smith Jan 29 '15 at 22:11
  • 1
    $\begingroup$ The explicit computation of the digits is harder, but the proof that it is indeed irrational is much easier! $\endgroup$ – cody Jan 30 '15 at 15:47
  • $\begingroup$ @cody You meant transcendental, not irrational. But I agree. $\endgroup$ – Stephen Montgomery-Smith Jan 30 '15 at 17:26

protected by davidlowryduda Jan 26 '15 at 9:54

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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