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