Stone: Section 11

From CSWiki

An encoding for the set of all finitely describable functions

In the beginning of this section, we prove that we cannot encode the set of all functions. However, in a practical sense, a variation of this encoding is possible. In a sense, we can encode the set of all specific functions that we'd want to talk about. Whenever we want to talk about a specific function, we have to specify it. To specify a function, we must describe them in mathematical notation, using a finite alphabet. This description can be encoded as a string, which can in turn be encoded as a natural number, as we've already seen. What this argument shows is that there exist uncountably many functions that can't even be described unambiguously in a finite fashion.

The person behind the theory

Georg Cantor came up with the idea of uncountably infinite sets. The thought that there could be multiple sizes of infinity dazzled the mathematicians of the 19th century.