Chapter 1 Functions (section 4.4)
************************************
1.1 Introduction
*=*=*=*=*=*=*=*=*
The notion of function is pretty natural, and used in many domains
(programming languages, calculus, ...). 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.
Exemple 1 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 ?"
You can speak about THE color of the car: uniquely defined.
1.2 Formal definition of functions
*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
1.2.1 Functions with one variable
==================================
Définition 1 A function f: S -> 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.
function
This unique element, denoted f(s) is the image of s.
If f(s)=y, then s is a preimage of y.
S is the domain of f;
T is the codomain of f;
The set { f(s) , sin S} is the range of f.
Exemple 2 The identity on a set S if the function id_S:S-> S defined
by id_S(x):=x.
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.
Exemple 3 f(n):=n+2;
f(L):=sort(L);
f(x):=[x].
Définition 2 Graph of a function from R to R (or any subset of
them):
Exercice 1 Draw the graphs of the functions f(x)=x^2, g(x)=(x)^1/2,
and h(x):=|x|.
1.2.2 Functions with several variables
=======================================
The argument of a function does not need to be a simple number.
Exemple 4 f(x,y)=x^2+2xy
Définition 3 A function with n variables is a function whose
argument is a n-uple:
S ×···× S
f : -> T.
1 n
Exemple 5 Here are a few functions with several variables:
- f :{ students}×{ test1,test2,final} -> {1,2,...,100}
f(Jason,test2):=···
- f: { True,False}^3 -> { True,False}
f(A,B,C)=(A/\ B)'/\ C
1.2.3 Equality of functions
============================
Exemple 6 Are the functions f(x):=x and g(x):=|x| equal ?
Définition 4 Two functions f and g are equal iff they have same
domain S, same codomain T, and f(x)=g(x) for all x in S.
1.3 Properties of functions
*=*=*=*=*=*=*=*=*=*=*=*=*=*=
1.3.1 Injective, surjective and bijective functions
====================================================
Exemple 7 Let P be the set of all residents in America;
let N be the set of all assigned Social Security Number (SSN);
let SSN: P-> N be the function which assigns to each person x its SSN
SSN(x).
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.
Définition 5 The function SSN is invertible.
The inverse of the function SSN is the function SSN^-1: N-> P such
that:
SSN^-1(n) is the person having n as SSN.
What properties does a function need to be invertible?
To be invertible, a function needs to have the two following
properties:
Définition 6 A function f :S -> T is injective (one-to-one) iff
(for all xin S)(for all yin S) (f(x)=f(y))->(x=y)
``If x and y have the same SSN, then x is the same person as y''
Définition 7 A function f :S -> T is surjective (onto) iff
(for all yin T)(there exists xin S) f(x)=y
``For any assigned SSN, there is a person which has this SSN.''
Définition 8 A function f :S -> T is bijective iff it's injective
and surjective.
Exercice 2 Which one of the following functions from R to R are
bijective?
1. f(x):=x^2;
2. f(x):=x^3;
3. f(x):=1/1+x^2;
4. f(x):=exp(x);
5. f(x):=log(x);
1.3.2 Composition of functions
===============================
Définition 9 Let f:S-> T and g:T-> U be two functions.
The composition function g f is the function from S to U defined by
g f(x):=g(f(x)).
Remarque 1 The standard symbol for composition is an empty circle!
In those notes a full circle is used instead due to a bug in lyx ...
Exercice 3 Define f:R->R by f(x):=x+1, and g:R->R by g(x):=x^2.
What is the value of g f(1)? What is g f?
What is the value of f g(1)? What is f g?
Théorème 1 Let f:S-> T and g:T-> U be two functions.
1. If f and g are injective, then g f is injective.
2. If f and g are surjective, then g f is surjective.
3. If f and g are bijective, then g f is bijective.
Proof. 3. is a direct consequence of 1 and 2.
1. Assume f and g are injective. We have :
(for all x)(for all y) (f(x)=f(y)) -> (x=y)
(for all x)(for all y) (g(x)=g(y)) -> (x=y)
We want to prove that :
(for all x)(for all y) (g f(x)=g f(y)) -> (x=y)
Take x and y such that g f(x)=g 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!
2. Left as exercise.
1.3.3 Inverse of function
==========================
Exemple 8 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.
Définition 10 Let f:S-> T be a function.
If there exists a function g:T-> S such that g f=id_S and f g=id_T,
then g is called the inverse function of f, and is denoted f^-1.
Théorème 2 A function f is bijective iff its inverse f^-1 exists.
Exercice 4 Give the inverses (if they exists!) of the following
functions:
1. f(x):=x-1;
2. f(x):=x^2;
3. f(x):=x^3;
4. f(x):=exp(x).
1.4 Functions and counting
*=*=*=*=*=*=*=*=*=*=*=*=*=*
1.4.1 Injections, surjections, bijections and cardinality of sets
==================================================================
Exemple 9 You distribute n different cakes between k child.
Such a distribution can be formalized by a function f:
f(4)=5 means that the 4th cake is given to the 5th child.
1. Suppose f is injective.
- What does it mean ?
- What can you say about n and k ?k>= n
2. Suppose f is surjective.
- What does it mean ?
- What can you say about n and k ?
3. Suppose f is bijective.
- What does it mean ?
- What can you say about n and k ?
Théorème 3 Let S and T be two sets.
If there exists an injective function between S and T, then |S|<=|T|.
If there exists a surjective function between S and T, then |S|>=|T|.
If there exists a bijective function between S and T, then |S|=|T|.
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:
- Two sets have the same cardinality (size), iff they are in bijection.
- A set is of size n iff it's in bijection with {1,...,n}.
1.4.2 Examples of bijections
=============================
Finite and countable sets
-------------------------
Do you remember how we proved that Z was countable ?
- A set S is finite if there is an enumeration s_1,...,s_k of S.
This enumeration is actually a bijection from {1,...,k} to S!
- A set S is denumerable if there is an enumeration s_1,...,s_k,... of
S.
This enumeration is actually a bijection from N to S!
Y/B buildings, 0/1 strings and pairs of rabbits
-----------------------------------------------
Problem 1 Counting:
1. buildings with yellow and blue floors, without consecutive yellow
floors.
2. strings of 0 and 1 without two consecutive 1.
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.
Problem 2 Counting pairs of rabbits after n generations (ex 29 p.
140).
Here also the solution is the Fibonacci sequence.
Can you find the bijection ?
Strings of well-balanced parenthesis and Dyck paths
---------------------------------------------------
A string of well-balanced parenthesis is a string such as (()()),
where each open parenthesis is closed and vice versa.
Définition 11 A Dyck path of size n, is a path in N×N from (0,0) to
(2n,0) such that each step is either (1,1) or (1,-1).
Dyck
The important fact is that such a path never goes under the x-axis.
Exercice 5 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.
Do you notice something ?
Conjecture 1 There are as many Dyck paths of size n than strings of
well balanced parenthesis of length 2n.
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-> D.
Take s=s_1··· s_2nin S, and build a path f(s) in the following way:
read s from left to right; if s_i is a (, go right and up, else go
right and down.
Exercice 6 Draw f(s) for the following strings: (), ()(),
((()(())())()).
Why is f(s) indeed a Dyck path of size n?
- There are 2n steps to the right
- In s, there are as many '(' as ')', so the final position is (2n,0).
- At any position i in s, there are more '(' than ')' before i.
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 '(' to g(p), and
for each down step, add a ')'.
Exercice 7 Apply g to the paths obtained in the previous exercises.
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 pin D and g(f(s))=s, for
any sin S.
So g is indeed an inverse for f.
Therefore, f is a bijection and consequently |S|=|D|, as wanted.
Ordered trees and strings of well-balanced parenthesis
------------------------------------------------------
Définition 12 The set of all ordered trees can be defined
recursively as follow:
- A single node is an ordered tree
- If t_1,...,t_k are k ordered trees, the structure obtained by adding
a common father to t_1,...,t_k is an ordered tree.
Exercice 8 Draw all ordered trees on 1,2,3,4,5 nodes.
Exemple 10 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