Favorite non-constructive proofs.

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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.