Relations
Class notes
Groups and other algebraic structures
Document also available in PDF, Postscript, DVI, Text, LaTeX, LyX.
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^{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 nuple:
f : S_{1}×···× 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}^{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
(onetoone
) 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^{2};
 f(x):=x^{3};
 f(x):=1/1+x^{2};
 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^{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.

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):=x1;
 f(x):=x^{2};
 f(x):=x^{3};
 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_{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:

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 wellbalanced 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 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 xaxis.
Exercice 5
Find all strings of wellbalanced 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_{2n}in 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 wellbalanced 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 n1 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}=n1.
Théorème 4
There are as many trees with n nodes as strings of well balanced
parenthesis of length 2(n1).
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(n1),
and viceversa, 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 MACS358 /
Nicolas M. Thiéry
Last modified: Fri Jan 19 13:12:19 2007