\chapter{Functions and Maps}

\section{Functions}



Authors may differentiate between a 'function' and a 'map', but they are really the same thing; 'map' tends to be used for special types of functions but in this text the definitions are synonymous. Generally the term 'function' will be used, unless the function in question is conventionally referred to as a map.

Functions were defined earlier as a special type of relation. We further study the different range of functions that exist





\begin{definition}
\emph{map} is a synonym for function; this word is favoured when the  is associated with a 'special structure' (like linear spaces, topological spaces, groups, rings, and so; don't worry if you don't know what these are).
\end{definition}

%\begin{definition}
%A \emph{homomorphism} is a map between 'special structures' that preserves the behaviour of
%\end{definition}

%\begin{definition}
%\emph{operator} is a function whose domain is a 'space'.
%\end{definition}

\begin{definition}
\emph{operation} is a function whose domain and codomain are the same set.
\end{definition}



\begin{definition}
The \emph{domain of a function} is the set of all well defined inputs for the function.
\[ f : X \to Y \implies \mathrm{Dom}(f)= \{ x \in X : f(x) \text{ is well defined}\} \]
\end{definition}

\begin{definition}
The \emph{predomain of a function} is the set representing the 'space' of which the domain is a subset of.
\[ f : X \to Y \implies X \text{ is the predomain of } f \]
\end{definition}

\begin{definition}
The \emph{codomain of a function}
\[ f : X \to Y \implies \mathrm{Codom}(f)= Y \]
\end{definition}

\begin{definition}
The \emph{image of a subset} is the set of all outputs the function has mapped to some subset of its domain.
\[ f(U) = \{ f(u) : u \in U\} \]
The \emph{image of a function} is the set of all outputs the function has mapped to its domain elements.
\[ \mathrm{Im}(f)= \{ f(x) : x \in \mathrm{Dom}(f) \} =f [\mathrm{dom}(f)] \]
\end{definition}

\begin{definition}
The \emph{preimage of a subset} is the set of all inputs the function has mapped to some subset of its image.
\[ f^{-1}(U) = \{ x \in \mathrm{dom}(f) : f(x) \in U  \}\]
\emph{Fibers} are preimages of a singleton.
	\[ f^{-1}(\{u\}) = \{ x \in \mathrm{dom}(f) : f(x) = u  \}\]
\end{definition}

The term 'range' is used ambiguously to denote either the codomain or image; from my experience it is used informally in contexts where the image is equal to the codomain. Consider the function $f : \mathbb{R} \to \mathbb{R}$ defined by $f(x)=x^3 -3x$, indeed $\mathrm{Im}(f)=\mathrm{Codom}(f)= \mathbb{R}$, hence no confusion can occur on the function's 'range'.





\section{Types of functions}

Functions can differ significantly regarding what type of objects it maps in its domain and image. Functions might also obey certain specific properties on how domain elements are mapped, however we can discuss some general properties of functions that rely on no other mathematics other than set theory.

\begin{definition}[Injective function]
An \emph{injective function} 
\[ f \text{ is injective } \iff f(x)=f(y) \iff x=y\]
\end{definition}



\begin{definition}[Surjective function]
A \emph{surjective function}
\[ f \text{ is surjective } \iff  \forall y \in \mathrm{Codom}(f) \exists x \in \mathrm{Dom}(f) [ f(x)=y ] \]
\end{definition}






\begin{definition}[Bijective function]
A \emph{bijective function} is a function that is both injective and surjective.
\[ f \text{ is bijective } \iff f \text{ is injective } \land  f \text{ is surjective } \]
\end{definition}




\begin{definition}
The \emph{composition operator} $\circ$ is a $(g \circ f)=g(f(x))$
\end{definition}



\begin{definition}
An \emph{invertible function} is a function $f : X \to Y$ such that there exists some $f^{-1} : Y \to X$ that can be well defined in the following manner.
\[ f^{-1} (f (x) ) = x\]
$f^{-1}$ is then called the \emph{inverse function of $f$}.
\end{definition}



\begin{theorem}
A function is invertible iff it is bijective.
\end{theorem}




\begin{definition}
An \emph{operation} is a function whose domain is the same set as its image $f : X \to X$
\end{definition}

\begin{definition}
	An \emph{$n$-ary function} is a function that takes $n$ arguments. $n$ is called the \emph{arity} of this function.
\end{definition}



\begin{definition}
	Given a function $f$, a \emph{fixed point} $x_0 \in \mathrm{dom}(f)$
	\[ x_{0} \text{ is a fixed point of } f \iff f(x_0)=x_0\]
\end{definition}


$f(x)=\sin (x)+x$; this function has a fixed point of $\pi$ since $f(\pi)=\pi$.



\begin{proposition}
	\[f ( \cup_{j \in J} U_j ) =  \cup_{j \in J} f(U_j ) \]
	\[f ( \cap_{j \in J} U_j ) \subseteq  \cap_{j \in J} f(U_j ) \]
\end{proposition}

\begin{proposition}
If $f$ is an injective function then the following holds.
\[f ( \cap_{j \in J} U_j ) = \cap_{j \in J} f(U_j ) \]
\end{proposition}


\section{Indexed families}

Sets are powerful objects; we've been able to develop much of mathematics through their grace. However, sets are limited in that they are unordered and can only hold one 'instance' of some mathematical object (i.e sets don't allow repetition of elements). The theory of functions can build upon the notion of a set to allow 'ordered collections' structures.

\begin{definition}
An \emph{indexed family} is a function $f : I \to X$ $(x_i)_{i \in I}$ or $(x_i)$
\begin{itemize}
\item $I$ is the index set
\item $X$ is the set of objects
\end{itemize}
\end{definition}


An indexed family is formally the same as just function, though the "idea" and notation of an indexed family is supposed to be a way to model some collection of objects where objects may repeat.



\begin{definition}[$n$-tuple (function definition)]
An \emph{$n$-tuple} or just \emph{tuple} is an indexed family with index set $\mathbb{N} \cap [1,n]$
$(x_1 ,x_2 , \hdots , x_n )$
$(x_k)^{n}_{k=1}$
$(x_k)$
\end{definition}


$n$-tuples on their own are of particular interest in combinatorics, however $n$-tuples also are useful as a means of preseting a definition for complex mathematical objects that have several components, since the $n$-tuple can list each component with its own index. 

\begin{definition}[Ordered pair]
An \emph{ordered pair} is a $2$-tuple.
\end{definition}



\begin{definition}[Sequence]
A \emph{sequence} is an indexed family with index set $\mathbb{N}$, $\mathbb{Z}$, or $\mathbb{N} \setminus \{0\}$
\end{definition}

Sequences are extremely useful across mathematics, however they are of particular importance in topology and mathematical analysis.

\begin{definition}[Subsequence]
	A \emph{subsequence of $(x_n)$} is a monotone increasing sequence $(n_k)$ where the object set is the same as the index set, composed with the sequence $(x_m)$. The result is a sequence $(x_{n_k})$
\end{definition}

The intuition is that a subsequence of $(x_n)$ is a sequence similar to the sequence $(x_n)$, except it may skip some of its indexes.


\begin{definition}[Contained Indexed family]
An index family contained within $X$ is an index family whose image is contained within $X$
\[ (x_i)_{i\in I} \subseteq X \iff \forall i \in I [ x_i \in X ] \]
\end{definition}

Note that we can similarly talk about a tuple contained within $X$, or sequence contained within $X$


\section{Tuples and sequences}

\begin{definition}[$n$-tuple (collection definition)]
An \emph{$n$-tuple} is an ordered collection of objects, where the same object may appear multiple times. The $k$th object in the tuple is called the \emph{$k$th term of the $n$-tuple}.
\end{definition}




\begin{definition}
The \emph{characteristic function of $S$ on $U$} is the function $\chi_{S} : U \to \{0,1\} $ with $S \subseteq U$ defined in the following manner.
\[ \chi_{S}(x)= \begin{cases} 1 & x \in S \\ 0 & x \notin S \end{cases} \]
\end{definition}