Sets

A set is a collection of distinct objects. The class of CS120 is a set. So is the group of all first year students at the IITD. We will use the notation $\{a,b,c\}$ to denote the collection of the objects $a,b$ and $c$. The elements in a set are not ordered in any fashion. Thus the set $\{a,b,c\}$ is the same as the set $\{b,a,c\}$. Two sets are equal if they contain exactly the same elements.

We can describe a set either by enumerating all the elements of the set or by stating the properties that uniquely characterize the elements of the set. Thus, the set of all even positive integers not larger than 10 can be described either as $S = \{2,4,6,8,10\}$ or, equivalently, as $S = \{x \mid$   $\mbox{$x$\ is an even positive integer not larger than 10}$$\}$

A set can have another set as one of its elements. For example, the set $A = \{\{a,b,c\},d\}$ contains two elements $\{a,b,c\}$ and $d$; and the first element is itself a set.

We will use the notation $x \in S$ to denote that $x$ is an element of (``belongs to'') the set $S$.

A set $A$ is a subset of another set $B$, denoted as $A \subseteq B$, if $x \in B$ whenever $x \in A$.

An empty set is one which contains no elements and we will denote it with the symbol $\phi$. For example, let $S$ be the set of all students who fail the course CS120. $S$ might turn out to be empty (hopefully; if everybody studies hard). By definition, the empty set $\phi$ is a subset of all sets. We will also assume an Universe of discourse $\cal U$, and every set that we will consider is a subset of ${\cal U}$. Thus we have

1. $\phi \subseteq A$ for any set $A$
2. $A \subseteq {\cal U}$ for any set $A$

The union of two sets $A$ and $B$, denoted $A \cup B$ is the set whose elements are exactly the elements of either $A$ or $B$ (or both). The intersection of two sets $A$ and $B$, denoted $A \cap B$ is the set whose elements are exactly the elements of both $A$ and $B$. Thus, we have

1. $S = A \cup B = \{x \mid (x \in A)$    or $(x \in B)\}$
2. $S = A \cap B = \{x \mid (x \in A)$    and $(x \in B)\}$

We also have, for any set $A$

1. $A \cup \phi = A$
2. $A \cup {\cal U} = {\cal U}$
3. $A \cap \phi = \phi$
4. $A \cap {\cal U} = A$

The Cartesian product of two sets $A$ and $B$, denoted by $A \times B$, is the set of all ordered pairs $(a,b)$ such that $a \in A$ and $b \in B$. Thus,

$$A \times B = \{(a,b) \mid (a \in A)$$    and $$(b \in B)\}$$

$A^n$ is the set of all ordered $n$-tuples $(a_1,a_2,\ldots,a_n)$ such that $a_i \in A$ for all $i$. i.e.,

$$A^n = \underbrace{A \times A \times \cdots \times A}_{n \mbox{ times}}$$

We will use the following notation to denote some standard sets:

The set of Natural Numbers

^2.1 $\mathbb{N}= \{0,1,2,\ldots\}$

The set of positive integers

$\mathbb{P}= \{1,2,3,\ldots\}$

The set of integers

$\mathbb{Z}= \{\ldots,-2,-1,0,1,2,\ldots\}$

The set of real numbers

$\mathbb{R}$

The Boolean set

$\mathbb{B}= \{false,true\}$