What are natural examples of non-relativizable proofs?

What are the most awesome examples of non-constructive existence proofs?

• Answer:

  Almost constructive proofs An almost-constructive-proof shows that something exists, and is one of a few possible constructions, without being able to pinpoint the specific one. It's a really peculiar state of affairs. A famous example of this kind asks us to find two irrational numbers [math]a,b[/math] such that [math]a^b[/math] is rational. Well, we can take [math]a=b=\sqrt{2}[/math]. Is [math]a^b[/math] rational? If it is, that's our example. If not, let [math]a=\sqrt{2}^{\sqrt{2}}[/math] and [math]b=\sqrt{2}[/math]; now [math]a^b=2[/math] so this is our example (since we're now assuming that [math]a[/math] is irrational!). We have solved the problem by showing that such a pair of number exists, without being able to pinpoint the specific example. (In fact, thanks to deep theorems in the theory of transcendental numbers, we know for a fact that [math]a[/math] is indeed irrational. The point is that this knowledge is not necessary to solve, non-constructively, the original problem). Another curious example of this kind is the following recent one from the theory of fields. Background: A field is a collection of things (numbers, functions, apples, whatever) and two operations ("addition" and "multiplication") that satisfy various familiar axioms, like [math]a \times (b+c) = a \times b + a \times c[/math]. You can find the full list of axioms in the Wikipedia article http://en.wikipedia.org/wiki/Field_(mathematics). If [math]F[/math] is a field, we can form a new field [math]F(x)[/math] of rational functions with coefficients in [math]F[/math]. For example, if [math]F[/math] consists of the rational numbers, then [math]\frac{x^2+\frac{1}{3}}{x-2}[/math] is such a rational function, and it's easy to see that such rational functions can be added and multiplied and themselves form a field. Two fields [math]F, K[/math] are called isomorphic if they are "essentially the same": the elements of one can be mapped to those of the other so that each element in each field has a unique partner in the other field, and the arithmetic operations of matching elements yield matching elements. It's really like the fields have the same elements with different names. Question: Suppose [math]F, K[/math] are two fields such that the fields [math]F(x)[/math] and [math]K(x)[/math] are isomorphic. Does it follow that [math]F[/math] and [math]K[/math] are themselves isomorphic? Answer: No. We know that the answer is no. But can we exhibit a counterexample? Well... Not exactly. In the paper http://www.jstor.org/discover/10.2307/1971174?uid=2&uid=4&sid=21102690195617, the authors found two fields [math]F, K[/math] that are non-isomorphic yet [math]F(x)(y)(z)[/math] is isomorphic to [math]K(x)(y)(z)[/math]. However,  they don't know if [math]F(x)[/math] and [math]K(x)[/math] are isomorphic or not, nor whether [math]F(x)(y)[/math] is isomorphic to [math]K(x)(y)[/math]. So the counterexample to the question is either the pair [math]F,K[/math] or the pair [math]F(x),K(x)[/math] or the pair [math]F(x)(y), K(x)(y)[/math], but we can't tell which! The Game of Chomp Another famous example is the game http://en.wikipedia.org/wiki/Chomp. The game is pretty simple: there's a rectangular array of squares, like a chocolate bar, where the lower left corner is missing. Players take turns picking a square and removing it along with everything that lies either above it, to the right of it, or both. The player that collects the last square wins. Who has the winning strategy? It's easy to show that whatever the original dimensions of the array are, the first player must have a winning strategy. Otherwise, the second player can force a win (there's no draw), but that's impossible: if the second player can force a win, they have a winning response to any move by the first player; but if the first player starts by removing the upper-right corner, and the second player responds to whatever clever move, that clever move could have been taken by the first player in the first place. QED This is called a "strategy-stealing argument". Even though we now know that the first player has a winning strategy, for most boards we don't know what that strategy is. The Axiom of Choice A classical source of non-constructiveness in mathematics is the axiom of choice, which states that the cartesian product of non-empty sets is non-empty. Since the axiom claims the existence of something (an element in the cartesian product) without explicitly exhibiting it, any proof that relies on it in an essential way is a non-constructive proof. Standard examples include the http://en.wikipedia.org/wiki/Well-order of the real numbers, or the existence of a http://en.wikipedia.org/wiki/Non-measurable_set of real numbers. Another fine example is the http://en.wikipedia.org/wiki/De_Bruijn%E2%80%93Erd%C5%91s_theorem_(graph_theory). One consequence of this theorem, for example, is this: suppose we're trying to color the points of the plane using [math]k[/math] colors such that no two points of the same color are a distance of 1 apart. What is the smallest number [math]k[/math] of colors that's needed? Nobody knows the answer (it is either 4, 5, 6 or 7). But thanks to the http://en.wikipedia.org/wiki/De_Bruijn%E2%80%93Erd%C5%91s_theorem_(graph_theory)we know that there exists some finite set of points in the plane that has that same number of minimum colors; that is, whatever the answer is, it is forced by some finite collection of points. Of course, nobody knows such a finite collection. In particular, nobody ever found a finite set of points that requires 5 colors.