"We define a set as a compilation \(M\) of comprising specific and clearly distinguishable objects within the scope of our perception or thought. These objects are referred to as the elements of \(M\)." - Georg Cantor, 1895
If \(x\) is such an element of \(M\), we write \(x\in M\). If \(x\) does not belong to \(M\), we write \(x \notin M\).
Ways of representing sets include the enumerative notation, also called the extensional description, such as
\[M=\{a, b, c, d, e\}\text{ or } M=\{1, 2, 3, ...\}\]
Concrete sets built this way can mix numbers, letters, or unrelated objects side by side, for example
\[\{7, 8, 9, 10, B, D, K, A\}\qquad\text{or}\qquad\{5, a, A, \text{house}, \text{number}\}.\]
Listing the elements of a set never depends on the order in which they are written, and repeating an element changes nothing about the set. The square numbers up to \(20\) can therefore be written in several equivalent ways:
\[\{1, 4, 9, 16\} = \{4, 1, 16, 9\} = \{4, 9, 9, 1, 4, 16\}.\]
but sets can also be specified descriptively, also called the intensional description:
\[M = \{n : A(n)\}\]
With a statement \(A(n)\), such as, for example "\(n\) is even/odd" or "\(n\bmod 3=0\)". Some authors separate the property with a vertical bar instead of a colon, \(M=\{n\mid A(n)\}\); both mean the same thing. Descriptive definitions are not limited to numbers: the unit circle in the plane, for instance, is the set of points at distance \(1\) from the origin,
\[E = \{(\cos t, \sin t) : t\in\mathbb{R}\},\]
parametrized by the angle \(t\).
Sets can also be empty, meaning there is no element \(x\) that belongs to the set. In such cases, we assign a symbol to the empty set:
\[M = \{\} = \emptyset\]
Because equality of sets requires exactly the same elements, there is only ever one empty set, however it arises. An empty set often appears unexpectedly from a descriptive definition whose property nothing can satisfy, for example the natural numbers \(n\) with \(n<10\) and \(n^2>200\), or the points \((x,y)\) on the unit circle \(E\) above with \(x+y=2\): neither condition singles out any element, so both descriptions equal \(\emptyset\).
Sets can be nested arbitrarily, as for example,
\[M = \{\{1, 2, 3\}, \{4, 5, 6\}\}\]
The cardinality of a set \(M\) is the number of elements, that are contained in the set and is denoted by vertical lines:
\[n = |M|\]
More precisely, a nonempty set \(M\) is called finite if there exist a natural number \(n\) and a bijective mapping \(M\to\{1,2,\dots,n\}\); this \(n\) is then the cardinality of \(M\), written \(n=|M|\). The empty set is finite by convention, with \(|\emptyset|=0\), and a set that is not finite is called infinite. This is what makes "counting" precise: pairing off the elements of \(M\) one at a time with \(1,2,\dots,n\) is exactly a bijection to \(\{1,\dots,n\}\).
The complement of set \(M\) is denoted by a bar over the set symbol, and it refers to all elements from a fixed universal set \(U\) excluding the elements in our set \(M\):
\[\overline{M} := U\backslash M\]
When it is clear which universal set is meant, the complement is sometimes written as \(M^c\) instead of \(\overline{M}\).
A set can also be represented in interval notation. A square bracket is considered inclusive, while a round bracket indicates exclusion from the interval, which can be combined as desired:
\[[a, b] := \{x\in\mathbb{R} : a\leq x\leq b\}\] \[(a, b) := \{x\in\mathbb{R} : a< x< b\}\]
Subsets
Let \(A\) and \(B\) be sets; then \(A\) is a subset of \(B\), and \(B\) is the superset of \(A\), if every element \(x \in A\) is also an element of \(B\). In notation, we write:
\[A\subseteq B\]
If, in addition to \(A \subseteq B\), we also have \(B \subseteq A\), then the two sets are equal, and we say:
\[A=B\]
This double-inclusion criterion is the standard way to prove that two sets are equal: show separately that every element of \(A\) lies in \(B\) and that every element of \(B\) lies in \(A\).
If \(A\subseteq B\) but \(A\neq B\), then \(A\) is called a proper subset of \(B\), written \(A\subset B\). Some authors instead use \(A\subset B\) as a synonym for \(A\subseteq B\), allowing equality; here \(\subset\) always denotes strict inclusion, so \(A\subset B\) means \(A\subseteq B\) together with \(A\neq B\). Every set is trivially a subset of itself, \(M\subseteq M\), but never a proper subset of itself.
Subset relationships are transitive. So, let \(A, B, C\) be sets, and if \(A \subseteq B\) and \(B \subseteq C\), then it follows that \(A \subseteq C\).
We can also state that if \(A \subseteq B\) and \(A \subseteq C\), then \(A \subseteq B \cap C\).
If we know that \(A \subseteq B\), the statement \(A \subseteq B \cup C\) holds for any set \(C\).
For finite sets, the subset relation also controls cardinality: if \(A\subseteq B\) and \(B\) is finite, then \(A\) is finite too, with \(|A|\le|B|\). Moreover, if in addition \(|A|=|B|\), then already \(A=B\) — a finite set cannot contain a proper subset of the same size. This fails for infinite sets: \(2\mathbb{Z}\subset\mathbb{Z}\) is a proper subset, yet both are infinite and can be put into a bijection with each other via \(n\mapsto 2n\).
Known Set Symbols
The set of natural numbers:
\[\mathbb{N} := \{1, 2, 3, ...\}\]
The set of natural numbers including 0:
\[\mathbb{N}_0 := \mathbb{N}\cup \{0\}\]
Some authors use a notation for even natural numbers:
\[2\mathbb{N} := \{2, 4, 6, ...\}\]
The set of integers:
\[\mathbb{Z} := \{0, \pm 1, \pm 2, \pm 3, ...\}\]
The set of rational numbers:
\[\mathbb{Q} := \left\{\frac{a}{b} : a\in\mathbb{Z}, b\in\mathbb{N} \right\}\]
The set of real numbers:
\[\mathbb{R} := \mathbb{Q}\cup\{\sqrt{2}, \sqrt{5}, \pi, ...\}\]
Restricting to a sign gives the positive reals,
\[\mathbb{R}_{>0} := \{x\in\mathbb{R} : x>0\},\]
and analogously \(\mathbb{R}_{\geq 0}\), \(\mathbb{R}_{<0}\), \(\mathbb{R}_{\leq 0}\) denote the nonnegative, negative, and nonpositive reals.
The set of complex numbers:
\[\mathbb{C} := \{a+\mathbf{i}b\ : a, b\in\mathbb{R}\}\]
The set of Quaternions:
\[\mathbb{H} := \{w+\mathbf{i}x+\mathbf{j}y+\mathbf{k}z\ : w,x,y,z\in\mathbb{R}\}\]
The sets form a chain of subset relationships. The natural numbers are a subset of the integers, and so on:
\[\mathbb{N}\subseteq\mathbb{N}_0\subseteq\mathbb{Z}\subseteq\mathbb{Q}\subseteq\mathbb{R}\subseteq\mathbb{C}\]
In practice this means, for example, that \(3\) can be written as \[3 = \frac{3}{1} = 3.0 = 3 + 0i\] while \(3+4i\) cannot be represented as a real, rational, integer, or natural number.
Set Operations
To visualize sets and their relationships, one commonly uses Venn or Euler diagrams: the underlying universal set is drawn as a rectangle, and the sets under consideration are shown inside as closed curves such as circles or ovals. For finite sets, the individual elements are sometimes written directly into the diagram as symbols.
Let \(A\) and \(B\) be sets. The union of \(A\) and \(B\) is denoted as \(A \cup B\) and represents the set containing all elements that are in either \(A\) or \(B\):
\[A\cup B := \{x : x\in A\lor x\in B\}\]
For concrete sets \(M=\{1,2,3,4\}\) and \(N=\{4,5,6\}\), the union collects every element that appears in either set:
\[M\cup N = \{1,2,3,4,5,6\}.\]
Let \(A\) and \(B\) be sets. The intersection of \(A\) and \(B\) is denoted as \(A \cap B\) and represents the set containing all elements that are common to both \(A\) and \(B\).
\[A\cap B := \{x : x\in A\land x\in B\}\]
For the same sets, the intersection keeps only the shared element:
\[M\cap N = \{4\}.\]
Two sets are said to be disjoint from each other, specifically, when \(A \cap B = \emptyset\).
Let \(A\) and \(B\) be sets. The difference of \(A\) and \(B\) is denoted as \(A \setminus B\) and represents the set containing all elements that are in \(A\) but without the elements in \(B\):
\[A\backslash B := \{x : x\in A\land x\notin B\}\]
For the same sets,
\[M\setminus N = \{1,2,3\}\qquad\text{while}\qquad N\setminus M = \{5,6\}.\]
So, unlike union and intersection, the difference is not commutative: in general \(A\setminus B\neq B\setminus A\). Difference and complement are related by \(A\setminus B = A\cap\overline{B}\), since removing the elements of \(B\) from \(A\) is the same as keeping only the elements of \(A\) that lie outside \(B\).
Disjoint versus Overlapping Sets
Whether \(A\) and \(B\) overlap does not change what \(A\cap B\), \(A\cup B\), and \(A\setminus B\) mean, but it does change how they look in a Venn diagram:
a) Disjoint case (\(A\cap B=\emptyset\)):
b) Overlapping case (\(A\cap B\neq\emptyset\)):
Symmetric Difference
The symmetric difference \(A\triangle B\) collects the elements that belong to exactly one of the two sets, but not to both:
\[A\triangle B := (A\setminus B)\cup(B\setminus A) = (A\cap\overline{B})\cup(\overline{A}\cap B)\]
For \(M=\{1,2,3,4\}\) and \(N=\{4,5,6\}\) from above,
\[M\triangle N = \{1,2,3,5,6\},\]
and \(A\triangle B=\emptyset\) exactly when \(A=B\), since no element is left over in either set.
Both intersection and union are commutative, meaning
\[A\cap B = B\cap A\]
\[A\cup B = B\cup A\]
And both intersection and union are associative (allowing the omission of parentheses), meaning
\[(A\cap B)\cap C = A\cap(B\cap C)\]
\[(A\cup B)\cup C = A\cup(B\cup C)\]
Associativity of \(\cup\) follows from associativity of the logical \(\lor\): for any element \(x\),
\[x\in(A\cup B)\cup C \iff (x\in A\lor x\in B)\lor x\in C \iff x\in A\lor(x\in B\lor x\in C) \iff x\in A\cup(B\cup C).\]
Associativity of \(\cap\) follows the same way from associativity of \(\land\).
Furthermore, the distributive law holds
\[A\cup (B\cap C) =(A\cup B)\cap (A\cup C)\]
\[A \cap(B\cup C) =(A\cap B)\cup (A\cap C)\]
A One-Sided Inclusion
Not every natural-looking combination of \(\cup\) and \(\cap\) is an identity like the ones above. For any sets \(A,B,C\),
\[(A\cup B)\cap C \subseteq A\cup(B\cap C),\]
but the reverse inclusion does not hold in general; the diagram above shades exactly \((A\cup B)\cap C\), the part of \(C\) that also lies in \(A\) or \(B\), which visibly excludes the rest of \(A\). To prove the inclusion, let \(x\in(A\cup B)\cap C\), so \(x\in C\) and, in addition, \(x\in A\) or \(x\in B\). If \(x\in A\), then trivially \(x\in A\cup(B\cap C)\). Otherwise \(x\in B\), and combined with \(x\in C\) this gives \(x\in B\cap C\), so again \(x\in A\cup(B\cap C)\). Either way \(x\in A\cup(B\cap C)\), proving the inclusion.
For the converse, take \(A=\{1\}\) and \(B=C=\emptyset\). Then \((A\cup B)\cap C = \{1\}\cap\emptyset=\emptyset\), while \(A\cup(B\cap C) = \{1\}\cup\emptyset=\{1\}\), so \(A\cup(B\cap C)\not\subseteq(A\cup B)\cap C\): the inclusion above cannot be strengthened to an equality.
Besides the distributive law, complements combine with union and intersection through the De Morgan's laws:
\[\overline{A\cap B} = \overline{A}\cup\overline{B}\]
\[\overline{A\cup B} = \overline{A}\cap\overline{B}\]
Both sides of the first law describe exactly the same shaded region, everything outside the lens-shaped overlap of \(A\) and \(B\), so a single diagram illustrates the identity. To prove it, we show both inclusions. Let \(x\in\overline{A\cap B}\) be arbitrary, so \(x\notin A\cap B\), that is, not both \(x\in A\) and \(x\in B\) hold. Hence \(x\notin A\) or \(x\notin B\), so \(x\in\overline{A}\cup\overline{B}\); this shows \(\overline{A\cap B}\subseteq\overline{A}\cup\overline{B}\).
Conversely, let \(x\in\overline{A}\cup\overline{B}\), so \(x\notin A\) or \(x\notin B\). Either way \(x\) cannot lie in both \(A\) and \(B\) simultaneously, so \(x\notin A\cap B\), that is, \(x\in\overline{A\cap B}\); this shows \(\overline{A}\cup\overline{B}\subseteq\overline{A\cap B}\). Together the two inclusions give \(\overline{A\cap B}=\overline{A}\cup\overline{B}\), and the second law follows analogously by exchanging the roles of union and intersection.
Idempotent, Absorption, and Complement Laws
A few further identities round out the algebra of sets. Intersecting or uniting a set with itself changes nothing, the idempotent laws:
\[A\cap A = A\]
\[A\cup A = A\]
The absorption laws let one operation swallow the other:
\[A\cap(A\cup B) = A\]
\[A\cup(A\cap B) = A\]
Both follow directly from the definitions: for the first, any \(x\in A\cap(A\cup B)\) already satisfies \(x\in A\), and conversely every \(x\in A\) lies in \(A\) and, trivially, in \(A\cup B\), so \(x\in A\cap(A\cup B)\); the second is analogous.
A set combined with its own complement recovers the extremes, the complement laws:
\[A\cap\overline{A} = \emptyset\]
\[A\cup\overline{A} = U\]
Applying the complement twice returns the original set, the law of double complement:
\[\overline{\overline{A}} = A\]
Finally, the empty set and the universal set act as absorbing or neutral elements for intersection and union respectively:
\[U\cap A = A \qquad \emptyset\cap A = \emptyset\]
\[\emptyset\cup A = A \qquad U\cup A = U\]
and their own complements swap roles entirely: \(\overline{\emptyset}=U\) and \(\overline{U}=\emptyset\).
Combining the difference identity \(A\setminus B=A\cap\overline{B}\) from above with De Morgan's laws and the double complement law gives the complement of a difference:
\[\overline{A\setminus B} = \overline{A\cap\overline{B}} = \overline{A}\cup\overline{\overline{B}} = \overline{A}\cup B.\]
Power Set
The power set \(\mathcal{P}(M)\) of a set \(M\) is the set of all subsets of \(M\), including \(M\) itself and the empty set:
\[\mathcal{P}(M) := \{X : X\subseteq M\}\]
For example, with \(M=\{1,2\}\),
\[\mathcal{P}(M) = \{\emptyset, \{1\}, \{2\}, \{1,2\}\}\]
A set with \(n\) elements has exactly \(2^n\) subsets, since each element is independently either included or excluded; here \(|\mathcal{P}(M)|=2^{|M|}=4\) matches the four subsets listed above.
Unions and Intersections of Arbitrary Families
Union and intersection generalize beyond two sets to an entire family of sets indexed by some index set \(I\). For a family \((M_i)_{i\in I}\), define
\[\bigcap_{i\in I} M_i := \{x : x\in M_i \text{ for all } i\in I\}\]
\[\bigcup_{i\in I} M_i := \{x : x\in M_i \text{ for some } i\in I\}\]
so that membership in the intersection or union unfolds into a quantified statement,
\[x\in\bigcap_{i\in I}M_i \iff \forall i\in I: x\in M_i,\]
\[x\in\bigcup_{i\in I}M_i \iff \exists i\in I: x\in M_i.\]
For \(I=\{1,2\}\) and \(M_1=A\), \(M_2=B\), these reduce to the pairwise \(A\cap B\) and \(A\cup B\) from above; the index set \(I\) is even allowed to be infinite, for example
\[\bigcap_{n\in\mathbb{N}}\left[0,\tfrac1n\right] = \{0\}\qquad\text{and}\qquad\bigcup_{n\in\mathbb{N}}\left[0,1-\tfrac1n\right] = [0,1).\]
Cartesian Product
Let \(A, B\) be sets. Then the cartesian product of these two sets is defined as
\[A\times B = \{(a, b) : a\in A, b\in B\}\]
Here, \((a, b)\) is an ordered pair, which we call a tuple, and in which the order is significant: \((a, b) \neq (b, a)\).
More generally, for \(n\geq 2\) nonempty sets \(M_1,\ldots,M_n\), the cartesian product collects all ordered \(n\)-tuples,
\[M_1\times\cdots\times M_n := \{(x_1,\ldots,x_n) : x_1\in M_1,\ldots,x_n\in M_n\},\]
of which the pair construction above is the case \(n=2\).
For finite sets, the cartesian product is naturally pictured as a grid of points, one for every combination of an element from \(A\) with an element from \(B\). For \(|A|=2\) and \(|B|=3\), this grid has \(2\cdot 3=6\) points:
Example: \(A = \{1,2\}, B=\{3\}\)
\[A\times B = \{(1, 3), (2, 3)\}\]
Since ordered pairs remember which coordinate came from which set, the cartesian product is not commutative as a set: swapping the factors relabels every pair, so in general \(A\times B\neq B\times A\). For instance,
\[\{0,1\}\times\{a,b,c\} = \{(0,a),(0,b),(0,c),(1,a),(1,b),(1,c)\}\]
while
\[\{a,b,c\}\times\{0,1\} = \{(a,0),(a,1),(b,0),(b,1),(c,0),(c,1)\},\]
two visibly different sets of pairs.
If \(A\) and \(B\) are equal, we write \(A^2\). This can be extended to \(A^3, A^4, ...\), such as, for example,
\[\mathbb{R}^3 = \mathbb{R}\times\mathbb{R}\times\mathbb{R} = \{(x, y, z): x,y,z\in\mathbb{R}\}\]