In mathematics, a set is a collection of different things; the things are called elements or members of the set and are typically mathematical objects: numbers, symbols, points in space, lines, other geometric shapes, variables, functions, or even other sets. Mathematics typically does not define precisely what constitutes a "set" or "collection", because such a definition would have to be in terms of something else previously defined. Instead, sets serve as foundational objects whose behavior is described by axioms modeled on intuition about collections, and then essentially all other mathematical objects are rigorously defined in terms of sets. Set theory studies possible axiom systems and their consequences. Since the first half of the 20th century, ZFC (Zermelo–Fraenkel set theory with the axiom of choice) has been the axiom system most commonly used.
Context Before the end of the 19th century, sets were not studied specifically, and they were not clearly distinguished from sequences. Most mathematicians considered infinity as potential—meaning that it is the result of an endless process—and were reluctant to consider infinite sets. For example, a line was considered not as a set of points, but as a locus where a point may be located. The mathematical study of infinite sets began with Georg Cantor (1845–1918). This provided some counterintuitive statements and paradoxes. For example, the number line has an infinite number of elements that is strictly larger than the infinite number of natural numbers, and any line segment has the same number of elements as the whole line. Assuming the existence of a set of all sets led to a contradiction, Russell's paradox. This led to the foundational crisis of mathematics, and to proposed resolutions. One of these, Zermelo–Fraenkel set theory, has been generally adopted as a foundation of set theory and all mathematics, though much of mathematics does not require its full power. Meanwhile, sets started to be widely used in all mathematics. In particular, algebraic structures and mathematical spaces are typically defined in terms of sets. Also, many older mathematical results are restated in terms of sets. For example, Euclid's theorem is often stated as "the set of the prime numbers is infinite". This wide use of sets in mathematics was prophesied by David Hilbert when saying: "No one will drive us from the paradise that Cantor created for us." The object of this article is to summarize the manipulation rules and properties of sets that are commonly used in mathematics, without reference to a specific logical framework. For the branch of mathematics that studies sets, see Set theory; for an informal presentation of the corresponding logical framework, see Naive set theory; for a more formal presentation, see Axiomatic set theory and Zermelo–Fraenkel set theory.
Basic notions In mathematics, a set is a collection of different things, called elements or members of the set. A set may also be called a collection or family, especially when its elements are themselves sets; this may avoid confusion between the set and its members. A set may be specified either by listing its elements or by giving a property that characterizes its elements, such as for the set of the prime numbers or the set of all students in a given class. If x {\displaystyle x} is an element of a set S {\displaystyle S} , one says that x {\displaystyle x} belongs to S {\displaystyle S} or is in S {\displaystyle S} , and one writes x ∈ S {\displaystyle x\in S} . The statement " y {\displaystyle y} is not in S {\displaystyle S\,} " is written as y ∉ S {\displaystyle y\not \in S} . For example, if Z {\displaystyle \mathbb {Z} } is the set of all integers, then − 3 ∈ Z {\displaystyle -3\in \mathbb {Z} } and 1.5 ∉ Z {\displaystyle 1.5\not \in \mathbb {Z} } . The axiom of extensionality states that two sets are equal if and only if they have the same elements. There exists a set with no elements, and extensionality implies that there is only one such set. It is called the empty set (or null set) and is denoted ∅ {\displaystyle \varnothing } , ∅ {\displaystyle \emptyset } , or { } {\displaystyle \{\,\}} . A singleton is a set with exactly one element. If x {\displaystyle x} is this element, the singleton is denoted { x } {\displaystyle \{x\}} . The sets { ∅ } {\displaystyle \{\emptyset \}} and ∅ {\displaystyle \emptyset } are different, because the former has one element (namely, ∅ {\displaystyle \emptyset } ) and the latter has no elements at all. A set is finite if there exists a natural number n {\displaystyle n} such that the first n {\displaystyle n} natural numbers can be put in bijection (one-to-one correspondence) with the elements of the set. In this case, one says that n {\displaystyle n} is the number of elements of the set. A set is infinite if such an n {\displaystyle n} does not exist. The empty set is a finite set with 0 {\displaystyle 0} elements.
The natural numbers form an infinite set, commonly denoted N {\displaystyle \mathbb {N} } . Other examples of infinite sets include the integers ( Z {\displaystyle \mathbb {Z} } ), the rational numbers ( Q {\displaystyle \mathbb {Q} } ), the real numbers ( R {\displaystyle \mathbb {R} } ), nonzero real vector spaces, curves, and most other mathematical spaces.
Specifying a set Extensionality implies that to specify a set, it suffices either to list its elements or to provide a property that characterize the set's elements among the elements of a possibly larger set.
Roster notation Roster or enumeration notation is a notation introduced by Ernst Zermelo in 1908 that specifies a set by listing its elements between braces, separated by commas. For example, one sees that { 4 , 2 , 1 , 3 } {\displaystyle \{4,2,1,3\}} and { blue, white, red } {\displaystyle \{{\text{blue, white, red}}\}} denote sets and not tuples because of the enclosing braces. The notations { } {\displaystyle \{\,\}} for the empty set and { x } {\displaystyle \{x\}} for a singleton are examples of roster notation. When specifying a set, all that matters is whether each potential element is in the set or not, so a set does not change if elements are repeated or arranged in a different order. For example,
{ 1 , 2 , 3 , 4 } = { 4 , 2 , 1 , 3 } = { 4 , 2 , 4 , 3 , 1 , 3 } . {\displaystyle \{1,2,3,4\}=\{4,2,1,3\}=\{4,2,4,3,1,3\}.}
When there is a clear pattern for generating all set elements, one can use an ellipsis to abbreviate the notation; for example, { 1 , 2 , 3 , … , 10 } {\displaystyle \{1,2,3,\ldots ,10\}} is a shorthand for { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 } {\displaystyle \{1,2,3,4,5,6,7,8,9,10\}} . Ellipses in roster notation can also be used to describe some infinite sets; for example, the set of all integers can be denoted as
{ … , − 3 , − 2 , − 1 , 0 , 1 , 2 , 3 , … } {\displaystyle \{\ldots ,-3,-2,-1,0,1,2,3,\ldots \}}
or
{ 0 , 1 , − 1 , 2 , − 2 , 3 , − 3 , … } . {\displaystyle \{0,1,-1,2,-2,3,-3,\ldots \}.}
Set-builder notation
Set-builder notation specifies a set as being the set of all elements that satisfy some logical formula. More precisely, if P ( x ) {\displaystyle P(x)} is a logical formula depending on a variable x {\displaystyle x} , which evaluates to true or false depending on the value of x {\displaystyle x} , then
{ x ∣ P ( x ) } {\displaystyle \{x\mid P(x)\}}
or
{ x : P ( x ) } {\displaystyle \{x:P(x)\}}
denotes the set of all x {\displaystyle x} for which P ( x ) {\displaystyle P(x)} is true. For example, a set F {\displaystyle F} can be specified as follows:
F = { n ∣ n is an integer, and 0 ≤ n ≤ 19 } . {\displaystyle F=\{n\mid n{\text{ is an integer, and }}0\leq n\leq 19\}.}
In this notation, the vertical bar "|" is read as "such that", and the whole formula can be read as " F {\displaystyle F} is the set of all n {\displaystyle n} such that n {\displaystyle n} is an integer in the range from 0 to 19 inclusive". Some logical formulas, such as S is a set {\displaystyle \color {red}{S{\text{ is a set}}}} or S is a set and S ∉ S {\displaystyle \color {red}{S{\text{ is a set and }}S\not \in S}} 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 U {\displaystyle U} that must contain all elements of the specified set, and write the notation as
{ x ∣ x ∈ U and ... } {\displaystyle \{x\mid x\in U{\text{ and ...}}\}}
or
{ x ∈ U ∣ ... } . {\displaystyle \{x\in U\mid {\text{ ...}}\}.}
One may also define U {\displaystyle U} 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 U {\displaystyle U} . This amounts to saying that x ∈ U {\displaystyle x\in U} is implicit in set-builder notation. In this case, U {\displaystyle U} is often called the domain of discourse or a universe. For example, with the convention that a lower case Latin letter may represent a real number and nothing else, the expression
{ x ∣ x ∉ Q } {\displaystyle \{x\mid x\not \in \mathbb {Q} \}}
is an abbreviation of
{ x ∈ R ∣ x ∉ Q } , {\displaystyle \{x\in \mathbb {R} \mid x\not \in \mathbb {Q} \},}
which defines the irrational numbers.
Subsets
A subset of a set B {\displaystyle B} is a set A {\displaystyle A} such that every element of A {\displaystyle A} is also an element of B {\displaystyle B} . The following are different ways of expressing the same thing:
A {\displaystyle A} is a subset of B {\displaystyle B} , ∀ x ( x ∈ A ⟹ x ∈ B ) {\displaystyle \forall x\;(x\in A\implies x\in B)} , A {\displaystyle A} is contained in B {\displaystyle B} , A ⊆ B {\displaystyle A\subseteq B} , B {\displaystyle B} is a superset of A {\displaystyle A} , B {\displaystyle B} contains A {\displaystyle A} , B ⊇ A {\displaystyle B\supseteq A} . The relationship between sets established by ⊆ is called inclusion or containment. A set A {\displaystyle A} is a proper subset of a set B {\displaystyle B} if A ⊆ B {\displaystyle A\subseteq B} and A ≠ B {\displaystyle A\neq B} ; to denote this, one writes A ⊊ B {\displaystyle A\subsetneq B} , or A ⫋ B {\displaystyle A\subsetneqq B} . Likewise, one may write B ⊋ A {\displaystyle B\supsetneq A} or B ⫌ A {\displaystyle B\supsetneqq A} . The notation A ⊂ B {\displaystyle A\subset B} often means A ⊆ B {\displaystyle A\subseteq B} , but some authors use A ⊂ B {\displaystyle A\subset B} to mean A ⊊ B {\displaystyle A\subsetneq B} . To avoid ambiguity, one can write A ⊆ B {\displaystyle A\subseteq B} or A ⊊ B {\displaystyle A\subsetneq B} , depending on what is intended.
Examples The set of all humans is a proper subset of the set of all mammals. { 1 , 3 } ⊂ { 1 , 2 , 3 , 4 } {\displaystyle \{1,3\}\subset \{1,2,3,4\}} { 1 , 2 , 3 , 4 } ⊆ { 1 , 2 , 3 , 4 } {\displaystyle \{1,2,3,4\}\subseteq \{1,2,3,4\}}
Properties of containment Two sets are equal if and only if they contain each other: A = B {\displaystyle A=B} is equivalent to ( A ⊆ B {\displaystyle A\subseteq B} and B ⊆ A {\displaystyle B\subseteq A} ). The empty set is a subset of every set: ∀ A , ∅ ⊆ A {\displaystyle \forall A,\varnothing \subseteq A} .
Basic operations There are several standard operations that produce new sets from given sets, analogously to how addition and multiplication 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 with Euler diagrams and Venn diagrams.
Intersection
The intersection of two sets A {\displaystyle A} and B {\displaystyle B} is a set denoted A ∩ B {\displaystyle A\cap B} whose elements are those elements that belong to both A {\displaystyle A} and B {\displaystyle B} . That is,
A ∩ B = { x ∣ x ∈ A ∧ x ∈ B } , {\displaystyle A\cap B=\{x\mid x\in A\land x\in B\},}
where ∧ {\displaystyle \land } denotes the logical and. Intersection is associative and commutative; this means that for proceeding a sequence of intersections, one may proceed in any order, without the need of parentheses for specifying the order of operations. If S {\displaystyle {\mathcal {S}}} is a nonempty set of sets, its intersection, denoted
⋂ A ∈ S A , {\textstyle \bigcap _{A\in {\mathcal {S}}}A,} is the set whose elements are those elements that belong to all sets in S {\displaystyle {\mathcal {S}}} . That is,
⋂ A ∈ S A = { x ∣ ( ∀ A ∈ S ) x ∈ A } . {\displaystyle \bigcap _{A\in {\mathcal {S}}}A=\{x\mid (\forall A\in {\mathcal {S}})\;x\in A\}.}
Example: If S = { X , Y } {\displaystyle {\mathcal {S}}=\{X,Y\}} , then ⋂ A ∈ S A = X ∩ Y {\textstyle \bigcap _{A\in {\mathcal {S}}}A=X\cap Y} .
Union
The union of two sets A {\displaystyle A} and B {\displaystyle B} is a set denoted A ∪ B {\displaystyle A\cup B} whose elements are those elements that belong to A {\displaystyle A} or B {\displaystyle B} or both. That is,
A ∪ B = { x ∣ x ∈ A ∨ x ∈ B } , {\displaystyle A\cup B=\{x\mid x\in A\lor x\in B\},}
where ∨ {\displaystyle \lor } denotes the logical or. Union is associative and commutative. If S {\displaystyle {\mathcal {S}}} is a set of sets, its union, denoted
⋃ S = ⋃ A ∈ S A , {\textstyle \bigcup S=\bigcup _{A\in {\mathcal {S}}}A,} is the set whose elements are those elements that belong to at least one set in S {\displaystyle {\mathcal {S}}} . That is,
⋃ A ∈ S A = { x ∣ ( ∃ A ∈ S ) x ∈ A } . {\displaystyle \bigcup _{A\in {\mathcal {S}}}A=\{x\mid (\exists A\in {\mathcal {S}})\;x\in A\}.}
Example: If S = { X , Y } {\displaystyle {\mathcal {S}}=\{X,Y\}} , then ⋃ A ∈ S A = X ∪ Y {\textstyle \bigcup _{A\in {\mathcal {S}}}A=X\cup Y} .
Set difference
The set difference of two sets A {\displaystyle A} and B {\displaystyle B} , is a set, denoted A ∖ B {\displaystyle A\setminus B} or A − B {\displaystyle A-B} , whose elements are those elements that belong to A {\displaystyle A} , but not to B {\displaystyle B} . That is,
A ∖ B = { x ∣ x ∈ A ∧ x ∉ B } , {\displaystyle A\setminus B=\{x\mid x\in A\land x\not \in B\},}
where ∧ {\displaystyle \land } denotes the logical and.
When B ⊆ A {\displaystyle B\subseteq A} the difference A ∖ B {\displaystyle A\setminus B} is also called the complement of B {\displaystyle B} in A {\displaystyle A} . When all sets that are considered are subsets of a fixed universal set U {\displaystyle U} , the complement U ∖ A {\displaystyle U\setminus A} is often called the absolute complement of A {\displaystyle A} .
The symmetric difference of two sets A {\displaystyle A} and B {\displaystyle B} , denoted A Δ B {\displaystyle A\,\Delta \,B} , is the set of those elements that belong to A {\displaystyle A} or B {\displaystyle B} but not to both:
A Δ B = ( A ∖ B ) ∪ ( B ∖ A ) . {\displaystyle A\,\Delta \,B=(A\setminus B)\cup (B\setminus A).}
Algebra of subsets
The set of all subsets of a set U {\displaystyle U} is called the powerset of U {\displaystyle U} , often denoted P ( U ) {\displaystyle {\mathcal {P}}(U)} . The powerset is an algebraic structure whose main operations are union, intersection, set difference, symmetric difference and absolute complement (complement in U {\displaystyle U} ). The powerset is a Boolean ring that has symmetric difference as addition, intersection as multiplication, the empty set as additive identity, U {\displaystyle U} as multiplicative identity, and the subset itself as the additive inverse. The powerset is also a Boolean algebra for which the join ∨ {\displaystyle \lor } is the union ∪ {\displaystyle \cup } , the meet ∧ {\displaystyle \land } is the intersection ∩ {\displaystyle \cap } , and the negation is the set complement. As for every Boolean algebra, the powerset is also a partially ordered set for set inclusion. It is also a complete lattice. The axioms of these structures induce many identities relating subsets, which are detailed in the linked articles.
Functions
A function f {\displaystyle f} from a set A {\displaystyle A} to a set B {\displaystyle B} is a rule that assigns to each element of A {\displaystyle A} a unique element of B {\displaystyle B} . For example, the square function maps each real number x {\displaystyle x} to x 2 {\displaystyle x^{2}} . The notation f : A → B {\displaystyle f:A\to B} denotes a function f {\displaystyle f} from A {\displaystyle A} to B {\displaystyle B} . The result of applying f {\displaystyle f} to an element a {\displaystyle a} of A {\displaystyle A} is denoted f ( a ) {\displaystyle f(a)} ; it is called the value of f {\displaystyle f} at a {\displaystyle a} , or the image of a {\displaystyle a} under f {\displaystyle f} . The set A {\displaystyle A} is called the domain of f {\displaystyle f} , and B {\displaystyle B} is called the codomain of f {\displaystyle f} . The graph of a function f : A → B {\displaystyle f:A\to B} is the set of all ordered pairs ( a , f ( a ) ) {\displaystyle (a,f(a))} as a {\displaystyle a} ranges over all elements of A {\displaystyle A} . It is a subset of the Cartesian product A × B {\displaystyle A\times B} defined below. For example, the graph of the square function is a parabola in R × R = R 2 {\displaystyle \mathbb {R} \times \mathbb {R} =\mathbb {R} ^{2}} ; it contains points such as ( 3 , 9 ) {\displaystyle (3,9)} and ( − 4 , 16 ) {\displaystyle (-4,16)} . Once the domain and codomain are specified, the graph of f {\displaystyle f} contains the same information as f {\displaystyle f} itself. This point of view allows one to formally define 'function' in terms of sets. Specifically, a function from A {\displaystyle A} to B {\displaystyle B} is a triple ( A , B , G ) {\displaystyle (A,B,G)} of sets with G ⊂ A × B {\displaystyle G\subset A\times B} such that for every element a {\displaystyle a} in A {\displaystyle A} , there exists a unique element b {\displaystyle b} in B {\displaystyle B} such that ( a , b ) ∈ G {\displaystyle (a,b)\in G} . (For functions from R {\displaystyle \mathbb {R} } to R {\displaystyle \mathbb {R} } especially, the condition on G {\displaystyle G} is called the vertical line test.)
Indexed families Intuitively, an indexed 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 usual functional notation f ( x ) {\displaystyle f(x)} 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 a i {\displaystyle a_{i}} . When the index set is { 1 , 2 } {\displaystyle \{1,2\}} , an indexed family is called an ordered pair. When the index set is the set of the n {\displaystyle n} first natural numbers, an indexed family is called an n {\displaystyle n} -tuple. When the index set is the set of all natural numbers an indexed family is called a sequence. In all these cases, the natural order of the natural numbers allows omitting indices for explicit indexed families. For example, ( b , 2 , b ) {\displaystyle (b,2,b)} denotes the 3-tuple A {\displaystyle A} such that A 1 = b , A 2 = 2 , A 3 = b {\displaystyle A_{1}=b,A_{2}=2,A_{3}=b} . The above notations ⋃ A ∈ S A {\displaystyle \textstyle \bigcup _{A\in {\mathcal {S}}}A} and ⋂ A ∈ S A {\displaystyle \textstyle \bigcap _{A\in {\mathcal {S}}}A} are commonly replaced with a notation involving indexed families, namely
⋃ i ∈ I A i = { x ∣ ( ∃ i ∈ I ) x ∈ A i } {\displaystyle \bigcup _{i\in {\mathcal {I}}}A_{i}=\{x\mid (\exists i\in {\mathcal {I}})\;x\in A_{i}\}} and
⋂ i ∈ I A i = { x ∣ ( ∀ i ∈ I ) x ∈ A i } . {\displaystyle \bigcap _{i\in {\mathcal {I}}}A_{i}=\{x\mid (\forall i\in {\mathcal {I}})\;x\in A_{i}\}.}
The formulas of the above sections are special cases of the formulas for indexed families, where S = I {\displaystyle {\mathcal {S}}={\mathcal {I}}} and i = A = A i {\displaystyle i=A=A_{i}} . The formulas remain correct, even in the case where A i = A j {\displaystyle A_{i}=A_{j}} for some i ≠ j {\displaystyle i\neq j} , since A = A ∪ A = A ∩ A {\displaystyle A=A\cup A=A\cap A} .
External operations 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 are Cartesian product, disjoint union, set exponentiation and power set.
Cartesian product
Given sets A {\displaystyle A} and B {\displaystyle B} , their Cartesian product (or simply product), denoted A × B {\displaystyle A\times B} , is the set of all ordered pairs ( a , b ) {\displaystyle (a,b)} such that a ∈ A {\displaystyle a\in A} and b ∈ B {\displaystyle b\in B} ; that is,
A × B = { ( a , b ) ∣ a ∈ A and b ∈ B } . {\displaystyle A\times B=\{(a,b)\mid a\in A{\text{ and }}b\in B\}.}
The definition makes sense even if A = B {\displaystyle A=B} . One can likewise define A × B × C {\displaystyle A\times B\times C} as a set of ordered triples ( a , b , c ) {\displaystyle (a,b,c)} , and likewise for any finite number of sets. In fact, the number of sets does not have to be finite. Given any indexed family of sets ( A i ) i ∈ I {\displaystyle (A_{i})_{i\in I}} , the product