# Sets
In this section we will review basic concepts of set theory.
```{index} Set
```
````{prf:definition} Set
:label: def-set
A *set* is a collection of objects viewed as a single entity.
````
It is just a working definition which we will use in this book.
* Sets are denoted by capital letters.
* Objects in a set are called *members*, *elements* or *points*.
* $x \in A$ means that element $x$ belongs to set $A$.
* $x \notin A$ means that $x$ doesn't belong to set $A$.
* $\{ a,b,c\}$ denotes a set with elements $a$, $b$, and $c$. Their order
is not relevant.
* $\{ x \ST \text{property}(x) \}$ is a set of elements which satisfy a given property
(a predicate or a condition or a rule).
```{index} Set; singleton
```
````{prf:definition} Singleton set
:label: def-singleton-set
A set with only one element is known as a *singleton* set.
````
```{index} Set; equality
```
````{prf:definition} Set equality
:label: def-equal-sets
Two sets $A$ and $B$ are said to be equal ($A=B$) if they have precisely the same elements. i.e.
if $x \in A$ then $x \in B$ and vice versa. Otherwise, they are not equal ($A \neq B$).
````
```{index} Subset
```
````{prf:definition} Subset
:label: def-subset
A set $A$ is called a *subset* of another set $B$ if every element of $A$ belongs to $B$.
This is denoted as $A \subseteq B$. Formally $A \subseteq B \iff (x \in A \implies x \in B)$.
````
````{prf:remark}
:label: rem-set-subset-equal
$A = B \iff (A \subseteq B \text{ and } B \subseteq A)$.
````
```{index} Subset; proper
```
````{prf:definition} Proper subset
:label: def-proper-subset
If $A \subseteq B$ and $A \neq B$ then $A$ is called a *proper subset* of $B$ denoted by $A \subset B$.
````
```{index} Set; empty
```
````{prf:definition} Empty set
:label: def-empty-set
A set without any elements is called the *empty* or *void* set. It is denoted by $\EmptySet$.
````
```{index} Set; operations
```
````{prf:definition} Set operations
:label: def-set-operations
We define fundamental set operations below
* The *union* $A \cup B$ of $A$ and $B$ is defined as
$$
A \cup B = \{ x \ST x \in A \text{ or } x \in B\}.
$$
* The *intersection* $A \cap B$ of $A$ and $B$ is defined as
$$
A \cap B = \{ x \ST x \in A \text{ and } x \in B\}.
$$
* The *difference* $A \setminus B$ of $A$ and $B$ is defined as
$$
A \setminus B = \{ x \ST x \in A \text{ and } x \notin B\}.
$$
Note that, we often use the notation $A B$ for the intersection of
$A$ and $B$.
````
```{index} Set; disjoint
```
````{prf:definition} Disjoint sets
:label: def-disjoint-sets
$A$ and $B$ are called *disjoint* if $A \cap B = \EmptySet$.
````
Some useful identities
* $(A \cup B) \cap C = (A \cup C) \cap (B \cup C)$.
* $(A \cap B) \cup C = (A \cap C) \cup (B \cap C)$.
* $(A \cup B) \setminus C = (A \setminus C) \cap (B \setminus C)$.
* $(A \cap B) \setminus C = (A \setminus C) \cap (B \setminus C)$.
```{index} Set; symmetric difference
```
````{prf:definition} Symmetric difference
:label: def-symmetric-difference
*Symmetric difference* between sets $A$ and $B$ is defined as
$$
A \Delta B = ( A \setminus B) \cup (B \setminus A)
$$
i.e. the elements which are in $A$ but not in $B$ and the elements which are in $B$ but not in $A$.
````
## Family of sets
```{index} Family of sets
```
````{prf:definition} Family of sets
:label: def-set-family
A *Family of sets* is a nonempty set $\mathcal{F}$ whose members are sets by themselves.
````
```{index} Family of sets; index set
```
````{prf:definition} Families indexed by an index set
:label: def-index-set
If for each element $i$ of a non-empty set $I$,
a subset $A_i$ of a fixed set $X$ is assigned,
then $\{ A_i\}_{i \in I}$ ( or $\{ A_i \ST i \in I\}$ or simply $\{A_i\}$
denotes the family whose members are the sets
$A_i$.
The set $I$ is called the *index set* of the family and
its members are known as *indices*.
````
````{prf:example} Index sets
:label: ex-index-sets
Following are some examples of index sets
* $\{1,2,3,4\}$: the family consists of only 4 sets.
* $\{0,1,2,3\}$: the family consists again of only 4 sets but indices are different.
* $\Nat$: The sets in family are indexed by natural numbers. They are
countably infinite.
* $\ZZ$: The sets in family are indexed by integers. They are countably
infinite.
* $\QQ$: The sets in family are indexed by rational numbers. They are
countably infinite.
* $\RR$: There are uncountably infinite sets in the family.
````
````{prf:remark}
:label: rem-st-indexing-family-self
If $\mathcal{F}$ is a family of sets,
then by letting $I=\mathcal{F}$ and
$A_i = i \quad \forall i \in I$,
we can express $\mathcal{F}$ in the form of
$\{ A_i\}_{i \in I}$.
In other words, a family of sets can index itself.
````
```{index} Family of sets; union
```
````{prf:definition} Union of families of sets
:label: def-union-family-of-sets
Let $\{ A_i\}_{i \in I}$ be a family of sets. The *union* of the family is defined to be
$$
\bigcup_{i\in I} A_i = \{ x \ST \exists i \in I \text{ such that } x \in A_i\}.
$$
In words, every element of the union exists in one of the members of the family.
````
```{index} Family of sets; intersection
```
````{prf:definition} Intersection of families of sets
:label: def-intersection-family-of-sets
Let $\{ A_i\}_{i \in I}$ be a family of sets. The *intersection* of the family is defined to be
$$
\bigcap_{i \in I} A_i = \{ x \ST x \in A_i \quad \forall i \in I\}.
$$
In words, every element of the union exists in every member of the family.
````
We will also use simpler notation $\bigcup A_i$, $\bigcap A_i$
for denoting the union and intersection of family.
If $I =\Nat = \{1,2,3,\dots\}$ (the set of natural numbers),
then we will denote
union and intersection by $\bigcup_{i=1}^{\infty}A_i$ and $\bigcap_{i=1}^{\infty}A_i$.
````{prf:proposition} Generalized distributive laws
:label: res-st-generalized-distributive-laws
$$
&\left ( \bigcup_{i\in I} A_i \right ) \cap B = \bigcup_{i\in I} \left ( A_i \cap B \right )\\
&\left ( \bigcap_{i\in I} A_i \right ) \cup B = \bigcap_{i\in I} \left ( A_i \cup B \right )
$$
````
```{index} Family of sets; pairwise disjoint
```
````{prf:definition} Family of pairwise disjoint sets
:label: def-pairwise-disjoint-sets
A family of sets $\{ A_i\}_{i \in I}$ is called *pairwise disjoint*
if for each pair $i, j \in I$
the sets $A_i$ and $A_j$ are disjoint i.e. $A_i \cap A_j = \EmptySet$.
````
```{index} Power set
```
````{prf:definition} Power set
:label: def-power-set
The set of all subsets of a set $A$ is called its *power set* and is denoted by
$\Power (A)$.
````
In the following $X$ is a big fixed set (sort of a frame of reference) and
we will be considering different subsets of it.
````{prf:remark} The subset satisfying a property
:label: res-st-property-predicate
Let $X$ be a fixed set. If $P(x)$ is a property well defined for all $x \in X$, then
the set of all $x$ for which $P(x)$ is true is denoted by $\{x \in X \ST P(x)\}$.
````
```{index} Set; complement
```
````{prf:definition} Complement of a set
:label: def-complement-set
Let $A$ be a set. Its *complement* w.r.t. a fixed set $X$ is the set $A^c = X \setminus A$.
````
```{prf:proposition}
:label: res-st-complement-properties
Let $X$ be a fixed set, $A, B$ be subsets of $X$ and $A^c$ denote the
complement of some subset $A$ of $X$ w.r.t. $X$.
We have the following results:
* $(A^c)^c = A$.
* $A \cap A^c = \EmptySet$.
* $A \cup A^c = X$.
* $A\setminus B = A \cap B^c$.
* $A \subseteq B \iff B^c \subseteq A^c$.
* $(A \cup B)^c = A^c \cap B^c$.
* $(A \cap B)^c = A^c \cup B^c$.
```
## Ordered Pairs and n-Tuples
We will introduce the notion of *ordered pairs* informally
following {cite}`wiki:ordered-pair`.
```{index} Ordered pair
```
```{prf:definition} Ordered pair
:label: def-st-ordered-pair
For any two objects a and b, the *ordered pair* (a, b) is a
notation specifying the two objects a and b, in that order.
```
```{prf:property} Equality of ordered pairs
:label: res-st-ordered-pair-equality
$$
(a_1, a_2) = (b_1, b_2) \iff a_1 = b_1 \text{ and } a_2 = b_2.
$$
```
A tuple {cite}`wiki:tuple` is a finite ordered list of elements.
An n-tuple is a sequence (ordered list) of $n$ elements where
$n$ is a non-negative integer.
* A tuple may contain multiple instances of the same element.
* Tuple elements are ordered.
* A tuple has a finite number of elements.
Following is an informal definition
```{prf:definition} n-tuple
:label: def-st-n-tuple
For any $n$ objects $a_1, a_2, \dots, a_n$ where $n \in \Nat$, the
*n-tuple* $(a_1, a_2, \dots, a_n)$ is a notation specifying the
$n$ objects in that order.
The 0-tuple $()$ is an tuple containing $0$ elements.
```
```{prf:property} Equality of n-tuples
:label: res-st-n-tuple-equality
$$
(a_1, a_2, \dots, a_n) = (b_1, b_2, \dots, b_n) \iff a_1 = b_1, a_2 = b_2, \dots, \text{ and } a_n = b_n.
$$
```
In other words, $(a_1,\dots, a_n) = (b_1,\dots,b_n)$ if and only if
$a_i = b_i \Forall i = 1,\dots,n$.
## Cartesian Products
In this section, we restrict our
attention to finite Cartesian products.
Cartesian product over infinite sets is
discussed later.
```{prf:definition} Binary Cartesian product
:label: def-st-binary-cartesian-product
The *Cartesian product* of the two sets $A$ and $B$ denoted
by $A \times B$ is the set of all possible ordered pairs
of elements where the first element is from $A$ and the second
is from $B$:
$$
A \times B \triangleq \{ (a, b) \ST a \in A \text{ and } b \in B \}.
$$
```
```{prf:definition} Finite Cartesian product
:label: def-st-finite-cartesian-product
Similarly, the Cartesian product of a finite family of
sets $(A_1, \dots, A_n)$ is written as
$A_1 \times \dots \times A_n$ and its members are
denoted as $n$-tuples, i.e.:
$$
A_1 \times \dots \times A_n = \{(a_1, \dots, a_n) \ST a_i \in A_i \Forall
i = 1,\dots,n\}.
$$
The sets $A_i$ may be same of different.
```
```{prf:remark}
:label: res-st-n-th-power-of-set
If $A_1 = A_2 = \dots = A_n = A$, then it is standard to write
$A_1 \times \dots \times A_n$ as $A^n$.
```
```{prf:example} $A^n$
:label: ex-st-a-n-1
Let $A = \{ 0, +1, -1\}$.
Then $A^2$ is
$$
\{\\
&(0,0), (0,+1), (0,-1),\\
&(+1,0), (+1,+1), (+1,-1),\\
&(-1,0), (-1,+1), (-1,-1)\\
\}.
$$
And $A^3$ is given by
$$
\{\\
&(0,0,0), (0,0,+1), (0,0,-1),\\
&(0,+1,0), (0,+1,+1), (0,+1,-1),\\
&(0,-1,0), (0,-1,+1), (0,-1,-1),\\
&(+1,0,0), (+1,0,+1), (+1,0,-1),\\
&(+1,+1,0), (+1,+1,+1), (+1,+1,-1),\\
&(+1,-1,0), (+1,-1,+1), (+1,-1,-1),\\
&(-1,0,0), (-1,0,+1), (-1,0,-1),\\
&(-1,+1,0), (-1,+1,+1), (-1,+1,-1),\\
&(-1,-1,0), (-1,-1,+1), (-1,-1,-1)\\
&\}.
$$
```
## Covers
```{prf:definition} Cover
:label: def-st-cover
A family $\{ A_i \}_{i \in I}$ of subsets of $X$ is said to *cover* a set
$A$ if
$$
A \subseteq \bigcup_{i \in I} A_i.
$$
Here $I$ is an index set indexing the sets in the family. $I$
could be finite, countable or uncountable.
```
```{prf:example}
:label: ex-st-cover-1
1. The family $\{[n, n+1]\}_{n \in \ZZ}$ covers $\RR$.
1. The family $\{[n-1, n]\}_{n \in \Nat}$ covers $\RR_{+}$.
1. The family $\{(n-1, n+1)\}_{n \in \Nat}$ covers $\RR_{++}$.
```
```{prf:definition} Subcover
:label: def-st-subcover
If a subfamily of a cover $\{ A_i \}_{i \in I}$ of $A$ also covers
$A$, then the subfamily is called a *subcover*.
```
* Covers play an important role in the theory of
metric spaces. See {prf:ref}` open covers `.