I am interested in theorems with unexpected conclusions. I don't mean an unintuitive result (like the existence of a spacefilling curve), but rather a result whose conclusion seems disconnected from the hypotheses. My favorite is the following. Let $f(n)$ be the number of ways to write the nonnegative integer $n$ as a sum of powers of 2, if no power of 2 can be used more than twice. For instance, $f(6)=3$ since we can write 6 as $4+2=4+1+1=2+2+1+1$. We have $(f(0),f(1),\dots) = $ $(1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,\dots)$. The conclusion is that the numbers $f(n)/f(n+1)$ run through all the reduced positive rational numbers exactly once each. See A002487 in the OnLine Encyclopedia of Integer Sequences for more information. What are other nice examples of "unexpected conclusions"?
closed as no longer relevant by Felipe Voloch, Bill Johnson, Andres Caicedo, Mark Sapir, Ryan Budney Jan 5 '12 at 21:50This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center. If this question can be reworded to fit the rules in the help center, please edit the question. 


The first time I ever saw Cayley's Fundamental Theorem of Group Theory  i.e. every group is isomorphic to a group of permutations on a nonempty set  I was floored and I knew anything that contained a statement that bizarre that's true was something I wanted to do in life. 


EckmannHilton argument. I mean, WHY? 


How about Shelah's truly remarkable ${\aleph_\omega}^{\aleph_0}\leq 2^{\aleph_0}\cdot\aleph_{\omega_4}$ (and variations of it)? After seeing various independence results in set theory it is very surprising that anything of this generality can be proved in ZFC. Hence the disconnect between the assumptions and the outcome is that there are no assumptions (beyond the usual axioms of set theory). And then there is the ever puzzling (open) question "Why the hell is it $\omega_4$?" 


In the strict spirit of your question, the hypothesis that 1 = 1 has as conclusion that the moon is made of green cheese. 


Weil's conjecture (proved by Grothendieck) that the number of points of an algebraic variety over finite fields is dictated by the topology of the same algebraic variety over ${\mathbb C}$ (more precisely its Betti numbers). BaezDuarte's criterium: If $1$ is in the closure of the subspace of $L^2([1,+\infty[,\frac{dt}{t^2})$ spanned by the {$\frac{t}{n}$} (fractional part), for $n\geq 1$, then Riemann Hypothesis holds. 


The classical differential geometry results should definitely be mentioned here. Although it may seem not surprising for us, Gauss found his Theorema Egregium to be truly remarkable and unexpected. My favorite example is GaussBonnet Theorem. 


Polya's Theorem: Simple random walk on $\mathbb{Z}^d$ is recurrent for $d\leq2$ and transient for $d>2$. There is also a nice connection between this theorem and infinite networks of resistors. It turns out that the resistance of the whole network $\mathbb{Z}^d$ (one puts a unit source in one point and takes away sinks to $\infty$) is finite iff corresppnding random walk is transient :) 


Definition: Let $A$ and $B$ be selfadjoint matrices, with the partial order $A\ge B$ if $AB$ is positive semidefinite. If $A$ is selfadjoint with spectrum in the interval $[a,b]$ and $f\colon [a,b] \to \mathbb{R}$ is a realfunction, define $f(A)$ using the spectral theorem. The function $f$ is called matrix monotone if $A\ge B$ implies $f(A)\ge f(B)$ for all $A,B$ with spectra in the domain $[a,b]$ of $f$. Loewner's theorem: A function $f\colon [a,b] \to \mathbb{R}$ is matrix monotone iff it has an analytic extension to the upper and lower halfplanes so that the each of these halfplanes is mapped into itself. 


Suppose $f(z)$ and $g(z)$ are two functions meromorphic in the plane. Suppose also that there are five distinct numbers $a_1,\ldots,a_5$ such that the solution sets $\lbrace z : f(z) = a_i\rbrace$ and $\lbrace z : g(z) = a_i\rbrace$ are equal. Then either $f(z)$ and $g(z)$ are equal everywhere or they are both constant. 


A theorem of Erdos and Hajnal: Any graph with no 4cycles is countably colorable. Now, admittedly, this conclusion is less surprising when you state the actual stronger theorem that this is a corollary to: Any graph which is not countably colorable must contain a copy of $K_{\aleph_1,n}$ for every finite n. But in particular it must contain a 4cycle, which is not only a surprising statement on its own but is also especially surprising considering that given $k$ and any finite $n$ there are finite graphs with girth at least $k$ and chromatic numberat least $n$, and that given $k$ and an arbitrary cardinal $\kappa$ there are graphs with odd girth at least $k$ and chromatic number at least $\kappa$. But, no 4cycles? Countably colorable! 


If $f\colon [a,b] \to \mathbb{R}$ is increasing, then $f$ is differentiable almost everywhere [w.r.t. Lebesgue measure]. (We can further conclude that $f'$ is measurable and $\int_a^b f'(x)\ dx \leq f(b)  f(a)$, but it's the first part that struck me when I learned it.) And sure it makes sense, but knowing how real analysis often is, one might think that there must be some increasing function that fails to be differentiable on a set of positive measure. 


Here's one I was reminded of recently. Recall that a projective plane is a triple $(P, L, I)$ where $P$ is a set of "points," $L$ is a set of "lines," and $I$ is a subset of $P \times L$ describing the incidence relations which satisfies certain axioms. A finite projective plane always has $n^2 + n + 1$ points for some $n$ which is known as the order of the plane. So far, so geometric and combinatorial. Theorem (BruckRyser): If $n \equiv 1, 2 \bmod 4$, then $n$ is a sum of two squares. This is still the only known general criterion for ruling out orders of projective planes! It's conjectured that $n$ must be a power of a prime (examples include the projective planes which occur as $\mathbb{P}^2 \mathbb{F}_q$), but it's not even known whether there exists a projective plane of order $12$. (There is a "theorem with an unexpected proof" in this area as well. For finite projective planes, Desargues' theorem implies Pappus's theorem, but the only known proof goes through Wedderburn's little theorem!) 


How about the CookLevin theorem  boolean satisfiability is NP complete. Though the consequence that "if there exists a polynomial time algorithm for boolean satisfiability then all problems in NP can be solved in polynomial time" may fit the bill better! I mean what does boolean satifiability have to do with finding hamiltonians on graphs or finding shortest roots in networks?! Ivan 


Here are three examples from combinaorics: 1) The Frankl Wilson' theorem (The paper can be found here). This theorem in extremal combinatorics has a large number of amazing applications: Explicit Ramsey constructions, applications in combinatorial geometry; applications regarding Shannon capacity of union of graphs and many more. 2) TrotterSzemeredi The result by Trotter and Szemeredi regarding the maximum number of incidences between points and lines in the plane had remarkable applications including one discovered by Elekes' to the productsum theorem. 3) The mod p product sum theorem by BourgainKatzTao had many surprising applications in many directions. (One reason for the wide applicability is that when you multiply matrices sums and products mix.) 


The following pearl by Jacobson can under no circumstances be left out from the list: Let $\mathbf{R}$ be a ring with center $\mathrm{Z}$. Let us suppose that you can find $n \in \mathbb{N}_{>1}$ such that $x^{n}x \in \mathrm{Z}$ for every $x \in \mathbf{R}$. Then $\mathbf{R}$ is a commutative ring. A good place to learn more about results of this kind is Herstein's Noncommutative rings. 


A proper algebraic group is abelian. 


There is a theorem by Bernstein that I like: If $f$ is a $C^{\infty}$function on the intervall $I$ such that $f$ and the derivatives of $f$ to every order are nonnegative on $I$ then $f$ is analytic. An example would be $e^x$ which satisfies the assumptions and thus is analytic (on the whole real line). 


I was very surprised when I first saw that the product of all primes $p$ such that $p12n,$ is the denominator of Bernoulli number $B_{2n}$. 


Given a $C^{\infty}$ function $f(x)$, let $\Delta_n$ be the difference between the integral of $f(x)$ and its $n$'th Riemann sum: $$\Delta_n = \int_0^1 f ~dx ~~ \sum_{i=1}^{n} f(i/n) \frac{1}{n}$$ Clearly, $\Delta_n$ goes to $0$, but at what rate? Its easy to see that its possible for $\Delta_n$ to decay as $\Theta(1/n)$, e.g consider what happens with $f(x)=x$. Theorem: If $f(x)$ is periodic with period $1$, then $\Delta_n$ decays faster than any polynomial in $n$. 


Whitehead problem: Is every abelian group A with $Ext^1(A, \mathbb{Z}) = 0$ a free abelian group? 


Reciprocity/duality theorems may give you unexpected results if you don't expect the connections. Dan Ranmas already mentioned Poincare duality. To clarify, Poincare duality is not just abstract nonsense. It fails for nonmanifolds like general abstract simlicial complexes. For a [mod $2$] oriented manifold of dimension $d$, the [mod $2$] homology in dimension $k$ is isomorphic to the [mod $2$] homology in dimension $dk$. Quadratic reciprocity relates whether $p$ is a square mod $q$ with whether $q$ is a square mod $p$. Weil reciprocity relates the values of a rational function $f$ at the zeros and poles of $g$ with the values of $g$ at the zeros and poles of $f$. Stanley reciprocity relates a generating function for the lattice points in a convex cone with a generating function for the lattice points in the interior evaluated at reciprocal arguments. 


If arbitrary products of nonempty sets are nonempty, then you can decompose a unit ball in $\mathbb R^3$ into finitely many pieces and rigidly reassemble then into two balls of radius 1. That is, the axiom of choice implies the BanachTarski paradox. Of course, there are plenty of other results which depend on the axiom of choice, and many of them qualify, whether their conclusion seems to violate physical intuition or not. The point is that the conclusion seems nothing like the assumption. 


One of my personal favorite theorems with an unexpected application is the AtiyahSinger index theorem. I don't know if the application can be labeled as "real" mathematics, but it is amazing how it works. In the article An SU(2) Anomaly, Edward Witten shows that certain "SU(2) gauge theories" having an odd number of doublets of Dirac fermions are "mathematically inconsistent". In this case, the latter means that all path integrals vanish. That all path integrals vanish is a consequence of the fact that $\pi_4(SU(2)) = \mathbf{Z}/2\mathbf{Z}$. Thus, there is also some homotopy theory involved! For completeness, here is the reference E. Witten, An SU(2) Anomaly. Phys. Lett. B 117 (1982), pages 324328. 


Logic/computability theory is quite good at turning up seemingly special processes with unexpectedly universal outcomes. Goodstein's theorem (already mentioned) is one example. Another is the Matiyasevich theorem that polynomials with integer coefficients produce all computably enumerable sets. One way to state this is that each c.e. set is the set of nonnegative values of such a polynomial. 


I have always found Kuratowski 14set problem among the most surprising elementary theorems I know. Why 14?! (This was recently discussed in this MO question.) 


The TaniyamaShimura conjecture (now proved, by Wiles and others): all elliptic curves over $\mathbb Q$ are modular. It's magical that one can give a "formula" for the numbers of points on the curve modulo $p$ using modular forms. 


The existence of two nonisomorphic isospectral Riemannian manifolds "we can't hear the Shape of a Drum" can be deduced from the existence of two quasi conjugated subgroups of $PSL_2(7)$ 


It is well known that a group $G$ can't be written as the union of two proper subgroups. On the other hand there are groups that can be written as the union of three proper subgroups, my favorite one the quaternions $Q_8$. Now, I remember the following fact from my undergrad group theory class: if $G$ is a finite group such that $G$ is the union of three proper subgroups then the Klein four group $V_4$ is a quotient of $G$. 


Maybe by now no one thinks of it as counterintuitive, but what about Poincaré Duality? The following formulation (for psuedomanifolds) might fit this question best: If K is a finite simplicial complex satisfying:
then the (mod 2) Betti numbers of K in complementary dimensions must be equal! 


Let G be a group of order p(p+1), with more than one pSylow. Then p is either 2 or a Mersenne prime. (Indeed, G exists uniquely for each such p.) One of my own I'm proud of: http://front.math.ucdavis.edu/0911.4941 Let H be a degree n hypersurface in nspace (yes, same n) over $F_p$. From H we may be able to construct many other subschemes, by decomposing, intersecting components, decomposing again, intersecting again, ... If the number of $F_p$ points on H is not a multiple of p, then all these subschemes are reduced. 

