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 true (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.