A couple of others have mentioned Gödel's theorem, Turing's
noncomputability results, and Turing degrees below the halting
problem. If I may elaborate a little, the ancestor of all these
constructions was Cantor's diagonal construction, which 
constructs a real number different from all members of a
countable list of reals.

When the diagonal argument is applied to the real numbers
defined by Turing machines, it seems to compute a real number
that is not computable, so one is forced to conclude that there
is no algorithm for deciding *which* machines define real numbers,
and this leads to the unsolvability of the halting problem. Then, 
when one thinks about machines for generating theorems (about Turing
machines, say), one sees that a machine cannot generate all 
(and only) true theorems -- a form of Gödel's theorem.

Increasingly sophisticated versions of the diagonal construction
developed in the 1950s, starting with Friedberg and Muchnik's
construction of c.e. sets $A$ and $B$ with incomparable degrees of 
unsolvability in 1956. That is, $A$ and $B$ can each be enumerated 
by Turing machine, but no machine can solve the membership problem
for $A$, even given complete membership information about $B$, and vice versa.

After the discovery of the Friedberg-Muchnik result, it became 
something of an industry to devise more and more complicated
diagonal constructions, in what became known as the theory of 
*degrees of unsolvability*. I have the impression that, by around 
1970, the whole raison d'etre of this theory was to devise ingenious
constructions.