This article is about sets themselves. For the branches of mathematics studying sets, seeNaive set theory andSet theory.
Collection of mathematical objects
A set of polygons in anEuler diagramThis set equals the one above since they have the same elements.
Inmathematics, aset is a collection of different things; the things areelements ormembers of the set and are typicallymathematical objects: numbers, symbols, points in space, lines, othergeometric shapes, variables, or other sets. A set may befinite orinfinite. There is a unique set with no elements, called theempty set; a set with a single element is asingleton.
Sets are ubiquitous in modern mathematics. Indeed,set theory, more specificallyZermelo–Fraenkel set theory, has been the standard way to provide rigorousfoundations for all branches of mathematics since the first half of the 20th century.
Before the end of the 19th century, sets were not studied specifically, and were not clearly distinguished fromsequences. Most mathematicians consideredinfinity aspotential—meaning that it is the result of an endless process—and were reluctant to considerinfinite sets, that is sets whose number of members is not anatural number. Specifically, aline was not considered as the set of its points, but as alocus where points may be located.
The mathematical study of infinite sets began withGeorg Cantor (1845–1918). This provided some counterintuitive facts and paradoxes. For example, thenumber line has aninfinite number of elements that is strictly larger than the infinite number ofnatural numbers, and anyline segment has the same number of elements as the whole space. Also,Russell's paradox implies that the phrase "the set of all sets" is self-contradictory.
Generally, the common usage of sets in mathematics does not require the full power of Zermelo–Fraenkel set theory. In mathematical practice, sets can be manipulated independently of thelogical framework of this theory.
The object of this article is to summarize the manipulation rules and properties of sets that are commonly used in mathematics, without reference to any logical framework. For the branch of mathematics that studies sets, seeSet theory; for an informal presentation of the corresponding logical framework, seeNaive set theory; for a more formal presentation, seeAxiomatic set theory andZermelo–Fraenkel set theory.
In mathematics, a set is a collection of different things.[2][3][4][5] These things are calledelements ormembers of the set and are typicallymathematical objects of any kind such as numbers, symbols,points in space,lines, othergeometrical shapes,variables,functions, or even other sets.[6][7] A set may also be called acollection or family, especially when its elements are themselves sets; this may avoid the confusion between the set and its members, and may make reading easier. A set may be specified either by listing its elements or by a property that characterizes its elements, such as for the set of theprime numbers or the set of all students in a given class.[8][9][10]
If is an element of a set, one says thatbelongs to oris in, and this is written as.[11] The statement " is not in" is written as, which can also be read as "y is not inS".[12][13] For example, if is the set of theintegers, one has and. Each set is uniquely characterized by its elements. In particular, two sets that have precisely the same elements areequal (they are the same set).[14] This property, calledextensionality, can be written in formula asThis implies that there is only one set with no element, theempty set (ornull set) that is denoted,[a] or[17][18] Asingleton is a set with exactly one element.[b] If is this element, the singleton is denoted If is itself a set, it must not be confused with For example, is a set with no elements, while is a singleton with as its unique element.
A set isfinite if there exists anatural number such that the first natural numbers can be put inone to one correspondence with the elements of the set. In this case, one says that is the number of elements of the set. A set isinfinite if such an does not exist. Theempty set is a finite set with elements.
All standard number systems are infinite sets
The natural numbers form an infinite set, commonly denoted. Other examples of infinite sets includenumber sets that contain the natural numbers,real vector spaces,curves and most sorts ofspaces.
Extensionality implies that for specifying a set, one has either to list its elements or to provide a property that uniquely characterizes the set elements.
Roster orenumeration notation is a notation introduced byErnst Zermelo in 1908 that specifies a set by listing its elements betweenbraces, separated by commas.[19][20][21][22][23] For example, one knows thatanddenote sets and nottuples because of the enclosing braces.
Above notations and for the empty set and for a singleton are examples of roster notation.
When specifying sets, it only matters whether each distinct element is in the set or not; this means a set does not change if elements are repeated or arranged in a different order. For example,[24][25][26]
When there is a clear pattern for generating all set elements, one can useellipses for abbreviating the notation,[27][28] such as infor the positive integers not greater than.
Ellipses allow also expanding roster notation to some infinite sets. For example, the set of all integers can be denoted as
Set-builder notation specifies a set as being the set of all elements that satisfy somelogical formula.[29][30][31] More precisely, if is a logical formula depending on avariable, which evaluates totrue orfalse depending on the value of, thenor[32]denotes the set of all for which is true.[8] For example, a setF can be specified as follows:In this notation, thevertical bar "|" is read as "such that", and the whole formula can be read as "F is the set of alln such thatn is an integer in the range from 0 to 19 inclusive".
Some logical formulas, such as or cannot be used in set-builder notation because there is no set for which the elements are characterized by the formula. There are several ways for avoiding the problem. One may prove that the formula defines a set; this is often almost immediate, but may be very difficult.
One may also introduce a larger set that must contain all elements of the specified set, and write the notation asor
One may also define once for all and take the convention that every variable that appears on the left of the vertical bar of the notation represents an element of. This amounts to say that is implicit in set-builder notation. In this case, is often calledthedomain of discourse or auniverse.
For example, with the convention that a lower case Latin letter may represent areal number and nothing else, theexpressionis an abbreviation ofwhich defines theirrational numbers.
Asubset of a set is a set such that every element of is also an element of.[33] If is a subset of, one says commonly that iscontained in,contains, or is asuperset of. This denoted and. However many authors use and instead. The definition of a subset can be expressed in notation as
A set is aproper subset of a set if and. This is denoted and. When is used for the subset relation, or in case of possible ambiguity, one uses commonly and.[34]
Therelationship between sets established by ⊆ is calledinclusion orcontainment. Equality between sets can be expressed in terms of subsets. Two sets are equal if and only if they contain each other: that is,A ⊆B andB ⊆A is equivalent toA =B.[30][8] The empty set is a subset of every set:∅ ⊆A.[17]
Examples:
The set of all humans is a proper subset of the set of all mammals.
There are several standardoperations that produce new sets from given sets, in the same way asaddition andmultiplication produce new numbers from given numbers. The operations that are considered in this section are those such that all elements of the produced sets belong to a previously defined set. These operations are commonly illustrated withEuler diagrams andVenn diagrams.[35]
The main basic operations on sets are the following ones.
Theintersection of two sets and is a set denoted whose elements are those elements that belong to both and. That is,where denotes thelogical and.
Intersection isassociative andcommutative; this means that for proceeding a sequence of intersections, one may proceed in any order, without the need of parentheses for specifying theorder of operations. Intersection has no generalidentity element. However, if one restricts intersection to the subsets of a given set, intersection has as identity element.
If is a nonempty set of sets, its intersection, denoted is the set whose elements are those elements that belong to all sets in. That is,
These two definitions of the intersection coincide when has two elements.
Theunion of two sets and is a set denoted whose elements are those elements that belong to or or both. That is,where denotes thelogical or.
Union isassociative andcommutative; this means that for proceeding a sequence of intersections, one may proceed in any order, without the need of parentheses for specifying theorder of operations. The empty set is anidentity element for the union operation.
If is a set of sets, its union, denoted is the set whose elements are those elements that belong to at least one set in. That is,
These two definitions of the union coincide when has two elements.
Theset difference of two sets and, is a set, denoted or, whose elements are those elements that belong to, but not to. That is,where denotes thelogical and.
Thecomplement ofA inU
When the difference is also called thecomplement of in. When all sets that are considered are subsets of a fixeduniversal set, the complement is often called theabsolute complement of.
Thesymmetric difference ofA andB
Thesymmetric difference of two sets and, denoted, is the set of those elements that belong toA orB but not to both:
The set of all subsets of a set is called thepowerset of, often denoted. The powerset is an algebraic structure whose main operations are union, intersection, set difference, symmetric difference and absolute complement (complement in).
The powerset is aBoolean ring that has the symmetric difference as addition, the intersection as multiplication, the empty set asadditive identity, asmultiplicative identity, and complement as additive inverse.
The powerset is also aBoolean algebra for which thejoin is the union, themeet is the intersection, and the negation is the set complement.
Afunction from a setA—thedomain—to a setB—thecodomain—is a rule that assigns to each element ofA a unique element ofB. For example, thesquare function maps every real numberx tox2. Functions can be formally defined in terms of sets by means of theirgraph, which are subsets of theCartesian product (see below) of the domain and the codomain.
Functions are fundamental for set theory, and examples are given in following sections.
Intuitively, anindexed family is a set whose elements are labelled with the elements of another set, the index set. These labels allow the same element to occur several times in the family.
Formally, an indexed family is a function that has the index set as its domain. Generally, the usualfunctional notation is not used for indexed families. Instead, the element of the index set is written as a subscript of the name of the family, such as in.
When the index set is, an indexed family is called anordered pair. When the index set is the set of the first natural numbers, an indexed family is called an-tuple. When the index set is the set of all natural numbers an indexed family is called asequence.
In all these cases, the natural order of the natural numbers allows omitting indices for explicit indexed families. For example, denotes the 3-tuple such that.
The above notations and are commonly replaced with a notation involving indexed families, namely and
The formulas of the above sections are special cases of the formulas for indexed families, where and. The formulas remain correct, even in the case where for some, since
In§ Basic operations, all elements of sets produced by set operations belong to previously defined sets. In this section, other set operations are considered, which produce sets whose elements can be outside all previously considered sets. These operations areCartesian product,disjoint union,set exponentiation andpower set.
The Cartesian product of two sets has already been used for defining functions.
Given two sets and, theirCartesian product, denoted is the set formed by all ordered pairs such that and; that is,
This definition does not suppose that the two sets are different. In particular,
Since this definition involves a pair of indices (1,2), it generalizes straightforwardly to the Cartesian product ordirect product of any indexed family of sets:That is, the elements of the Cartesian product of a family of sets are all families of elements such that each one belongs to the set of the same index. The fact that, for every indexed family of nonempty sets, the Cartesian product is a nonempty set is insured by theaxiom of choice.
Given two sets and, theset exponentiation, denoted, is the set that has as elements all functions from to.
Equivalently, can be viewed as the Cartesian product of a family, indexed by, of sets that are all equal to. This explains the terminology and the notation, sinceexponentiation with integer exponents is a product where all factors are equal to the base.
Thepower set of a set is the set that has all subsets of as elements, including theempty set and itself.[30] It is often denoted. For example,
There is a natural one-to-one correspondence (bijection) between the subsets of and the functions from to; this correspondence associates to each subset the function that takes the value on the subset and elsewhere. Because of this correspondence, the power set of is commonly identified with set exponentiation:In this notation, is often abbreviated as, which gives[30][36]In particular, if has elements, then has elements.[37]
Thedisjoint union of two or more sets is similar to the union, but, if two sets have elements in common, these elements are considered as distinct in the disjoint union. This is obtained by labelling the elements by the indexes of the set they are coming from.
The disjoint union of two sets and is commonly denoted and is thus defined as
If is a set with elements, then has elements, while has elements.
The disjoint union of two sets is a particular case of the disjoint union of an indexed family of sets, which is defined as
The disjoint union is thecoproduct in thecategory of sets. Therefore the notationis commonly used.
Given an indexed family of sets, there is anatural mapwhich consists in "forgetting" the indices.
This maps is always surjective; it is bijective if and only if the arepairwise disjoint, that is, all intersections of two sets of the family are empty. In this case, and are commonly identified, and one says that their union is thedisjoint union of the members of the family.
If a set is the disjoint union of a family of subsets, one says also that the family is apartition of the set.
Informally, the cardinality of a setS, often denoted|S|, is the number of its members.[38] This number is thenatural number when there is abijection between the set that is considered and the set of the first natural numbers. The cardinality of the empty set is.[39] A set with the cardinality of a natural number is called afinite set which is true for both cases. Otherwise, one has aninfinite set.[40]
The fact that natural numbers measure the cardinality of finite sets is the basis of the concept of natural number, and predates for several thousands years the concept of sets. A large part ofcombinatorics is devoted to the computation or estimation of the cardinality of finite sets.
The cardinality of an infinite set is commonly represented by acardinal number, exactly as the number of elements of a finite set is represented by a natural numbers. The definition of cardinal numbers is too technical for this article; however, many properties of cardinalities can be dealt without referring to cardinal numbers, as follows.
Two sets and have the same cardinality if there exists a one-to-one correspondence (bijection) between them. This is denoted and would be anequivalence relation on sets, if a set of all sets would exist.
For example, the natural numbers and the even natural numbers have the same cardinality, since multiplication by two provides such a bijection. Similarly, theinterval and the set of all real numbers have the same cardinality, a bijection being provided by the function.
Having the same cardinality of aproper subset is a characteristic property of infinite sets:a set is infinite if and only if it has the same cardinality as one of its proper subsets.So, by the above example, the natural numbers form an infinite set.[30]
Besides equality, there is a natural inequality between cardinalities: a set has a cardinality smaller than or equal to the cardinality of another set if there is aninjection frome to. This is denoted
Schröder–Bernstein theorem implies that and imply Also, one has if and only if there is a surjection from to. For every two sets and, one has either or[c] So, inequality of cardinalities is atotal order.
The cardinality of the set of the natural numbers, denoted is the smallest infinite cardinality. This means that if is a set of natural numbers, then either is finite or
Sets with cardinality less than or equal to are calledcountable sets; these are either finite sets orcountably infinite sets (sets of cardinality); some authors use "countable" to mean "countably infinite". Sets with cardinality strictly greater than are calleduncountable sets.
Cantor's diagonal argument shows that, for every set, its power set (the set of its subsets) has a greater cardinality:This implies that there is no greatest cardinality.
The cardinality of set of thereal numbers is called thecardinality of the continuum and denoted. (The term "continuum" referred to thereal line before the 20th century, when the real line was not commonly viewed as a set of numbers.)
Since, as seen above, the real line has the same cardinality of anopen interval, every subset of that contains a nonemptyopen interval has also the cardinality.
One hasmeaning that the cardinality of the real numbers equals the cardinality of thepower set of the natural numbers. In particular,[41]
When published in 1878 byGeorg Cantor,[42] this result was so astonishing that it was refused by mathematicians, and several tens years were needed before its common acceptance.
Thecontinuum hypothesis, was a conjecture formulated by Georg Cantor in 1878 that there is no set with cardinality strictly between and.[42] In 1963,Paul Cohen proved that the continuum hypothesis isindependent of theaxioms ofZermelo–Fraenkel set theory with theaxiom of choice.[44] This means that if the most widely usedset theory isconsistent (that is not self-contradictory),[d] then the same is true for both the set theory with the continuum hypothesis added as a further axiom, and the set theory with the negation of the continuum hypothesis added.
Informally, the axiom of choice says that, given any family of nonempty sets, one can choose simultaneously an element in each of them.[e] Formulated this way, acceptability of this axiom sets a foundational logical question, because of the difficulty of conceiving an infinite instantaneous action. However, there are several equivalent formulations that are much less controversial and have strong consequences in many areas of mathematics. In the present days, the axiom of choice is thus commonly accepted in mainstream mathematics.
A more formal statement of the axiom of choice is:the Cartesian product of every indexed family of nonempty sets is non empty.
Other equivalent forms are described in the following subsections.
Zorn's lemma is an assertion that is equivalent to the axiom of choice under the other axioms of set theory, and is easier to use in usual mathematics.
Let be a partial ordered set. Achain in is a subset that istotally ordered under the induced order. Zorn's lemma states that, if every chain in has anupper bound in, then has (at least) amaximal element, that is, an element that is not smaller than another element of.
In most uses of Zorn's lemma, is a set of sets, the order is set inclusion, and the upperbound of a chain is taken as the union of its members.
An example of use of Zorn's lemma, is the proof that everyvector space has abasis. Here the elements of arelinearly independent subsets of the vector space. The union of a chain of elements of is linearly independent, since an infinite set is linearly independent if and only if each finite subset is, and every finite subset of the union of a chain must be included in a member of the chain. So, there exist a maximal linearly independent set. This linearly independent set must span the vector space because of maximality, and is therefore a basis.
Another classical use of Zorn's lemma is the proof that every properideal—that is, an ideal that is not the whole ring—of aring is contained in amaximal ideal. Here, is the set of the proper ideals containing the given ideal. The union of chain of ideals is an ideal, since the axioms of an ideal involve a finite number of elements. The union of a chain of proper ideals is a proper ideal, since otherwise would belong to the union, and this implies that it would belong to a member of the chain.
The axiom of choice is equivalent with the fact that a well-order can be defined on every set, where a well-order is atotal order such that every nonempty subset has a least element.
Simple examples of well-ordered sets are the natural numbers (with the natural order), and, for everyn, the set of then-tuples of natural numbers, with thelexicographic order.
Well-orders allow a generalization ofmathematical induction, which is calledtransfinite induction. Given a property (predicate) depending on a natural number, mathematical induction is the fact that for proving that is always true, it suffice to prove that for every,
Transfinite induction is the same, replacing natural numbers by the elements of a well-ordered set.
Often, a proof by transfinite induction easier if three cases are proved separately, the two first cases being the same as for usual induction:
is true, where denotes the least element of the well-ordered set
where denotes thesuccessor of, that is the least element that is greater than
^Cantor, Georg; Jourdain, Philip E.B. (Translator) (1915).Contributions to the founding of the theory of transfinite numbers. New York Dover Publications (1954 English translation).By an 'aggregate' (Menge) we are to understand any collection into a whole (Zusammenfassung zu einem Ganzen)M of definite and separate objectsm of our intuition or our thought. Here: p.85
