Contents
raw book

Sets

Robert Eisele

"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, such as

\[M=\{a, b, c, d, e\}\text{ or } M=\{1, 2, 3, ...\}\]

but sets can also be specified descriptively:

\[M = \{n : A(n)\}\]

With a statement \(A(n)\), such as, for example "\(n\) is even/odd" or "\(n\bmod 3=0\)".

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:

\[\emptyset:= \{\}\]

Sets can be nested arbitrarily, as for example,

\[M = \{\{1, 2, 3\}, \{4, 5\}\}\]

The cardinality of a set \(M\) is the number of elements, that are contained in the set and is denoted by vertical lines:

\[|M|\]

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\]

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\]

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\).

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\pm3, ...\}\]

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}, ...\}\]

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}\subseteq\mathbb{H}\]

Set Operations

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\}\]

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\}\]

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\}\]

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)\]

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)\]

as well as the De Morgan's laws:

\[\overline{A\cap B} = \overline{A}\cup\overline{B}\]

\[\overline{A\cup B} = \overline{A}\cap\overline{B}\]

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)\).

Example: \(A = \{1,2\}, B=\{3\}\)

\[A\times B = \{(1, 3), (2, 3)\}\]

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}\}\]