Groups and other algebraic structures
Document also available in PDF, Postscript, DVI, Text, LaTeX, LyX.

Functions

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.

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², 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²+2xy

Définition 3 A function with n variables is a function whose argument is a n-uple:

f : S₁×···× S_n -> T.

Exemple 5 Here are a few functions with several variables:

f :{ students}×{ test1,test2,final} -> {1,2,...,100}
f(Jason,test2):=···
f: { True,False}³ -> { 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?

f(x):=x²;
f(x):=x³;
f(x):=1/1+x²;
f(x):=exp(x);
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².

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.

If f and g are injective, then g¤ f is injective.
If f and g are surjective, then g¤ f is surjective.
If f and g are bijective, then g¤ f is bijective.

Proof. 3. is a direct consequence of 1 and 2.

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!
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:

f(x):=x-1;
f(x):=x²;
f(x):=x³;
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.

Suppose f is injective.
- What does it mean ?
- What can you say about n and k ?k>= n
Suppose f is surjective.
- What does it mean ?
- What can you say about n and k ?
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₁,...,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₁,...,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:

buildings with yellow and blue floors, without consecutive yellow floors.
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).

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₁··· 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₁,...,t_k are k ordered trees, the structure obtained by adding a common father to t₁,...,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 <n.

By construction, t is build by adding a common father to k trees t₁,...,t_k.

Let n_i be the number of nodes of t_i.

We have n=n₁+···+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)+···+(n_k-1)+k=n₁+···+n_k=n-1.

Théorème 4 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₁,...,t_k, then f(t):=(f(t₁))···(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.

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

Relations

Class notes

Groups and other algebraic structures
Functions / CSM MACS-358 / Nicolas M. Thiéry
Last modified: Fri Jan 19 13:12:19 2007