Sets, Logic, and Computation

In the 19th century, perennial concerns about the role of infinity in mathematics were finally addressed by the development of

set theory

and

formal logic

. Set theory was proposed as a mathematical theory of infinity and formal logic was proposed as a mathematical theory of proof (partly to avoid the paradoxes that seem to arise when reasoning about infinity). In this chapter we discuss these two developments, whose interaction led to mind-bending consequences in the 20th century. Both set theory and logic throw completely new light on the question, “What is mathematics?” But they turn out to be double-edged swords.

Set theory brings remarkable clarity to the concept of infinity, but it shows infinity to be unexpectedly complicated–in fact, more complicated than set theory itself can describe.

Formal logic encompasses all known methods of proof, but at the same time it shows these methods to be

incomplete

. In particular, any reasonably strong system of logic cannot prove its own consistency.

Formal logic is the origin of the concept of

computability

, which gives a rigorous definition of an

algorithmically solvable problem

. However, some important problems turn out to be

unsolvable

.

It might be thought that the limits of formal proof are too remote to be of interest to ordinary mathematicians. But in the next chapter we will show how these limits are now being reached in one of the most down-to-earth fields of mathematics: combinatorics.