Many examples comes to mind, the most famous being the Gödel's theorems viewed as formalisations of the Liar's paradox. I just realised that the proof of non-calculability of Kolmogorov complexity is a positive rewriting of Berry's paradox. My question (perhaps to be made into collective mode) is a) what are the best examples you know ? b) (more important) is there some explication of this productivity of paradoxes (or, conversely, do you know of paradoxes with no interesting follow-up) ?

-
You should maybe make this community wiki (and perhaps ask for one example for answer). –  Pietro Majer Dec 15 '12 at 13:20
Could you perhaps elaborate what you want to be understood by a 'paradox.' –  quid Dec 15 '12 at 13:28
It is not very correct to say that first incompleteness theorem is formalization of the Liar. As positive results which found their inspiration in paradoxes I'd rather mention development of type theory or various axiomatizations of intuitive theory of sets. But I am not sure whether OP would consider this as an answer to his question. –  Mad Hatter Dec 15 '12 at 14:17
Perhaps this is the kind of thing you mean: mathoverflow.net/questions/53498/nontrivial-circular-arguments/…? –  Joel David Hamkins Dec 15 '12 at 14:40
A paradox for which I don't know of interesting follow-up (and in fact , I find it hard to convince that it is an interesting paradox) is the cheap-horses paradox: Rare things are expensive; cheap horses are rare; Therefore cheap horses are expensive. –  Gil Kalai Dec 16 '12 at 11:52

Kritchman and Raz adapted the surprise examination paradox (a/k/a the unexpected hanging paradox) to prove Godel's second incompleteness theorem (extending the ideas underlying Chaitin's Berry's-paradox-inspired proof of Godel's first incompleteness theorem).

I blogged on this here.

-
This paradox has led to other positive results as well. See for example D. Borwein, J. M. Borwein and P. Maréchal, Surprise maximization, Amer. Math. Monthly 107 (2000), 517–527. –  Timothy Chow Dec 16 '12 at 22:50

If you accept that the Banach-Tarski result is a "paradox" (although not an antinomy), then it was a productive paradox insofar as it led von Neumann to consider finitely additive invariant measures, work which eventually blossomed into the study of amenable groups.

-
I'd also add here the Tits' alternative, which is a far-reaching generalization of the Hausdorff's paradox (precursor to Banach-Tarski), which was based on a construction free subgroups in $SO(3)$. –  Misha Dec 15 '12 at 18:16

Russell's paradox resulted in formulation of type theory and set theory.

-
This seems like a bit of an oversimplification (I'm sure you're aware of what I'm about to say, Andrej). Certainly there was recognition of the need to restrict the principle of comprehension when Zermelo introduced his axiomatization of set theory, but my understanding is that it was really the discussion of the well-ordering principle and its underpinnings that drove him to carefully specify the axioms of Zermelo set theory with choice. See also Timothy Chow's answer here: mathoverflow.net/questions/28656/… –  Todd Trimble Dec 15 '12 at 15:43
Right, I wrote it oversimplified on purpose. The point is that Cantor concieved of set theory, and Russell made the point that things were a bit subtler than they seemed. –  Andrej Bauer Dec 16 '12 at 0:56
I would also add that Cantor already knew in essence what came to be called Russell's paradox: he knew, by his eponymous theorem, that no set $V$ could contain its own power set. See en.wikipedia.org/wiki/Cantor%27s_paradox. There's a nice observation at the nLab, at ncatlab.org/nlab/show/Cantor%27s+paradox, that Russell's paradox is the $\beta$-reduced form of the proof of Cantor's theorem as applied to Cantor's paradox. The "target" of Russell's paradox was Frege's Grundgesetze der Arithmetik (if I can put it like that; his letter to Frege was rather kind and gentlemanly). –  Todd Trimble Dec 16 '12 at 3:04

Zeno's paradox on Achilles and the tortoise is related to the formula for infinite geometric sums and more generally to the idea that infinite sums can lead to finite outcomes.

It is quite remarkable how relevant 17th century calculus is to Zeno's three paradoxes. In fact, it looks that in a different universe these paradoxes could have started calculus. Terry Tao remarked on some post I made about it: "Zeno's arrow paradox can be reinterpreted in the light of the theory of differential equations that the equations of motion must be second-order in time rather than first-order, since one has to specify initial velocity in addition to initial position in order to have a well-posed system. So the arrow paradox may well be the earliest precursor of Newton's famous equation F=ma..."

-

More in the spirit than the letter of the question, some of Alan Turing's work can be seen as applications of contradiction. The development of the Turing Machine and using it to resolve Hilbert's Entscheidungsproblem can be seen as a successful use of the Liar Paradox, and elsewhere I read a quote which suggested that Turing took a result from mathematical logic (from a contradiction one can prove anything) and used it to help build one of the codebreaking systems used in World War II.