2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Michael Nov 15 '19 at 19:35
  • $\begingroup$ 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. $\endgroup$ – Don Thousand Nov 15 '19 at 19:40
  • $\begingroup$ 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!) $\endgroup$ – Noah Schweber Nov 15 '19 at 19:45
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @MatthewDaly It's truly a great argument. Especially when you compare it to the proof that $\sqrt 2^{\sqrt 2}$ is in fact irrational. $\endgroup$ – lulu Nov 15 '19 at 19:43
  • 3
    $\begingroup$ 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. $\endgroup$ – Ben Nov 16 '19 at 4:52
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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