Set (mathematics)

File:Example of a set.svg

A set of polygons in an Euler diagram

File:Example of a set rearranged.svg

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

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 geometrical shapes, variables, or even other sets.Template:Sfn 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.

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.Template:Sfn

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 potentialTemplate:Mdashmeaning that it is the result of an endless processTemplate:Mdashand were reluctant to consider infinite sets, that is sets whose number of members is not a natural number. In particular, 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.Template:Sfn 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 Template:Tmath is an element of a set Template:Tmath, one says that Template:Tmath belongs to Template:Tmath or is in Template:Tmath, and this is written as Template:Tmath.Template:Sfn The statement "Template:Tmath is not in Template:Tmath" is written as Template:Tmath, which can also be read as "y is not in B". For example, if Template:Tmath is the set of the integers, one has Template:Tmath and Template:Tmath. 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 $$A=B⟺\mathrm{\forall }x(x\in A⟺x\in B).$$This implies that there is only one set with no element, the empty set (or null set) that is denoted Template:Tmath,Template:Efn or Template:TmathTemplate:Sfn A singleton is a set with exactly one element.Template:Efn If Template:Tmath is this element, the singleton is denoted Template:Tmath If Template:Tmath is itself a set, it must not be confused with Template:Tmath For example, Template:Tmath is a set with no elements, while Template:Tmath is a singleton with Template:Tmath as its unique element.

A set is finite if there exists a natural number Template:Tmath such that the Template:Tmath first natural numbers can be put in one to one correspondence with the elements of the set. In this case, one says that Template:Tmath is the number of elements of the set. A set is infinite if such an Template:Tmath does not exists. The empty set is a finite set with Template:Tmath elements. The natural numbers form an infinite set, commonly denoted Template:Tmath.

Specifying a set

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

Above notations Template:Tmath and Template:Tmath 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, $$\{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 $$\{1,2,3,\dots ,1000\}$$ for the positive integers not greater than Template:Tmath.

Ellipses allow also expanding roster notation to some infinite sets. For example, the set of all integers can be denoted as $$\{\dots ,-3,-2,-1,0,1,2,3,\dots \}$$ or $$\{0,1,-1,2,-2,3,-3,\dots \}.$$

Set-builder notation

Set-builder notation specifies a set as being the set of all elements that satisfy some logical formula. More precisely, if Template:Tmath is a logical formula depending on a variable Template:Tmath, which evaluates to true or false depending on the value of Template:Tmath, then $$\{x\mid P(x)\}$$ or $$\{x:P(x)\}$$ denotes the set of all Template:Tmath for which Template:Tmath is true. For example, a set Template:Mvar can be specified as follows: $$F=\{n\mid n\text{ is an integer, and }0\le n\le 19\}.$$ In this notation, the vertical bar "|" is read as "such that", and the whole formula can be read as "Template:Mvar is the set of all Template:Mvar such that Template:Mvar is an integer in the range from 0 to 19 inclusive".

Some logical formulas, such as Template:Tmath or Template:Tmath 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 Template:Tmath that must contain all elements of the specified set, and write the notation as $$\{x\mid x\in U\text{ and ...}\}$$ or $$\{x\in U\mid \text{ ...}\}.$$

One may also define Template:Tmath once for all and take the convention that every variable that appears on the left of the vertical bat of the notation represents an element of Template:Tmath. This amounts to say that Template:Tmath is implicit in set-builder notation. In this case, Template:Tmath 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\mid x\in ̸\mathbb{Q}\}$$ is an abbreviation of $$\{x\in ℝ\mid x\in ̸\mathbb{Q}\},$$ which defines the irrational numbers.

Subsets

Template:Main A subset of a set Template:Tmath is a set Template:Tmath such that every element of Template:Tmath is also an element of Template:Tmath. If Template:Tmath is a subset of Template:Tmath, one says commonly that Template:Tmath is contained in Template:Tmath, Template:Tmath contains Template:Tmath, or Template:Tmath is a superset of Template:Tmath. This denoted Template:Tmath and Template:Tmath. However many authors use Template:Tmath and Template:Tmath instead. The definition of a subset can be expressed in notation as $$A\subseteq B\text{if and only if}\mathrm{\forall }x(x\in A⟹x\in B).$$

A set Template:Tmath is a proper subset of a set Template:Tmath if Template:Tmath and Template:Tmath. This is denoted Template:Tmath and Template:Tmath. When Template:Tmath is used for the subset relation, or in case of possible ambiguity, one uses commonly Template:Tmath and Template:Tmath.Template:Sfn

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, Template:Math and Template:Math is equivalent to A = B. The empty set is a subset of every set: Template:Math.Template:Sfn

Examples:

• The set of all humans is a proper subset of the set of all mammals.
• Template:Math.
• Template:Math

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 Venn diagrams.

The main basic operations on sets are the following ones.

Intersection

Error creating thumbnail:

The intersection of Template:Mvar and Template:Mvar, denoted Template:Math

The intersection of two sets Template:Tmath and Template:Tmath is a set denoted Template:Tmath whose elements are those elements that belong to both Template:Tmath and Template:Tmath. That is, $$A\cap B=\{x\mid x\in A\wedge x\in B\},$$ where Template:Tmath 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 Template:Tmath, intersection has Template:Tmath as identity element.

If Template:Tmath is a nonempty set of sets, its intersection, denoted $\bigcap _{A\in 𝒮}A,$ is the set whose elements are those elements that belong to all sets in Template:Tmath. That is, $$\bigcap _{A\in 𝒮}A=\{x\mid (\mathrm{\forall }A\in 𝒮)x\in A\}.$$

These two definitions of the intersection coincide when Template:Tmath has two elements.

Union

The union of Template:Math and Template:Math, denoted Template:Math

The union of two sets Template:Tmath and Template:Tmath is a set denoted Template:Tmath whose elements are those elements that belong to Template:Tmath or Template:Tmath, or both. That is, $$A\cup B=\{x\mid x\in A\vee x\in B\},$$ where Template:Tmath 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 Template:Tmath is a set of sets, its union, denoted $\bigcup _{A\in 𝒮}A,$ is the set whose elements are those elements that belong to at least one set in Template:Tmath. That is, $$\bigcup _{A\in 𝒮}A=\{x\mid (\mathrm{\exists }A\in 𝒮)x\in A\}.$$

These two definitions of the union coincide when Template:Tmath has two elements.

Set difference

The set difference Template:Math

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

Error creating thumbnail:

The complement of A in U

When Template:Tmath the difference Template:Tmath is also called the complement of Template:Tmath in Template:Tmath. When all sets that are considered are subsets of a fixed unversal set Template:Tmath, the complement Template:Tmath is often called the absolute complement of Template:Tmath.

File:Venn0110.svg

The symmetric difference of A and B

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

Algebra of subsets

Template:Main The set of all subsets of a set Template:Tmath is called the powerset of Template:Tmath, often denoted Template:Tmath. The powerset is an algebraic structure whose main operations are union, intersection, set difference, symmetric difference and absolute complement (complement in Template:Tmath).

The powerset is a Boolean ring that has the symmetric difference as addition, the intersection as multiplication, the emptyset as additive identity, Template:Tmath as multiplicative identity, and complement as additive inverse.

The powerset is also a Boolean algebra for which the join Template:Tmath is the union Template:Tmath, the meet Template:Tmath is the intersection Template:Tmath, 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.

Applications

Sets are ubiquitous in modern mathematics. For example, structures in abstract algebra, such as groups, fields and rings, are sets closed under one or more operations.

One of the main applications of naive set theory is in the construction of relations. A relation from a domain Template:Math to a codomain Template:Math is a subset of the Cartesian product Template:Math. For example, considering the set Template:Math of shapes in the game of the same name, the relation "beats" from Template:Math to Template:Math is the set Template:Math; thus Template:Math beats Template:Math in the game if the pair Template:Math is a member of Template:Math. Another example is the set Template:Math of all pairs Template:Math, where Template:Math is real. This relation is a subset of Template:Math, because the set of all squares is subset of the set of all real numbers. Since for every Template:Math in Template:Math, one and only one pair Template:Math is found in Template:Math, it is called a function. In functional notation, this relation can be written as Template:Math.

Euler and Venn diagrams

A is a subset of B.
B is a superset of A.

An Euler diagram is a graphical representation of a collection of sets; each set is depicted as a planar region enclosed by a loop, with its elements inside. If Template:Mvar is a subset of Template:Mvar, then the region representing Template:Mvar is completely inside the region representing Template:Mvar. If two sets have no elements in common, the regions do not overlap.

A Venn diagram, in contrast, is a graphical representation of Template:Mvar sets in which the Template:Mvar loops divide the plane into Template:Math zones such that for each way of selecting some of the Template:Mvar sets (possibly all or none), there is a zone for the elements that belong to all the selected sets and none of the others. For example, if the sets are Template:Mvar, Template:Mvar, and Template:Mvar, there should be a zone for the elements that are inside Template:Mvar and Template:Mvar and outside Template:Mvar (even if such elements do not exist).

Special sets of numbers in mathematics

The natural numbers $\mathbb{N}$ are contained in the integers $\mathbb{Z}$, which are contained in the rational numbers $\mathbb{Q}$, which are contained in the real numbers $ℝ$, which are contained in the complex numbers $ℂ$

There are sets of such mathematical importance, to which mathematicians refer so frequently, that they have acquired special names and notational conventions to identify them.

Many of these important sets are represented in mathematical texts using bold (e.g. $𝐙$) or blackboard bold (e.g. $\mathbb{Z}$) typeface. These include

• $𝐍$ or $\mathbb{N}$, the set of all natural numbers: $𝐍=\{0,1,2,3,...\}$ (often, authors exclude Template:Math);
• $𝐙$ or $\mathbb{Z}$, the set of all integers (whether positive, negative or zero): $𝐙=\{...,-2,-1,0,1,2,3,...\}$;
• $𝐐$ or $\mathbb{Q}$, the set of all rational numbers (that is, the set of all proper and improper fractions): $𝐐=\{\frac{a}{b}\mid a,b\in 𝐙,b\ne 0\}$. For example, Template:Math and Template:Math;
• $𝐑$ or $ℝ$, the set of all real numbers, including all rational numbers and all irrational numbers (which include algebraic numbers such as $\sqrt{2}$ that cannot be rewritten as fractions, as well as transcendental numbers such as [[Pi|Template:Mvar]] and [[e (mathematical constant)|Template:Math]]);
• $𝐂$ or $ℂ$, the set of all complex numbers: Template:Math, for example, Template:Math.

Each of the above sets of numbers has an infinite number of elements. Each is a subset of the sets listed below it.

Sets of positive or negative numbers are sometimes denoted by superscript plus and minus signs, respectively. For example, ${𝐐}^{+}$ represents the set of positive rational numbers.

Functions

A function (or mapping) from a set Template:Mvar to a set Template:Mvar is a rule that assigns to each "input" element of Template:Mvar an "output" that is an element of Template:Mvar; more formally, a function is a special kind of relation, one that relates each element of Template:Mvar to exactly one element of Template:Mvar. A function is called

• injective (or one-to-one) if it maps any two different elements of Template:Mvar to different elements of Template:Mvar,
• surjective (or onto) if for every element of Template:Mvar, there is at least one element of Template:Mvar that maps to it, and
• bijective (or a one-to-one correspondence) if the function is both injective and surjective — in this case, each element of Template:Mvar is paired with a unique element of Template:Mvar, and each element of Template:Mvar is paired with a unique element of Template:Mvar, so that there are no unpaired elements.

An injective function is called an injection, a surjective function is called a surjection, and a bijective function is called a bijection or one-to-one correspondence.

Cardinality

The cardinality of a set Template:Math, denoted Template:Math, is the number of members of Template:Math. For example, if Template:Math, then Template:Math. Repeated members in roster notation are not counted, so Template:Math, too.

More formally, two sets share the same cardinality if there exists a bijection between them.

The cardinality of the empty set is zero.

Infinite sets and infinite cardinality

The list of elements of some sets is endless, or infinite. For example, the set $\mathbb{N}$ of natural numbers is infinite. In fact, all the special sets of numbers mentioned in the section above are infinite. Infinite sets have infinite cardinality.

Some infinite cardinalities are greater than others. Arguably one of the most significant results from set theory is that the set of real numbers has greater cardinality than the set of natural numbers. Sets with cardinality less than or equal to that of $\mathbb{N}$ are called countable sets; these are either finite sets or countably infinite sets (sets of the same cardinality as Template:Tmath); some authors use "countable" to mean "countably infinite". Sets with cardinality strictly greater than that of $\mathbb{N}$ are called uncountable sets.

However, it can be shown that the cardinality of a straight line (i.e., the number of points on a line) is the same as the cardinality of any segment of that line, of the entire plane, and indeed of any finite-dimensional Euclidean space.

The continuum hypothesis

Template:Main The continuum hypothesis, formulated by Georg Cantor in 1878, is the statement that there is no set with cardinality strictly between the cardinality of the natural numbers and the cardinality of a straight line. In 1963, Paul Cohen proved that the continuum hypothesis is independent of the axiom system ZFC consisting of Zermelo–Fraenkel set theory with the axiom of choice. (ZFC is the most widely-studied version of axiomatic set theory.)

Power sets

Template:Main The power set of a set Template:Math is the set of all subsets of Template:Math. The empty set and Template:Math itself are elements of the power set of Template:Math, because these are both subsets of Template:Math. For example, the power set of Template:Math is Template:Math. The power set of a set Template:Math is commonly written as Template:Math or Template:Math.Template:Sfn

If Template:Math has Template:Math elements, then Template:Math has Template:Math elements.Template:Sfn For example, Template:Math has three elements, and its power set has Template:Math elements, as shown above.

If Template:Math is infinite (whether countable or uncountable), then Template:Math is uncountable. Moreover, the power set is always strictly "bigger" than the original set, in the sense that any attempt to pair up the elements of Template:Math with the elements of Template:Math will leave some elements of Template:Math unpaired. (There is never a bijection from Template:Math onto Template:Math.)

Partitions

A partition of a set S is a set of nonempty subsets of S, such that every element x in S is in exactly one of these subsets. That is, the subsets are pairwise disjoint (meaning any two sets of the partition contain no element in common), and the union of all the subsets of the partition is S.Template:Sfn

Principle of inclusion and exclusion

File:A union B.svg

The inclusion-exclusion principle for two finite sets states that the size of their union is the sum of the sizes of the sets minus the size of their intersection.

The inclusion–exclusion principle is a technique for counting the elements in a union of two finite sets in terms of the sizes of the two sets and their intersection. It can be expressed symbolically as $$|A\cup B|=|A|+|B|-|A\cap B|.$$

A more general form of the principle gives the cardinality of any finite union of finite sets: $$\begin{array}{cc}|A_1\cup A_2\cup A_3\cup \dots \cup A_n|=& (\left|A_1\right|+\left|A_2\right|+\left|A_3\right|+\dots \left|A_n\right|)\\ & -(|A_1\cap A_2|+|A_1\cap A_3|+\dots |A_{n-1}\cap A_n|)\\ & +\dots \\ & +{(-1)}^{n-1}\left(|A_1\cap A_2\cap A_3\cap \dots \cap A_n|\right).\end{array}$$

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.

File:Passage with the set definition of Georg Cantor.png

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:

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):

Naive set theory

Template:Main 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.Template:Sfn As a consequence, e.g. Template:Math and Template:Math represent the same set. Unlike sets, multisets can be distinguished by the number of occurrences of an element; e.g. Template:Math and Template:Math represent different multisets, while Template:Math and Template:Math are equal. Tuples can even be distinguished by element order; e.g. Template:Math and Template:Math 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., Template:Mset, 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

References

• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite book

External links

• Template:Wiktionaryinline
• Cantor's "Beiträge zur Begründung der transfiniten Mengenlehre" Template:In lang