Sets

A set of polygons in an Euler diagram

In mathematics, a set is a collection of elements. The elements that make up a set can be any kind of mathematical objects: numbers, symbols, points in space, lines, other geometrical shapes, variables, or even other sets. The set with no element is the empty set; a set with a single element is a singleton. A set may have a finite number of elements or be an infinite set. Two sets are equal if and only if they have precisely the 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.

Origin

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.

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 called a set a class: "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 is in that case is the class."

Naïve 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 a member of B, and every element of B is an element of A; this property is called the extensionality of sets.

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.

How sets are defined and set notation

Mathematical texts commonly denote sets by capital letters in italic, such as A, B, C. A set may also be called a collection or family, especially when its elements are themselves sets.

Roster notation

Roster or enumeration notation defines a set by listing its elements between curly brackets, separated by commas:

A = {4, 2, 1, 3}

B = {blue, white, red}.

In a set, all that matters is whether each element is in it or not, so the ordering of the elements in roster notation is irrelevant (in contrast, in a sequence, a tuple, or a permutation of a set, the ordering of the terms matters). For example, {2, 4, 6} and {4, 6, 4, 2} represent the same set.

For sets with many elements, especially those following an implicit pattern, the list of members can be abbreviated using an ellipsis '...'. For instance, the set of the first thousand positive integers may be specified in roster notation as

{1, 2, 3, ..., 1000}.

Infinite sets in roster notation

An infinite set is a set with an endless list of elements. To describe an infinite set in roster notation, an ellipsis is placed at the end of the list, or at both ends, to indicate that the list continues forever. For example, the set of nonnegative integers is

{0, 1, 2, 3, 4, ...},

and the set of all integers is

{..., −3, −2, −1, 0, 1, 2, 3, ...}.

Semantic definition

Another way to define a set is to use a rule to determine what the elements are:

Let A be the set whose members are the first four positive integers.

Let B be the set of colors of the French flag.

Such a definition is called a semantic description.

Set-builder notation

Set-builder notation specifies a set as a selection from a larger set, determined by a condition on the elements. For example, a set F can be defined as follows:

F $=\{n\mid n{\text{ is an integer, and }}0\leq n\leq 19\}.$

In this notation, the vertical bar "

• A ⊆ B if and only if A ∩ B = A.

Complements

The relative complement
of B in A

The complement of A in U

The symmetric difference of A and B

Two sets can also be "subtracted". The relative complement of B in A (also called the set-theoretic difference of A and B), denoted by A \ B (or A − B), is the set of all elements that are members of A, but not members of B. It is valid to "subtract" members of a set that are not in the set, such as removing the element green from the set {1, 2, 3}; doing so will not affect the elements in the set.

In certain settings, all sets under discussion are considered to be subsets of a given universal set U. In such cases, U \ A is called the absolute complement or simply complement of A, and is denoted by A′ or A^c.

• A′ = U \ A

Examples:

• {1, 2} \ {1, 2} = ∅.
• {1, 2, 3, 4} \ {1, 3} = {2, 4}.
• If U is the set of integers, E is the set of even integers, and O is the set of odd integers, then U \ E = E′ = O.

Some basic properties of complements include the following:

• A \ B ≠ B \ A for A ≠ B.
• A ∪ A′ = U.
• A ∩ A′ = ∅.
• (A′)′ = A.
• ∅ \ A = ∅.
• A \ ∅ = A.
• A \ A = ∅.
• A \ U = ∅.
• A \ A′ = A and A′ \ A = A′.
• U′ = ∅ and ∅′ = U.
• A \ B = A ∩ B′.
• if A ⊆ B then A \ B = ∅.

An extension of the complement is the symmetric difference, defined for sets A, B as

$A\,\Delta \,B=(A\setminus B)\cup (B\setminus A).$

For example, the symmetric difference of {7, 8, 9, 10} and {9, 10, 11, 12} is the set {7, 8, 11, 12}. The power set of any set becomes a Boolean ring with symmetric difference as the addition of the ring (with the empty set as neutral element) and intersection as the multiplication of the ring.

Cartesian product

A new set can be constructed by associating every element of one set with every element of another set. The Cartesian product of two sets A and B, denoted by A × B, is the set of all ordered pairs (a, b) such that a is a member of A and b is a member of B.

Examples:

• {1, 2} × {red, white, green} = {(1, red), (1, white), (1, green), (2, red), (2, white), (2, green)}.
• {1, 2} × {1, 2} = {(1, 1), (1, 2), (2, 1), (2, 2)}.
• {a, b, c} × {d, e, f} = {(a, d), (a, e), (a, f), (b, d), (b, e), (b, f), (c, d), (c, e), (c, f)}.

Some basic properties of Cartesian products:

• A × ∅ = ∅.
• A × (B ∪ C) = (A × B) ∪ (A × C).
• (A ∪ B) × C = (A × C) ∪ (B × C).

Let A and B be finite sets; then the cardinality of the Cartesian product is the product of the cardinalities:

• |A × B| = |B × A| = |A| × |B|.

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 A to a codomain B is a subset of the Cartesian product A × B. For example, considering the set S = {rock, paper, scissors} of shapes in the game of the same name, the relation "beats" from S to S is the set B = {(scissors,paper), (paper,rock), (rock,scissors)}; thus x beats y in the game if the pair (x,y) is a member of B. Another example is the set F of all pairs (x, x²), where x is real. This relation is a subset of R × R, because the set of all squares is subset of the set of all real numbers. Since for every x in R, one and only one pair (x,...) is found in F, it is called a function. In functional notation, this relation can be written as $F(x)=x^{2}$.

Principle of inclusion and exclusion

The inclusion-exclusion principle is used to calculate the size of the union of sets: the size of the union is the size of the two sets, minus the size of their intersection.

The inclusion–exclusion principle is a counting technique that can be used to count the number of elements in a union of two sets—if the size of each set and the size of their intersection are known. It can be expressed symbolically as

$|A\cup B|=|A|+|B|-|A\cap B|.$

A more general form of the principle can be used to find the cardinality of any finite union of sets:

${\begin{aligned}\left|A_{1}\cup A_{2}\cup A_{3}\cup \ldots \cup A_{n}\right|=&\left(\left|A_{1}\right|+\left|A_{2}\right|+\left|A_{3}\right|+\ldots \left|A_{n}\right|\right)\\&{}-\left(\left|A_{1}\cap A_{2}\right|+\left|A_{1}\cap A_{3}\right|+\ldots \left|A_{n-1}\cap A_{n}\right|\right)\\&{}+\ldots \\&{}+\left(-1\right)^{n-1}\left(\left|A_{1}\cap A_{2}\cap A_{3}\cap \ldots \cap A_{n}\right|\right).\end{aligned}}$

De Morgan's laws

Augustus De Morgan stated two laws about sets.

If A and B are any two sets then,

• (A ∪ B)′ = A′ ∩ B′

The complement of A union B equals the complement of A intersected with the complement of B.

• (A ∩ B)′ = A′ ∪ B′

The complement of A intersected with B is equal to the complement of A union to the complement of B.

Resources

• Sets and Subsets, Book Chapter
• Guided Notes

Licensing

Content obtained and/or adapted from:

• Set (mathematics), Wikipedia under a CC BY-SA license