%% LyX 1.3 created this file. For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[english]{amsbook}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\setlength\parskip{\smallskipamount}
\setlength\parindent{0pt}
\usepackage{graphicx}
\usepackage{amssymb}
\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\newcommand{\noun}[1]{\textsc{#1}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
\numberwithin{section}{chapter}
\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\numberwithin{equation}{section} %% Comment out for sequentially-numbered
\numberwithin{figure}{section} %% Comment out for sequentially-numbered
\theoremstyle{definition}
\newtheorem*{example*}{Exemple}
\theoremstyle{definition}
\newtheorem*{defn*}{Définition}
\theoremstyle{definition}
\newtheorem{xca}{Exercice}
\theoremstyle{remark}
\newtheorem*{rem*}{Remarque}
\theoremstyle{plain}
\newtheorem*{thm*}{Théorème}
\theoremstyle{definition}
\newtheorem{problem}[thm]{Problem}
\theoremstyle{plain}
\newtheorem*{conjecture*}{Conjecture}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\usepackage[francais,american]{babel}
\makeatother
\begin{document}
\chapter{Functions (section 4.4)}
\section{Introduction}
The notion of function is pretty natural, and used in many domains
(programming languages, calculus, \ldots{}). So far, the intuitive
notion of function was sufficient, but we now need a more formal definition,
and we will use relations for this.
We will also see how certain functions, called bijections, provide
powerful counting methods.
\begin{example*}
Let $S$ be a set of cars and $T$ be the set of all colors.
Consider the relation {}``is of color''.
What properties does this relation have ?\char`\"{}
%
%
%
%
%
%%
You can speak about THE color of the car: uniquely defined.
\end{example*}
\section{Formal definition of functions}
\subsection{Functions with one variable}
\begin{defn*}
A \emph{function} $f:\textrm{ }S\textrm{ }\rightarrow\textrm{ }T$
between two sets $S$ and $T$ is a relation such that any element
$s$ of $S$ is in relation with a unique element of $T$.
\vspace{0.3cm}
\begin{center}\includegraphics{function.eps}\end{center}
\vspace{0.3cm}
This unique element, denoted $f(s)$ is the \emph{image} of $s$.
If $f(s)=y$, then $s$ is a \emph{preimage} of $y$.
\vspace{0.3cm}
$S$ is the \emph{domain} of $f$;
$T$ is the \emph{codomain} of $f$;
The set $\{ f(s)\textrm{ },\textrm{ }s\in S\}$ is the \emph{range}
of $f$.
\end{defn*}
\begin{example*}
The identity on a set $S$ if the function $id_{S}:S\rightarrow S$
defined by $id_{S}(x):=x$.
\end{example*}
One way to define a function is to provide an equation, or any other
mean that allows to compute the image of an element of the domain.
\begin{example*}
$f(n):=n+2$;
$f(L):=sort(L)$;
$f(x):=[x]$.
\end{example*}
\begin{defn*}
\emph{Graph} of a function from $\R$ to $\R$ (or any subset of them):
\end{defn*}
\begin{xca}
Draw the graphs of the functions $f(x)=x^{2}$, $g(x)=\sqrt{x}$,
and $h(x):=\left|x\right|$.
\end{xca}
\subsection{Functions with several variables}
The argument of a function does not need to be a simple number.
\begin{example*}
$f(x,y)=x^{2}+2xy$
\end{example*}
\begin{defn*}
A function with $n$ variables is a function whose argument is a $n$-uple:
\[
f\textrm{ }:\textrm{ }S_{1}\times\cdots\times S_{n}\textrm{ }\rightarrow\textrm{ }T.\]
\end{defn*}
\begin{example*}
Here are a few functions with several variables:
\end{example*}
\begin{itemize}
\item $f\textrm{ }:\{ students\}\times\{ test1,test2,final\}\textrm{ }\rightarrow\textrm{ }\{1,2,\ldots,100\}$
\[
f(Jason,test2):=\cdots\]
\item $f:\textrm{ }\{ True,False\}^{3}\textrm{ }\rightarrow\textrm{ }\{ True,False\}$\[
f(A,B,C)=(A\wedge B)'\wedge C\]
\end{itemize}
\subsection{Equality of functions}
\begin{example*}
Are the functions $f(x):=x$ and $g(x):=\left|x\right|$ equal ?
\end{example*}
%
%
%
%
%
%%
\begin{defn*}
Two functions $f$ and $g$ are \emph{equal} iff they have same domain
$S$, same codomain $T$, and $f(x)=g(x)$ for all $x$ in $S$.
\end{defn*}
\section{Properties of functions}
\subsection{Injective, surjective and bijective functions}
\begin{example*}
Let $P$ be the set of all residents in America;
let $N$ be the set of all assigned Social Security Number (SSN);
let $SSN:\textrm{ }P\rightarrow N$ be the function which assigns
to each person $x$ its SSN $SSN(x)$.
\end{example*}
A Social Security Number is useful because it uniquely describes a
person!
That is, given an assigned SSN, you can find the person having this
SSN.
\begin{defn*}
The function $SSN$ is \emph{invertible}.
The \emph{inverse} of the function $SSN$ is the function $SSN^{-1}:\textrm{ }N\rightarrow P$
such that:
$SSN^{-1}(n)$ is the person having $n$ as SSN.
\end{defn*}
What properties does a function need to be invertible?
%
%
%
%
%
%%
To be invertible, a function needs to have the two following properties:
\begin{defn*}
A function $f\textrm{ }:S\textrm{ }\rightarrow\textrm{ }T$ is \emph{injective}
(\emph{one-to-one}) iff
\[
(\forall x\in S)(\forall y\in S)\textrm{ }(f(x)=f(y))\rightarrow(x=y)\]
{}``If x and y have the same SSN, then x is the same person as y''
\begin{defn*}
A function $f\textrm{ }:S\textrm{ }\rightarrow\textrm{ }T$ is \emph{surjective}
(\emph{onto}) iff
\end{defn*}
\[
(\forall y\in T)(\exists x\in S)\textrm{ }f(x)=y\]
{}``For any assigned SSN, there is a person which has this SSN.''
\begin{defn*}
A function $f\textrm{ }:S\textrm{ }\rightarrow\textrm{ }T$ is \emph{bijective}
iff it's injective and surjective.
\end{defn*}
\end{defn*}
\begin{xca}
Which one of the following functions from $\R$ to $\R$ are bijective?
\end{xca}
\begin{enumerate}
\item $f(x):=x^{2}$;
\item $f(x):=x^{3}$;
\item $f(x):=\frac{1}{1+x^{2}}$;
\item $f(x):=\exp(x)$;
\item $f(x):=\log(x)$;
\end{enumerate}
\subsection{Composition of functions}
\begin{defn*}
Let $f:S\rightarrow T$ and $g:T\rightarrow U$ be two functions.
The \emph{composition function} $g\bullet f$ is the function from
$S$ to $U$ defined by\[
g\bullet f(x):=g(f(x)).\]
\end{defn*}
\begin{rem*}
The standard symbol for composition is an empty circle! In those notes
a full circle is used instead due to a bug in lyx ...
\end{rem*}
\begin{xca}
Define $f:\R\rightarrow\R$ by $f(x):=x+1$, and $g:\R\rightarrow\R$
by $g(x):=x^{2}$.
What is the value of $g\bullet f(1)$? What is $g\bullet f$?
What is the value of $f\bullet g(1)$? What is $f\bullet g$?
\end{xca}
\begin{thm*}
Let $f:S\rightarrow T$ and $g:T\rightarrow U$ be two functions.
%
%
%
%
%%
\end{thm*}
\begin{enumerate}
\item If $f$ and $g$ are injective, then $g\bullet f$ is injective.
\item If $f$ and $g$ are surjective, then $g\bullet f$ is surjective.
\item If $f$ and $g$ are bijective, then $g\bullet f$ is bijective.
\end{enumerate}
\begin{proof}
3. is a direct consequence of 1 and 2.
\begin{enumerate}
\item Assume $f$ and $g$ are injective. We have :\[
(\forall x)(\forall y)\textrm{ }(f(x)=f(y))\textrm{ }\rightarrow\textrm{ }(x=y)\]
\[
(\forall x)(\forall y)\textrm{ }(g(x)=g(y))\textrm{ }\rightarrow\textrm{ }(x=y)\]
We want to prove that :\[
(\forall x)(\forall y)\textrm{ }(g\bullet f(x)=g\bullet f(y))\textrm{ }\rightarrow\textrm{ }(x=y)\]
Take $x$ and $y$ such that $g\bullet f(x)=g\bullet f(y)$\\
By definition $g(f(x))=g(f(y))$.\\
Then, since $g$ is injective, $f(x)=f(y)$. \\
Since $f$ is also injective $x=y$. \\
We are done!
\item Left as exercise.
\end{enumerate}
\end{proof}
\subsection{Inverse of function}
\begin{example*}
If you take the SSN of a person, and then lookup the person having
this SSN, you will get back the original person. That is, composing
the function $SSN$ and the function $SSN^{-1}$ yields the identity.
\end{example*}
\begin{defn*}
Let $f:S\rightarrow T$ be a function.
If there exists a function $g:T\rightarrow S$ such that $g\bullet f=id_{S}$
and $f\bullet g=id_{T}$, then $g$ is called the \emph{inverse function}
of $f$, and is denoted $f^{-1}$.
\end{defn*}
\begin{thm*}
A function $f$ is bijective iff its inverse $f^{-1}$ exists.
\end{thm*}
\begin{xca}
Give the inverses (if they exists!) of the following functions:
\begin{enumerate}
\item $f(x):=x-1$;
\item $f(x):=x^{2}$;
\item $f(x):=x^{3}$;
\item $f(x):=\exp(x)$.
\end{enumerate}
\end{xca}
\section{Functions and counting}
\subsection{Injections, surjections, bijections and cardinality of sets}
\begin{example*}
You distribute $n$ different cakes between $k$ child.
Such a distribution can be formalized by a function $f$:
$f(4)=5$ means that the $4$th cake is given to the $5$th child.
\end{example*}
\begin{enumerate}
\item Suppose $f$ is injective.
\begin{itemize}
\item What does it mean ?
\item What can you say about $n$ and $k$ ?$k\geq n$
\end{itemize}
\item Suppose $f$ is surjective.
\begin{itemize}
\item What does it mean ?
\item What can you say about $n$ and $k$ ?
\end{itemize}
\item Suppose $f$ is bijective.
\begin{itemize}
\item What does it mean ?
\item What can you say about $n$ and $k$ ?
\end{itemize}
\end{enumerate}
\begin{thm*}
Let $S$ and $T$ be two sets.
If there exists an injective function between $S$ and $T$, then
$\left|S\right|\leq\left|T\right|$.
If there exists a surjective function between $S$ and $T$, then
$\left|S\right|\geq\left|T\right|$.
If there exists a bijective function between $S$ and $T$, then $\left|S\right|=\left|T\right|$.
\end{thm*}
Note that we have never given a formal definition of the size of a
set.
We just relied on the intuitive notion.
In set theory, the theorem above is actually the definition of cardinality:
\begin{itemize}
\item Two sets have the same cardinality (size), iff they are in bijection.
\item A set is of size $n$ iff it's in bijection with $\{1,\ldots,n\}$.
\end{itemize}
\subsection{Examples of bijections}
\subsubsection{Finite and countable sets}
Do you remember how we proved that $Z$ was countable ?
\begin{itemize}
\item A set $S$ is finite if there is an enumeration $s_{1},\ldots,s_{k}$
of $S$.\\
This enumeration is actually a bijection from $\{1,\ldots,k\}$ to
$S$!
\item A set $S$ is denumerable if there is an enumeration $s_{1},\ldots,s_{k},\ldots$
of $S$.\\
This enumeration is actually a bijection from $\N$ to $S$!
\end{itemize}
\subsubsection{Y/B buildings, 0/1 strings and pairs of rabbits}
\begin{problem}
Counting:
\begin{enumerate}
\item buildings with yellow and blue floors, without consecutive yellow
floors.
\item strings of $0$ and $1$ without two consecutive $1$.
\end{enumerate}
\end{problem}
The answer in both case is the Fibonacci sequence.
Those two problems are fundamentally the same:
There is a bijection between solutions of the first and solutions
to the second!
So if you solve the one of them, you solve both of them.
\begin{problem}
Counting pairs of rabbits after $n$ generations (ex 29 p. 140).
\end{problem}
Here also the solution is the Fibonacci sequence.
Can you find the bijection ?
\subsubsection{Strings of well-balanced parenthesis and Dyck paths}
A string of well-balanced parenthesis is a string such as \texttt{\noun{(()())}}\textsf{\noun{,}}
where each open parenthesis is closed and vice versa.
\begin{defn*}
A Dyck path of size $n$, is a path in $\N\times\N$ from $(0,0)$
to $(2n,0)$ such that each step is either $(1,1)$ or $(1,-1)$.
\vspace{0.3cm}
\begin{center}\includegraphics{Dyck.eps} \end{center}
The important fact is that such a path never goes under the x-axis.
\end{defn*}
\begin{xca}
Find all strings of well-balanced parenthesis of length $0$, $2$,
$4$,$6$, $8$, $10$.
Find all Dyck paths of size $0$, $1$, $2$, $3$, $4$.
\end{xca}
Do you notice something ?
\begin{conjecture*}
There are as many Dyck paths of size $n$ than strings of well balanced
parenthesis of length $2n$.
\end{conjecture*}
How to prove this conjecture?
Let $D$ be the set of Dyck paths of size $n$.
Let $S$ be the set of strings of well balanced parenthesis of length
$2n$.
We just have to construct a bijection $f:S\rightarrow D$.
Take $s=s_{1}\cdots s_{2n}\in S$, and build a path $f(s)$ in the
following way:
read $s$ from left to right; if $s_{i}$ is a \texttt{(}, go right
and up, else go right and down.
\begin{xca}
Draw $f(s)$ for the following strings: \texttt{()}, \texttt{()()},
\texttt{((()(())())())}.
\end{xca}
Why is $f(s)$ indeed a Dyck path of size $n$?
\begin{itemize}
\item There are $2n$ steps to the right
\item In $s$, there are as many $'('$ as $')'$, so the final position
is $(2n,0)$.
\item At any position $i$ in $s$, there are more $'('$ than $')'$ before
$i$.
\end{itemize}
How to prove that $f$ a bijection ?
Lets try to construct an inverse $g$ for $f$:
Take a path $p$, and build a string $g(p)$ in the following way:
go through $p$ from left two right. For each up step, add a \texttt{$'('$}
to $g(p)$, and for each down step, add a \texttt{$')'$}.
\begin{xca}
Apply $g$ to the paths obtained in the previous exercises.
\end{xca}
For the same reasons as above, the resulting string $g(p)$ is a string
of well balanced parenthesis.
Moreover, by construction $f(g(p))=p$ for any $p\in D$ and $g(f(s))=s$,
for any $s\in S$.
So $g$ is indeed an inverse for $f$.
Therefore, $f$ is a bijection and consequently $\left|S\right|=\left|D\right|$,
as wanted.
\subsubsection{Ordered trees and strings of well-balanced parenthesis}
\begin{defn*}
The set of all ordered trees can be defined recursively as follow:
\end{defn*}
\begin{itemize}
\item A single node is an ordered tree
\item If $t_{1},\ldots,t_{k}$ are $k$ ordered trees, the structure obtained
by adding a common father to $t_{1},\ldots,t_{k}$ is an ordered tree.
\end{itemize}
\begin{xca}
Draw all ordered trees on $1,2,3,4,5$ nodes.
\end{xca}
\begin{example*}
Prove that any ordered tree on $n$ nodes has $n-1$ edges.
%
%
%
%
%
%%
Ordered trees are defined recursively, so using recursion seems reasonable.
The property is true on a tree with one node.
Let $t$ be a tree on $n>1$ nodes.
Assume the property is true for any tree of size $