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 idS:S-> S defined by idS(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)=x2, 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)=x2+2xy
Définition 3   A function with n variables is a function whose argument is a n-uple:
f : S1×···× Sn -> 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 (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):=x2;
2. f(x):=x3;
3. f(x):=1/1+x2;
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):=x2.

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=idT, 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):=x2;
3. f(x):=x3;
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 s1,...,sk of S.
This enumeration is actually a bijection from {1,...,k} to S!
• A set S is denumerable if there is an enumeration s1,...,sk,... 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).

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=s1··· s2nin S, and build a path f(s) in the following way:

read s from left to right; if si 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 t1,...,tk are k ordered trees, the structure obtained by adding a common father to t1,...,tk 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
1,...,tk.

Let n
i be the number of nodes of ti.

We have n=n
1+···+nk+1.

Clearly n
i<n, so by induction each ti has ni-1 edges.

Conclusion: the number of edges of t is :
(n1-1)+···+(nk-1)+k=n1+···+nk=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 t1,...,tk, then f(t):=(f(t1))···(f(tk)).
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