What Is a Set? The Simplest Idea in Mathematics and the Most Trouble

Sets supply a common language in which every other mathematical object can be defined. A number can be constructed as a set, a function is a set of ordered pairs, a relation is a set of pairs, a geometric figure is a set of points, and a sequence is a function from the counting numbers. That means a single theory can serve as a foundation for the whole subject, which is what motivated the enormous effort put into it from the late nineteenth century. The basic operations are few: union combines sets, intersection takes what is common, complement takes what is outside, and the subset relation orders them. The power set of a set is the set of all its subsets, which is a construction that turns out to be surprisingly consequential. Membership is the only primitive relation, so everything else is defined in terms of whether one thing belongs to another, which is an extraordinarily austere starting point.

Georg Cantor's work on infinite sets in the 1870s produced results that were resisted violently and are now standard:

• •Two sets have the same size if their members can be paired off exactly, which extends counting to infinite collections without requiring anyone to count
• •The counting numbers, the even numbers and the fractions all have the same size by that criterion, which is counterintuitive since each seems smaller or larger than another
• •The real numbers are strictly larger, proved by the diagonal argument, which shows that any proposed list of them omits at least one
• •There are therefore different sizes of infinity, and the power set of any set is strictly larger than the set, so the sizes continue upward without end
• •The continuum hypothesis asks whether any size sits between the counting numbers and the reals, and it was shown to be neither provable nor refutable from the standard axioms
• •Cantor's contemporaries included prominent mathematicians who regarded the work as illegitimate, and his reputation recovered only later

The naive approach allowed any describable collection to be a set, and Bertrand Russell showed in 1901 that this is contradictory. Consider the set of all sets that do not contain themselves, and ask whether it contains itself: if it does then by definition it does not, and if it does not then by definition it does. The contradiction is not a curiosity, since it arises from the most natural formulation of the idea and it destroyed Gottlob Frege's project of founding arithmetic on logic at the moment of publication, as Frege acknowledged in an appendix written after receiving Russell's letter. The repair was axiomatic set theory, which abandons the principle that any description determines a set and instead specifies which constructions are permitted, so that the problematic collection cannot be formed. The resulting system, generally with the axiom of choice included, is the standard foundation and has not produced a contradiction in over a century, which is not a proof that it cannot.

Beyond foundations, the vocabulary is pervasive and mostly invisible. Databases are built on set operations, since a query returns a set of records and joins, unions and intersections are exactly the operations described above, which is why relational database theory is stated in those terms. Probability is defined over sets of outcomes, with events being subsets of a sample space and the whole apparatus following from that. Programming languages provide set types and set comprehensions directly. Logic and type theory connect to it closely. Statistics, topology, algebra and analysis all use it as their common notation. And at school level the vocabulary appears in Venn diagrams, which are a visual notation for exactly these operations and which were introduced by John Venn in 1880 for reasoning about logical relations rather than for teaching arithmetic.

Everything in mathematics can be built from collections with membership as the only primitive relation, which is why so much was invested in the idea. Pairing members off extends counting to infinite collections, and the diagonal argument shows the real numbers are strictly larger than the counting numbers. Allowing any description to define a set produces a contradiction, which axiomatic systems avoid by restricting what may be constructed.