# 1.2. Sets#

In this section we will review basic concepts of set theory.

Definition 1.1 (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).

Definition 1.2 (Singleton set)

A set with only one element is known as a singleton set.

Definition 1.3 (Set equality)

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

Definition 1.4 (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)$$.

Remark 1.1

$$A = B \iff (A \subseteq B \text{ and } B \subseteq A)$$.

Definition 1.5 (Proper subset)

If $$A \subseteq B$$ and $$A \neq B$$ then $$A$$ is called a proper subset of $$B$$ denoted by $$A \subset B$$.

Definition 1.6 (Empty set)

A set without any elements is called the empty or void set. It is denoted by $$\EmptySet$$.

Definition 1.7 (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$$.

Definition 1.8 (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)$$.

Definition 1.9 (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$$.

## 1.2.1. Family of sets#

Definition 1.10 (Family of sets)

A Family of sets is a nonempty set $$\mathcal{F}$$ whose members are sets by themselves.

Definition 1.11 (Families indexed by an 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.

Example 1.1 (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.

Remark 1.2

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.

Definition 1.12 (Union of families 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.

Definition 1.13 (Intersection of families 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$$.

Proposition 1.1 (Generalized distributive laws)

$\begin{split} &\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 ) \end{split}$

Definition 1.14 (Family of 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$$.

Definition 1.15 (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.

Remark 1.3 (The subset satisfying a property)

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

Definition 1.16 (Complement of a set)

Let $$A$$ be a set. Its complement w.r.t. a fixed set $$X$$ is the set $$A^c = X \setminus A$$.

Proposition 1.2

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

## 1.2.2. Ordered Pairs and n-Tuples#

We will introduce the notion of ordered pairs informally following [88].

Definition 1.17 (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.

Property 1.1 (Equality of ordered pairs)

$(a_1, a_2) = (b_1, b_2) \iff a_1 = b_1 \text{ and } a_2 = b_2.$

A tuple [90] 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

Definition 1.18 (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.

Property 1.2 (Equality of n-tuples)

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

## 1.2.3. Cartesian Products#

In this section, we restrict our attention to finite Cartesian products. Cartesian product over infinite sets is discussed later.

Definition 1.19 (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 \}.$

Definition 1.20 (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.

Remark 1.4

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

Example 1.2 ($$A^n$$)

Let $$A = \{ 0, +1, -1\}$$.

Then $$A^2$$ is

$\begin{split} \{\\ &(0,0), (0,+1), (0,-1),\\ &(+1,0), (+1,+1), (+1,-1),\\ &(-1,0), (-1,+1), (-1,-1)\\ \}. \end{split}$

And $$A^3$$ is given by

$\begin{split} \{\\ &(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)\\ &\}. \end{split}$

## 1.2.4. Covers#

Definition 1.21 (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.

Example 1.3

1. The family $$\{[n, n+1]\}_{n \in \ZZ}$$ covers $$\RR$$.

2. The family $$\{[n-1, n]\}_{n \in \Nat}$$ covers $$\RR_{+}$$.

3. The family $$\{(n-1, n+1)\}_{n \in \Nat}$$ covers $$\RR_{++}$$.

Definition 1.22 (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 open covers.