$
\def\P{\mathsf{P}}
\def\R{\mathbb{R}}
\def\defeq{\stackrel{\tiny\text{def}}{=}}
\def\c{\,|\,}
$

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.

- There is no importance to the order in which the elements of a set appear. Thus $\{1,2,3\}$, is the same set as $\{3,2,1\}$.
- An element may either appear in a set or not, but it may not appear more than one time.
- Sets are typically denoted by an uppercase letter, for example $A$ or $B$.
- It is possible that the elements of a set are sets themselves, for example $\{1,2,\{3,4\}\}$ is a set containing three elements (two scalars and one set). We typically denote such sets with calligraphic notation, for example $\mathcal{U}$.

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$.

Figure A.1.1 below illustrates these concepts in the case of two sets $A,B$ with a 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.

The properties below are direct consequences of the definitions above.

- 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*}
- $(A^c)^c=A, \quad \emptyset^c=\Omega,\quad \Omega^c=\emptyset$
- $\emptyset\subset A$
- $A\subset A$
- $A\subset B$ and $B\subset C$ implies $A\subset C$
- $A\subset B$ if and only if $B^c\subset A^c$
- $A\cup A=A=A\cap A$
- $A\cup\Omega = \Omega, \quad A\cap\Omega = A$
- $A\cup\emptyset = A, \quad A\cap\emptyset = \emptyset$.

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

library(sets) A = set("a", "b", "c") 2^A

## {{}, {"a"}, {"b"}, {"c"}, {"a", "b"}, {"a", ## "c"}, {"b", "c"}, {"a", "b", "c"}}

A = set("a", "b", set("a", "b")) 2^A

## {{}, {"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

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$.

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.

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.