Last updates: 8 June 2011

A **set** is a collection of objects which are called **elements**.
Write $s\in S$ if $s$ is an element
of a set $S$.

The **empty set** $\varnothing $ is the set with no elements.

A **subset** $T$ of a set $S$ is a set
$T$ such that if $t\in T$
then $t\in S$.
Write $T\subseteq S$ if $T$ is a subset of
$S$.

HW: Show that the emptyset is a subset of every set.

Two sets $S$ and $T$ are **equal** if
$S\subseteq T$ and $T\subseteq S$.
Write $T=S$ if the set $T$ is equal
to the set $S$.

Let $S$ and $T$ be sets. The **union** of
$S$ and $T$ is the set $S\cup T$
of all $u$ such that $u\in S$
or $u\in T$,
$$S\cup T=\left\{u\phantom{\rule{.5em}{0ex}}\right|\phantom{\rule{.5em}{0ex}}u\in S\phantom{\rule{.5em}{0ex}}\text{or}\phantom{\rule{.5em}{0ex}}u\in T\}.$$

Let $S$ and $T$ be sets. The **intersection** of
$S$ and $T$ is the set $S\cap T$
of all $u$ such that $u\in S$
and $u\in T$,
$$S\cap T=\left\{u\phantom{\rule{.5em}{0ex}}\right|\phantom{\rule{.5em}{0ex}}u\in S\phantom{\rule{.5em}{0ex}}\text{and}\phantom{\rule{.5em}{0ex}}u\in T\}.$$

Let $S$ and $T$ be sets. The sets
$S$ and $T$ are **disjoint** if
$S\cap T=\varnothing $.

Let $S$ and $T$ be sets. The sets
The set $S$ is a **proper subset** of
$T$ if $S\subseteq T$ and
$S\ne T$.
Write $S\u2acbT$ if $S$
is a proper subset of $T$.

The **product** of sets $S$ and $T$
is the set $S\times T$ of all ordered pairs
$(s,t)$ where
$s\in S$ and
$t\in T$,
$$S\times T=\left\{\right(s,t\left)\phantom{\rule{0.5em}{0ex}}\right|\phantom{\rule{0.5em}{0ex}}s\in S,t\in T\}.$$
More generally, given sets
${S}_{1},\dots ,{S}_{n}$,
the **product**
$\prod _{i}{S}_{i}$
is the set of all tuples
$({s}_{1},\dots ,{s}_{n})$ such that
${s}_{i}\in {S}_{i}$.

The elements of a set $S$
are **indexed** by the elements of a set
$I$ if each element of $S$ is labeled by a
unique element of $I$.
In this case ${s}_{i}$
for $i\in I$
will often be written to denote elements of $S$ so that
$S=\left\{{s}_{i}\phantom{\rule{0.5em}{0ex}}\right|\phantom{\rule{0.5em}{0ex}}i\in I\}$.
(CHECK THIS WORDING WITH THE ORIGINAL.)

**Notation:**
$$\begin{array}{rcl}\mathbb{Z}& =& \{\dots ,-2,-1,0,1,2,\dots \}\phantom{\rule{2em}{0ex}}\text{is the set of integers,}\\ {\mathbb{Z}}_{\ge 0}& =& \{0,1,2,\dots \}\phantom{\rule{2em}{0ex}}\text{is the set of nonnegative integers,}\\ {\mathbb{Z}}_{>0}& =& \{1,2,3,\dots \}\phantom{\rule{2em}{0ex}}\text{is the set of positive integers,}\\ [1,n]& =& \{1,2,\dots ,n\}\phantom{\rule{2em}{0ex}}\text{for each}n\in {\mathbb{Z}}_{0},\\ \mathbb{R}& & \text{is the set of real numbers, and}\\ \mathbb{Q}& & \text{is the set of complex numbers.}\end{array}$$.

**Example.**
Let $S$, $T$, $U$, and
$V$ be the sets
$S=\{1,2\}$,
$U=\{1,2\}$,
$T=\{1,2,3\}$
and
$V=\{2,3\}$.
Then

- (a) $S\subseteq U\subseteq T$,
- (b) $U\u2288V$,
- (c) $U\cup V=T$,
- (d) $U\cap V=\left\{2\right\}$, and
- (e) $S\times T=\left\{\right(1,1),(1,2),(1,3),(2,1),(2,2),(2,3\left)\right\}$.

Let $S$ and $T$ be sets. A **function**
or **map** $f:S\to T$
is given by associating to each element $s\in S$ a unique
element $f\left(s\right)\in T$.
Write
$$\begin{array}{rcl}f:S& \u27f6& T\\ s& \u27fc& f\left(s\right)\end{array}$$
Often in mathematics one will try to define a function without being explicitly sure if what has been defined
is really a function. In order to check tha ta function is **well defined** one must check
that

- (a) If $s\in S$ then $f\left(s\right)\in T$, and
- (b) if ${s}_{1}={s}_{2}$ then $f\left({s}_{1}\right)=f\left({s}_{2}\right)$.

Let $S$ and $T$ be sets. Two functions
$f:S\to T$
and $g:S\to T$
are **equal** if they satisfy

if $s\in S$ then $f\left(s\right)=g\left(s\right)$. |

Let $S$ and $T$ be sets and let
$f:S\to T$
be a functions. Let $R\subseteq S$.
The **restriction** of $f$ to $R$
is the function $f{|}_{R}$ defined by
$$\begin{array}{rcl}{f|}_{R}:S& \u27f6& T\\ r& \u27fc& f\left(r\right).\end{array}$$

A function $f:S\to T$
is **injective** if $f$ satisfies the condition

If ${s}_{1},{s}_{2}\in S$ and $f\left({s}_{1}\right)=f\left({s}_{2}\right)$ then ${s}_{1}={s}_{2}$. |

A function $f:S\to T$
is **surjective** if $f$ satisfies the condition

If $t\in T$ then there exists $s\in S$ such that $f\left(s\right)=t$. |

A function is **bijective** if it is both injective and surjective.

Let $S$ and $T$ be sets. The sets $S$
and $T$ are **isomorphic**, or **have the same cardinality**,
$\mathrm{Card}\left(S\right)=\mathrm{Card}\left(T\right)$
if there is a bijective function from $S$ to $T$.

**Notation:** Let $S$ be a set. Then $\mathrm{Card}\left(S\right)=\{\begin{array}{ll}0,& \text{if}S=\varnothing \text{,}\\ n& \text{if}\mathrm{Card}\left(S\right)=\mathrm{Card}\left(\right\{1,2,\dots ,n\left\}\right),\\ \mathrm{\infty},& \text{otherwise.}\end{array}$

Note that even in the case where $\mathrm{Card}\left(S\right)=\infty $ and $\mathrm{Card}\left(T\right)=\infty $ it may be that $\mathrm{Card}\left(S\right)\ne \mathrm{Card}\left(T\right)$.

Let $S$ be a set.

- The set $S$ is
**finite**if $\mathrm{Card}\left(S\right)\ne \infty $. - The set $S$ is
**infinite**if $S$ is not finite. - The set $S$ is
**countable**if $S$ is finite or $\mathrm{Card}\left(S\right)=\mathrm{Card}\left({\mathbb{Z}}_{>0}\right)$. - The set $S$ is
**countably infinite**if $S$ is countable and not finite. - The set $S$ is
**uncountable**if $S$ is not countable.

HW: Show that $\mathrm{Card}\left(\mathbb{R}\right)=\infty $, that $\mathrm{Card}\left(\mathbb{Q}\right)=\infty $, and that $\mathrm{Card}\left(\mathbb{R}\right)\ne \mathrm{Card}\left(\mathbb{Q}\right)$.

Let $f:S\to T$
and $g:T\to U$
be functions. The **composition** of $f$ and $g$
is the function $g\circ f$ given by
$$\begin{array}{rcl}g\circ f:S& \u27f6& U\\ s& \u27fc& g\left(f\right(s\left)\right).\end{array}$$

Let $S$ be a set. The **identity map** on $S$
is the function given by
$$\begin{array}{rcl}{\mathrm{id}}_{S}:S& \u27f6& S\\ s& \u27fc& s.\end{array}$$

Let $f:S\to T$
be a function. The **inverse function** to $f$ is a
function ${f}^{-1}:T\to S$ such that

$f\circ {f}^{-1}={\mathrm{id}}_{T}$ and ${f}^{-1}\circ f={\mathrm{id}}_{S},$ |

Let $f:S\to T$ be a function. An inverse function to $f$ exists if and only if $f$ is bijective.

**Examples.**
It is useful to visualise a function
$f:S\to T$
as a graph with edges
$(s,f(s\left)\right)$
connecting elements $s\in S$ and
$f\left(s\right)\in T$.
With this idea in mind we have the following examples.

(a) a function |
(b) not a function |
(c) not a function |

(d) an injective function |
(e) a surjective function |
(f) a bijective function |

Representing functions as graphs, the identity function ${\mathrm{id}}_{S}$ looks like

(a) the identity function ${\iota}_{S}$ |

In the pictures below, if the left graph is a pictorial representation of a function $f:S\to T$ then the inverse function to $f$, ${f}^{-1}:T\to S$, is represented by the graph on the right; the graph for ${f}^{-1}$ is the mirror-image of the graph for $f$.

(b) the function $f$ |
(c) the function ${f}^{-1}$ |

Graph (d) below, represents a function $g:S\to T$ which is not bijective (it is neither injective nor surjective). The inverse function to $g$ does not exist in this case; graph (e) of a possible candidate, is not the graph of a function.

(d) the function $g$ |
(e) not a function |

Almost everything in mathematics is built from sets and functions. Groups, rings, fields, vector spaces, ... are all sets with specific functions which have special properties. In the society of mathematics, sets and functions are the individuals and the fascination is the way that the individuals, each one different from the others, interact.

The set of subsets of a set $S$ forms a partially ordered set under inclusion $\subseteq $. The union $\cup $ and intersection $\cap $ make the set of subsets of $S$ into a Boolean algebra. Functions are the morphisms in the category 𝒮et of sets and products are products in the category 𝒮et.