Set theory is the branch of
mathematical logic
Mathematical logic is the study of logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of for ...
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
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern 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
Julius Wilhelm Richard Dedekind (6 October 1831 – 12 February 1916) was a German mathematician who made important contributions to number theory, abstract algebra (particularly ring theory), and
the axiomatic foundations of arithmetic. His ...
and
Georg Cantor
Georg Ferdinand Ludwig Philipp Cantor ( , ; – January 6, 1918) was a German mathematician. He played a pivotal role in the creation of set theory, which has become a fundamental theory in mathematics. Cantor established the importance of ...
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
Naive set theory is any of several theories of sets used in the discussion of the foundations of mathematics.
Unlike Set theory#Axiomatic set theory, axiomatic set theories, which are defined using Mathematical_logic#Formal_logical_systems, forma ...
''. After the discovery of
paradoxes
A paradox is a logically self-contradictory statement or a statement that runs contrary to one's expectation. It is a statement that, despite apparently valid reasoning from true premises, leads to a seemingly self-contradictory or a logically u ...
within
naive set theory
Naive set theory is any of several theories of sets used in the discussion of the foundations of mathematics.
Unlike Set theory#Axiomatic set theory, axiomatic set theories, which are defined using Mathematical_logic#Formal_logical_systems, forma ...
(such as
Russell's paradox
In mathematical logic, Russell's paradox (also known as Russell's antinomy) is a set-theoretic paradox discovered by the British philosopher and mathematician Bertrand Russell in 1901. Russell's paradox shows that every set theory that contains a ...
,
Cantor's paradox
In set theory, Cantor's paradox states that there is no set of all cardinalities. This is derived from the theorem that there is no greatest cardinal number. In informal terms, the paradox is that the collection of all possible "infinite sizes" is ...
and the
Burali-Forti paradox
In set theory, a field of mathematics, the Burali-Forti paradox demonstrates that constructing "the set of all ordinal numbers" leads to a contradiction and therefore shows an antinomy in a system that allows its construction. It is named after C ...
) various
axiomatic system
In mathematics and logic, an axiomatic system is any set of axioms from which some or all axioms can be used in conjunction to logically derive theorems. A theory is a consistent, relatively-self-contained body of knowledge which usually contai ...
s were proposed in the early twentieth century, of which
Zermelo–Fraenkel set theory
In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such as ...
(with or without the
axiom of choice
In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collectio ...
) 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
Infinity is that which is boundless, endless, or larger than any natural number. It is often denoted by the infinity symbol .
Since the time of the ancient Greeks, the philosophical nature of infinity was the subject of many discussions amo ...
, and has various applications in
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
(such as in the theory of
relational algebra
In database theory, relational algebra is a theory that uses algebraic structures with a well-founded semantics for modeling data, and defining queries on it. The theory was introduced by Edgar F. Codd.
The main application of relational algebra ...
),
philosophy
Philosophy (from , ) is the systematized study of general and fundamental questions, such as those about existence, reason, knowledge, values, mind, and language. Such questions are often posed as problems to be studied or resolved. Some ...
and
formal semantics. Its foundational appeal, together with its
paradoxes
A paradox is a logically self-contradictory statement or a statement that runs contrary to one's expectation. It is a statement that, despite apparently valid reasoning from true premises, leads to a seemingly self-contradictory or a logically u ...
, its implications for the concept of infinity and its multiple applications, have made set theory an area of major interest for
logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...
ians and
philosophers of mathematics
The philosophy of mathematics is the branch of philosophy that studies the assumptions, foundations, and implications of mathematics. It aims to understand the nature and methods of mathematics, and find out the place of mathematics in people's ...
. Contemporary research into set theory covers a vast array of topics, ranging from the structure of the
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
line to the study of the
consistency
In classical deductive logic, a consistent theory is one that does not lead to a logical contradiction. The lack of contradiction can be defined in either semantic or syntactic terms. The semantic definition states that a theory is consistent ...
of
large cardinal
In the mathematical field of set theory, a large cardinal property is a certain kind of property of transfinite cardinal numbers. Cardinals with such properties are, as the name suggests, generally very "large" (for example, bigger than the least ...
s.
History
![Georg Cantor 1894](https://upload.wikimedia.org/wikipedia/commons/7/73/Georg_Cantor_1894.jpg)
Mathematical topics typically emerge and evolve through interactions among many researchers. Set theory, however, was founded by a single paper in 1874 by
Georg Cantor
Georg Ferdinand Ludwig Philipp Cantor ( , ; – January 6, 1918) was a German mathematician. He played a pivotal role in the creation of set theory, which has become a fundamental theory in mathematics. Cantor established the importance of ...
: "
On a Property of the Collection of All Real Algebraic Numbers
Cantor's first set theory article contains Georg Cantor's first theorems of transfinite set theory, which studies infinite sets and their properties. One of these theorems is his "revolutionary discovery" that the set of all real numbers is uncou ...
".
Since the 5th century BC, beginning with Greek mathematician
Zeno of Elea
Zeno of Elea (; grc, Ζήνων ὁ Ἐλεᾱ́της; ) was a pre-Socratic Greek philosopher of Magna Graecia and a member of the Eleatic School founded by Parmenides. Aristotle called him the inventor of the dialectic. He is best known fo ...
in the West and early
Indian mathematicians
chronology of Indian mathematicians spans from the Indus Valley civilisation and the Vedas to Modern India.
Indian mathematicians have made a number of contributions to mathematics that have significantly influenced scientists and mathematicians ...
in the East, mathematicians had struggled with the concept of
infinity
Infinity is that which is boundless, endless, or larger than any natural number. It is often denoted by the infinity symbol .
Since the time of the ancient Greeks, the philosophical nature of infinity was the subject of many discussions amo ...
. Especially notable is the work of
Bernard Bolzano
Bernard Bolzano (, ; ; ; born Bernardus Placidus Johann Gonzal Nepomuk Bolzano; 5 October 1781 – 18 December 1848) was a Bohemian mathematician, logician, philosopher, theologian and Catholic priest of Italian extraction, also known for his liber ...
in the first half of the 19th century. Modern understanding of infinity began in 1870–1874, and was motivated by Cantor's work in
real analysis
In mathematics, the branch of real analysis studies the behavior of real numbers, sequences and series of real numbers, and real functions. Some particular properties of real-valued sequences and functions that real analysis studies include converg ...
. An 1872 meeting between Cantor and
Richard Dedekind
Julius Wilhelm Richard Dedekind (6 October 1831 – 12 February 1916) was a German mathematician who made important contributions to number theory, abstract algebra (particularly ring theory), and
the axiomatic foundations of arithmetic. His ...
influenced Cantor's thinking, and culminated in Cantor's 1874 paper.
Cantor's work initially polarized the mathematicians of his day. While
Karl Weierstrass
Karl Theodor Wilhelm Weierstrass (german: link=no, Weierstraß ; 31 October 1815 – 19 February 1897) was a German mathematician often cited as the "father of modern analysis". Despite leaving university without a degree, he studied mathematics ...
and Dedekind supported Cantor,
Leopold Kronecker
Leopold Kronecker (; 7 December 1823 – 29 December 1891) was a German mathematician who worked on number theory, algebra and logic. He criticized Georg Cantor's work on set theory, and was quoted by as having said, "'" ("God made the integers, ...
, now seen as a founder of
mathematical constructivism
In the philosophy of mathematics, constructivism asserts that it is necessary to find (or "construct") a specific example of a mathematical object in order to prove that an example exists. Contrastingly, in classical mathematics, one can prove th ...
, did not. Cantorian set theory eventually became widespread, due to the utility of Cantorian concepts, such as
one-to-one correspondence
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
among sets, his proof that there are more
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
s than integers, and the "infinity of infinities" ("
Cantor's paradise
''Cantor's paradise'' is an expression used by in describing set theory and infinite cardinal numbers developed by Georg Cantor. The context of Hilbert's comment was his opposition to what he saw as L. E. J. Brouwer's reductive attempts to circum ...
") resulting from the
power set
In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is po ...
operation. This utility of set theory led to the article "Mengenlehre", contributed in 1898 by
Arthur Schoenflies
Arthur Moritz Schoenflies (; 17 April 1853 – 27 May 1928), sometimes written as Schönflies, was a German mathematician, known for his contributions to the application of group theory to crystallography, and for work in topology.
Schoenflies ...
to
Klein's encyclopedia
Felix Klein's ''Encyclopedia of Mathematical Sciences'' is a German mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, an ...
.
The next wave of excitement in set theory came around 1900, when it was discovered that some interpretations of Cantorian set theory gave rise to several contradictions, called
antinomies
Antinomy (Greek ἀντί, ''antí'', "against, in opposition to", and νόμος, ''nómos'', "law") refers to a real or apparent mutual incompatibility of two laws. It is a term used in logic and epistemology, particularly in the philosophy of I ...
or
paradoxes
A paradox is a logically self-contradictory statement or a statement that runs contrary to one's expectation. It is a statement that, despite apparently valid reasoning from true premises, leads to a seemingly self-contradictory or a logically u ...
.
Bertrand Russell
Bertrand Arthur William Russell, 3rd Earl Russell, (18 May 1872 – 2 February 1970) was a British mathematician, philosopher, logician, and public intellectual. He had a considerable influence on mathematics, logic, set theory, linguistics, ...
and
Ernst Zermelo
Ernst Friedrich Ferdinand Zermelo (, ; 27 July 187121 May 1953) was a German logician and mathematician, whose work has major implications for the foundations of mathematics. He is known for his role in developing Zermelo–Fraenkel axiomatic se ...
independently found the simplest and best known paradox, now called
Russell's paradox
In mathematical logic, Russell's paradox (also known as Russell's antinomy) is a set-theoretic paradox discovered by the British philosopher and mathematician Bertrand Russell in 1901. Russell's paradox shows that every set theory that contains a ...
: consider "the set of all sets that are not members of themselves", which leads to a contradiction since it must be a member of itself and not a member of itself. In 1899, Cantor had himself posed the question "What is the
cardinal number
In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a natural number: the number of elements in the set. Th ...
of the set of all sets?", and obtained a related paradox. Russell used his paradox as a theme in his 1903 review of continental mathematics in his ''
The Principles of Mathematics
''The Principles of Mathematics'' (''PoM'') is a 1903 book by Bertrand Russell, in which the author presented his famous paradox and argued his thesis that mathematics and logic are identical.
The book presents a view of the foundations of ...
''. Rather than the term ''set'', Russell used the term ''
class
Class or The Class may refer to:
Common uses not otherwise categorized
* Class (biology), a taxonomic rank
* Class (knowledge representation), a collection of individuals or objects
* Class (philosophy), an analytical concept used differentl ...
'', which has subsequently been used more technically.
In 1906, the term ''set'' appeared in the book ''Theory of Sets of Points'' by husband and wife
William Henry Young
William Henry Young Fellow of the Royal Society, FRS (London, 20 October 1863 – Lausanne, 7 July 1942) was an English people, English mathematician. Young was educated at City of London School and Peterhouse, Cambridge. He worked on measure ...
and
Grace Chisholm Young
Grace Chisholm Young (née Chisholm, 15 March 1868 – 29 March 1944) was an English mathematician. She was educated at Girton College, Cambridge, England and continued her studies at Göttingen University in Germany, where in 1895 she receive ...
, published by
Cambridge University Press
Cambridge University Press is the university press of the University of Cambridge. Granted letters patent by Henry VIII of England, King Henry VIII in 1534, it is the oldest university press
A university press is an academic publishing hou ...
.
The momentum of set theory was such that debate on the paradoxes did not lead to its abandonment. The work of Zermelo in 1908 and the work of
Abraham Fraenkel
Abraham Fraenkel ( he, אברהם הלוי (אדולף) פרנקל; February 17, 1891 – October 15, 1965) was a German-born Israeli mathematician. He was an early Zionist and the first Dean of Mathematics at the Hebrew University of Jerusalem. ...
and
Thoralf Skolem
Thoralf Albert Skolem (; 23 May 1887 – 23 March 1963) was a Norwegian mathematician who worked in mathematical logic and set theory.
Life
Although Skolem's father was a primary school teacher, most of his extended family were farmers. Skolem ...
in 1922 resulted in the set of axioms
ZFC, which became the most commonly used set of axioms for set theory. The work of
analysts, such as that of
Henri Lebesgue
Henri Léon Lebesgue (; June 28, 1875 – July 26, 1941) was a French mathematician known for his theory of integration, which was a generalization of the 17th-century concept of integration—summing the area between an axis and the curve of ...
, demonstrated the great mathematical utility of set theory, which has since become woven into the fabric of modern mathematics. Set theory is commonly used as a foundational system, although in some areas—such as
algebraic geometry
Algebraic geometry is a branch of mathematics, classically studying zeros of multivariate polynomials. Modern algebraic geometry is based on the use of abstract algebraic techniques, mainly from commutative algebra, for solving geometrical ...
and
algebraic topology
Algebraic topology is a branch of mathematics that uses tools from abstract algebra to study topological spaces. The basic goal is to find algebraic invariant (mathematics), invariants that classification theorem, classify topological spaces up t ...
—
category theory
Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, cate ...
is thought to be a preferred foundation.
Basic concepts and notation
Set theory begins with a fundamental
binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
between an object and a set . If is a ''
member
Member may refer to:
* Military jury, referred to as "Members" in military jargon
* Element (mathematics), an object that belongs to a mathematical set
* In object-oriented programming, a member of a class
** Field (computer science), entries in ...
'' (or ''element'') 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.
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
In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
'' 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
In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...
'' is defined. is called 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 .
Just as
arithmetic
Arithmetic () is an elementary part of mathematics that consists of the study of the properties of the traditional operations on numbers— addition, subtraction, multiplication, division, exponentiation, and extraction of roots. In the 19th ...
features
binary operation
In mathematics, a binary operation or dyadic operation is a rule for combining two elements (called operands) to produce another element. More formally, a binary operation is an operation of arity two.
More specifically, an internal binary op ...
s on
number
A number is a mathematical object used to count, measure, and label. The original examples are the natural numbers 1, 2, 3, 4, and so forth. Numbers can be represented in language with number words. More universally, individual numbers c ...
s, set theory features binary operations on sets. The following is a partial list of them:
*''
Union
Union commonly refers to:
* Trade union, an organization of workers
* Union (set theory), in mathematics, a fundamental operation on sets
Union may also refer to:
Arts and entertainment
Music
* Union (band), an American rock group
** ''Un ...
'' 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
In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, their i ...
'' 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
In set theory, the complement of a set , often denoted by (or ), is the set of elements not in .
When all sets in the universe, i.e. all sets under consideration, are considered to be members of a given set , the absolute complement of is the ...
'' 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
A complement is something that completes something else.
Complement may refer specifically to:
The arts
* Complement (music), an interval that, when added to another, spans an octave
** Aggregate complementation, the separation of pitch-class ...
'' 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
In set theory, a universal set is a set which contains all objects, including itself. In set theory as usually formulated, it can be proven in multiple ways that a universal set does not exist. However, some non-standard variants of set theory inc ...
as in the study of
Venn diagram
A Venn diagram is a widely used diagram style that shows the logical relation between set (mathematics), sets, popularized by John Venn (1834–1923) in the 1880s. The diagrams are used to teach elementary set theory, and to illustrate simple ...
s.
*''
Symmetric difference
In mathematics, the symmetric difference of two sets, also known as the disjunctive union, is the set of elements which are in either of the sets, but not in their intersection. For example, the symmetric difference of the sets \ and \ is \.
Th ...
'' 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
In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is
: A\ti ...
'' of and , denoted , is the set whose members are all possible
ordered pair
In mathematics, an ordered pair (''a'', ''b'') is a pair of objects. The order in which the objects appear in the pair is significant: the ordered pair (''a'', ''b'') is different from the ordered pair (''b'', ''a'') unless ''a'' = ''b''. (In con ...
s , where is a member of and is a member of . For example, the Cartesian product of
*''
Power set
In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is po ...
'' of a set , denoted
, is the set whose members are all of the possible subsets of . For example, the power set of is .
Some basic sets of central importance are the set of
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
s, the set of
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
s and the
empty set
In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other ...
—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.
Ontology
A set is
pure
Pure may refer to:
Computing
* A pure function
* A pure virtual function
* PureSystems, a family of computer systems introduced by IBM in 2012
* Pure Software, a company founded in 1991 by Reed Hastings to support the Purify tool
* Pure-FTPd, F ...
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
In set theory and related branches of mathematics, the von Neumann universe, or von Neumann hierarchy of sets, denoted by ''V'', is the class of hereditary well-founded sets. This collection, which is formalized by Zermelo–Fraenkel set theory (Z ...
'' of pure sets, and many systems of
axiomatic set theory
Set theory is the branch of mathematical logic that studies Set (mathematics), 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, ...
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
In mathematics, specifically set theory, a cumulative hierarchy is a family of sets W_\alpha indexed by ordinals \alpha such that
* W_\alpha \subseteq W_
* If \lambda is a limit ordinal, then W_\lambda = \bigcup_ W_
Some authors additionally r ...
, based on how deeply their members, members of members, etc. are nested. Each set in this hierarchy is assigned (by
transfinite recursion
Transfinite induction is an extension of mathematical induction to well-ordered sets, for example to sets of ordinal numbers or cardinal numbers. Its correctness is a theorem of ZFC.
Induction by cases
Let P(\alpha) be a property defined for a ...
) an
ordinal number
In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals (first, second, th, etc.) aimed to extend enumeration to infinite sets.
A finite set can be enumerated by successively labeling each element with the least n ...
, known as its ''rank.'' The rank of a pure set
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
, the set
is defined to consist of all pure sets with rank less than
. The entire von Neumann universe is denoted
.
Formalized set theory
Elementary set theory can be studied informally and intuitively, and so can be taught in primary schools using
Venn diagram
A Venn diagram is a widely used diagram style that shows the logical relation between set (mathematics), sets, popularized by John Venn (1834–1923) in the 1880s. The diagrams are used to teach elementary set theory, and to illustrate simple ...
s. The intuitive approach tacitly assumes that a set may be formed from the class of all objects satisfying any particular defining condition. This assumption gives rise to paradoxes, the simplest and best known of which are
Russell's paradox
In mathematical logic, Russell's paradox (also known as Russell's antinomy) is a set-theoretic paradox discovered by the British philosopher and mathematician Bertrand Russell in 1901. Russell's paradox shows that every set theory that contains a ...
and the
Burali-Forti paradox
In set theory, a field of mathematics, the Burali-Forti paradox demonstrates that constructing "the set of all ordinal numbers" leads to a contradiction and therefore shows an antinomy in a system that allows its construction. It is named after C ...
. Axiomatic set theory was originally devised to rid set theory of such paradoxes.
The most widely studied systems of axiomatic set theory imply that all sets form a
cumulative hierarchy
In mathematics, specifically set theory, a cumulative hierarchy is a family of sets W_\alpha indexed by ordinals \alpha such that
* W_\alpha \subseteq W_
* If \lambda is a limit ordinal, then W_\lambda = \bigcup_ W_
Some authors additionally r ...
. Such systems come in two flavors, those whose
ontology
In metaphysics, ontology is the philosophical study of being, as well as related concepts such as existence, becoming, and reality.
Ontology addresses questions like how entities are grouped into categories and which of these entities exis ...
consists of:
*''Sets alone''. This includes the most common axiomatic set theory,
Zermelo–Fraenkel set theory with the
axiom of choice (ZFC). Fragments of ZFC include:
**
Zermelo set theory
Zermelo set theory (sometimes denoted by Z-), as set out in a seminal paper in 1908 by Ernst Zermelo, is the ancestor of modern Zermelo–Fraenkel set theory (ZF) and its extensions, such as von Neumann–Bernays–Gödel set theory (NBG). It be ...
, which replaces the
axiom schema of replacement
In set theory, the axiom schema of replacement is a schema of axioms in Zermelo–Fraenkel set theory (ZF) that asserts that the image of any set under any definable mapping is also a set. It is necessary for the construction of certain infinite ...
with that of
separation
Separation may refer to:
Films
* ''Separation'' (1967 film), a British feature film written by and starring Jane Arden and directed by Jack Bond
* ''La Séparation'', 1994 French film
* ''A Separation'', 2011 Iranian film
* ''Separation'' (20 ...
;
**
General set theory
General set theory (GST) is George Boolos's (1998) name for a fragment of the axiomatic set theory Z. GST is sufficient for all mathematics not requiring infinite sets, and is the weakest known set theory whose theorems include the Peano axioms.
...
, a small fragment of
Zermelo set theory
Zermelo set theory (sometimes denoted by Z-), as set out in a seminal paper in 1908 by Ernst Zermelo, is the ancestor of modern Zermelo–Fraenkel set theory (ZF) and its extensions, such as von Neumann–Bernays–Gödel set theory (NBG). It be ...
sufficient for the
Peano axioms
In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly ...
and
finite set
In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,
:\
is a finite set with five elements. Th ...
s;
**
Kripke–Platek set theory
The Kripke–Platek set theory (KP), pronounced , is an axiomatic set theory developed by Saul Kripke and Richard Platek.
The theory can be thought of as roughly the predicative part of ZFC and is considerably weaker than it.
Axioms
In its fo ...
, which omits the axioms of infinity,
powerset
In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is postu ...
, and
choice
A choice is the range of different things from which a being can choose. The arrival at a choice may incorporate motivators and models. For example, a traveler might choose a route for a journey based on the preference of arriving at a giv ...
, and weakens the axiom schemata of
separation
Separation may refer to:
Films
* ''Separation'' (1967 film), a British feature film written by and starring Jane Arden and directed by Jack Bond
* ''La Séparation'', 1994 French film
* ''A Separation'', 2011 Iranian film
* ''Separation'' (20 ...
and
replacement.
*''Sets and
proper class
Proper may refer to:
Mathematics
* Proper map, in topology, a property of continuous function between topological spaces, if inverse images of compact subsets are compact
* Proper morphism, in algebraic geometry, an analogue of a proper map for ...
es''. These include
Von Neumann–Bernays–Gödel set theory
In the foundations of mathematics, von Neumann–Bernays–Gödel set theory (NBG) is an axiomatic set theory that is a conservative extension of Zermelo–Fraenkel–choice set theory (ZFC). NBG introduces the notion of class, which is a collect ...
, which has the same strength as
ZFC for theorems about sets alone, and
Morse–Kelley set theory
In the foundations of mathematics, Morse–Kelley set theory (MK), Kelley–Morse set theory (KM), Morse–Tarski set theory (MT), Quine–Morse set theory (QM) or the system of Quine and Morse is a first-order axiomatic set theory that is closely ...
and
Tarski–Grothendieck set theory
Tarski–Grothendieck set theory (TG, named after mathematicians Alfred Tarski and Alexander Grothendieck) is an axiomatic set theory. It is a non-conservative extension of Zermelo–Fraenkel set theory (ZFC) and is distinguished from other axio ...
, both of which are stronger than ZFC.
The above systems can be modified to allow ''
urelement
In set theory, a branch of mathematics, an urelement or ur-element (from the German prefix ''ur-'', 'primordial') is an object that is not a set, but that may be an element of a set. It is also referred to as an atom or individual.
Theory
There ...
s'', objects that can be members of sets but that are not themselves sets and do not have any members.
The ''
New Foundations
In mathematical logic, New Foundations (NF) is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of ''Principia Mathematica''. Quine first proposed NF in a 1937 article titled "New Foundations ...
'' systems of NFU (allowing
urelement
In set theory, a branch of mathematics, an urelement or ur-element (from the German prefix ''ur-'', 'primordial') is an object that is not a set, but that may be an element of a set. It is also referred to as an atom or individual.
Theory
There ...
s) and NF (lacking them), associate with
Willard Van Orman Quine
Willard Van Orman Quine (; known to his friends as "Van"; June 25, 1908 – December 25, 2000) was an American philosopher and logician in the analytic tradition, recognized as "one of the most influential philosophers of the twentieth century". ...
, are not based on a cumulative hierarchy. NF and NFU include a "set of everything", relative to which every set has a complement. In these systems urelements matter, because NF, but not NFU, produces sets for which the
axiom of choice
In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collectio ...
does not hold. Despite NF's ontology not reflecting the traditional cumulative hierarchy and violating well-foundedness,
Thomas Forster
Thomas Forster (1683 – October 1738), of Adderstone Hall, Northumberland, was an English landowner and Tory politician who sat in the House of Commons from 1708 to 1716. He served as a general of the Jacobite army in the 1715 Uprising ...
has argued that it does reflect an
iterative conception of set.
Systems of
constructive set theory
Constructive set theory is an approach to mathematical constructivism following the program of axiomatic set theory.
The same first-order language with "=" and "\in" of classical set theory is usually used, so this is not to be confused with a co ...
, such as CST, CZF, and IZF, embed their set axioms in
intuitionistic
In the philosophy of mathematics, intuitionism, or neointuitionism (opposed to preintuitionism), is an approach where mathematics is considered to be purely the result of the constructive mental activity of humans rather than the discovery of fu ...
instead of
classical logic
Classical logic (or standard logic or Frege-Russell logic) is the intensively studied and most widely used class of deductive logic. Classical logic has had much influence on analytic philosophy.
Characteristics
Each logical system in this class ...
. Yet other systems accept classical logic but feature a nonstandard membership relation. These include
rough set theory and
fuzzy set theory
In mathematics, fuzzy sets (a.k.a. uncertain sets) are Set (mathematics), sets whose Element (mathematics), elements have degrees of membership. Fuzzy sets were introduced independently by Lotfi Asker Zadeh, Lotfi A. Zadeh in 1965 as an extension o ...
, in which the value of an
atomic formula
In mathematical logic, an atomic formula (also known as an atom or a prime formula) is a formula with no deeper propositional structure, that is, a formula that contains no logical connectives or equivalently a formula that has no strict subformu ...
embodying the membership relation is not simply True or False. The
Boolean-valued model
In mathematical logic, a Boolean-valued model is a generalization of the ordinary Tarskian notion of structure from model theory. In a Boolean-valued model, the truth values of propositions are not limited to "true" and "false", but instead take v ...
s of
ZFC are a related subject.
An enrichment of
ZFC called
internal set theory
Internal set theory (IST) is a mathematical theory of sets developed by Edward Nelson that provides an axiomatic basis for a portion of the nonstandard analysis introduced by Abraham Robinson. Instead of adding new elements to the real numbers, Ne ...
was proposed by
Edward Nelson
Edward Nelson (May 4, 1932 – September 10, 2014) was an American mathematician. He was professor in the Mathematics Department at Princeton University. He was known for his work on mathematical physics and mathematical logic. In mathematical ...
in 1977.
Applications
Many mathematical concepts can be defined precisely using only set theoretic concepts. For example, mathematical structures as diverse as
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
s,
manifolds
In mathematics, a manifold is a topological space that locally resembles Euclidean space near each point. More precisely, an n-dimensional manifold, or ''n-manifold'' for short, is a topological space with the property that each point has a Ne ...
,
rings
Ring may refer to:
* Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry
* To make a sound with a bell, and the sound made by a bell
:(hence) to initiate a telephone connection
Arts, entertainment and media Film and ...
,
vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but can ...
s, and
relational algebra
In database theory, relational algebra is a theory that uses algebraic structures with a well-founded semantics for modeling data, and defining queries on it. The theory was introduced by Edgar F. Codd.
The main application of relational algebra ...
s can all be defined as sets satisfying various (axiomatic) properties.
Equivalence
Equivalence or Equivalent may refer to:
Arts and entertainment
*Album-equivalent unit, a measurement unit in the music industry
*Equivalence class (music)
*''Equivalent VIII'', or ''The Bricks'', a minimalist sculpture by Carl Andre
*'' Equival ...
and
order relation
Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article intro ...
s 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
The ''Principia Mathematica'' (often abbreviated ''PM'') is a three-volume work on the foundations of mathematics written by mathematician–philosophers Alfred North Whitehead and Bertrand Russell and published in 1910, 1912, and 1913. ...
'', 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
First or 1st is the ordinal form of the number one (#1).
First or 1st may also refer to:
*World record, specifically the first instance of a particular achievement
Arts and media Music
* 1$T, American rapper, singer-songwriter, DJ, and rec ...
or
second-order logic
In logic and mathematics, second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory.
First-order logic quantifies onl ...
. For example, properties of the
natural
Nature, in the broadest sense, is the physical world or universe. "Nature" can refer to the phenomena of the physical world, and also to life in general. The study of nature is a large, if not the only, part of science. Although humans are p ...
and
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
s can be derived within set theory, as each number system can be identified with a set of
equivalence class
In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements a ...
es under a suitable
equivalence relation
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation.
Each equivalence relation ...
whose field is some
infinite set
In set theory, an infinite set is a set that is not a finite set. Infinite sets may be countable or uncountable.
Properties
The set of natural numbers (whose existence is postulated by the axiom of infinity) is infinite. It is the only set th ...
.
Set theory as a foundation for
mathematical analysis
Analysis is the branch of mathematics dealing with continuous functions, limit (mathematics), limits, and related theories, such as Derivative, differentiation, Integral, integration, measure (mathematics), measure, infinite sequences, series (m ...
,
topology
In mathematics, topology (from the Greek language, Greek words , and ) is concerned with the properties of a mathematical object, geometric object that are preserved under Continuous function, continuous Deformation theory, deformations, such ...
,
abstract algebra
In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures. Algebraic structures include groups, rings, fields, modules, vector spaces, lattices, and algebras over a field. The term ''a ...
, and
discrete mathematics
Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continuous f ...
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
Metamath is a formal language and an associated computer program (a proof checker) for archiving, verifying, and studying mathematical proofs. Several databases of proved theorems have been developed using Metamath covering standard results in l ...
, includes human-written, computer-verified derivations of more than 12,000 theorems starting from
ZFC set theory,
first-order logic
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
and
propositional logic
Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions (which can be true or false) and relations b ...
.
Areas of study
Set theory is a major area of research in mathematics, with many interrelated subfields.
Combinatorial set theory
''Combinatorial set theory'' concerns extensions of finite
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...
to infinite sets. This includes the study of
cardinal arithmetic
In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a natural number: the number of elements in the set. The ...
and the study of extensions of
Ramsey's theorem
In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (say ...
such as the
Erdős–Rado theorem
In partition calculus, part of combinatorial set theory, a branch of mathematics, the Erdős–Rado theorem is a basic result extending Ramsey's theorem to uncountable sets. It is named after Paul Erdős and Richard Rado. It is sometimes also attr ...
.
Descriptive set theory
''Descriptive set theory'' is the study of subsets of the
real line
In elementary mathematics, a number line is a picture of a graduated straight line (geometry), line that serves as visual representation of the real numbers. Every point of a number line is assumed to correspond to a real number, and every real ...
and, more generally, subsets of
Polish space
In the mathematical discipline of general topology, a Polish space is a separable completely metrizable topological space; that is, a space homeomorphic to a complete metric space that has a countable dense subset. Polish spaces are so named bec ...
s. It begins with the study of
pointclass
In the mathematical field of descriptive set theory, a pointclass is a collection of sets of points, where a ''point'' is ordinarily understood to be an element of some perfect Polish space. In practice, a pointclass is usually characterized by ...
es in the
Borel hierarchy In mathematical logic, the Borel hierarchy is a stratification of the Borel algebra generated by the open subsets of a Polish space; elements of this algebra are called Borel sets. Each Borel set is assigned a unique countable ordinal number called ...
and extends to the study of more complex hierarchies such as the
projective hierarchy
In the mathematical field of descriptive set theory, a subset A of a Polish space X is projective if it is \boldsymbol^1_n for some positive integer n. Here A is
* \boldsymbol^1_1 if A is analytic
* \boldsymbol^1_n if the complement of A, X\set ...
and the
Wadge hierarchy In descriptive set theory, within mathematics, Wadge degrees are levels of complexity for sets of reals. Sets are compared by continuous reductions. The Wadge hierarchy is the structure of Wadge degrees. These concepts are named after William W. Wad ...
. Many properties of
Borel set
In mathematics, a Borel set is any set in a topological space that can be formed from open sets (or, equivalently, from closed sets) through the operations of countable union, countable intersection, and relative complement. Borel sets are named ...
s can be established in ZFC, but proving these properties hold for more complicated sets requires additional axioms related to determinacy and large cardinals.
The field of
effective descriptive set theory
Effective descriptive set theory is the branch of descriptive set theory dealing with sets of reals having lightface definitions; that is, definitions that do not require an arbitrary real parameter (Moschovakis 1980). Thus effective descriptive ...
is between set theory and
recursion theory
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since e ...
. It includes the study of
lightface pointclass
In the mathematical field of descriptive set theory, a pointclass is a collection of sets of points, where a ''point'' is ordinarily understood to be an element of some perfect Polish space. In practice, a pointclass is usually characterized by ...
es, and is closely related to
hyperarithmetical theory In recursion theory, hyperarithmetic theory is a generalization of Turing computability. It has close connections with definability in second-order arithmetic and with weak systems of set theory such as Kripke–Platek set theory. It is an importa ...
. In many cases, results of classical descriptive set theory have effective versions; in some cases, new results are obtained by proving the effective version first and then extending ("relativizing") it to make it more broadly applicable.
A recent area of research concerns
Borel equivalence relation In mathematics, a Borel equivalence relation on a Polish space ''X'' is an equivalence relation on ''X'' that is a Borel algebra, Borel subset of ''X'' × ''X'' (in the product topology).
Formal definition
Given Borel equivalence relation ...
s and more complicated definable
equivalence relation
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation.
Each equivalence relation ...
s. This has important applications to the study of
invariants in many fields of mathematics.
Fuzzy set theory
In set theory as
Cantor
A cantor or chanter is a person who leads people in singing or sometimes in prayer. In formal Jewish worship, a cantor is a person who sings solo verses or passages to which the choir or congregation responds.
In Judaism, a cantor sings and lead ...
defined and Zermelo and Fraenkel axiomatized, an object is either a member of a set or not. In ''
fuzzy set theory
In mathematics, fuzzy sets (a.k.a. uncertain sets) are Set (mathematics), sets whose Element (mathematics), elements have degrees of membership. Fuzzy sets were introduced independently by Lotfi Asker Zadeh, Lotfi A. Zadeh in 1965 as an extension o ...
'' this condition was relaxed by
Lotfi A. Zadeh
Lotfi Aliasker Zadeh (; az, Lütfi Rəhim oğlu Ələsgərzadə; fa, لطفی علیعسکرزاده; 4 February 1921 – 6 September 2017) was a mathematician, computer scientist, electrical engineer, artificial intelligence researcher, an ...
so an object has a ''degree of membership'' in a set, a number between 0 and 1. For example, the degree of membership of a person in the set of "tall people" is more flexible than a simple yes or no answer and can be a real number such as 0.75.
Inner model theory
An ''inner model'' of Zermelo–Fraenkel set theory (ZF) is a transitive
class
Class or The Class may refer to:
Common uses not otherwise categorized
* Class (biology), a taxonomic rank
* Class (knowledge representation), a collection of individuals or objects
* Class (philosophy), an analytical concept used differentl ...
that includes all the ordinals and satisfies all the axioms of ZF. The canonical example is the
constructible universe
In mathematics, in set theory, the constructible universe (or Gödel's constructible universe), denoted by , is a particular class of sets that can be described entirely in terms of simpler sets. is the union of the constructible hierarchy . It w ...
''L'' developed by Gödel.
One reason that the study of inner models is of interest is that it can be used to prove consistency results. For example, it can be shown that regardless of whether a model ''V'' of ZF satisfies the
continuum hypothesis
In mathematics, the continuum hypothesis (abbreviated CH) is a hypothesis about the possible sizes of infinite sets. It states that
or equivalently, that
In Zermelo–Fraenkel set theory with the axiom of choice (ZFC), this is equivalent to ...
or the
axiom of choice
In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collectio ...
, the inner model ''L'' constructed inside the original model will satisfy both the generalized continuum hypothesis and the axiom of choice. Thus the assumption that ZF is consistent (has at least one model) implies that ZF together with these two principles is consistent.
The study of inner models is common in the study of
determinacy
Determinacy is a subfield of set theory, a branch of mathematics, that examines the conditions under which one or the other player of a game has a winning strategy, and the consequences of the existence of such strategies. Alternatively and sim ...
and
large cardinal
In the mathematical field of set theory, a large cardinal property is a certain kind of property of transfinite cardinal numbers. Cardinals with such properties are, as the name suggests, generally very "large" (for example, bigger than the least ...
s, especially when considering axioms such as the axiom of determinacy that contradict the axiom of choice. Even if a fixed model of set theory satisfies the axiom of choice, it is possible for an inner model to fail to satisfy the axiom of choice. For example, the existence of sufficiently large cardinals implies that there is an inner model satisfying the axiom of determinacy (and thus not satisfying the axiom of choice).
Large cardinals
A ''large cardinal'' is a cardinal number with an extra property. Many such properties are studied, including
inaccessible cardinal
In set theory, an uncountable cardinal is inaccessible if it cannot be obtained from smaller cardinals by the usual operations of cardinal arithmetic. More precisely, a cardinal is strongly inaccessible if it is uncountable, it is not a sum of ...
s,
measurable cardinal
In mathematics, a measurable cardinal is a certain kind of large cardinal number. In order to define the concept, one introduces a two-valued measure on a cardinal , or more generally on any set. For a cardinal , it can be described as a subdivisio ...
s, and many more. These properties typically imply the cardinal number must be very large, with the existence of a cardinal with the specified property unprovable in
Zermelo–Fraenkel set theory
In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such as ...
.
Determinacy
''Determinacy'' refers to the fact that, under appropriate assumptions, certain two-player games of perfect information are determined from the start in the sense that one player must have a winning strategy. The existence of these strategies has important consequences in descriptive set theory, as the assumption that a broader class of games is determined often implies that a broader class of sets will have a topological property. The
axiom of determinacy
In mathematics, the axiom of determinacy (abbreviated as AD) is a possible axiom for set theory introduced by Jan Mycielski and Hugo Steinhaus in 1962. It refers to certain two-person topological games of length ω. AD states that every game of ...
(AD) is an important object of study; although incompatible with the axiom of choice, AD implies that all subsets of the real line are well behaved (in particular, measurable and with the perfect set property). AD can be used to prove that the
Wadge degree In descriptive set theory, within mathematics, Wadge degrees are levels of complexity for sets of reals. Sets are compared by continuous reductions. The Wadge hierarchy is the structure of Wadge degrees. These concepts are named after William W. W ...
s have an elegant structure.
Forcing
Paul Cohen
Paul Joseph Cohen (April 2, 1934 – March 23, 2007) was an American mathematician. He is best known for his proofs that the continuum hypothesis and the axiom of choice are independent from Zermelo–Fraenkel set theory, for which he was award ...
invented the method of ''
forcing'' while searching for a
model
A model is an informative representation of an object, person or system. The term originally denoted the Plan_(drawing), plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin ''modulus'', a mea ...
of
ZFC in which the
continuum hypothesis
In mathematics, the continuum hypothesis (abbreviated CH) is a hypothesis about the possible sizes of infinite sets. It states that
or equivalently, that
In Zermelo–Fraenkel set theory with the axiom of choice (ZFC), this is equivalent to ...
fails, or a model of ZF in which the
axiom of choice
In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collectio ...
fails. Forcing adjoins to some given model of set theory additional sets in order to create a larger model with properties determined (i.e. "forced") by the construction and the original model. For example, Cohen's construction adjoins additional subsets of the
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
s without changing any of the
cardinal number
In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a natural number: the number of elements in the set. Th ...
s of the original model. Forcing is also one of two methods for proving
relative consistency
In classical deductive logic, a consistent theory is one that does not lead to a logical contradiction. The lack of contradiction can be defined in either semantic or syntactic terms. The semantic definition states that a theory is consistent ...
by finitistic methods, the other method being
Boolean-valued model
In mathematical logic, a Boolean-valued model is a generalization of the ordinary Tarskian notion of structure from model theory. In a Boolean-valued model, the truth values of propositions are not limited to "true" and "false", but instead take v ...
s.
Cardinal invariants
A ''cardinal invariant'' is a property of the real line measured by a cardinal number. For example, a well-studied invariant is the smallest cardinality of a collection of
meagre set
In the mathematical field of general topology, a meagre set (also called a meager set or a set of first category) is a subset of a topological space that is small or negligible in a precise sense detailed below. A set that is not meagre is calle ...
s of reals whose union is the entire real line. These are invariants in the sense that any two isomorphic models of set theory must give the same cardinal for each invariant. Many cardinal invariants have been studied, and the relationships between them are often complex and related to axioms of set theory.
Set-theoretic topology
''Set-theoretic topology'' studies questions of
general topology
In mathematics, general topology is the branch of topology that deals with the basic set-theoretic definitions and constructions used in topology. It is the foundation of most other branches of topology, including differential topology, geomet ...
that are set-theoretic in nature or that require advanced methods of set theory for their solution. Many of these theorems are independent of ZFC, requiring stronger axioms for their proof. A famous problem is the
normal Moore space question, a question in general topology that was the subject of intense research. The answer to the normal Moore space question was eventually proved to be independent of ZFC.
Objections to set theory
From set theory's inception, some mathematicians
have objected to it as a
foundation for mathematics. The most common objection to set theory, one
Kronecker voiced in set theory's earliest years, starts from the
constructivist view that mathematics is loosely related to computation. If this view is granted, then the treatment of infinite sets, both in
naive
Naivety (also spelled naïvety), naiveness, or naïveté is the state of being naive. It refers to an apparent or actual lack of experience and sophistication, often describing a neglect of pragmatism in favor of moral idealism. A ''naïve'' may b ...
and in axiomatic set theory, introduces into mathematics methods and objects that are not computable even in principle. The feasibility of constructivism as a substitute foundation for mathematics was greatly increased by
Errett Bishop
Errett Albert Bishop (July 14, 1928 – April 14, 1983) was an Americans, American mathematician known for his work on analysis. He expanded constructive analysis in his 1967 ''Foundations of Constructive Analysis'', where he Mathematical proof, p ...
's influential book ''Foundations of Constructive Analysis''.
A different objection put forth by
Henri Poincaré
Jules Henri Poincaré ( S: stress final syllable ; 29 April 1854 – 17 July 1912) was a French mathematician, theoretical physicist, engineer, and philosopher of science. He is often described as a polymath, and in mathematics as "The ...
is that defining sets using the axiom schemas of
specification
A specification often refers to a set of documented requirements to be satisfied by a material, design, product, or service. A specification is often a type of technical standard.
There are different types of technical or engineering specificati ...
and
replacement, as well as the
axiom of power set
In mathematics, the axiom of power set is one of the Zermelo–Fraenkel axioms of axiomatic set theory.
In the formal language of the Zermelo–Fraenkel axioms, the axiom reads:
:\forall x \, \exists y \, \forall z \, \in y \iff \forall w \ ...
, introduces
impredicativity
In mathematics, logic and philosophy of mathematics, something that is impredicative is a self-referencing definition. Roughly speaking, a definition is impredicative if it invokes (mentions or quantifies over) the set being defined, or (more com ...
, a type of
circularity, into the definitions of mathematical objects. The scope of predicatively founded mathematics, while less than that of the commonly accepted Zermelo–Fraenkel theory, is much greater than that of constructive mathematics, to the point that
Solomon Feferman
Solomon Feferman (December 13, 1928 – July 26, 2016) was an American philosopher and mathematician who worked in mathematical logic.
Life
Solomon Feferman was born in The Bronx in New York City to working-class parents who had immigrated to th ...
has said that "all of scientifically applicable analysis can be developed
sing predicative methods
Singing is the act of creating musical sounds with the voice. A person who sings is called a singer, artist or vocalist (in jazz and/or popular music). Singers perform music (arias, recitatives, songs, etc.) that can be sung with or without ...
.
Ludwig Wittgenstein
Ludwig Josef Johann Wittgenstein ( ; ; 26 April 1889 – 29 April 1951) was an Austrian-British philosopher who worked primarily in logic, the philosophy of mathematics, the philosophy of mind, and the philosophy of language. He is considere ...
condemned set theory philosophically for its connotations of
mathematical platonism
The philosophy of mathematics is the branch of philosophy that studies the assumptions, foundations, and implications of mathematics. It aims to understand the nature and methods of mathematics, and find out the place of mathematics in people's ...
. He wrote that "set theory is wrong", since it builds on the "nonsense" of fictitious symbolism, has "pernicious idioms", and that it is nonsensical to talk about "all numbers". Wittgenstein identified mathematics with algorithmic human deduction; the need for a secure foundation for mathematics seemed, to him, nonsensical. Moreover, since human effort is necessarily finite, Wittgenstein's philosophy required an ontological commitment to radical
constructivism
Constructivism may refer to:
Art and architecture
* Constructivism (art), an early 20th-century artistic movement that extols art as a practice for social purposes
* Constructivist architecture, an architectural movement in Russia in the 1920s a ...
and
finitism
Finitism is a philosophy of mathematics that accepts the existence only of finite mathematical objects. It is best understood in comparison to the mainstream philosophy of mathematics where infinite mathematical objects (e.g., infinite sets) are ac ...
. Meta-mathematical statements — which, for Wittgenstein, included any statement quantifying over infinite domains, and thus almost all modern set theory — are not mathematics. Few modern philosophers have adopted Wittgenstein's views after a spectacular blunder in ''
Remarks on the Foundations of Mathematics
''Remarks on the Foundations of Mathematics'' (german: Bemerkungen über die Grundlagen der Mathematik) is a book of Ludwig Wittgenstein's notes on the philosophy of mathematics. It has been translated from German to English by G.E.M. Anscombe, ...
'': Wittgenstein attempted to refute
Gödel's incompleteness theorems
Gödel's incompleteness theorems are two theorems of mathematical logic
Mathematical logic is the study of logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research i ...
after having only read the abstract. As reviewers
Kreisel
Kreisel (German for gyro) is the name of a turn found on some bobsleigh, luge, and skeleton tracks around the world. It is a single continuous curve which turns far enough around that the track must go under itself on the exit of the curve.
Ther ...
,
Bernays,
Dummett, and
Goodstein all pointed out, many of his critiques did not apply to the paper in full. Only recently have philosophers such as
Crispin Wright
Crispin James Garth Wright (; born 21 December 1942) is a British philosopher, who has written on neo-Fregean (neo-logicist) philosophy of mathematics, Wittgenstein's later philosophy, and on issues related to truth, realism, cognitivism, skep ...
begun to rehabilitate Wittgenstein's arguments.
Category theorists
Category, plural categories, may refer to:
Philosophy and general uses
*Categorization, categories in cognitive science, information science and generally
*Category of being
*Categories (Aristotle), ''Categories'' (Aristotle)
*Category (Kant)
...
have proposed
topos theory
In mathematics, a topos (, ; plural topoi or , or toposes) is a category that behaves like the category of sheaves of sets on a topological space (or more generally: on a site). Topoi behave much like the category of sets and possess a notion ...
as an alternative to traditional axiomatic set theory. Topos theory can interpret various alternatives to that theory, such as
constructivism
Constructivism may refer to:
Art and architecture
* Constructivism (art), an early 20th-century artistic movement that extols art as a practice for social purposes
* Constructivist architecture, an architectural movement in Russia in the 1920s a ...
, finite set theory, and
computable
Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is close ...
set theory. Topoi also give a natural setting for forcing and discussions of the independence of choice from ZF, as well as providing the framework for
pointless topology In mathematics, pointless topology, also called point-free topology (or pointfree topology) and locale theory, is an approach to topology that avoids mentioning points, and in which the lattices of open sets are the primitive notions. In this appr ...
and
Stone space In topology and related areas of mathematics, a Stone space, also known as a profinite space or profinite set, is a compact totally disconnected Hausdorff space. Stone spaces are named after Marshall Harvey Stone who introduced and studied them in t ...
s.
An active area of research is the
univalent foundations Univalent foundations are an approach to the foundations of mathematics in which mathematical structures are built out of objects called ''types''. Types in univalent foundations do not correspond exactly to anything in set-theoretic foundations, bu ...
and related to it
homotopy type theory
In mathematical logic and computer science, homotopy type theory (HoTT ) refers to various lines of development of intuitionistic type theory, based on the interpretation of types as objects to which the intuition of (abstract) homotopy theory ...
. Within homotopy type theory, a set may be regarded as a homotopy 0-type, with
universal properties
In mathematics, more specifically in category theory, a universal property is a property that characterizes up to an isomorphism the result of some constructions. Thus, universal properties can be used for defining some objects independently fro ...
of sets arising from the inductive and recursive properties of
higher inductive type
In mathematical logic and computer science, homotopy type theory (HoTT ) refers to various lines of development of intuitionistic type theory, based on the interpretation of types as objects to which the intuition of (abstract) homotopy theory a ...
s. Principles such as the
axiom of choice
In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collectio ...
and the
law of the excluded middle
In logic, the law of excluded middle (or the principle of excluded middle) states that for every proposition, Exclusive or, either this proposition or its negation is Truth value, true. It is one of the so-called Law of thought#The three tradit ...
can be formulated in a manner corresponding to the classical formulation in set theory or perhaps in a spectrum of distinct ways unique to type theory. Some of these principles may be proven to be a consequence of other principles. The variety of formulations of these axiomatic principles allows for a detailed analysis of the formulations required in order to derive various mathematical results.
''Homotopy Type Theory: Univalent Foundations of Mathematics''
The Univalent Foundations Program. Institute for Advanced Study
The Institute for Advanced Study (IAS), located in Princeton, New Jersey, in the United States, is an independent center for theoretical research and intellectual inquiry. It has served as the academic home of internationally preeminent scholar ...
.
Set theory in mathematical education
As set theory gained popularity as a foundation for modern mathematics, there has been support for the idea of introducing the basics of naive set theory
Naive set theory is any of several theories of sets used in the discussion of the foundations of mathematics.
Unlike Set theory#Axiomatic set theory, axiomatic set theories, which are defined using Mathematical_logic#Formal_logical_systems, forma ...
early in mathematics education
In contemporary education, mathematics education, known in Europe as the didactics or pedagogy of mathematics – is the practice of teaching, learning and carrying out scholarly research into the transfer of mathematical knowledge.
Although rese ...
.
In the US in the 1960s, the New Math
New Mathematics or New Math was a dramatic but temporary change in the way mathematics was taught in American grade schools, and to a lesser extent in European countries and elsewhere, during the 1950s1970s. Curriculum topics and teaching pract ...
experiment aimed to teach basic set theory, among other abstract concepts, to primary school
A primary school (in Ireland, the United Kingdom, Australia, Trinidad and Tobago, Jamaica, and South Africa), junior school (in Australia), elementary school or grade school (in North America and the Philippines) is a school for primary e ...
students, but was met with much criticism. The math syllabus in European schools followed this trend, and currently includes the subject at different levels in all grades. Venn diagram
A Venn diagram is a widely used diagram style that shows the logical relation between set (mathematics), sets, popularized by John Venn (1834–1923) in the 1880s. The diagrams are used to teach elementary set theory, and to illustrate simple ...
s are widely employed to explain basic set-theoretic relationships to primary school
A primary school (in Ireland, the United Kingdom, Australia, Trinidad and Tobago, Jamaica, and South Africa), junior school (in Australia), elementary school or grade school (in North America and the Philippines) is a school for primary e ...
students (even though John Venn
John Venn, Fellow of the Royal Society, FRS, Fellow of the Society of Antiquaries of London, FSA (4 August 1834 – 4 April 1923) was an English mathematician, logician and philosopher noted for introducing Venn diagrams, which are used in l ...
originally devised them as part of a procedure to assess the validity
Validity or Valid may refer to:
Science/mathematics/statistics:
* Validity (logic), a property of a logical argument
* Scientific:
** Internal validity, the validity of causal inferences within scientific studies, usually based on experiments
** ...
of inference
Inferences are steps in reasoning, moving from premises to logical consequences; etymologically, the word '' infer'' means to "carry forward". Inference is theoretically traditionally divided into deduction and induction, a distinction that in ...
s in term logic
In philosophy, term logic, also known as traditional logic, syllogistic logic or Aristotelian logic, is a loose name for an approach to formal logic that began with Aristotle and was developed further in ancient history mostly by his followers, th ...
).
Set theory is used to introduce students to logical operators
In logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a logical constant. They can be used to connect logical formulas. For instance in the syntax of propositional logic, the binary c ...
(NOT, AND, OR), and semantic or rule description (technically intensional definition
In logic, extensional and intensional definitions are two key ways in which the objects, concepts, or referents a term refers to can be defined. They give meaning or denotation to a term.
Intensional definition
An intensional definition gives ...
) of sets (e.g. "months starting with the letter ''A''"), which may be useful when learning computer programming
Computer programming is the process of performing a particular computation (or more generally, accomplishing a specific computing result), usually by designing and building an executable computer program. Programming involves tasks such as ana ...
, since boolean logic
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variable (mathematics), variables are the truth values ''true'' and ''false'', usually denote ...
is used in various programming language
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming ...
s. Likewise, set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
s and other collection-like objects, such as multiset
In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that e ...
s and list
A ''list'' is any set of items in a row. List or lists may also refer to:
People
* List (surname)
Organizations
* List College, an undergraduate division of the Jewish Theological Seminary of America
* SC Germania List, German rugby union ...
s, are common datatype
In computer science and computer programming, a data type (or simply type) is a set of possible values and a set of allowed operations on it. A data type tells the compiler or interpreter how the programmer intends to use the data. Most progra ...
s in computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
and programming.
In addition to that, set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
s are commonly referred to in mathematical teaching when talking about different types of numbers (the sets of natural numbers
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''cardinal n ...
, of integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s, of real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
s, etc.), and when defining a mathematical function
In mathematics, a function from a set to a set assigns to each element of exactly one element of .; the words map, mapping, transformation, correspondence, and operator are often used synonymously. The set is called the domain of the functi ...
as a relation from one set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
(the domain
Domain may refer to:
Mathematics
*Domain of a function, the set of input values for which the (total) function is defined
**Domain of definition of a partial function
**Natural domain of a partial function
**Domain of holomorphy of a function
* Do ...
) to another set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
(the range
Range may refer to:
Geography
* Range (geographic), a chain of hills or mountains; a somewhat linear, complex mountainous or hilly area (cordillera, sierra)
** Mountain range, a group of mountains bordered by lowlands
* Range, a term used to i ...
).
See also
*
* Class (set theory)
In set theory and its applications throughout mathematics, a class is a collection of sets (or sometimes other mathematical objects) that can be unambiguously defined by a property that all its members share. Classes act as a way to have set-like ...
* List of set theory topics
This page is a list of articles related to set theory.
Articles on individual set theory topics
Lists related to set theory
* Glossary of set theory
* List of large cardinal properties
* List of properties of sets of reals
* List o ...
* Relational model
The relational model (RM) is an approach to managing data using a Structure (mathematical logic), structure and language consistent with first-order logic, first-order predicate logic, first described in 1969 by English computer scientist Edgar F. ...
– borrows from set theory
* Venn diagram
A Venn diagram is a widely used diagram style that shows the logical relation between set (mathematics), sets, popularized by John Venn (1834–1923) in the 1880s. The diagrams are used to teach elementary set theory, and to illustrate simple ...
Notes
References
*
*
Further reading
*
*
*
*
*
*
External links
* Daniel Cunningham
Set Theory
article in the ''Internet Encyclopedia of Philosophy
The ''Internet Encyclopedia of Philosophy'' (''IEP'') is a scholarly online encyclopedia, dealing with philosophy, philosophical topics, and philosophers. The IEP combines open access publication with peer reviewed publication of original pape ...
''.
* Jose Ferreiros
"The Early Development of Set Theory"
article in the '' tanford Encyclopedia of Philosophy'.
* Foreman, Matthew, Akihiro Kanamori
is a Japanese-born American mathematician. He specializes in set theory and is the author of the monograph on large cardinal property, large cardinals, ''The Higher Infinite''. He has written several essays on the history of mathematics, especia ...
, eds.
Handbook of Set Theory
'. 3 vols., 2010. Each chapter surveys some aspect of contemporary research in set theory. Does not cover established elementary set theory, on which see Devlin (1993).
*
*
* Schoenflies, Arthur (1898)
Mengenlehre
in Klein's encyclopedia
Felix Klein's ''Encyclopedia of Mathematical Sciences'' is a German mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, an ...
.
*
*
{{Authority control
S
Formal methods
Georg Cantor