Set (mathematics)

In mathematics, a set is a collection of different things; these things are called elements or members of the set and are typically mathematical objects of any kind: numbers, symbols, points in space, lines, other geometric shapes, variables, or even other sets. A set may be finite or infinite, depending whether the number of its elements is finite or not. There is a unique set with no elements, called the empty set; a set with a single element is a singleton.

A set of polygons in an Euler diagram

This set equals the one depicted above since both have the very same elements.

Sets are ubiquitous in modern mathematics. Indeed, set theory, more specifically Zermelo–Fraenkel set theory, has been the standard way to provide rigorous foundations for all branches of mathematics since the first half of the 20th century.

Context

Before the end of the 19th century, sets were not studied specifically, and 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, that is sets whose number of members is not a natural number. Specifically, a line was not considered as the set of its points, but as a locus where points may be located.

The mathematical study of sets began with Georg Cantor (1845–1918). This provided some counterintuitive facts 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 space. Also, Russell's paradox implies that the phrase "the set of all sets" is self-contradictory.

Together with other counterintuitive results, this led to the foundational crisis of mathematics, which was eventually resolved with the general adoption of Zermelo–Fraenkel set theory as a robust foundation of set theory and all mathematics.

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 which Cantor created for us."

Generally, the common usage of sets in mathematics does not requires the full power of Zermelo–Fraenkel set theory. In mathematical practice, sets can be manipulated independently of the logical 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.

Definitions

In mathematics, a set is a collection of different things. These things are called elements or members of the set and are typically mathematical objects of any kind such as numbers, symbols, points in space, lines, other geometrical shapes, variables, functions, or even other sets. A set may also be called a collection 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 the prime numbers or the set of all students in a given class.

If ⁠${\displaystyle x}$⁠ is an element of a set ⁠${\displaystyle S}$⁠, one says that ⁠${\displaystyle x}$⁠ belongs to ⁠${\displaystyle S}$⁠ or is in ⁠${\displaystyle S}$⁠, and this is written as ⁠${\displaystyle x\in S}$⁠. The statement "⁠${\displaystyle y}$⁠ is not in ⁠${\displaystyle S\,}$⁠" is written as ⁠${\displaystyle y\not \in S}$⁠, which can also be read as "y is not in B". For example, if ⁠${\displaystyle \mathbb {Z} }$⁠ is the set of the integers, one has ⁠${\displaystyle -3\in \mathbb {Z} }$⁠ and ⁠${\displaystyle 1.5\not \in \mathbb {Z} }$⁠. Each set is uniquely characterized by its elements. In particular, two sets that have precisely the same elements are equal (they are the same set). This property, called extensionality, can be written in formula as $${\displaystyle A=B\iff \forall x\;(x\in A\iff x\in B).}$$This implies that there is only one set with no element, the empty set (or null set) that is denoted ⁠${\displaystyle \varnothing ,\emptyset }$⁠, or ⁠${\displaystyle \{\,\}.}$⁠ A singleton is a set with exactly one element. If ⁠${\displaystyle x}$⁠ is this element, the singleton is denoted ⁠${\displaystyle \{x\}.}$⁠ If ⁠${\displaystyle x}$⁠ is itself a set, it must not be confused with ⁠${\displaystyle \{x\}.}$⁠ For example, ⁠${\displaystyle \emptyset }$⁠ is a set with no elements, while ⁠${\displaystyle \{\emptyset \}}$⁠ is a singleton with ⁠${\displaystyle \emptyset }$⁠ as its unique element.

A set is finite if there exists a natural number ⁠${\displaystyle n}$⁠ such that the ⁠${\displaystyle n}$⁠ first natural numbers can be put in one to one correspondence with the elements of the set. In this case, one says that ⁠${\displaystyle n}$⁠ is the number of elements of the set. A set is infinite if such an ⁠${\displaystyle n}$⁠ does not exist. The empty set is a finite set with ⁠${\displaystyle 0}$⁠ elements.

All standard number systems are infinite sets

The natural numbers form an infinite set, commonly denoted ⁠${\displaystyle \mathbb {N} }$⁠. Other examples of infinite sets include number sets that contain the natural numbers, real vector spaces, curves and most sorts of spaces.

Specifying a set

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 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 knows that ${\displaystyle \{4,2,1,3\}}$ and ${\displaystyle \{{\text{blue, white, red}}\}}$ denote sets and not tuples because of the enclosing braces.

Above notations ⁠${\displaystyle \{\,\}}$⁠ and ⁠${\displaystyle \{x\}}$⁠ for the empty set and for a singleton are examples of roster notation.

For a set, all that matters is whether each element is in it or not; so, the set is not changed if one changes the order or repeat some elements. So, one has, for example, $${\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 ellipses for abbreviating the notation, such as in $${\displaystyle \{1,2,3,\ldots ,1000\}}$$ for the positive integers not greater than ⁠${\displaystyle 1000}$⁠.

Ellipses allow also expanding roster notation to some infinite sets. For example, the set of all integers can be denoted as $${\displaystyle \{\ldots ,-3,-2,-1,0,1,2,3,\ldots \}}$$ or $${\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 ⁠${\displaystyle P(x)}$⁠ is a logical formula depending on a variable ⁠${\displaystyle x}$⁠, which evaluates to true or false depending on the value of ⁠${\displaystyle x}$⁠, then $${\displaystyle \{x\mid P(x)\}}$$ or $${\displaystyle \{x:P(x)\}}$$ denotes the set of all ⁠${\displaystyle x}$⁠ for which ⁠${\displaystyle P(x)}$⁠ is true. For example, a set F can be specified as follows: $${\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 is the set of all n such that n is an integer in the range from 0 to 19 inclusive".

Some logical formulas, such as ⁠${\displaystyle \color {red}{S{\text{ is a set}}}}$⁠ or ⁠${\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 ⁠${\displaystyle U}$⁠ that must contain all elements of the specified set, and write the notation as $${\displaystyle \{x\mid x\in U{\text{ and ...}}\}}$$ or $${\displaystyle \{x\in U\mid {\text{ ...}}\}.}$$

One may also define ⁠${\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 ⁠${\displaystyle U}$⁠. This amounts to say that ⁠${\displaystyle x\in U}$⁠ is implicit in set-builder notation. In this case, ⁠${\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 $${\displaystyle \{x\mid x\not \in \mathbb {Q} \}}$$ is an abbreviation of $${\displaystyle \{x\in \mathbb {R} \mid x\not \in \mathbb {Q} \},}$$ which defines the irrational numbers.

Subsets

A subset of a set ⁠${\displaystyle B}$⁠ is a set ⁠${\displaystyle A}$⁠ such that every element of ⁠${\displaystyle A}$⁠ is also an element of ⁠${\displaystyle B}$⁠. If ⁠${\displaystyle A}$⁠ is a subset of ⁠${\displaystyle B}$⁠, one says commonly that ⁠${\displaystyle A}$⁠ is contained in ⁠${\displaystyle B}$⁠, ⁠${\displaystyle B}$⁠ contains ⁠${\displaystyle A}$⁠, or ⁠${\displaystyle B}$⁠ is a superset of ⁠${\displaystyle A}$⁠. This denoted ⁠${\displaystyle A\subseteq B}$⁠ and ⁠${\displaystyle B\supseteq A}$⁠. However many authors use ⁠${\displaystyle A\subset B}$⁠ and ⁠${\displaystyle B\supset A}$⁠ instead. The definition of a subset can be expressed in notation as $${\displaystyle A\subseteq B\quad {\text{if and only if}}\quad \forall x\;(x\in A\implies x\in B).}$$

A set ⁠${\displaystyle A}$⁠ is a proper subset of a set ⁠${\displaystyle B}$⁠ if ⁠${\displaystyle A\subseteq B}$⁠ and ⁠${\displaystyle A\neq B}$⁠. This is denoted ⁠${\displaystyle A\subset B}$⁠ and ⁠${\displaystyle B\supset A}$⁠. When ⁠${\displaystyle A\subset B}$⁠ is used for the subset relation, or in case of possible ambiguity, one uses commonly ⁠${\displaystyle A\subsetneq B}$⁠ and ⁠${\displaystyle B\supsetneq A}$⁠.

The relationship between sets established by ⊆ is called inclusion or containment. 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 and B ⊆ A is equivalent to A = B. The empty set is a subset of every set: ∅ ⊆ A.

Examples:

• The set of all humans is a proper subset of the set of all mammals.
• {1, 3} ⊂ {1, 2, 3, 4}.
• {1, 2, 3, 4} ⊆ {1, 2, 3, 4}

Basic operations

There are several standard operations that produce new sets from given sets, in the same way as 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.

The main basic operations on sets are the following ones.

Intersection

The intersection of A and B, denoted A ∩ B

The intersection of two sets ⁠${\displaystyle A}$⁠ and ⁠${\displaystyle B}$⁠ is a set denoted ⁠${\displaystyle A\cap B}$⁠ whose elements are those elements that belong to both ⁠${\displaystyle A}$⁠ and ⁠${\displaystyle B}$⁠. That is, $${\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. Intersection has no general identity element. However, if one restricts intersection to the subsets of a given set ⁠${\displaystyle U}$⁠, intersection has ⁠${\displaystyle U}$⁠ as identity element.

If ⁠${\displaystyle {\mathcal {S}}}$⁠ is a nonempty set of sets, its intersection, denoted ${\textstyle \bigcap _{A\in {\mathcal {S}}}A,}$ is the set whose elements are those elements that belong to all sets in ⁠${\displaystyle {\mathcal {S}}}$⁠. That is, $${\displaystyle \bigcap _{A\in {\mathcal {S}}}A=\{x\mid (\forall A\in {\mathcal {S}})\;x\in A\}.}$$

These two definitions of the intersection coincide when ⁠${\displaystyle {\mathcal {S}}}$⁠ has two elements.

Union

The union of A and B, denoted A ∪ B

The union of two sets ⁠${\displaystyle A}$⁠ and ⁠${\displaystyle B}$⁠ is a set denoted ⁠${\displaystyle A\cup B}$⁠ whose elements are those elements that belong to ⁠${\displaystyle A}$⁠ or ⁠${\displaystyle B}$⁠ or both. That is, $${\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; 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. The empty set is an identity element for the union operation.

If ⁠${\displaystyle {\mathcal {S}}}$⁠ is a set of sets, its union, denoted ${\textstyle \bigcup _{A\in {\mathcal {S}}}A,}$ is the set whose elements are those elements that belong to at least one set in ⁠${\displaystyle {\mathcal {S}}}$⁠. That is, $${\displaystyle \bigcup _{A\in {\mathcal {S}}}A=\{x\mid (\exists A\in {\mathcal {S}})\;x\in A\}.}$$

These two definitions of the union coincide when ⁠${\displaystyle {\mathcal {S}}}$⁠ has two elements.

Set difference

The set difference A \ B

The set difference of two sets ⁠${\displaystyle A}$⁠ and ⁠${\displaystyle B}$⁠, is a set, denoted ⁠${\displaystyle A\setminus B}$⁠ or ⁠${\displaystyle A-B}$⁠, whose elements are those elements that belong to ⁠${\displaystyle A}$⁠, but not to ⁠${\displaystyle B}$⁠. That is, $${\displaystyle A\setminus B=\{x\mid x\in A\land x\not \in B\},}$$ where ⁠${\displaystyle \land }$⁠ denotes the logical and.

The complement of A in U

When ⁠${\displaystyle B\subseteq A}$⁠ the difference ⁠${\displaystyle A\setminus B}$⁠ is also called the complement of ⁠${\displaystyle B}$⁠ in ⁠${\displaystyle A}$⁠. When all sets that are considered are subsets of a fixed universal set ⁠${\displaystyle U}$⁠, the complement ⁠${\displaystyle U\setminus A}$⁠ is often called the absolute complement of ⁠${\displaystyle A}$⁠.

The symmetric difference of A and B

The symmetric difference of two sets ⁠${\displaystyle A}$⁠ and ⁠${\displaystyle B}$⁠, denoted ⁠${\displaystyle A\,\Delta \,B}$⁠, is the set of those elements that belong to A or B but not to both: $${\displaystyle A\,\Delta \,B=(A\setminus B)\cup (B\setminus A).}$$

Algebra of subsets

The set of all subsets of a set ⁠${\displaystyle U}$⁠ is called the powerset of ⁠${\displaystyle U}$⁠, often denoted ⁠${\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 ⁠${\displaystyle U}$⁠).

The powerset is a Boolean ring that has the symmetric difference as addition, the intersection as multiplication, the emptyset as additive identity, ⁠${\displaystyle U}$⁠ as multiplicative identity, and complement as 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 every Boolean algebra, the power set 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 from a set A—the domain—to a set B—the codomain—is a rule that assigns to each element of A a unique element of B. For example, the square function maps every real number x to x². Functions can be formally defined in terms of sets by means of their graph, which are subsets of the Cartesian product (see below) of the domain and the codomain.

Functions are fundamental for set theory, and examples are given in following sections.

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 ⁠${\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 ⁠${\displaystyle a_{i}}$⁠.

When the index set is ⁠${\displaystyle \{1,2\}}$⁠, an indexed family is called an ordered pair. When the index set is the set of the ⁠${\displaystyle n}$⁠ first natural numbers, an indexed family is called an ⁠${\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, ⁠${\displaystyle (b,2,b)}$⁠ denotes the 3-tuple ⁠${\displaystyle A}$⁠ such that ⁠${\displaystyle A_{1}=b,A_{2}=2,A_{3}=b}$⁠.

The above notations ${\textstyle \bigcup _{A\in {\mathcal {S}}}A}$ and ${\textstyle \bigcap _{A\in {\mathcal {S}}}A}$ are commonly replaced with a notation involving indexed families, namely $${\displaystyle \bigcup _{i\in {\mathcal {I}}}A_{i}=\{x\mid (\exists i\in {\mathcal {I}})\;x\in A_{i}\}}$$ and $${\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 ⁠${\displaystyle {\mathcal {S}}={\mathcal {I}}}$⁠ and ⁠${\displaystyle i=A=A_{i}}$⁠. The formulas remain correct, even in the case where ⁠${\displaystyle A_{i}=A_{j}}$⁠ for some ⁠${\displaystyle i\neq j}$⁠, since ⁠${\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

The Cartesian product of two sets has already be used for defining functions.

Given two sets ⁠${\displaystyle A_{1}}$⁠ and ⁠${\displaystyle A_{2}}$⁠, their Cartesian product, denoted ⁠${\displaystyle A_{1}\times A_{2}}$⁠ is the set formed by all ordered pairs ⁠${\displaystyle (a_{1},a_{2})}$⁠ such that ⁠${\displaystyle a_{1}\in A_{1}}$⁠ and ⁠${\displaystyle a_{i}\in A_{1}}$⁠; that is, $${\displaystyle A_{1}\times A_{2}=\{(a_{1},a_{2})\mid a_{1}\in A_{1}\land a_{2}\in A_{2}\}.}$$

This definition does not supposes that the two sets are different. In particular, $${\displaystyle A\times A=\{(a_{1},a_{2})\mid a_{1}\in A\land a_{2}\in A\}.}$$

Since this definition involves a pair of indices (1,2), it generalizes straightforwardly to the Cartesian product or direct product of any indexed family of sets: $${\displaystyle \prod _{i\in {\mathcal {I}}}A_{i}=\{(a_{i})_{i\in {\mathcal {I}}}\mid (\forall i\in {\mathcal {I}})\;a_{i}\in A_{i}\}.}$$ 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 the axiom of choice.

Set exponentiation

Given two sets ⁠${\displaystyle E}$⁠ and ⁠${\displaystyle F}$⁠, the set exponentiation, denoted ⁠${\displaystyle F^{E}}$⁠, is the set that has as elements all functions from ⁠${\displaystyle E}$⁠ to ⁠${\displaystyle F}$⁠.

Equivalently, ⁠${\displaystyle F^{E}}$⁠ can be viewed as the Cartesian product of a family, indexed by ⁠${\displaystyle E}$⁠, of sets that are all equal to ⁠${\displaystyle F}$⁠. This explains the terminology and the notation, since exponentiation with integer exponents is a product where all factors are equal to the base.

Power set

The power set of a set ⁠${\displaystyle E}$⁠ is the set that has all subsets of ⁠${\displaystyle E}$⁠ as elements, including the emptyset and ⁠${\displaystyle E}$⁠ itself. It is often denoted ⁠${\displaystyle {\mathcal {P}}(E)}$⁠. For example, $${\displaystyle {\mathcal {P}}(\{1,2,3\})=\{\emptyset ,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}.}$$

There is a natural one-to-one correspondence (bijection) between the subsets of ⁠${\displaystyle E}$⁠ and the functions from ⁠${\displaystyle E}$⁠ to ⁠${\displaystyle \{0,1\}}$⁠; this correspondence associates to each subset the function that takes the value ⁠${\displaystyle 1}$⁠ on the subset and ⁠${\displaystyle 0}$⁠ elsewhere. Because of this correspondence, the power set of ⁠${\displaystyle E}$⁠ is commonly identified with a set exponentiation: $${\displaystyle {\mathcal {P}}(E)=\{0,1\}^{E}.}$$ In this notation, ⁠${\displaystyle \{0,1\}}$⁠ is often abbreviated as ⁠${\displaystyle 2}$⁠, which gives $${\displaystyle {\mathcal {P}}(E)=2^{E}.}$$ In particular, if ⁠${\displaystyle E}$⁠ has ⁠${\displaystyle n}$⁠ elements, then ⁠${\displaystyle 2^{E}}$⁠ has ⁠${\displaystyle 2^{n}}$⁠ elements.

Disjoint union

The disjoint 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 ⁠${\displaystyle A}$⁠ and ⁠${\displaystyle B}$⁠ is commonly denoted ⁠${\displaystyle A\sqcup B}$⁠ and is thus defined as $${\displaystyle A\sqcup B=\{(a,i)\mid (i=1\land a\in A)\lor (i=2\land a\in B\}.}$$

If ⁠${\displaystyle A=B}$⁠ is a set with ⁠${\displaystyle n}$⁠ elements, then ⁠${\displaystyle A\cup A=A}$⁠ has ⁠${\displaystyle n}$⁠ elements, while ⁠${\displaystyle A\sqcup A}$⁠ has ⁠${\displaystyle 2n}$⁠ 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 $${\displaystyle \bigsqcup _{i\in {\mathcal {I}}}=\{(a,i)\mid i\in {\mathcal {I}}\land a\in A_{i}\}.}$$

The disjoint union is the coproduct in the category of sets. Therefore the notation $${\displaystyle \coprod _{i\in {\mathcal {I}}}=\{(a,i)\mid i\in {\mathcal {I}}\land a\in A_{i}\}}$$ is commonly used.

Internal disjoint union

Given an indexed family of sets ⁠${\displaystyle (A_{i})_{i\in {\mathcal {I}}}}$⁠, there is a natural map $${\displaystyle {\begin{aligned}\bigsqcup _{i\in {\mathcal {I}}}A_{i}&\to \bigcup _{i\in {\mathcal {I}}}A_{i}\\(a,i)&\mapsto a,\end{aligned}}}$$ which consists in "forgetting" the indices.

This maps is always surjective; it is bijective if and only if the ⁠${\displaystyle A_{i}}$⁠ are pairwise disjoint, that is, all intersections of two sets of the family are empty. In this case, ${\textstyle \bigcup _{i\in {\mathcal {I}}}A_{i}}$ and ${\textstyle \bigsqcup _{i\in {\mathcal {I}}}A_{i}}$ are commonly identified, and one says that their union is the disjoint 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 a partition of the set.

Cardinality

Informally, the cardinality of a set S, often denoted |S|, is the number of its members.

This number is the natural number ⁠${\displaystyle n}$⁠ when there is a bijection between the set that is considered and the set ⁠${\displaystyle \{1,2,\ldots ,n\}}$⁠ of the ⁠${\displaystyle n}$⁠ first natural numbers. The cardinality of the empty set is ⁠${\displaystyle 0}$⁠. In both cases, the set is said to be a finite set. Otherwise, one has an infinite set.

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 of combinatorics is devoted to the computation or estimation of the cardinality of finite sets.

Infinite cardinalities

The cardinality of an infinite set is commonly represented by a cardinal 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 ⁠${\displaystyle S}$⁠ and ⁠${\displaystyle T}$⁠ have the same cardinality if there exists a one-to-one correspondence (bijection) between them. This is denoted ${\displaystyle |S|=|T|,}$ and would be an equivalence 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, the interval ⁠${\displaystyle (-1,1)}$⁠ and the set of all real numbers have the same cardinality, a bijection being provided by the function ⁠${\displaystyle x\mapsto \tan(\pi x/2)}$⁠.

Having the same cardinality of a proper 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.

Besides equality, there is a natural inequality between cardinalities: a set ⁠${\displaystyle S}$⁠ has a cardinality smaller than or equal to the cardinality of another set ⁠${\displaystyle T}$⁠ if there is an injection frome ⁠${\displaystyle S}$⁠ to ⁠${\displaystyle T}$⁠. This is denoted ${\displaystyle |S|\leq |T|.}$

Schröder–Bernstein theorem implies that ${\displaystyle |S|\leq |T|}$ and ${\displaystyle |T|\leq |S|}$ imply ${\displaystyle |S|=|T|.}$ Also, one has ${\displaystyle |S|\leq |T|,}$ if and only if there is a surjection from ⁠${\displaystyle T}$⁠ to ⁠${\displaystyle S}$⁠. For every two sets ⁠${\displaystyle S}$⁠ and ⁠${\displaystyle T}$⁠, one has either ${\displaystyle |S|\leq |T|}$ or ${\displaystyle |T|\leq |S|.}$ So, inequality of cardinalities is a total order.

The cardinality of the set ⁠${\displaystyle \mathbb {N} }$⁠ of the natural numbers, denoted ${\displaystyle |\mathbb {N} |=\aleph _{0},}$ is the smallest infinite cardinality. This means that if ⁠${\displaystyle S}$⁠ is a set of natural numbers, then either ⁠${\displaystyle S}$⁠ is finite or ${\displaystyle |S|=|\mathbb {N} |.}$

Sets with cardinality less than or equal to ${\displaystyle |\mathbb {N} |=\aleph _{0}}$ are called countable sets; these are either finite sets or countably infinite sets (sets of cardinality ${\displaystyle \aleph _{0}}$); some authors use "countable" to mean "countably infinite". Sets with cardinality strictly greater than ${\displaystyle \aleph _{0}}$ are called uncountable sets.

Cantor's diagonal argument shows that, for every set ⁠${\displaystyle S}$⁠, its power set (the set of its subsets) ⁠${\displaystyle 2^{S}}$⁠ has a greater cardinality: $${\displaystyle |S|<\left|2^{S}\right|.}$$ This implies that there is no greatest cardinality.

Cardinality of the real numbers

The cardinality of set of the real numbers is called the cardinality of the continuum and denoted ⁠${\displaystyle {\mathfrak {c}}}$⁠. (The term "continuum" referred to the real 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 ⁠${\displaystyle \mathbb {R} }$⁠ has the same cardinality of an open interval, every subset of ⁠${\displaystyle \mathbb {R} }$⁠ that contains a nonempty open interval has also the cardinality ⁠${\displaystyle {\mathfrak {c}}}$⁠.

One has $${\displaystyle {\mathfrak {c}}=2^{\aleph _{0}},}$$ meaning that the cardinality of the real numbers equals the cardinality of the power set of the natural numbers. In particular, $${\displaystyle {\mathfrak {c}}>\aleph _{0}.}$$

When published in 1878 by Georg Cantor, this result was so astonishing that it was refused by mathematicians, and several tens years were needed before its common acceptance.

It can be shown that ⁠${\displaystyle {\mathfrak {c}}}$⁠ is also the cardinality of the entire plane, and of any finite-dimensional Euclidean space.

The continuum hypothesis, was a conjecture formulated by Georg Cantor in 1878 that there is no set with cardinality strictly between ⁠${\displaystyle \aleph _{0}}$⁠ and ⁠${\displaystyle {\mathfrak {c}}}$⁠. In 1963, Paul Cohen proved that the continuum hypothesis is independent of the axioms of Zermelo–Fraenkel set theory with the axiom of choice. This means that if the most widely used set theory is consistent (that is not self-contradictory), 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.

History

The concept of a set emerged in mathematics at the end of the 19th century. The German word for set, Menge, was coined by Bernard Bolzano in his work Paradoxes of the Infinite.

Passage with a translation of the original set definition of Georg Cantor. The German word Menge for set is translated with aggregate here.

Georg Cantor, one of the founders of set theory, gave the following definition at the beginning of his Beiträge zur Begründung der transfiniten Mengenlehre:

A set is a gathering together into a whole of definite, distinct objects of our perception or our thought—which are called elements of the set.

Bertrand Russell introduced the distinction between a set and a class (a set is a class, but some classes, such as the class of all sets, are not sets; see Russell's paradox):

When mathematicians deal with what they call a manifold, aggregate, Menge, ensemble, or some equivalent name, it is common, especially where the number of terms involved is finite, to regard the object in question (which is in fact a class) as defined by the enumeration of its terms, and as consisting possibly of a single term, which in that case is the class.

Naive set theory

The foremost property of a set is that it can have elements, also called members. Two sets are equal when they have the same elements. More precisely, sets A and B are equal if every element of A is an element of B, and every element of B is an element of A; this property is called the extensionality of sets. As a consequence, e.g. {2, 4, 6} and {4, 6, 4, 2} represent the same set. Unlike sets, multisets can be distinguished by the number of occurrences of an element; e.g. [2, 4, 6] and [4, 6, 4, 2] represent different multisets, while [2, 4, 6] and [6, 4, 2] are equal. Tuples can even be distinguished by element order; e.g. (2, 4, 6) and (6, 4, 2) represent different tuples.

The simple concept of a set has proved enormously useful in mathematics, but paradoxes arise if no restrictions are placed on how sets can be constructed:

• Russell's paradox shows that the "set of all sets that do not contain themselves", i.e., {x | x is a set and x ∉ x}, cannot exist.
• Cantor's paradox shows that "the set of all sets" cannot exist.

Naïve set theory defines a set as any well-defined collection of distinct elements, but problems arise from the vagueness of the term well-defined.

Axiomatic set theory

In subsequent efforts to resolve these paradoxes since the time of the original formulation of naïve set theory, the properties of sets have been defined by axioms. Axiomatic set theory takes the concept of a set as a primitive notion. The purpose of the axioms is to provide a basic framework from which to deduce the truth or falsity of particular mathematical propositions (statements) about sets, using first-order logic. According to Gödel's incompleteness theorems however, it is not possible to use first-order logic to prove any such particular axiomatic set theory is free from paradox.

See also

• Algebra of sets
• Alternative set theory
• Category of sets
• Class (set theory)
• Family of sets
• Fuzzy set
• Mereology
• Principia Mathematica

Notes

1. Some typographical variants are occasionally used, such as ϕ, or ϕ.
2. The term unit set is also occasionally used.
3. This property is equivalent to the axiom of choice.
4. The consistency of set theory cannot proved from within itself.

References

1. 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 objects m of our intuition or our thought. Here: p.85
2. P. K. Jain; Khalil Ahmad; Om P. Ahuja (1995). Functional Analysis. New Age International. p. 1. ISBN 978-81-224-0801-0.
3. Samuel Goldberg (1 January 1986). Probability: An Introduction. Courier Corporation. p. 2. ISBN 978-0-486-65252-8.
4. Thomas H. Cormen; Charles E Leiserson; Ronald L Rivest; Clifford Stein (2001). Introduction To Algorithms. MIT Press. p. 1070. ISBN 978-0-262-03293-3.
5. Halmos 1960, p. 1.
6. Hilbert, David (1926), "Über das Unendliche", Mathematische Annalen, vol. 95, pp. 161–190, doi:10.1007/BF01206605, JFM 51.0044.02, S2CID 121888793

   "Aus dem Paradies, das Cantor uns geschaffen, soll uns niemand vertreiben können."

   Translated in Van Heijenoort, Jean, On the infinite, Harvard University Press

7. Maddocks, J. R. (2004). Lerner, K. Lee; Lerner, Brenda Wilmoth (eds.). The Gale Encyclopedia of Science. Gale. pp. 3587–3589. ISBN 0-7876-7559-8.
8. Devlin, Keith J. (1981). "Sets and functions". Sets, Functions and Logic: Basic concepts of university mathematics. Springer. ISBN 978-0-412-22660-1.
9. "Set - Encyclopedia of Mathematics". encyclopediaofmath.org. Retrieved 2025-02-06.
10. Publishers, HarperCollins. "The American Heritage Dictionary entry: set". www.ahdictionary.com. Retrieved 2025-02-06.
11. Halmos 1960, p. 2.
12. Marek Capinski; Peter E. Kopp (2004). Measure, Integral and Probability. Springer Science & Business Media. p. 2. ISBN 978-1-85233-781-0.
13. "Set Symbols". www.mathsisfun.com. Retrieved 2020-08-19.
14. Stoll, Robert (1974). Sets, Logic and Axiomatic Theories. W. H. Freeman and Company. pp. 5. ISBN 9780716704577.
15. Aggarwal, M.L. (2021). "1. Sets". Understanding ISC Mathematics Class XI. Vol. 1. Arya Publications (Avichal Publishing Company). p. A=3.
16. Sourendra Nath, De (January 2015). "Unit-1 Sets and Functions: 1. Set Theory". Chhaya Ganit (Ekadash Shreni). Scholar Books Pvt. Ltd. p. 5.
17. Halmos 1960, p. 8.
18. K.T. Leung; Doris Lai-chue Chen (1 July 1992). Elementary Set Theory, Part I/II. Hong Kong University Press. p. 27. ISBN 978-962-209-026-2.
19. A. Kanamori, "The Empty Set, the Singleton, and the Ordered Pair", p.278. Bulletin of Symbolic Logic vol. 9, no. 3, (2003). Accessed 21 August 2023.
20. Charles Roberts (24 June 2009). Introduction to Mathematical Proofs: A Transition. CRC Press. p. 45. ISBN 978-1-4200-6956-3.
21. David Johnson; David B. Johnson; Thomas A. Mowry (June 2004). Finite Mathematics: Practical Applications (Docutech Version). W. H. Freeman. p. 220. ISBN 978-0-7167-6297-3.
22. Ignacio Bello; Anton Kaul; Jack R. Britton (29 January 2013). Topics in Contemporary Mathematics. Cengage Learning. p. 47. ISBN 978-1-133-10742-2.
23. Susanna S. Epp (4 August 2010). Discrete Mathematics with Applications. Cengage Learning. p. 13. ISBN 978-0-495-39132-6.
24. Stephen B. Maurer; Anthony Ralston (21 January 2005). Discrete Algorithmic Mathematics. CRC Press. p. 11. ISBN 978-1-4398-6375-6.
25. "Introduction to Sets". www.mathsisfun.com. Retrieved 2020-08-19.
26. D. Van Dalen; H. C. Doets; H. De Swart (9 May 2014). Sets: Naïve, Axiomatic and Applied: A Basic Compendium with Exercises for Use in Set Theory for Non Logicians, Working and Teaching Mathematicians and Students. Elsevier Science. p. 1. ISBN 978-1-4831-5039-0.
27. Alfred Basta; Stephan DeLong; Nadine Basta (1 January 2013). Mathematics for Information Technology. Cengage Learning. p. 3. ISBN 978-1-285-60843-3.
28. Laura Bracken; Ed Miller (15 February 2013). Elementary Algebra. Cengage Learning. p. 36. ISBN 978-0-618-95134-5.
29. Frank Ruda (6 October 2011). Hegel's Rabble: An Investigation into Hegel's Philosophy of Right. Bloomsbury Publishing. p. 151. ISBN 978-1-4411-7413-0.
30. John F. Lucas (1990). Introduction to Abstract Mathematics. Rowman & Littlefield. p. 108. ISBN 978-0-912675-73-2.
31. Weisstein, Eric W. "Set". Wolfram MathWorld. Retrieved 2020-08-19.
32. Ralph C. Steinlage (1987). College Algebra. West Publishing Company. ISBN 978-0-314-29531-6.
33. Felix Hausdorff (2005). Set Theory. American Mathematical Soc. p. 30. ISBN 978-0-8218-3835-8.
34. Halmos 1960, p. 3.
35. Tanton, James (2005). "Set theory". Encyclopedia of Mathematics. New York: Facts On File. pp. 460–61. ISBN 0-8160-5124-0.
36. Halmos 1960, p. 19.
37. Halmos 1960, p. 20.
38. Yiannis N. Moschovakis (1994). Notes on Set Theory. Springer Science & Business Media. ISBN 978-3-540-94180-4.
39. Karl J. Smith (7 January 2008). Mathematics: Its Power and Utility. Cengage Learning. p. 401. ISBN 978-0-495-38913-2.
40. John Stillwell (16 October 2013). The Real Numbers: An Introduction to Set Theory and Analysis. Springer Science & Business Media. ISBN 978-3-319-01577-4.
41. Cantor, Georg (1878). "Ein Beitrag zur Mannigfaltigkeitslehre". Journal für die Reine und Angewandte Mathematik. 1878 (84): 242–258. doi:10.1515/crll.1878.84.242 (inactive 1 November 2024).{{cite journal}}: CS1 maint: DOI inactive as of November 2024 (link)
42. David Tall (11 April 2006). Advanced Mathematical Thinking. Springer Science & Business Media. p. 211. ISBN 978-0-306-47203-9.
43. Cohen, Paul J. (December 15, 1963). "The Independence of the Continuum Hypothesis". Proceedings of the National Academy of Sciences of the United States of America. 50 (6): 1143–1148. Bibcode:1963PNAS...50.1143C. doi:10.1073/pnas.50.6.1143. JSTOR 71858. PMC 221287. PMID 16578557.
44. José Ferreirós (16 August 2007). Labyrinth of Thought: A History of Set Theory and Its Role in Modern Mathematics. Birkhäuser Basel. ISBN 978-3-7643-8349-7.
45. Steve Russ (9 December 2004). The Mathematical Works of Bernard Bolzano. OUP Oxford. ISBN 978-0-19-151370-1.
46. William Ewald; William Bragg Ewald (1996). From Kant to Hilbert Volume 1: A Source Book in the Foundations of Mathematics. OUP Oxford. p. 249. ISBN 978-0-19-850535-8.
47. Paul Rusnock; Jan Sebestík (25 April 2019). Bernard Bolzano: His Life and Work. OUP Oxford. p. 430. ISBN 978-0-19-255683-7.
48. Georg Cantor (Nov 1895). "Beiträge zur Begründung der transfiniten Mengenlehre (1)". Mathematische Annalen (in German). 46 (4): 481–512.
49. Bertrand Russell (1903) The Principles of Mathematics, chapter VI: Classes
50. Jose Ferreiros (1 November 2001). Labyrinth of Thought: A History of Set Theory and Its Role in Modern Mathematics. Springer Science & Business Media. ISBN 978-3-7643-5749-8.
51. Raatikainen, Panu (2022). Zalta, Edward N. (ed.). "Gödel's Incompleteness Theorems". Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University. Retrieved 2024-06-03.

References

• Dauben, Joseph W. (1979). Georg Cantor: His Mathematics and Philosophy of the Infinite. Boston: Harvard University Press. ISBN 0-691-02447-2.
• Halmos, Paul R. (1960). Naive Set Theory. Princeton, N.J.: Van Nostrand. ISBN 0-387-90092-6.
• Stoll, Robert R. (1979). Set Theory and Logic. Mineola, N.Y.: Dover Publications. ISBN 0-486-63829-4.
• Velleman, Daniel (2006). How To Prove It: A Structured Approach. Cambridge University Press. ISBN 0-521-67599-5.

External links

• The dictionary definition of set at Wiktionary
• Cantor's "Beiträge zur Begründung der transfiniten Mengenlehre" (in German)