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. 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. 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.

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) , s ∈ S} is the range of f. Exemple. The identity on a set S if the function id_{S} : S → S defined by id_{S}(x) := x.

2 1. FUNCTIONS (SECTION 4.4)

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. f(n) := n + 2; f(L) := sort(L); f(x) := [x]. Définition. Graph of a function from ℝ to ℝ (or any subset of them): Exercice 1. Draw the graphs of the functions f(x) = x^{2}, g(x) = \sqrt{x}, 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. f(x, y) = x^{2} + 2xy Définition. A function with n variables is a function whose argument is a n-uple:

f : S_{1} × ⋯ × S_{n} → T.

Exemple. Here are a few functions with several variables:

• f : {students} × {test1, test2, final} → {1, 2, …, 100}

f(Jason, test2) := ⋯

• f : {T rue, F alse}^{3} → {T rue, F alse}

f(A, B, C) = (A ∧ B)′ ∧ C

1.2.3. Equality of functions. Exemple. Are the functions f(x) := x and g(x) := |x| equal ? Définition. 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. 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. 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. A function f : S → T is injective (one-to-one) iff

(∀x ∈ S)(∀y ∈ 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. A function f : S → T is surjective (onto) iff

(∀y ∈ T)(∃x ∈ S) f(x) = y

“For any assigned SSN, there is a person which has this SSN.”

Définition. A function f : S → T is bijective iff it’s injective and surjective.

Exercice 2. Which one of the following functions from ℝ to ℝ are bijective?

(1) f(x) := x^{2};

(2) f(x) := x^{3};

(3) f(x) := \frac{1}{1+x^{2}} ;

(4) f(x) := exp(x);

(5) f(x) := log(x);

1.3.2. Composition of functions.

Définition. 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. 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 : ℝ → ℝ by f(x) := x + 1, and g : ℝ → ℝ 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. 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 :

(∀x)(∀y) (f(x) = f(y)) → (x = y)

(∀x)(∀y) (g(x) = g(y)) → (x = y)

We want to prove that :

(∀x)(∀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. 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. 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. 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. 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. 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.

1.4.2.1. 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 ℕ to S!

1.4.2.2. Y/B buildings, 0/1 strings and pairs of rabbits.

Problem 1.4.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 1.4.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 ?

1.4.2.3. Strings of well-balanced parenthesis and Dyck paths. A string of wellbalanced parenthesis is a string such as (()()), where each open parenthesis is closed and vice versa.

Définition. A Dyck path of size n, is a path in ℕ × ℕ from (0, 0) to (2n, 0) such that each step is either (1, 1) or (1, −1).

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. 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_{2n} ∈ 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 p ∈ D and g(f(s)) = s, for any s ∈ S. So g is indeed an inverse for f. Therefore, f is a bijection and consequently |S| = |D|, as wanted.

1.4.2.4. Ordered trees and strings of well-balanced parenthesis. Définition. 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 com-

mon father to t_{1}, …, t_{k} is an ordered tree.

Exercice 8. Draw all ordered trees on 1, 2, 3, 4, 5 nodes. Exemple. 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 < n. By construction, t is build by adding a common father to k trees t_{1}, …, t_{k}. Let n_{i} be the number of nodes of t_{i}. We have n = n_{1} + ⋯ + n_{k} + 1. Clearly n_{i} < n, so by induction each t_{i} has n_{i} − 1 edges. Conclusion: the number of edges of t is :

(n_{1} − 1) + ⋯ + (n_{k} − 1) + k = n_{1} + ⋯ + n_{k} = n − 1.

Théorème. There are as many trees with n nodes as strings of well balanced parenthesis of length 2(n − 1).

Let’s define recursively a bijection f between trees and well balanced parenthesis:

• If t has a single node, then f(t) is the empty string;

• If t is build from k subtrees t_{1}, …, t_{k}, then f(t) := (f(t_{1})) ⋯ (f(t_{k})).

Exercice 9. Apply f to a few trees.

Here also, it’s easy to construct the inverse of f, so f is a bijection. Since f maps trees on n nodes on strings of length 2(n − 1), and vice-versa, we are done with the proof of the theorem.

1.4.2.5. Catalan Numbers. We have seen that many different kind of objects (trees, strings of well balanced parenthesis, Dyck paths) are counted by the same sequence of numbers:

1, 1, 2, 5, 14, …

This sequence is called the Catalan sequence C(0), C(1), C(2), C(3), . . ..

Problem 1.4.3. What is the value C(n) ?

It’s enough to count, for example, the number of Dyck paths of length 2n. There is a beautiful trick to do this. It’s called André’s inversion principle. Will you find it ?

1.5. Conclusion

• There are often connections between apparently unrelated objects (trees, strings of well balanced parenthesis, Dyck paths, ...).

• Those connections, formalized by bijections, provide powerful methods for counting objects.

• The Sloane is very handy to suggest connections!