# Sets

## Contents

# 1.2. Sets#

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

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

(Singleton set)

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

(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\)).

(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)\).

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

(Proper subset)

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

(Empty set)

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

(Set operations)

We define fundamental set operations below

The

*union*\(A \cup B\) of \(A\) and \(B\) is defined as

The

*intersection*\(A \cap B\) of \(A\) and \(B\) is defined as

The

*difference*\(A \setminus B\) of \(A\) and \(B\) is defined as

Note that, we often use the notation \(A B\) for the intersection of \(A\) and \(B\).

(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)\).

(Symmetric difference)

*Symmetric difference* between sets \(A\) and \(B\) is defined as

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#

(Family of sets)

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

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

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

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.

(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

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

(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

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

(Generalized distributive laws)

(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\).

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

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

(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\).

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

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

(Equality of ordered pairs)

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

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

(Equality of n-tuples)

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.

(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\):

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

The sets \(A_i\) may be same of different.

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

\(A^n\))

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

Then \(A^2\) is

And \(A^3\) is given by

## 1.2.4. Covers#

(Cover)

A family \(\{ A_i \}_{i \in I}\) of subsets of \(X\) is said to *cover* a set
\(A\) if

Here \(I\) is an index set indexing the sets in the family. \(I\) could be finite, countable or uncountable.

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

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

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

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