1.1. 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 | 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 ⟺ (x \in A ⟹ x \in B)$ .

Remark 1.1

$A = B ⟺ (A \subseteq B 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 | x \in A or x \in B} .

The intersection $A \cap B$ of $A$ and $B$ is defined as

A \cap B = {x | x \in A and x \in B} .

The difference $A ∖ B$ of $A$ and $B$ is defined as

A ∖ B = {x | x \in A and x \notin 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) ∖ C = (A ∖ C) \cap (B ∖ C)$ .
$(A \cap B) ∖ C = (A ∖ C) \cap (B ∖ C)$ .

Definition 1.9 (Symmetric difference)

Symmetric difference between sets $A$ and $B$ is defined as

A Δ B = (A ∖ B) \cup (B ∖ 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.1.1. Family of sets¶

Definition 1.10 (Family of sets)

A Family of sets is a nonempty set $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} | 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.
$N$ : The sets in family are indexed by natural numbers. They are countably infinite.
$Z$ : The sets in family are indexed by integers. They are countably infinite.
$Q$ : The sets in family are indexed by rational numbers. They are countably infinite.
$R$ : There are uncountably infinite sets in the family.

Remark 1.2

If $F$ is a family of sets, then by letting $I = F$ and $A_{i} = i \forall i \in I$ , we can express $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

⋃_{i \in I} A_{i} = {x | \exists i \in I 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

⋂_{i \in I} A_{i} = {x | x \in A_{i} \forall i \in I} .

In words, every element of the union exists in every member of the family.

We will also use simpler notation $⋃ A_{i}$ , $⋂ A_{i}$ for denoting the union and intersection of family.

If $I = N = {1, 2, 3, \dots}$ (the set of natural numbers), then we will denote union and intersection by $⋃_{i = 1}^{\infty} A_{i}$ and $⋂_{i = 1}^{\infty} A_{i}$ .

Proposition 1.1 (Generalized distributive laws)

\begin{aligned} (⋃_{i \in I} A_{i}) \cap B = ⋃_{i \in I} (A_{i} \cap B) \\ (⋂_{i \in I} A_{i}) \cup B = ⋂_{i \in I} (A_{i} \cup B) \end{aligned}

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 $P (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 | 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 ∖ 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 ∖ B = A \cap B^{c}$ .
$A \subseteq B ⟺ B^{c} \subseteq A^{c}$ .
$(A \cup B)^{c} = A^{c} \cap B^{c}$ .
$(A \cap B)^{c} = A^{c} \cup B^{c}$ .

1.1.2. Ordered Pairs and n-Tuples¶

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

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}) ⟺ a_{1} = b_{1} and a_{2} = b_{2} .

A tuple [41] 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 N$ , 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}) ⟺ a_{1} = b_{1}, a_{2} = b_{2}, \dots, 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.1.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 ≜ {(a, b) | a \in A 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}) | 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{aligned} { \\ (0, 0), (0, + 1), (0, - 1), \\ (+ 1, 0), (+ 1, + 1), (+ 1, - 1), \\ (- 1, 0), (- 1, + 1), (- 1, - 1) \\ } . \end{aligned}

And $A^{3}$ is given by

\begin{aligned} { \\ (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{aligned}

1.1.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 ⋃_{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

The family ${[n, n + 1]}_{n \in Z}$ covers $R$ .
The family ${[n - 1, n]}_{n \in N}$ covers $R_{+}$ .
The family ${(n - 1, n + 1)}_{n \in N}$ covers $R_{+ +}$ .

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.

Topics in Signal Processing

Sets

Contents