The Analysis of Data, volume 1

Set Theory: Basic Definitions

A.1. Basic Definitions

This chapter describes set theory, a mathematical theory that underlies all of modern mathematics.
Definition A.1.1. A set is an unordered collection of elements.

Sets may be described by listing their elements between curly braces, for example $\{1,2,3\}$ is the set containing the elements 1, 2, and 3. Alternatively, we an describe a set by specifying a certain condition whose elements satisfy, for example $\{x: x^2=1\}$ is the set containing the elements $1$ and $-1$ (assuming $x$ is a real number).

We make the following observations.

Definition A.1.2. If $a$ is an element in a set $A$, we write $a\in A$. If $a$ is not an element of $A$, we write $a\not\in A$. The empty set, denoted by $\emptyset$ or $\{\}$, does not contain any element.
Definition A.1.3. A set $A$ with a finite number of elements is called a finite set and its size (number of elements) is denoted by $|A|$. A set with an infinite number of elements is called an infinite set.
Definition A.1.4. We denote $A\subset B$ if all elements in $A$ are also in $B$. We denote $A=B$ if $A\subset B$ and $B\subset A$, implying that the two sets are identical. The difference between two sets $A\setminus B$ is the set of elements in $A$ but not in $B$. The complement of a set $A$ with respect to a set $\Omega$ is $A^c=\Omega\setminus A$ (we may omit the set $\Omega$ if it is obvious from context). The symmetric difference between two sets $A,B$ is \[ A\triangle B = \{x: x\in A\setminus B \text{ or } x\in B\setminus A\}.\]
Example A.1.1. We have $\{1,2,3\}\setminus \{3,4\}=\{1,2\}$ and $\{1,2,3\}\triangle \{3,4\}=\{1,2,4\}$. Assuming $\Omega=\{1,2,3,4,5\}$, we have $\{1,2,3\}^c=\{4,5\}$.

In many cases we consider multiple sets indexed by a finite or infinite set. For example $U_{\alpha}, \alpha\in A$ represents multiple sets, one set for each element of $A$.

Example A.1.2. Below are three examples of multiple sets, $U_{\alpha}, \alpha\in A$. The first example shows two sets: $\{1\}$ and $\{2\}$. The second example shows multiple sets: $\{1,-1\}$, $\{2,-2\}$, $\{3,-3\}$, and so on. The third example shows multiple sets, each containing all real numbers between two consecutive natural numbers. \begin{align*} U_i&=\{i\},& i&\in A=\{1,2\},\\ U_i&=\{i,-i\},& i&\in A=\mathbb{N}=\{1,2,3,\ldots\},\\ U_{\alpha}&=\{\alpha+r: 0\leq r \leq 1\}, & \alpha&\in A=\mathbb{N}=\{1,2,3,\ldots\}. \end{align*}
Definition A.1.5. For multiple sets $U_{\alpha}, \alpha\in A$ we define the union and intersection operations as follows: \begin{align*} \bigcup_{\alpha\in A} U_{\alpha} & =\{u: u\in U_{\alpha} \text{ for one or more } \alpha\in A\}\\ \bigcap_{\alpha\in A} U_{\alpha} & =\{u: u\in U_{\alpha} \text{ for all } \alpha\in A\}. \end{align*}

Figure A.1.1 below illustrates these concepts in the case of two sets $A,B$ with a non-empty intersection.

two sets with non-empty intersection

Figure 1.2.1: Two circular sets $A,B$, their intersection $A\cap B$ (gray area with horizontal and vertical lines), and their union $A\cup B$ (gray area with either horizontal or vertical lines or both). The set $\Omega\setminus (A\cup B)=(A\cup B)^c=A^c\cap B^c$ is represented by white color.

Definition A.1.6. The sets $U_{\alpha}, \alpha\in A$ are mutually disjoint if $\cap_{\alpha\in A}U_{\alpha}=\emptyset$ and are pairwise disjoint if $\alpha\neq\beta$ implies $U_{\alpha}\cap U_{\beta}=\emptyset$. A union of pairwise disjoint sets $U_{\alpha}$, $\alpha\in A$ is denoted by $\uplus_{\alpha\in A} U_{\alpha}$.
Example A.1.3. \begin{align*} \{a,b,c\}\cap\{c,d,e\}&=\{c\}\\ \{a,b,c\}\cup\{c,d,e\}&=\{a,b,c,d,e\}\\ \{a,b,c\}\setminus\{c,d,e\}&=\{a,b\}. \end{align*}
Example A.1.4. If $A_1=\{1\}, A_2=\{1,2\}, A_3=\{1,2,3\}$ we have \begin{align*} \{A_i: i\in \{1,2,3\}\}&=\{\{1\},\{1,2\},\{1,2,3\}\}\\ \bigcup_{i\in\{1,2,3\}} A_i &= \{1,2,3\}\\ \bigcap_{i\in\{1,2,3\}} A_i &= \{1\}. \end{align*}

The properties below are direct consequences of the definitions above.

Proposition A.1.1. For all sets $A,B,C\subset \Omega$,
  1. Union and intersection are commutative and distributive: \begin{align*} A\cup B=B\cup A, \quad (A\cup B)\cup C = A\cup (B\cup C)\\ A\cap B=B\cap A, \quad (A\cap B)\cap C = A\cap (B\cap C) \end{align*}
  2. $(A^c)^c=A, \quad \emptyset^c=\Omega,\quad \Omega^c=\emptyset$
  3. $\emptyset\subset A$
  4. $A\subset A$
  5. $A\subset B$ and $B\subset C$ implies $A\subset C$
  6. $A\subset B$ if and only if $B^c\subset A^c$
  7. $A\cup A=A=A\cap A$
  8. $A\cup\Omega = \Omega, \quad A\cap\Omega = A$
  9. $A\cup\emptyset = A, \quad A\cap\emptyset = \emptyset$.
Definition A.1.7. The power set of a set $A$ is the set of all subsets of $A$, including the empty set $\emptyset$ and $A$. It is denoted by $2^A$.
Proposition A.1.2. If $A$ is a finite set then \[ |2^A| = 2^{|A|}.\]
Proof. We can describe each element of $2^A$ by a list of $|A|$ 0 or 1 digits (1 if the corresponding element is selected and 0 otherwise). The proposition follows since there are $2^{|A|}$ such lists (see Proposition 1.6.1).
Example A.1.5. \begin{align*} 2^{\{a,b\}} &= \{\emptyset,\{a,b\},\{a\},\{b\}\}\\ |2^{\{a,b\}}|&=4\\ \sum_{A\in2^{\{a,b\}}} |A| &= 0+2+1+1= 4. \end{align*}

The R package sets is convenient for illustrating basic concepts. For example, the code below examines the power set of three different finite sets.

A = set("a", "b", "c")
## {{}, {"a"}, {"b"}, {"c"}, {"a", "b"}, {"a",
##  "c"}, {"b", "c"}, {"a", "b", "c"}}
A = set("a", "b", set("a", "b"))
## {{}, {"a"}, {"b"}, {{"a", "b"}}, {"a", "b"},
##  {"a", {"a", "b"}}, {"b", {"a", "b"}}, {"a",
##  "b", {"a", "b"}}}
A = set(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
length(2^A)  # = 2^10
## [1] 1024
Proposition A.1.3. (Distributive Law of Sets) \begin{align*} \left(\bigcup_{\alpha\in Q} A_{\alpha}\right) \bigcap C &= \bigcup_{\alpha\in Q} \left(A_{\alpha} \bigcap C\right)\\ \left(\bigcap_{\alpha\in Q} A_{\alpha}\right) \bigcup C &= \bigcap_{\alpha\in Q} \left(A_{\alpha} \bigcup C\right). \end{align*}
Proof. We prove the first statement for the case of $|Q|=2$. The proof of the second statement is similar, and the general case is a straightforward extension.

We prove the set equality $U=V$ by showing $U\subset V$ and $V\subset U$. Let $x$ belong to the set $(A\cup B)\cap C$. This means that $x$ is in $C$ and also in either $A$ or $B$, which implies $x\in (A\cap C)\cup(B\cap C)$. On the other hand, if $x$ belongs to $(A\cap C)\cup(B\cap C)$, $x$ is in $A\cap C$ or in $B\cap C$. Therefore $x\in C$ and also $x$ is in either $A$ or $B$, implying that $x\in (A\cup B)\cap C$.

Proposition A.1.4. \begin{align*} S\setminus \bigcup_{\alpha\in Q} A_{\alpha} &= \bigcap_{\alpha\in Q} (S\setminus A_{\alpha})\\ S\setminus \bigcap_{\alpha\in Q} A_{\alpha} &= \bigcup_{\alpha\in Q} (S\setminus A_{\alpha}). \end{align*}
Proof. We prove the first result. The proof of the second result is similar. Let $x\in S\setminus \cup_{\alpha\in Q} A_{\alpha}$. This implies that $x$ is in $S$ but not in any of the $A_{\alpha}$ sets, which implies $x\in S\setminus A_{\alpha}$ for all $\alpha$, and therefore $x\in \cap_{\alpha\in Q} (S\setminus A_{\alpha})$. On the other hand, if $x\in \cap_{\alpha\in Q} (S\setminus A_{\alpha})$, then $x$ is in each of the $S\setminus A_{\alpha}$ sets. Therefore $x$ is in $S$ but not in any of the $A_{\alpha}$ sets, hence $x\in S\setminus \cup_{\alpha\in Q} A_{\alpha}$.
Corollary A.1.1 (De-Morgan's Law). \begin{align*} \left(\bigcup_{\alpha\in Q} A_{\alpha}\right)^c &= \bigcap_{\alpha\in Q} A_{\alpha}^c\\ \left(\bigcap_{\alpha\in Q} A_{\alpha}\right)^c &= \bigcup_{\alpha\in Q} A_{\alpha}^c. \end{align*}
Proof. This is a direct corollary of the previous proposition with $S=\Omega$.
Definition A.1.8. We define the sets of all natural numbers, integers, and rational numbers as follows: \begin{align*} \mathbb{N} &= \{1,2,3,\ldots\}\\ \mathbb{Z} &= \{\ldots,-1,0,1,\ldots\}\\ \mathbb{Q} &= \{p/q:p\in\mathbb{Z},q\in\mathbb{Z}\setminus\{0\}\}. \end{align*} The set of real numbers is denoted by $\R$.

One way to rigorously define the set of real numbers is as the completion of the rational numbers. The details may be found in standard real analysis textbooks, for example (Rudin, 1976). We do not pursue this formal definition here.

Definition A.1.9. We denote the closed interval, the open interval and the two types of half-open intervals between $a,b\in\R$ as \begin{align*} [a,b] &= \{x\in\R : a \leq x \leq b \}\\ (a,b) &= \{x\in\R : a < x < b \}\\ \end{align*} \begin{align*} [a,b) &= \{x\in\R : a \leq x < b \}\\ (a,b] &= \{x\in\R : a < x \leq b \}. \end{align*}
Example A.1.6. \begin{align*} \bigcup_{n\in\mathbb{N}}[0,n/(n+1))&=[0,1),\\ \bigcap_{n\in\mathbb{N}} [0,n/(n+1))&=[0,1/2). \end{align*}
Definition A.1.10. The Cartesian product of two sets $A$ and $B$ is \[A\times B=\{(a,b):a\in A,b\in B\}.\] In a similar way we define the Cartesian product of $n\in\mathbb{N}$ sets. The repeated Cartesian product of the same set, denoted as \[A^d= A\times \cdots\times A, \qquad d\in\mathbb{N},\] is the set of $d$-tuples or $d$-dimensional vectors whose components are elements in $A$.
Example A.1.7. $\R^d$ is the set of all $d$ dimensional vectors whose components are real numbers.
Definition A.1.11. A relation $R$ on a set $A$ is a subset of $A\times A$, or in other words a set of pairs of elements in $A$. If $(a,b)\in R$ we denote $a\sim b$ and if $(a,b)\not\in R$ we denote $a\not\sim b$. A relation is reflexive if $a\sim a$ for all $a\in A$. It is symmetric if $a\sim b$ implies $b\sim a$ for all $a,b\in A$. It is transitive if $a\sim b$ and $b\sim c$ implies $a\sim c$ for all $a,b,c\in A$. An equivalence relation is a relation that is reflexive, symmetric, and transitive.
Example A.1.8. Consider relation 1 where $a\sim b$ if $a\leq b$ over $\mathbb{R}$ and relation 2 where $a\sim b$ if $a=b$ over $\mathbb{Z}$. Relation 1 is reflexive and transitive but not symmetric. Relation 2 is reflexive, symmetric, and transitive and is therefore an equivalence relation.
Definition A.1.12. The sets $U_{\alpha}, \alpha\in A$ form a partition of $U$ if \[ \biguplus_{\alpha\in A} U_{\alpha} = U.\] In other words, the union of the pairwise disjoint sets $U_{\alpha}, \alpha\in A$ is $U$. The sets $U_{\alpha}$ are called equivalence classes.

An equivalence relation $\sim$ on $A$ induces a partition of $A$ as follows: $a\sim b$ if and only if $a$ and $b$ are in the same equivalence class.

Example A.1.9. Consider the set $A$ of all cities and the relation $a\sim b$ if the cities $a,b$ are in the same country. This relation is reflexive, symmetric, and transitive, and therefore is an equivalence relation. This equivalence relation induces a partition of all cities into equivalence classes consisting of all cities in the same country. The number of equivalence classes is the number of countries.