# What is a bijection?

## 1 – Informal description of the concept of bijection

It’s decided, I have my collection of old books appraised! bijection

To prepare the ground, you have to label each book and give it a serial number. As I have a set of labels (with a number written on each one), it’s going to be a breeze. But beware, this labeling must be “perfect” in the following sense:

– Condition 1: two separate numbers must not match the same book

– Condition 2: Each book must be assigned a number

In the jargon of mathematicians, we express this by saying that :

The correspondence of the set of the numbers to the set of my books must be bijective

Let’s explain this strange terminology. If at each number , we associate a book well determined from my collection, we say that we defined an application of towards .

In order to explain this link, we then note , for everything element of . It is said, at choice, that is the image of by or is an antecedent of by .

Clear, means the book bearing the label .

– If condition 1 above is fulfilled, the application f is said to be injective .

– If condition 2 is satisfied, we say that f is surjective.

And if f is both injective and surjective, we say that it is bijective (or that it is a bijection) : this means that each book has a unique  antecedent by , in other words, each book is identified by a number and only one.

Obviously, the above can be generalized to sets and absolutely arbitrary (a set being a collection of objects, without any more precision). Establish a bijection of towards consists in associating, with each element of , a definite element of , in such a way that :

Any element of has a unique antecedent in  bijection

It can be convenient to represent the sets by “potatoes” and to draw an arrow joining each element of in his image in .

The diagram below represents a bijection of the set \{“dog”, “cat”, “horse”, “lion”, “rabbit”\} to the set \{“bitch”, “cat”, “mare”, “Lioness”, “hase”\} :

PICT

This bijection seems natural: each male name is associated with the name of the corresponding female.

But we could imagine something else … for example :

PICT

Less natural is not it? And yet : I simply decided to respect the alphabetical order! Among the words belonging to the left set, the first in alphabetical order is “cat”; for this reason, I decide to associate with it the word “pussy” which is, among the words belonging to the right set, the first in alphabetical order. Similarly for the second (“horse”), to which I associate the second (“bitch”). Similarly for the third (“dog”), which I associate the third (“mare”), etc … You understand.

There is no reason to give up other possibilities, without trying to give them any logic (male \textrightarrow{} female, alphabetical order, or other …). We can verify that there are in all 120 bijections between these two sets. Why 120? Because it is the factorial of 5, that is to say the product of integers from 1 to 5. We can indeed show, in general, that given two sets each comprising n elements, exists in all and for all bijections from one to the other. bijection

Let’s look at this new example :

PICT

We considered here a set V of five names of European capitals :

as well as a set P of six European countries:

and each city has been associated with the country of which it is the capital. But the capital of Sweden does not appear in , and therefore the element “Sweden” has no antecedent. In other words, our application is not surjective (and, in particular, not bijective).

Let’s see something else …

\textbullet{} On my left, the whole

\textbullet{} On my right, the whole

If we associate with each element of the rest of his division by , we get this:

PICT

So, for example:

and so admits for image. Similarly for the other elements of .

This time, all elements of the right set are hit, but some are hit multiple times! It is therefore a non-injective application; in particular, it is not a bijection.

Composing bijections

There is a natural way, from any two applications, to make a third: this is called the composition. What is it about ?

Let’s imagine the whole inhabitants of a village and consider the application who, to each of these people, associates the couple or refers to the number of his boys and the number of his daughters. bijection

If for example Mr Tartempion belongs to and if he has three boys and a girl, then his picture by will be the couple .

Then consider the application who, to any couple of natural numbers associates their sum .

It is then possible to dial by : this consists, for each inhabitant of the village, to associate to him the image by of his image by . In other words, each person is associated with the number of his children. bijection

This new application is noted (which reads “ round “).

PICT

To formalize a little, let’s say that if and are any two applications, then is defined by:

Let’s mention a property that is both simple and very useful:

Yes and are bijections, the same goes for .

## 3 – Bijections … okay, but what for?

You guessed it by reading section 1: given two sets finished and , a necessary and sufficient condition for it to be possible to establish a bijection (a “perfect arrowing”) of towards is that these two sets have the same number of elements (we also say: the same cardinal).

This simple observation is one of the main keys to “combinatorics”, a field of mathematics in which one tries to answer questions such as “how many such finite sets have elements? “. Let’s give some illustrations. bijection

### Example 1: number of parts of a set

Given a set of cardinal , a natural question is to determine the number of its subsets. So, the whole has eight subsets, namely:

the empty set, noted

singletons , and (these are the subsets of cardinal 1)

the pairs , and (these are the subsets of cardinal 2)

all X himself

Generally, if is from cardinal so has exactly subset. Three rigorous proofs of this assertion are collected in the article “How much does a finite set have parts? “.

Without detailing here these somewhat technical proofs, let’s just say that one of them consists in establishing a bijection between the set of subsets of and another set whose cardinal is known (and equal to ).

### Example 2: Number of paths in a square network

Figure 1 below shows a coordinate system and a “path” joining the origin to the point of coordinates (positive integers) p and q. The rule of the game is as follows: starting from the origin, one can only move to the right or to the top, one unit in both cases. bijection

PICT

Figure 2 shows another possible path.

PICT

The number of such paths obviously depends on and . It can be noted to emphasize this dependence. But by what formula can we calculate ?

One way to answer is to associate with each path a word of letters, written in an alphabet with only two symbols: the letter ‘D’ (to indicate a movement to the right of a unit) and the letter H (to indicate an upward movement of a unit).

Thus, the path represented in FIG. 1 is associated with the word:

DHDDDHDHDHHDDHD

while the one shown in Figure 2 is associated with the word:

DHHDHDHDDDHDHDD

Knowledge of a particular path towards determines a word of length comprising times the letter D and the letter H. bijection

Reciprocally, each word of this type determines a single path: we thus see a bijection appear between the set of paths and that of the words having the aforementioned characteristics. To know the number of paths, it is therefore sufficient to calculate the number of words. But this is a routine operation: we can imagine a locker with boxes and count the number of ways to choose boxes among (those where we will place a letter D). Once this choice is made, the remaining boxes will inevitably be occupied by letters H.

The number of ways to choose objects among (without repetition or consideration of order) is classically given by the following formula (of which the member on the left reads “ among “):

Therefore, the number of paths is:

For example, if and , the number of paths is:

what can be confirmed by listing “by hand” the different possibilities. And if and , this number goes to:

but here, we abandon very quickly the idea to draw up an exhaustive list of possibilities! …

In passing, it is interesting to note the power of combinatorial methods: they give access to the calculation of the cardinal of a set, while avoiding the explicit enumeration of its elements (something impossible to achieve if these elements are very numerous).

### Example 3: Number of Transitive Binary Operations

It also happens that it is difficult to find a bijection between the finite set of which we are looking for the cardinal and a set of known cardinal. Thus, some apparently simple combinatorial questions remain unresolved to this day.

Given a set , we are sometimes led to provide this set with a binary relation, which simply means that each element of is related to zero, one or more other (s). You can visualize a binary relation by drawing an arrow of towards when is in a Relationship with . The diagram below represents a binary relation on a set of cardinal . We see in particular that is in a Relationship with , than is in relation with himself and with , than is not in contact with anyone, etc.

PICT

A binary relation is called transitive if, for any triplet of elements of , the fact that either in relation with and either in relation with leads that is in a Relationship with .

For example, overall , we can define the relation of divisibility: given two integers and belonging to , we say that “ Split When there is a natural number such as (We also say that “ is multiple of “). Here is a graphical representation (in order not to overload the figure, the points of the arrows have not been represented, but there is no doubt as to their orientation):

PICT

This relationship is transitive: if Split and if Split , then there are natural numbers and such as and , from where and so Split .

It is not very difficult to count the binary relations on a set Cardinal : there are ( to the power ). Let us say, without going into details, that this results from the existence of a bijection of the set of binary relations on towards all the applications of in .

We come to the question that kills: how many transitive binary relations can we define on a set of cardinal ? Answer: an integer for which no sympathetic formula has been found so far …

At most, can one (with the help of a computer) calculate the value of for small values of , but not much more. Here, compiled in a table, are the first 10 terms of this series of numbers:

PICT

A good exercise is to draw (potatoes and arrows …) the graphs of possible binary relations on a set with two elements, then to identify those of them that are transitive (we find ).

## 4 – Infinite Sets in Bijection

We said, at the beginning of the previous section, that given two sets finished and , conditions :

there is a bijection of towards

and have the same number of elements

are equivalent. But for infinite sets (that is to say with infinite elements), the expression “to have the same number of elements” does not make much sense anymore …

Moreover, things become in this context much less intuitive: in some cases, we observe the existence of bijections between two sets for which we have the impression that one is “bigger” than the other … (for example because it contains it strictly).

This is probably due to the fact that our mind develops, due to inappropriate terminology, an incorrect representation of the situation.

Here is a very classic example:

The natural numbers form a noted whole . If we add the negative integers we get a “bigger” set noted (initial of the German word “Zahl” which means number). The elements of are the “relative integers”.

Intuitively, we want to say “that there are twice as many elements in that in ! We could therefore think that there is no bijection of towards .

However, we can enumerate the relative integers, one after the other, so that each one is taken into account and that one never takes twice the same one. bijection

For this, it is out of the question to start with the positive integers, saying that “as soon as we are done with them”, we can go to negatives … and for good reason: we will never finish! On the other hand, one can envisage a “alternating enumeration”: a positive blow, a negative blow, and one begins again …

Let’s see the first steps of this enumeration:

PICT

More formally, with each natural number , we associate a relative integer noted defined by :

and it’s easy to show that is a bijection of towards .

In general, we say that a set is countable when there is a bijection of towards this set. So, the whole relative integers are countable.

We can show that the whole noted couples of natural numbers are also countable. A natural bijection of towards is suggested by the following figure: we list the pairs of natural numbers starting from and by traversing the successive “diagonals”, that is to say the sets , for

Sets are two to two disjoint and their union is whole. But the important point is that these sets are all finished, which ensures that no matter the couple considered, one will reach him in a finite number of stages, after having traversed a certain number of diagonals. Here we find, in a more elaborate form, the idea that allowed us to put and in bijection.

In the figure below, the points that make up the set are aligned on the red segment:

PICT

## 5 – A bijection of towards

This section will be a bit technical and will make use of knowledge generally taught in the first year of a math or science preparatory class. bijection

For the purposes of a subsequent explanation, relating to the non-countability of (see section 6), we will establish a bijection of towards .

At first, slightly modify the objective and build rather a bijection of towards . Just removing the left end of the gap will indeed make things easier …

Consider the application

We observe that u is the inverse of a strictly positive and decreasing function: is therefore strictly increasing. Furthermore continues because it is the opposite of a continuous function that does not cancel itself. As well as the limits of in and in are respectively and , we can say that u is a bijection. Here is his graph :

PICT

In order to obtain a bijection of towards , just build a bijection of towards and to consider (see section 2) the compound of by .

So consider the application:

here is the graph (the points represented by a small red disk are part of the graph of , while those represented by a small circle are not part of it):

PICT

Finally, the application is clearly a bijection, it is enough to finally consider the compound . We hold our bijection from to .

## 6 – The diagonal of Cantor

The German mathematician Georg Cantor (1845 – 1918) is credited with the following statement: is not countable.

As we have (see section 5) a bijection of towards , the existence of a bijection of towards result (by composition) in the existence of a bijection of towards . It is therefore sufficient to show that such a bijection does not exist, which is of course made by the absurd.

Any real number belonging to the interval can be written in a unique way, in the form of a proper decimal development (abbreviated DDP), that is, something of the style:

where the are integers between and (figures from the DDP of ) with the particular constraint that this development is not exclusively made up of 9 from a certain rank.

For example, the number can be written as desired:

\textbullet{} with an infinity of after the , what everyone just notes

\textbullet{} or with an infinity of after the

Do you have or doubt? Ok, let’s detail:

gold :

and so :

Convinced? From these two writings, we will retain the first, which constitutes the DDP of .

Suppose now the existence of a bijection . For each natural number n, the DDP of can be written:

We must understand this notation with two indices: means the – number (the numbering starts from ) of the DDP .

That’s where the great idea comes in brilliant idea of Cantor. He considers a real number whose DDP is

with the condition: for everything .

In a more visual way, one can imagine a table containing, line by line, the DDP of

This table therefore has an infinity of lines and each line has an infinity of columns! Cantor’s idea is to choose a sequence of numbers so that for all , the number be distinct from -th term of the diagonal.

PICT

As and given the uniqueness of the DDP, it is certain that .

Likewise, as and given the uniqueness of the DDP, it is certain that .

The argument becomes general: whatever the natural integer , we are certain that .

In other words, has no antecedent by , which is absurd since is supposed to be bijective!