# Favorite non-constructive proofs.

There are many results for which a constructive proof exists but is not as nice as the non-constructive proof. For example the explicit construction of a continuous nowhere-differentiable function is rather technical compared to the proof of existence invoking the Baire category theorem.

What are your favorite non-constructive proofs or methods?

• The Claude Shannon Capacity Theorem of Information Theory: There exist codes that get arbitrarily close to capacity (due to a randomization argument) but it is very hard to construct one. In particular, it is hard to find one with an easy coding/decoding rule. – Michael Nov 15 '19 at 19:35
• I think that the existence of normal numbers satisfies this. The constructive proof required an odd construction as well as quite a bit of work to show that the constructed number is normal, but the proof that nearly all reals are normal is far prettier. – Don Thousand Nov 15 '19 at 19:40
• I think this is a great question, but not appropriate for this site - it's simply too broad. (That said, I'll mention the proof that each Chomp game is determined, which is one-long line and reveals no information about the winning strategy whatsoever!) – Noah Schweber Nov 15 '19 at 19:45
• – Dave L. Renfro Nov 15 '19 at 19:51

I have always liked:

Claim: There exist irrational numbers $$\alpha,\beta$$, possibly equal, such that $$\alpha^{\beta}$$ is rational.

Pf: Consider $$\sqrt 2 ^{\sqrt 2}$$. If it is rational then we are done. If it is irrational, then call it $$\alpha$$ and consider $$\alpha^{\sqrt 2}=2$$. And we are done.

• @MatthewDaly It's truly a great argument. Especially when you compare it to the proof that $\sqrt 2^{\sqrt 2}$ is in fact irrational. – lulu Nov 15 '19 at 19:43
• This one is nice but it isn't really any simpler than a constructive proof. $\sqrt{2}^{\log_2(9)}=3$ is an easy example. Everyone knows that $\sqrt{2}$ is irrational, and $\log_2{9}$ is irrational because $2^a$ and $9^b$ are different mod 2. – Ben Nov 16 '19 at 4:52

Shout out for Brouwer's Fixed Point theorem, if only because Brouwer's other major claim to fame is being such a strict constructivist.

Strategy Stealing is another classic example that applies to a number of turn-based games. It shows that either the first player always wins or that the game will end in a tie, assuming perfect play from both sides. The proofs never actually exhibit the strategies in question.

For example take Tic Tac Toe (on an arbitrarily large board of size $$n\times n$$). Suppose player 2 has a winning strategy $$S$$, regardless of player 1's first move. Then we make a number of observations:

1) Regardless of where player 1 plays the first $$X$$, player 2 supposidly has a winning strategy, which is a function of the position of the first $$X$$.

2) There is never a disadvantage to having one of your pieces already on the board, meaning that if player 1 already has an $$X$$ on a given square, then that cannot the worse than not having an $$X$$ on that square.

3) By 1), player 1 can adopt player 2's strategy by randomly placing an $$X$$, and then after player 2 responds with their strategy $$S$$, player 1 applies $$S$$ to player 2's response, with $$X$$ and $$O$$ switched. If $$S$$ ever calls to play on the first $$X$$ that player 1 had to place, then player 1 can make a random move by 2).

So player 2 could not possibly have a winning strategy $$S$$, which means either player 1 always wins or the game always ends in a tie.