# Examples of non-constructive results

I'm giving a talk on constructive mathematics, and I'd like some snappy examples of weird things that happen in non-constructive math.

For example, it would be great if there were some theorem claiming $\neg \forall x. \neg P(x)$, where no $x$ satisfying $P(x)$ were known or knowable.

But other examples are welcome as well.

-
A standard example is the Intermediate Value Theorem, with $P(x)$ being "$f(x)=0$". But that one is not "weird"... Banach-Tarski is a pretty weird example. – Arturo Magidin Feb 15 '12 at 18:21
@ArturoMagidin, the IVT has a constructive version based on nested intervals. – lhf Feb 15 '12 at 18:22
– lhf Feb 15 '12 at 18:23
@lhf: The IVT ultimately relies on the supremum property; the proofs of which that I can think of right now are all by contradiction and non-constructive – Arturo Magidin Feb 15 '12 at 18:24

1
– lhf Feb 15 '12 at 18:25
show 1 more comment

## 6 Answers

At a fun level, there is the two-player game of Chomp.

Briefly, you have an $m\times n$ chocolate bar, divided into squares as usual. The lower left-hand little square is poisoned. The two players, A and B, play alternately. At any move, a player picks the lower left-hand corner of a square, and eats all squares above and/or to the right of that corner. The objective is not to eat the poisoned square.

One can prove quite simply that A has a winning strategy for any chocolate bar except the $1\times1$. But the proof is indirect. It is clear that for any specific bar, one of the two players has a winning strategy. One then shows that if B had a winning strategy, then A could adapt that strategy and win, by taking the square in the upper right-hand corner.

However, for even modest-sized chocolate bars, say $19\times 19$, no winning strategy for A is known. I may be out of date on the $19$, but know that computer searches for strategies have not had great success.

-

2
More generally, every two-player game of perfect information in which every play is finite and there are no ties has a winning strategy for one player or the other, by the Gale/Stewart theorem. E.g. if we declare that white wins any draw, then chess has this property and we have no idea which player has the winning strategy. – Carl Mummert Feb 16 '12 at 0:46
I think you mean that no efficient winning strategy for A is known? – Dan Brumleve Feb 16 '12 at 4:57
@Dan Brumleve: Yes, I was using the "no known" perhaps too casually, for any board one can try everything. – André Nicolas Feb 16 '12 at 5:04

1
Actually today one student told me a strategy that works for square bars (like $19\times 19$): Let's say the squares are numbered, the poisoned being (1,1). A picks $(2,2)$ as his first move. Now at each move B can only pick $(1,k)$ or $(k,1)$, and A just responds by reflecting the move, picking $(k,1)$ or $(1,k)$. It's easy to see that B is forced to take the last square. On a non-square board this strategy would fail - if A picked $(2,2)$, B would just pick the necessary squares to make the board diagonally symmetric and subsequently win the game. – Petr Pudlák Oct 29 '12 at 18:21

The existence of a Hamel Basis, that is, a basis for $\mathbb R$ as a vector space over $\mathbb Q$. No one knows a Hamel basis; it's probably unknowable in some sense.

The existence of a basis for every vector space is equivalent to the axiom of choice, which is the non-constructive piece of math by excellence.

-

2
There are plenty of constructive systems, such as Martin-Lof type theory, which include the axiom of choice. It is only nonconstructive when combined with various other principles of classical mathematics, such as the law of the excluded middle. – Carl Mummert Feb 15 '12 at 22:43

If $\Phi$ is any statement, the following is a consequence of the law of the excluded middie: $$(\exists n \in \mathbb{N})[(n = 0 \land \Phi) \lor (n \not = 0 \land \lnot \Phi)]$$ It will only be provable constructively if either $\Phi$ or $\lnot \Phi$ is provable constructively, because to prove it constructively you would have to produce an actual value of $n$, which means you would have to decide $\Phi$.

-

At least some time ago (I'm not sure if this has been cleared up recently), it was not known which of the quantities $\sqrt 2^\sqrt 2$ and $(\sqrt 2^\sqrt 2)^\sqrt 2$ furnishes an example of an irrational number raised to an irrational power that is rational.

-

3
– Steven Stadnicki Feb 15 '12 at 19:43

Brouwer's fixed point theorem in 2 dimensions is equivalent the fact that the game of Hex has a winning strategy but no one knows what that strategy is.

-

It is equivalent to at least one player winning eventually, it has nothing to do with strategy. But we do know that the first player can always win in Hex. – Michael Greinecker Feb 16 '12 at 1:31
@MichaelGreinecker Perhaps Wikipedia is wrong on this one then, but it says "John Nash proved in 1952 that a game of Hex cannot end in a tie, and that for a symmetric board there exists a winning strategy for the player who makes the first move (by the strategy-stealing argument). However, the argument is non-constructive : it only shows the existence of a winning strategy, without describing it explicitly. Finding an explicit strategy has been the main subject of research since then." – Ragib Zaman Feb 16 '12 at 3:45
That is true, but the relation between Hex and the (two-dimensional) Brouwer fixed point theorem is due to David Gale. Nash's "stealing strategy"-argument is however a nice example of a nonconstructive proof. – Michael Greinecker Feb 16 '12 at 9:22
@MichaelGreinecker I understand now, I was grouping two distinct results together. Thanks. – Ragib Zaman Feb 16 '12 at 11:55

It has been shown that almost all real numbers are normal in all bases (ref?), but I don't think that anyone has ever exhibited such a number.

-

1
@CarlMummert: You may be thinking of a different result; this one is pretty easy to prove. My favorite proof is probabilistic. Fix a base $b$. Since the base-$b$ digits of a $U(0,1)$ random variable $U$ are iid uniform on $\{0, 1, \dots, b-1\}$, the strong law of large numbers gives that $U$ is normal in base $b$, almost surely. Taking a countable intersection, $U$ is normal in every base, almost surely. Or in other words, Lebesgue-almost-every $x \in [0,1]$ is normal in every base. – Nate Eldredge Feb 15 '12 at 23:55

1
@Nate Eldredge: the question I had asked about in a deleted comment was about the Champernowne number .123456789101112... which is known to be normal in base 10, but AFAIK not known to be normal in other bases. – Carl Mummert Feb 16 '12 at 0:39
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 34, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9597520232200623, "perplexity_flag": "middle"}