Set theory
illustrating the intersection of two sets|class=skin-invert-image Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects.
≈ 11 min read
Set theory. encyclopegia.org, snapshot enwiki-001378615581. /a/set-theory
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
illustrating the intersection of two sets|class=skin-invert-image 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 objects 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 (e.g. Russell's paradox, Cantor's paradox, and the Burali-Forti paradox, et al.), various axiomatic systems were proposed in the early twentieth century, of which Zermelo–Fraenkel set theory (with or without the axiom of choice) 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 (such as in the theory of relational algebra), 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
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 CE. 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 (Paradoxien des Unendlichen, 1851) is generally considered the first rigorous introduction of sets to mathematics.
In his work, he (among other things) expanded on Galileo's paradox, and introduced one-to-one correspondence of infinite sets, for example between the intervals [0,5] and [0,12] by the relation 5y = 12x . 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 (see: Infinity (philosophy) and ). Since the 5th century BC, beginning with Greek philosopher Zeno of Elea in the West (and early Indian mathematicians in the East), 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 (1854) 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 (which he called Mannigfaltigkeit) now called point-set topology.
The lecture was published by Richard Dedekind in 18681, along with Riemann's paper on trigonometric series (which presented the Riemann integral). 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. \text{Let } R = \{ x \mid x \not \in x \} \text{, then } R \in R \iff R \not \in R 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 an element (or 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 A\subset B , A\subsetneq B , or A\subsetneqq B (note however that the notation A\subset B is sometimes used synonymously with A\subseteq B ; that is, allowing the possibility that and are equal). 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 (elements) 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 (elements which are in one of the sets, but not in both). 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 {1, 2} and {red, white} is Some basic sets of central importance are the set of natural numbers, the set of real numbers and the empty set – the unique set containing no elements.
The empty set is also occasionally called the null set, though this name is ambiguous and can lead to several interpretations. The empty set can be denoted with empty braces " \{ \} " or the symbol " \varnothing " or " \emptyset ". The power set of a set , denoted \mathcal{P}(A) , is the set whose members are all of the possible subsets of .
For example, the power set of is . Notably, \mathcal{P}(A) contains both and the empty set.
Ontology
A set is pure if all of its members are sets, all members of its members are sets, and so on. For example, the set containing only the empty set is a nonempty pure set. In modern set theory, it is common to restrict attention to the von Neumann universe of pure sets, and many systems of axiomatic set theory are designed to axiomatize the pure sets only.
There are many technical advantages to this restriction, and little generality is lost, because essentially all mathematical concepts can be modeled by pure sets. Sets in the von Neumann universe are organized into a cumulative hierarchy, based on how deeply their members, members of members, etc. are nested.
Each set in this hierarchy is assigned (by transfinite recursion) an ordinal number \alpha , known as its rank. The rank of a pure set X is defined to be the least ordinal that is strictly greater than the rank of any of its elements. For example, the empty set is assigned rank 0, while the set containing only the empty set is assigned rank 1.
For each ordinal \alpha , the set V_{\alpha} is defined to consist of all pure sets with rank less than \alpha . The entire von Neumann universe is denoted V .
Applications
Many mathematical concepts can be defined precisely using only set theoretic concepts. For example, mathematical structures as diverse as graphs, manifolds, rings, vector spaces, and relational algebras can all be defined as sets satisfying various (axiomatic) properties.
Equivalence and order relations are ubiquitous in mathematics, and the theory of mathematical relations can be described in set theory. Set theory is also a promising foundational system for much of mathematics.
Since the publication of the first volume of Principia Mathematica, it has been claimed that most (or even all) mathematical theorems can be derived using an aptly designed set of axioms for set theory, augmented with many definitions, using first or second-order logic. For example, properties of the natural and real numbers can be derived within set theory, as each of these number systems can be defined by representing their elements as sets of specific forms.
Set theory as a foundation for mathematical analysis, topology, abstract algebra, and discrete mathematics is likewise uncontroversial; mathematicians accept (in principle) that theorems in these areas can be derived from the relevant definitions and the axioms of set theory. However, it remains that few full derivations of complex mathematical theorems from set theory have been formally verified, since such formal derivations are often much longer than the natural language proofs mathematicians commonly present.
One verification project, Metamath, includes human-written, computer-verified derivations of more than 12,000 theorems starting from ZFC set theory, first-order logic and propositional logic.
See also
Class (set theory) Elementary Theory of the Category of Sets Glossary of set theory List of set theory topics Relational model – borrows from set theory Structural set theory Venn diagram
Text derived from https://en.wikipedia.org/w/index.php?oldid=1378615581 under CC BY-SA 4.0; modifications have been made.
References
- ↩Wikipedia “Set theory” publication date (×1) · confidence 0.95 revision URL