Sets and functions

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia
aram@unimelb.edu.au

Last updates: 8 June 2011

Sets

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\right|u\in S\text{or}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\right|u\in S\text{and}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⫋T$ 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)\right|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\right|i\in I\}$. (CHECK THIS WORDING WITH THE ORIGINAL.)

Notation: $$\begin{array}{rcl}\mathbb{Z}& =& \{\dots ,-2,-1,0,1,2,\dots \}\text{is the set of integers,}\\ {\mathbb{Z}}_{\ge 0}& =& \{0,1,2,\dots \}\text{is the set of nonnegative integers,}\\ {\mathbb{Z}}_{>0}& =& \{1,2,3,\dots \}\text{is the set of positive integers,}\\ [1,n]& =& \{1,2,\dots ,n\}\text{for each }n\in {\mathbb{Z}}_{>0},\\ ℝ& & \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⊈V$,

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

Functions

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& ⟶& T\\ s& ⟼& 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)$.

Write $f=g$ if $f$ and $g$ are equal functions.

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& ⟶& T\\ r& ⟼& 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.

Cardinality

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(ℝ\right)=\infty$, that $\mathrm{Card}\left(\mathbb{Q}\right)=\infty$, and that $\mathrm{Card}\left(ℝ\right)\ne \mathrm{Card}\left(\mathbb{Q}\right)$.

Composition of functions

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& ⟶& U\\ s& ⟼& 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& ⟶& S\\ s& ⟼& 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,$

where ${\mathrm{id}}_T$ and ${\mathrm{id}}_S$ are the identity functions on $T$ and $S$, respectively.

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

In these pictures the elements of the left column as elements of the set $S$ and the elements of the right column are the elements of the set $T$. In order to be a function the graph must have exactly one edge adjacent to each point in $S$. The function is injective if there is at most one edge adjacent to each point in $T$. The function is surjective if there is at lease one edge adjacent to each point in $T$.

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

Notes and References

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.

References

[Bou] N. Bourbaki, Theory of sets, Springer ????, MR?????.

page history