Set (mathematics)

Informally, a set is thought of as any collection of distinct elements. They may be defined in two ways: by enumeration of their members (a definition by extension), for example by identifying a room of students by listing their names, or by a defining property (a definition by intension), for example, by speaking of the set of all students in Room 101.

Sets are axiomatized and investigated in general by a branch of mathematics known as set theory. In particular, set theory studies what conditions must apply to a defining property in order that the elements with that property in fact form a set. (Some choices of property lead to paradoxes, and this topic still is not fully resolved.) The very existence of various sets introduced below is addressed by set theory, for example by the Zermelo-Fraenkel axioms.

Introduction

The basic property of sets is that they are solely determined by the elements they contain (this is called extensionality). Thus, we can identify sets by listing their elements. For instance, we can talk about the set that has as its elements the numbers 1, 2 and 3. This set is denoted {1, 2, 3}.

A consequence of this basic property is that a set cannot contain an element twice. The set {1, 2, 2, 3} contains the elements 1, 2 and 3 and is thus the same as the set {1, 2, 3}. This is the difference between sets and multisets; considered as multisets, {1, 2, 2, 3} and {1, 2, 3} are different.

For the same reason, the order in which the elements are listed does not matter. The sets {1, 2, 3} and {3, 2, 1} have the same elements and thus these two sets are equal. However, there are many contexts in which we want to consider structures that have elements in a certain order and these elements may be the same. Such a structure is called a tuple or a sequence. The tuple containing the elements 1, 2 and 3 (in that order) is different from the tuple containing the elements 3, 2 and 1. These tuples are denotes (1, 2, 3) and (3, 2, 1) respectively, with round brackets (or angle brackets) instead of curly brackets to emphasize the difference between tuples and sets.

Despite the intuitive definition, a set is usually not defined formally in terms of other mathematical objects; rather it is defined by the laws (called axioms) that is satisfies. For instance, one commonly requires that no set may be an element of itself. Because sets are defined by themselves, they are fundamental structures in mathematics and logic. Mathematicians have found ways to define many mathematical objects, such as the real numbers, in terms of sets.

The number of elements that a set contains does not have to be finite. Sets that contain a finite number of elements are called finite sets. Sets that contain an infinite number of elements are called infinite sets. The number of elements that a finite set contains is called that set's cardinality. The concept of cardinality can also be applied to infinite sets, though the concept is less intuitive, and relies upon bijections between sets.

Notation and terminology

Some sets can be denoted by a list of objects separated with commas, enclosed with curly brackets. As mentioned before, {1, 2, 3} is the set of the numbers 1, 2, and 3. We say that 1, 2, and 3 are its members or its elements. The set with no elements at all is called the empty set, denoted by ∅ = { }.

There are many other ways to write out sets. For example,

A = {x | 1 < x < 10, x is a natural number}

can be read as follows: A is the set of all x, where x is between 1 and 10, and x is a natural number. A could also be written as:

A = {2, 3, 4, 5, 6, 7, 8, 9}

Membership in a set is expressed with the ∈ symbol. To say that the set A contains the 2 as an element (or that 2 is an element of A), we write

2 ∈ A

The cardinality of a set is expressed by placing bars around the name of the set. For example, one would express the cardinality of the above set as such:

|A| = 8

Subsets

A set A is a subset of another set B if each element of A is an element of B. One says "A is contained in B" and writes A ⊂ B, alternatively that "B contains A" or B ⊃ A. If A ⊂ B and B ⊂ A, then A = B. Set A is a proper subset of set B if A ⊂ B and A ≠ B. Sometimes, for emphasis, the notation A⊆B is used when the possibility that A=B is allowed, and A⊂B is reserved for the case when A=B is excluded. If A is a subset of B, then B is a superset of A.

Set of sets

A set whose elements are also sets is called a set of sets. An important example is the set called the power set, a set whose elements consist of all the subsets of a set. (It may be observed that if a set is defined by a property, not by enumeration, there may be some complexity in discussing its subsets.) If A is a set, the power set of A often is denoted as ℘(A) or P(A) or ${\mathcal {P}}(A)$.

One might simplemindedly imagine labeling some individual subset of A as A_i with some index i from an index set I, and then referring to the collection of these subsets {A_i|i∈I} as a family of subsets of A. In a more elaborate formulation of this notion, one defines a family of subsets in terms of the set of all subsets of A, ℘(A), and a labeling scheme for designating each of the subsets in ℘(A) as A_i with some i∈I, using a mapping function f, itself called the family. Then the set {A_i} is called a family of subsets of A, and of course, depends upon the labeling family function f.

A famous letter from Cantor to Dedekind in 1899 pointed out that the notion of a "set of all sets" leads to a contradiction. Some sets include themselves (so-called impredicative definitions), and some do not: The set of all ideas is an idea. The set of all wikis is not a wiki. Impredicative definitions underlie paradoxes.

Union, intersection, difference

(PD) Image: John R. Brews
Venn diagrams; set A is the blue circle (left) and its interior, set B is the red circle (right) and its interior.

The union or sum of two sets A and B, written A ∪ B, is the set with elements that appear in A or B or both. That is:

$A\ \cup \ B=\{x|x\in A\ {\text{or}}\ x\in B\}\ .$

The intersection or product of A and B, written A ∩ B is the set with elements that appear in both set A and in set B. That is:

$A\ \cap \ B=\{x|x\in A\ {\text{and}}\ x\in B\}\ .$

The difference of two sets A and B, written A − B, is the set with elements of A that are not elements of B. It also is called the relative complement of B in set A. That is:

$A\ -\ B=\{x|x\in A\ {\text{and}}\ x\not \in B\}\ .$

The absolute complement of A, denoted ~A, is the set of all elements not contained in A:

$\sim A=\{x|x\not \in A\}\ ,$

which suggests there exists a broader universal set U that includes A and all other sets under discussion. Evidently it holds that:

$\sim \sim A=A\ .$

These notions are visualized in the Venn diagram of the figure, in which the circles represent subsets A and B of the universal set U, the rectangle.

The union and the intersection are commutative, that is:

$A\ \cup \ B\ =\ B\ \cup \ A\$

${\text{and}}\ A\ \cap \ B\ =\ B\ \cap \ A\ ,$

and associative:

$\left(A\ \cup \ B\right)\ \cup \ C\ =\ A\ \cup \ \left(\ B\ \cup \ C\right)\ {\text{and}}$   $\left(A\ \cap \ B\right)\ \cap \ C\ =\ A\ \cap \ \left(\ B\ \cap \ C\right)\ .$

Two sets A and B are said to be disjoint if A ∩ B = ∅. Also of interest are the absorption law:

$A\ \cup \ \left(\ A\ \cap \ B\ \right)=A;\ \ A\ \cap \ \left(\ A\ \cup \ B\ \right)=A\ ,$

and the distributive law:

$A\ \cup \ \left(\ B\ \cap \ C\ \right)\ =\ \left(\ A\ \cup \ B\ \right)\ \cap \ \left(A\ \cup \ C\ \right);$   $\ \ A\ \cap \ \left(\ B\ \cup \ C\ \right)\ =\ \left(\ A\ \cap \ B\ \right)\ \cup \ \left(\ A\ \cap \ C\ \right)\ .$

Other relations involving set operations between multiple sets A, B', C ... are known.

Cartesian products

The Cartesian product or direct product of two sets A and B is the set defined by:

$A\mathbf {\times } B=\{(a,\ b)|a\in A,\ b\in B\}\ .$

This definition can be extended to any number of sets. The couple (a, b) is called an ordered pair, because the order of the two entries is significant, indicating which set the element comes from. The set A × B = ∅ if and only if either A = ∅ or B = ∅.

Mappings or functions

Given two sets A and B, a mapping (or map) also called a function or transformation from A into B, is a rule associating each element of A to an element of B. Common notations for a mapping f are:

$f:A\rightarrow B\ {\text{or}}\ A\ \xrightarrow {f} \ B\ ,$

where the element a∈A is associated by the mapping f to an element b∈B, that is:

$b=f(a)\ \ {\text{or}}\ f:a\mapsto b,$

and b is called the image of a in B under f. The set A is called the domain of the mapping f, and the subset of B consisting of all the image points is the image (or sometimes range) of f, denoted as the subset of B given by:

$f(A)=\{f(a)|a\in A\}\ .$

The set B to which A is mapped is called the co-domain. Evidently, the image is a subset of the co-domain.

If the mapping f : A→B satisfies f(A) = B, then f is surjective and we say f maps A onto B, and the image equals the co-domain.

Two functions f and g are equal if they have the same domain A, the same co-domain B, and if f(a) = g(a) for all a∈A.

The mapping f is injective (or one-to-one) if a₁ ≠ a₂ means f(a₁) ≠ f(a₂) for all a₁,a₂ ∈ A.

Some special sets

Some sets that are ubiquitous in the mathematical literature have special symbols:

• $\emptyset$, the empty set, sometimes written {}.
• $\mathbb {N}$, the set of natural numbers
• $\mathbb {Z}$, the set of integers
• $\mathbb {Q}$, the set of rational numbers
• $\mathbb {R}$, the set of real numbers
• $\mathbb {F}$, the set of irrational numbers
• $\mathbb {C}$, the set of complex numbers
• $\mathbb {P}$, the set of prime numbers

Among other such well known sets are the fibonacci numbers, even numbers, odd numbers, quaternions, octonions and the Hamiltonian integers.

Some examples of sets

• The set consisting of all tuples (a,b), where a is any real number and ditto for b. This set is known as ℝ×ℝ or ℝ².
• The three element set {Red, Yellow, Green}.
• The set consisting of the two elements Brake, Accelerate.
• The set consisting of all tuples (a,b) where a is any element in the set {Red, Yellow, Green} and b is any element in the set {Brake, Accelerate}.
• The set of all functions from the set {Red, Yellow, Green} to the set {Brake, Accelerate}.