I give the solution of the first of the last exercises.

I reason aloud. I go slowly for those who did not get some math  
courses, or just forget them.  I cannot stress the importance of the  
notion of bijection in the "mathematical discovery of the universal  
machine" (the quote means that a nuance will be added here).

Counting is not so important. Th exercise motivation is in to develop  
familiarity with the notion of function and bijection. Then counting  
things provides example of functions from N to N.

> 1) count the number of bijections from a set A to itself.  (= card{x
> such that x is bijection from A to A})

This does not seem very obvious, so let us begin with the simplest  
set, for example the one which admits the shorter description when  
written in extension, that is the empty set { }.

The question in this case is: count the number of bijection between  
{ } and { }.

Hmm... This smells the subtle trap and it may be a good advise to  
avoid the simplest set or number. Zero and the empty set may be  
simplest in term of description but may be harder conceptually.

A simple case, in this and many cases, would be a set with not much  
elements. Let us count the number of bijections from {a, b} to itself.  
i.e. the bijections from {a, b} to {a, b}.

Here some beginners could have a trouble: "I don't remember what is a  
bijection". Well, the exercise is obviously with notes. I am not yet  
asking to buy a webcam so that I can look if you are not cheating, all  

Two things can happen. Either you find the passage in your diary where  
I explain bijection with the legendary story of the humans who cannot  
count, and compare the bigness of sets by using ropes.

You may remember how the farmer compare their *set* of animals,  
without being able to count. They compare two sets of animals by  
attaching a rope to ONE animal belonging to the set of your animals,  
say, and you bring that to ONE animal of your neighbor.
Three things can happen:
1) All your animals get attached to a rope, and got attached to some  
neighbor's animals, but some other animal of the neighbor are still  
freely going here and there. In this situation we say "damned, the set  
of animals of my neighbor is bigger than mine".
2) All your animals get they rope, and got attached  to the neighbor's  
animals. And all neighbor's animals are attached. In this situation we  
say "OK, my set of animals has the same cardinality than the set of my  
neighbor animals. Cardinality is the measure of set, when we compare  
it in this way. Now, this is the situation where a bijection exists.
3) All the neighbor's animal are attached to the rope, yet some of  
your own animals remain free. You can attach the rope to those free  
animals, but you will be unable to attach them to some neighbor  
animal, they are already all attached. In this situation you say  
nothing, because you are polite, you just let the neighbor saying  
"damned, the set of animals of my neighbor is bigger than mine".

  .... Or you don't remember that story, so you consult the austere  
notes with the definition. A, B ... represent sets.

A bijection between A and B is a function from A to B which is ONE-ONE  
and ONTO.

And what is a function? A set of couples (x, y), x in A, y in B,  
verifying the condition that no x in A is sent on different y in B. In  
a very large sense, the element of B depend on the element of A, and  
that dependence is represented by a couple (x, y).

With the farmer, the couples where made with one animal x attached by  
a rope to one animal y:  (x, y).

Well let us go back to the bijections from {a, b} to {a, b}. Oh, I see  
some anxiousness can rise due to the fact that we have the same set of  
both side. Why would ever a farmer compare the bigness of its set of  
animals with the bigness of its set of animals? Is that not a pure  
mathematical absurdity?

To ease the pain, in math, consists always in simplifying, so, just to  
keep the intuition provided by the farmer, let us distinguish the  
animal's neighbor, those which makes the arrival set, by different  
letters. And let us first search the bijections from {a, b} to {c, d}.  
{a, b} is the set of my animals. {c, d} is the set of animals of my  
neighbor. OK?

Well I have to build a bijection, which is a set, so I have to begin  
by "{", indicating I am building a set. Of course, this is implicit in  
the farmer's mind, because his goal consists in just comparing the two  
sets. But our goal is to find all bijections. So we have to be clear  
about them as mathematically represented objects, and bijections, like  
functions, have been defined or represented as sets.

Now I have to choose one of my animals; let us choose a. and attach  
the rope. The description of the bijection looks like:


I have to choose an animal belonging to the set of my neighbor's  
animals. Well, I have two choices: c or d. Let us choose c. The  
description of the bijection looks like:

{(a, c),

And then

{(a, c), (b, d)}

This *is* a function, which is ONTO and ONE-ONE.

Is there another?

Yes. I choose the other animals (cf the two choice above). But note  
already, that for the second animals I have only once choice.

The other is {(a, d), (b, c)}. Is there another one? No.

There are two bijections from {a, b} to {c, d}.  {(a, c), (b, d)}  and  
{(a, d), (b, c)}.
The set of bijections from {a, b} to {c, d} is the set {{(a, c), (b,  
d)}, {(a, d), (b, c)}}. This is more easy to build than to read.

Now the name of the element, or even what they consists in (animals,  
numbers, letters) is not relevant OK?

In particular there are as many bijection from {a, b} to {a, b} than  
from {a, b} to {c, d}. They are

{(a, a), (b, b)}


{(a, b), (b, a)}

A bijection from A to A is called a permutation of A.   {(a, a), (b,  
b)} is called the identity permutation on {a, b}.

Oh, card(A) = 2 (= A has two elements) entails that there is 2  

WE may generalize and believe that there are as many bijections from A  
to A, than there are elements in A.

OK? Let us test this theory on the simpler set {a}. How many  
bijections are there from (a} to {a}. Well, there is {(a,a)}, and  
that's all. One! Our theory succeeds.

If we infer that theory on { }, we may be tempted to say 0, for the  
number of bijections between { } and { }. But with a sample of two  
elements ...,  it is dangerous to infer too much quickly.

Let us look at {a, b, c}. Are there three bijections? And only three  
bijections? (Well if you remember the number of function from A to B  
is card(B)^card(A), so we could be astonished our conjecture is  

And indeed, I go systematically trying to figure out how to count the  
number of bijections from A to A for a finite set A in general.

Let us build a bijection from {a, b, c} to {a, b, c}.

It has to be something like {(a , _) , (b,  ),   (c,  ) }. Given that  
in a set the order has no importance, so the choices of beginning by  
(a,  or by (b,  or by (c   is not relevant. But once I choose say {(a,  
the number of choice to complete the second bijection is relevant {(a,  
b) ..., will not give the same bijection that {(a, c), ...

So I start with {(a,  I have three choices. Let us take c for the  
first choice, how many choices there is for the next element?

Well, given that the bijective function (bijection) have to be ONE- 
ONE, you loose a possibility at each choice. So there will be three  
possibility, then 2, the 1, and the bijection is completed.

So there will be 3 x 2 x 1 bijections. the number of choices are  
multiplied for the same reason that for the number of functions. Once  
a choice is made, the remaining choices are independent.

Let us look

{(a, a) (b, b), (c, c)}
{(a, a) (b, c), (c, b)}   choice: "{(a,a) ..."  multiplied by the  
bijections from {b, c} to {b, c}.

{(a, b), (b, a) (c, c)}
{(a, b), (b, c) (c, a)}

{(a, c), (b, a) (c, b)}
{(a, c), (b, b) (c, a)}

So three elements leads to 3 x 2 x 1 bijections; that is 6 bijections.

If there is n elements in the set, there will be n choices for the  
first couples, then, by the one )one condition, it will remains
(n-1) choices, then (n-2) .... up to the last 1 choice.

We have a "formula". if card(A) = n then then number of permutation on  
A, or of bijection from A to A, is n*(n-1)* ... 1.


Er, how many bijections from { } to { } ? In this case card(A) = 0.  
The formula we get does not seem to apply. What could be

0*(0-1)*(0-2)*  .... * 1   ?

At first sight it should be 0. Because 0*<anything> = 0 isn't it?    
false: 0 * any number = 0. But who could claim that the expression  
above is well determined: it is like you will never get to that "1".

I'm afraid we have to tackle the "simplest" case by reason alone,  
taking our definition seriously into account.

How many bijection are there, from { } to { }?

Well, bijections are sets, so we can begin {, and we have to put in  
that set couples (x, y) with x in { } and y in { }. But there is no x  
in { }, so we will not find any couples. So our set is empty, so we  
can close it directly, and the bijection looks like { }. It is the  
empty bijection. So we have find one, and only one.

So the number of bijections from the empty set to the empty set is  
ONE. (For the same reason, if you remember, that the number of  
functions from { } to { } is one. Card({ }^{ }) = 1).

That was the harder case.

Now let us write A° for the set of permutation on A. A permutation is  
defined by a bijection from A to A.

We have seen that if Card(A) = n, card(A°) = n*(n-1)*(n-2)* ... *1 if  
A is not empty, and Card(A°) = 1 if A is empty.

This motivates the definition of the following function from N to N,  
called factorial.
factorial(0) = 1, and factorial(n) = n*(n-1)*(n-2)*(n-3) * ... *1, if  
is n is different from 0.

Note this: if n is different from 0, for each n we have that fact(n) =  

factorial is a function from N to N, so it is the following set of  

{(0, 1), (1, 1), (2, 2), (3, 6), (4, 24), (5, 120), (6, 720), (7,  
5040), (8, 40320), (9, 362880), (10, 3628800), (11, 39916800), ...}

A good thing I did not ask you to give me all the bijections from a  
set from 10 elements to itself. See that if two farmer have 10 animals  
each, they is already 3628800 bijections between their two sets of  

Compare with the exponential function, which send n to 2^n

{(0, 1), (1, 2), (2, 4), (3, 8), (4, 16), (5, 32), (6, 64), (7, 128),  
(8, 256), (9, 512), (10, 1024), (11, 2048), ...}



> 2) describe some canonical bijection between 2^A and the powerset of  
> A.
> 3) I say that a set S is a proper subset of A if it is a subset of A,
> and different from A.
>     We have seen that there is a bijection between N and 2N = {0, 2,
> 4, 6, ...}. (see below *)
>     2N is a proper subset of N.
>     So we see that an infinite set can have a bijection with a proper
> subset.
>     The question is, could that be possible for a finite set?
> The bijection between N and 2N is the set {(0,0), (1,2), (2, 4), (3,
> 6), (4, 8), ...}.  More schematically, if you remember the ropes:
> N          2N
> 0 ------- 0
> 1 --------2
> 2 --------4
> 3 --------6
> ....
> 4) Be sure that you have been convinced by Brent  that there is a
> bijection between N and NxN, and between N and NxNxN, and etc. That is
> be sure there is a bijection between N and N^m for each N.
> 5) Key exercise for the sequel. First a definition. An alphabet A is a
> non empty finite set. I call its elements letter.
> Exemple. A = {a, b, c},, B = {0, 1}.. By A+ I mean the set of finite
> words on the alphabet A. A word is a finite sequence of letters, from
> some alphabet, like, on the alphabet A, aaabab, abbbbcbababcccacab,  
> etc.
> IA+ is obviously infinite, it contains *notably* a, aa, aaa, aaaa,
> aaaaa, aaaaaa, aaaaaaa, ...
> The word "word" has a larger meaning in math than in natural language.
> On the usual alphabet {A, B, ... Z}, an expression like
> HHYUJLIFSEFGXWKKODENN is a fully respectable word.
> Show that for any alphabet A, there is a bijection between N and A+
> Soon (asap, though) the proof of many theorems found by Cantor.
> Notably that there is NO bijection from N to N^N.
> Then Cantor proof will be done again and again, and again, ... in
> deeper and deeper and deeper contexts.
> Please ask any questions. It is not too late before we go in the
> *very* interesting matter, and very illuminating with respect to the
> question of the existence of universal machines, languages and  
> numbers.
> Bruno
> http://iridia.ulb.ac.be/~marchal/
> >


You received this message because you are subscribed to the Google Groups 
"Everything List" group.
To post to this group, send email to everything-list@googlegroups.com
To unsubscribe from this group, send email to 
For more options, visit this group at 

Reply via email to