Set (mathematics)

• 1. Introduction

  ›

  In mathematics, a set is a collection of different things, and those things, called elements or members, can be numbers, symbols, points in space, lines, geometric shapes, variables, functions, or even other sets. Almost everything else in mathematics is built on top of this one idea. Yet mathematics typically refuses to define precisely what a set actually is. A precise definition would have to lean on something else defined earlier, and sets sit at the very bottom of the stack. So instead of a definition, sets behave according to axioms modeled on our intuition about collections. How did a concept this slippery come to underpin all of mathematics? Why did its arrival trigger a crisis, produce paradoxes, and astonish the people who first understood it? And how does a single idea stretch from counting a handful of objects to comparing infinities that have no largest member?

• 2. The Paradise And The Crisis

  ›

  Before the end of the 19th century, sets were not studied on their own, and they were not clearly separated from sequences. Most mathematicians treated infinity as potential, the result of an endless process, and resisted the idea of an infinite set. A line, for instance, was seen not as a set of points but as a locus where a point might be located. Georg Cantor, who lived from 1845 to 1918, began the mathematical study of infinite sets. His work produced statements that felt impossible. The number line, he showed, holds an infinite number of elements strictly larger than the infinite number of natural numbers. Any line segment, meanwhile, holds the same number of elements as the whole line. Trouble arrived when mathematicians assumed there could be a set of all sets, which led straight to a contradiction known as Russell's paradox. That contradiction opened the foundational crisis of mathematics. Out of the proposed resolutions came Zermelo-Fraenkel set theory, generally adopted as the foundation of set theory and of all mathematics, even though much of mathematics never needs its full strength. David Hilbert captured what was at stake when he declared, "No one will drive us from the paradise that Cantor created for us."

• 3. Naming A Collection

  ›

  A set with no elements at all exists, and the axiom of extensionality guarantees there is only one such thing. It is called the empty set, or the null set. Extensionality is the rule that two sets are equal exactly when they share the same elements, and it does more than just settle equality. It also tells you how to pin down a set. You can specify a set by listing its elements, or by giving a property that picks them out, such as the property of being a prime number or being a student in a given class. Ernst Zermelo introduced roster notation in 1908, which names a set by listing its members between braces, separated by commas. In this style, order and repetition carry no meaning. A set does not change if its elements are repeated or rearranged, because all that matters is whether each candidate is in or out. When a clear pattern generates the members, an ellipsis can stand in for the rest, even for an infinite set like the integers. Set-builder notation takes the other route, describing a set as all elements satisfying some logical formula, with a vertical bar read aloud as "such that." Not every formula is safe to use this way. Some logical conditions characterize no set at all, the same danger that produced the contradiction Cantor's successors had to tame. To stay safe, one often fixes a larger set in advance, a domain of discourse sometimes called a universe, so that every variable to the left of the bar is understood to live inside it.

• 4. Building New From Old

  ›

  There are several standard operations that produce new sets from given ones, much as addition and multiplication produce new numbers. The intersection of two sets contains exactly the elements that belong to both, and it is illustrated with Euler diagrams and Venn diagrams. Intersection is associative and commutative, so a chain of intersections can be carried out in any order without parentheses. The union of two sets contains the elements that belong to one or the other or both, and it too is associative and commutative. The set difference contains the elements that belong to the first set but not the second. When the difference is taken inside a fixed universal set, it is called the absolute complement. The symmetric difference collects the elements belonging to one set or the other but not both. Gather all the subsets of a set together and you get its powerset. The powerset is a rich algebraic structure. It is a Boolean ring with symmetric difference as addition, intersection as multiplication, the empty set as additive identity, and each subset as its own additive inverse. It is also a Boolean algebra, where union is the join, intersection is the meet, and complement is the negation. And it is a partially ordered set under inclusion, in fact a complete lattice, the framework that will later let a single union climb an infinite chain.

• 5. Functions And Products

  ›

  A function from one set to another assigns to each element of the first a unique element of the second; the square function, for example, maps each real number to its square. The first set is the domain, the second is the codomain, and the result of applying the function is called the image. The graph of a function is the set of all ordered pairs as the input ranges over the domain. The graph of the square function is a parabola, containing points such as the pair built from an input and its square. Once domain and codomain are fixed, the graph carries the same information as the function itself, which lets a function be defined formally in terms of sets. This pairing idea generalizes. The Cartesian product of two sets is the set of all ordered pairs whose first entry comes from one set and second from the other, and it extends to triples and to any number of sets, finite or not. Set exponentiation pushes further, collecting all functions from one set to another. It can be seen as a Cartesian product of copies of the same set, one copy for each element of the index, which is exactly why exponentiation notation fits. A close cousin of these constructions is the power set, the set of all subsets including the empty set and the whole set. There is a natural one-to-one correspondence between the subsets of a set and the functions from that set into a two-element set, so the power set is commonly identified with set exponentiation. If a set has a finite number of elements, then its power set has two raised to that number of elements. The disjoint union offers a different blend, behaving like a union but treating shared elements as distinct by labelling each with the index of the set it came from. It is the coproduct in the category of sets, and when a set is the disjoint union of a family of its own subsets, that family is called a partition.

• 6. Counting The Uncountable

  ›

  The cardinality of a set is, informally, the number of its members, and the cardinality of the empty set is zero. A set has a natural number as its cardinality when there is a bijection between it and the first natural numbers; otherwise it is infinite. This idea that natural numbers measure the size of finite collections is the very basis of the concept of natural number, and it predates the concept of sets by several thousand years. For infinite sets, size is captured by cardinal numbers. Two sets share a cardinality when a one-to-one correspondence links them, a fact with a startling consequence. The natural numbers and the even natural numbers have the same cardinality, since multiplying by two pairs them up perfectly. Having the same size as a proper subset is the defining mark of an infinite set. The Schroder-Bernstein theorem secures the comparison of sizes, and for any two sets one cardinality is at least as large as the other, so cardinalities form a total order. The cardinality of the natural numbers is the smallest infinite cardinality. Sets no larger than this are called countable; sets strictly larger are uncountable. Cantor's diagonal argument proves that every set has a power set of strictly greater cardinality, which means there is no greatest cardinality at all. The next chapter shows where this ladder of sizes collides with the real line.

• 7. The Continuum Question

  ›

  The cardinality of the set of real numbers is called the cardinality of the continuum, a word that once named the real line itself, before the real line was commonly viewed as a set of numbers. This cardinality equals that of the power set of the natural numbers, and the real line shares its size with an open interval, so any subset of the line containing a nonempty open interval has the same cardinality too. The same value measures the entire plane and any finite-dimensional Euclidean space. When Georg Cantor published this result in 1878, it was so astonishing that mathematicians rejected it, and several decades passed before it found common acceptance. That same year Cantor formulated the continuum hypothesis, the conjecture that no set has a cardinality strictly between that of the natural numbers and that of the real numbers. The hypothesis resisted proof for generations. In 1963, Paul Cohen proved that the continuum hypothesis is independent of the axioms of Zermelo-Fraenkel set theory with the axiom of choice. If that widely used set theory is consistent, then it stays consistent whether the continuum hypothesis is added as an axiom or its negation is added instead. The question that astonished Cantor's contemporaries turned out to have no answer the axioms can force.

• 8. The Power To Choose

  ›

  The axiom of choice says, informally, that given any family of nonempty sets, one can choose an element from each of them simultaneously. Stated that way it raises a foundational worry, because an infinite instantaneous act of choosing is hard to picture. Yet it has several equivalent formulations that feel far less controversial and carry strong consequences across mathematics, so today it is commonly accepted in mainstream work. A more formal version says the Cartesian product of every indexed family of nonempty sets is nonempty. One equivalent is Zorn's lemma, which states that if every chain in a partially ordered set has an upper bound, then the set has a maximal element. Zorn's lemma proves that every vector space has a basis, taking the linearly independent subsets and climbing a chain to a maximal one that must span the space. It also proves that every proper ideal of a ring is contained in a maximal ideal. Another equivalent is the claim that every set can be given a well-order, a total order in which every nonempty subset has a least element. Well-orders unlock transfinite induction, a generalization of ordinary mathematical induction that replaces the natural numbers with the elements of a well-ordered set. Transfinite induction is fundamental for defining the ordinal numbers and the cardinal numbers, the very tools that let mathematicians count their way through the paradise Cantor opened.