Set theory
Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory – as a branch of mathematics – is mostly concerned with those that are relevant to mathematics as a whole.
The modern study of set theory was initiated by the German mathematicians Richard Dedekind and Georg Cantor in the 1870s. In particular, Georg Cantor is commonly considered the founder of set theory. The non-formalized systems investigated during this early stage go under the name of naive set theory. After the discovery of paradoxes within naive set theory, various axiomatic systems were proposed in the early twentieth century, of which Zermelo–Fraenkel set theory is still the best-known and most studied.
Set theory is commonly employed as a foundational system for the whole of mathematics, particularly in the form of Zermelo–Fraenkel set theory with the axiom of choice. Besides its foundational role, set theory also provides the framework to develop a mathematical theory of infinity, and has various applications in computer science, philosophy, formal semantics, and evolutionary dynamics. Its foundational appeal, together with its paradoxes, and its implications for the concept of infinity and its multiple applications have made set theory an area of major interest for logicians and philosophers of mathematics. Contemporary research into set theory covers a vast array of topics, ranging from the structure of the real number line to the study of the consistency of large cardinals.
History
Early history
The basic notion of grouping objects has existed since at least the emergence of numbers, and the notion of treating sets as their own objects has existed since at least the Tree of Porphyry in 3rd-century AD. The simplicity and ubiquity of sets makes it hard to determine the origin of sets as now used in mathematics; however, Bernard Bolzano's Paradoxes of the Infinite is generally considered the first rigorous introduction of sets to mathematics. In his work, he expanded on Galileo's paradox, and introduced one-to-one correspondence of infinite sets, for example between the intervals and by the relation. However, he resisted saying these sets were equinumerous, and his work is generally considered to have been uninfluential in mathematics of his time.Before mathematical set theory, basic concepts of infinity were considered to be in the domain of philosophy. Since the 5th century BC, beginning with Greek philosopher Zeno of Elea in the West, mathematicians had struggled with the concept of infinity. With the development of calculus in the late 17th century, philosophers began to generally distinguish between potential and actual infinity, wherein mathematics was only considered in the latter. Carl Friedrich Gauss famously stated:
Infinity is nothing more than a figure of speech which helps us talk about limits. The notion of a completed infinity doesn't belong in mathematics.Development of mathematical set theory was motivated by several mathematicians. Bernhard Riemann's lecture On the Hypotheses which lie at the Foundations of Geometry proposed new ideas about topology. His lectures also introduced the concept of basing mathematics in terms of sets or manifolds in the sense of a class now called point-set topology. The lecture was published by Richard Dedekind in 1868, along with Riemann's paper on trigonometric series, The latter was the starting point for a movement in real analysis of the study of “seriously” discontinuous functions. A young Georg Cantor entered into this area, which led him to the study of point-sets. Around 1871, influenced by Riemann, Dedekind began working with sets in his publications, which dealt very clearly and precisely with equivalence relations, partitions of sets, and homomorphisms. Thus, many of the usual set-theoretic procedures of twentieth-century mathematics go back to his work. However, he did not publish a formal explanation of his set theory until 1888.
Naive set theory
Set theory, as understood by modern mathematicians, is generally considered to be founded by a single paper in 1874 by Georg Cantor titled On a Property of the Collection of All Real Algebraic Numbers. In his paper, he developed the notion of cardinality, comparing the sizes of two sets by setting them in one-to-one correspondence. His "revolutionary discovery" was that the set of all real numbers is uncountable, that is, one cannot put all real numbers in a list. This theorem is proved using Cantor's first uncountability proof, which differs from the more familiar proof using his diagonal argument.Cantor introduced fundamental constructions in set theory, such as the power set of a set A, which is the set of all possible subsets of A. He later proved that the size of the power set of A is strictly larger than the size of A, even when A is an infinite set; this result soon became known as Cantor's theorem. Cantor developed a theory of transfinite numbers, called cardinals and ordinals, which extended the arithmetic of the natural numbers. His notation for the cardinal numbers was the Hebrew letter with a natural number subscript; for the ordinals he employed the Greek letter .
Set theory was beginning to become an essential ingredient of the new “modern” approach to mathematics. Originally, Cantor's theory of transfinite numbers was regarded as counter-intuitive – even shocking. This caused it to encounter resistance from mathematical contemporaries such as Leopold Kronecker and Henri Poincaré and later from Hermann Weyl and L. E. J. Brouwer, while Ludwig Wittgenstein raised philosophical objections.
Despite the controversy, Cantor's set theory gained remarkable ground around the turn of the 20th century with the work of several notable mathematicians and philosophers. Richard Dedekind, around the same time, began working with sets in his publications, and was famously constructing the real numbers in 1872 using Dedekind cuts. Cantor and Dedekind were in correspondence about set theory, especially in the 1870s. However, Dedekind's algebraic style only began to find followers in the 1890s. Cantor also worked with Giuseppe Peano in developing the Peano axioms, which formalized natural-number arithmetic, using set-theoretic ideas, which also introduced the epsilon symbol for set membership. Possibly most prominently, Gottlob Frege began to develop his Foundations of Arithmetic.
In his work, Frege tries to ground all mathematics in terms of logical axioms using Cantor's cardinality. For example, the sentence "the number of horses in the barn is four" means that four objects fall under the concept horse in the barn. Frege attempted to explain our grasp of numbers through cardinality, relying on Hume's principle.
However, Frege's work was short-lived, as it was found by Bertrand Russell that his axioms lead to a contradiction. Specifically, Frege's Basic Law V. According to Basic Law V, for any sufficiently well-defined property, there is the set of all and only the objects that have that property. The contradiction, called Russell's paradox, is shown as follows:
Let R be the set of all sets that are not members of themselves. If R is not a member of itself, then its definition entails that it is a member of itself; yet, if it is a member of itself, then it is not a member of itself, since it is the set of all sets that are not members of themselves. The resulting contradiction is Russell's paradox. In symbols:This came around a time of several paradoxes or counter-intuitive results. For example, that the parallel postulate cannot be proved, the existence of mathematical objects that cannot be computed or explicitly described, and the existence of theorems of arithmetic that cannot be proved with Peano arithmetic. The result was a foundational crisis of mathematics.
Basic concepts and notation
Set theory begins with a fundamental binary relation between an object and a set. If is a member of, the notation is used. A set is described by listing elements separated by commas, or by a characterizing property of its elements, within braces. Since sets are objects, the membership relation can relate sets as well, i.e., sets themselves can be members of other sets.A derived binary relation between two sets is the subset relation, also called set inclusion. If all the members of set are also members of set, then is a subset of, denoted. For example, is a subset of, and so is but is not. As implied by this definition, a set is a subset of itself. For cases where this possibility is unsuitable or would make sense to be rejected, the term proper subset is defined, variously denoted,, or . We call a proper subset of if and only if is a subset of, but is not equal to. Also, 1, 2, and 3 are members of the set, but are not subsets of it; and in turn, the subsets, such as, are not members of the set. More complicated relations can exist; for example, the set is both a member and a proper subset of the set.
Just as arithmetic features binary operations on numbers, set theory features binary operations on sets. The following is a partial list of them:
- Union of the sets and, denoted, is the set of all objects that are a member of, or, or both. For example, the union of and is the set.
- Intersection of the sets and, denoted, is the set of all objects that are members of both and. For example, the intersection of and is the set.
- Set difference of and, denoted, is the set of all members of that are not members of. The set difference is, while conversely, the set difference is. When is a subset of, the set difference is also called the complement of in. In this case, if the choice of is clear from the context, the notation is sometimes used instead of, particularly if is a universal set as in the study of Venn diagrams.
- Symmetric difference of sets and, denoted or, is the set of all objects that are a member of exactly one of and . For instance, for the sets and, the symmetric difference set is. It is the set difference of the union and the intersection, or.
- Cartesian product of and, denoted, is the set whose members are all possible ordered pairs, where is a member of and is a member of. For example, the Cartesian product of and is
The power set of a set, denoted, is the set whose members are all of the possible subsets of. For example, the power set of is. Notably, contains both and the empty set.