# Intuitive results with non-intuitive proofs?

Are there mathematical theorems that sound trivial and are obviously true, but are really tough to rigorously show?

For example I stumbled across this question. The author asks how to show that two continuous curves that connect the points $(0,0)$ with $(1,1)$ and $(0,1)$ with $(1,0)$ always have an intersection (the curves are restricted to $[0,1]\times[0,1]$). I asked a few persons and they all agreed that it is clear to be true from a geometrical point of view, but the actual proof is really tricky (especially if you do not use topology). This surprised me and also frightened me a bit, because I thought that trivial theorems always have trivial proofs (otherwise it would be difficult to learn mathematics). Are there more such examples or even stronger ones?

-
it is difficult, but it's worth ) –  Ilya Nov 3 '11 at 17:29
MO has a huge compilation of such results (well, almost: "Theorems that are ‘obvious’ but hard to prove"). –  t.b. Nov 3 '11 at 17:38
For $y=f(x)$, $y=g(x)$ it is not difficult, though a slightly subtle property of the reals is involved. For more general curves, yes, things get harder. But general curves, and even general continuous $f(x)$, can be pretty hairy. The issue is whether continuity is coextensive with the intuitive geometric notion of a curve. My opinion is that the two notions are, after one has seen enough pathological examples, clearly different. I don't think the result is at all obvious. –  André Nicolas Nov 3 '11 at 17:41
I removed the proof-theory tag; this is certainly not about proof theory. I added "intuition" which seems OK, but if it isn't quite right feel free to remove it. –  Carl Mummert Nov 3 '11 at 17:57
You should add to your question that the curves are restricted to $[0,1]\times[0,1]$, otherwise it is not true. I shouldn't have to click to the other page to find the full statement. –  Thomas Andrews Nov 3 '11 at 18:19

The theorem is not trivial. Everything hangs on the fact that the precise mathematical definition of "continuous" is extraordinarily broad; it allows for curves far stranger and more poorly-behaved than any typical "continuous" (in the intuitive sense) curve. Indeed it becomes considerably easier under any reasonable additional hypotheses, although as John Stillwell points out on MO one can force these hypotheses (e.g. piecewise-linear) to hold anyway. (I am somewhat surprised that he was able to avoid the full strength of the Jordan curve theorem, which is equally intuitive but really requires a lot of work to show for precisely the reasons I just gave.)

In general, there must necessarily exist short theorems with long proofs. More precisely, if $f(n)$ denotes the longest proof in a reasonably powerful formal system of a theorem of length $n$, then $f(n)$ grows faster than any computable function.

Proof. Suppose $f(n) \le g(n)$ where $g$ is computable. Then we can find an algorithm that finds proofs of theorems: simply test all proofs of length up to $g(n)$. But for a reasonably powerful formal system (one that can talk about Turing machines) such an algorithm cannot exist because of the unsolvability of the halting problem.

Whether this implies that there are intuitive results with non-intuitive proofs is up for debate. The examples I can think of (including the top-voted examples in the MO thread) are similar to yours; the result is clear intuitively because we have certain cases in mind, but the definitions are broad enough that some work is necessary to cover all cases.

-

In Alhfors' Complex Analysis, the concept of homology is first introduced through winding number. Eventually, Ahlfors shows (through the monodromy theorem and the Riemann mapping theorem) that the notion of homology through winding number is consistent with the more standard, topological one.

I don't know whether this is a case of a non-obvious connection, or the obliteration of an easy result with high-powered machinery. I'm inclined to believe the former.

-

I think that the nicest example of "simple theorem" even impossible to prove is the existence of the natural numbers. Their existence is indeed an axiom, called axiom of infinity (see http://en.wikipedia.org/wiki/Axiom_of_infinity)

-
For any two positive coprime integers $a$ and $d$, there are infinitely many primes of the form $a + nd$, where $n \geq 0$.