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 X of the numbers to the set Y of my books must be bijective

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

In order to explain this link, we then note L=f\left(k\right), for everything k element of X. It is said, at choice, that L is the image of k by f or k is an antecedent of L by f.

Clear, f\left(k\right) means the book bearing the label n\lyxmathsym{\textdegree}k.

– 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 f, in other words, each book is identified by a number and only one.

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

Any element of Y has a unique antecedent in X bijection

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

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

V={\mbox{"Paris","Berlin","Madrid","London","Rome"}}

as well as a set P of six European countries:

P={\mbox{"France","Germany","Spain","England","Italy","Sweden"}}

and each city has been associated with the country of which it is the capital. But the capital of Sweden does not appear in V, 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 G=\left\{ 16,12,27,31,5\right\}

\textbullet{} On my right, the whole D=\left\{ 0,1,2\right\}

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

PICT

So, for example:

    \[ 31=3\times10+1\]

 

and so 31 admits 1 for image. Similarly for the other elements of G.

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 V inhabitants of a village and consider the application u who, to each of these people, associates the couple \left(g,f\right) or g refers to the number of his boys and f the number of his daughters. bijection

If for example Mr Tartempion belongs to V and if he has three boys and a girl, then his picture by u will be the couple \left(3,1\right).

Then consider the application v who, to any couple \left(m,n\right) of natural numbers associates their sum m+n.

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

This new application is noted v\circ u (which reads “ v round u “).

PICT

To formalize a little, let’s say that if u:X\rightarrow Y and v:Y\rightarrow Z are any two applications, then v\circ u:X\rightarrow Z is defined by:

    \[ \forall x\in X,\:\left(v\circ u\right)\left(x\right)=v\left(u\left(x\right)\right)\]

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

Yes u and v are bijections, the same goes for v\circ u.

3 – Bijections … okay, but what for?

You guessed it by reading section 1: given two sets finished X and Y , a necessary and sufficient condition for it to be possible to establish a bijection (a “perfect arrowing”) of X towards Y 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 n , a natural question is to determine the number of its subsets. So, the whole X=\left\{ 1,2,3\right\} has eight subsets, namely:

the empty set, noted \emptyset

singletons \left\{ 1\right\}, \left\{ 2\right\} and \left\{ 3\right\} (these are the subsets of cardinal 1)

the pairs \left\{ 1,2\right\}, \left\{ 1,3\right\} and \left\{ 2,3\right\} (these are the subsets of cardinal 2)

all X himself

Generally, if X is from cardinal n so X has exactly 2^{n} 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 X and another set whose cardinal is known (and equal to 2^{n}).

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 p and q. It can be noted N\left(p,q\right) to emphasize this dependence. But by what formula can we calculate N\left(p,q\right)?

One way to answer is to associate with each path a word of p+q 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 \left(0,0\right) towards \left(p,q\right) determines a word of length p+q comprising p times the letter D and q 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 p+q boxes and count the number of ways to choose p boxes among p+q (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 k objects among n (without repetition or consideration of order) is classically given by the following formula (of which the member on the left reads “ k among n “):

    \[ \binom{n}{k}=\frac{n!}{k!\thinspace\left(n-k\right)!}\]

Therefore, the number of paths is:

    \[ \boxed{N\left(p,q\right)=\frac{\left(p+q\right)!}{p!\thinspace q!}}\]

For example, if p=3 and q=2, the number of paths is:

    \[ N\left(3,2\right)=\frac{5!}{3!\thinspace2!}=10\]

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

    \[ N\left(9,6\right)=\frac{15!}{9!\thinspace6!}=5005\]

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 E, we are sometimes led to provide this set with a binary relation, which simply means that each element of E is related to zero, one or more other (s). You can visualize a binary relation by drawing an arrow of x towards y when x is in a Relationship with y. The diagram below represents a binary relation on a set of cardinal 11. We see in particular that c is in a Relationship with d, than g is in relation with himself and with f, than e is not in contact with anyone, etc.

PICT

A binary relation is called transitive if, for any triplet \left(x,y,z\right) of elements of E, the fact that x either in relation with y and y either in relation with z leads that x is in a Relationship with z.

For example, overall A=\left\{ 1,2,3,4,5,6,7,8,9,10,11,12\right\}, we can define the relation of divisibility: given two integers m and n belonging to A, we say that “ m Split n When there is a natural number k such as n=km (We also say that “ n is multiple of m “). 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 m Split n and if n Split p, then there are natural numbers k and \ell such as n=km and p=\ell n, from where p=k\ell m and so m Split p.

It is not very difficult to count the binary relations on a set E Cardinal n : there are 2^{n^{2}} ( 2 to the power n^{2} ). Let us say, without going into details, that this results from the existence of a bijection of the set of binary relations on E towards all the applications of E^{2} in \left\{ 0,1\right\}.

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

At most, can one (with the help of a computer) calculate the value of T_{n} for small values of n, 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 2^{2^{2}}=16 possible binary relations on a set with two elements, then to identify those of them that are transitive (we find 13).

4 – Infinite Sets in Bijection

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

there is a bijection of X towards Y

X and Y 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 0,1,2,... form a noted whole \mathbb{N}. If we add the negative integers -1,-2,... we get a “bigger” set noted \mathbb{Z} (initial of the German word “Zahl” which means number). The elements of \mathbb{Z} are the “relative integers”.

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

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 n, we associate a relative integer noted f\left(n\right) defined by :

    \[ \boxed{f\left(n\right)=\left\{ \begin{array}{cc} {\displaystyle \frac{n}{2}} & \text{if }n\text{ even}\\ \\{\displaystyle -\frac{n+1}{2}} & \text{if }n\text{ odd}\end{array}\right.}\]

and it’s easy to show that f is a bijection of \mathbb{N} towards \mathbb{Z}.

In general, we say that a set is countable when there is a bijection of \mathbb{N} towards this set. So, the whole \mathbb{Z} relative integers are countable.

We can show that the whole noted \mathbb{N}^{2} couples of natural numbers are also countable. A natural bijection of \mathbb{N} towards \mathbb{N}^{2} is suggested by the following figure: we list the pairs of natural numbers starting from \left(0,0\right) and by traversing the successive “diagonals”, that is to say the sets E_{s}=\left\{ \left(p,q\right)\in\mathbb{N}^{2};\, p+q=s\right\}, for s=0,1,2,3,\cdots

Sets E_{0},E_{1},E_{2},... are two to two disjoint and their union is \mathbb{N}^{2} whole. But the important point is that these sets are all finished, which ensures that no matter the couple \left(p,q\right)\in\mathbb{N}^{2} 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 \mathbb{N} and \mathbb{Z} in bijection.

In the figure below, the points that make up the set E_{p+q-1} are aligned on the red segment:

PICT

5 – A bijection of \mathbb{R} towards \left[0,1\right[

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 \mathbb{R} (see section 6), we will establish a bijection of \mathbb{R} towards \left[0,1\right[.

At first, slightly modify the objective and build rather a bijection of \mathbb{R} towards \left]0,1\right[. Just removing the left end of the gap \left[0,1\right[ will indeed make things easier …

Consider the application

    \[ u:\mathbb{R}\rightarrow\left]0,1\right[,\: x\mapsto\frac{1}{1+e^{-x}}\]

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

PICT

In order to obtain a bijection of \mathbb{R} towards \left[0,1\right[, just build a bijection v of \left]0,1\right[ towards \left[0,1\right[ and to consider (see section 2) the compound of v by u.

So consider the application:

    \[ v:\left]0,1\right[\rightarrow\left]0,1\right],\thinspace x\mapsto\left\{ \begin{array}{cc} 2x & \text{if }x\in\left\{ 2^{-n};\thinspace n\in\mathbb{N}^{\star}\right\} \\ \\x & \text{other}\end{array}\right.\]

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

PICT

Finally, the application w\thinspace:\thinspace\left]0.1\right]\rightarrow\left[0,1\right[,\thinspace x\mapsto1-x is clearly a bijection, it is enough to finally consider the compound w\circ v\circ u. We hold our bijection from \mathbb{R} to \left[0,1\right[.

6 – The diagonal of Cantor

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

As we have (see section 5) a bijection of \mathbb{R} towards \left[0,1\right[, the existence of a bijection of \mathbb{N} towards \mathbb{R} result (by composition) in the existence of a bijection of \mathbb{N} towards \left[0,1\right[. It is therefore sufficient to show that such a bijection does not exist, which is of course made by the absurd.

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

    \[ x=0,c_{0}c_{1}c_{2}\cdots c_{n}\cdots\]

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

For example, the number \frac{1}{2} can be written as desired:

\textbullet{} 0,500000\cdots with an infinity of 0 after the 5, what everyone just notes 0,5

\textbullet{} or 0,499999\cdots with an infinity of 9 after the 4

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

    \[ 0,499999\cdots=0,4+0,099999\cdots\]

gold :

    \[ 0,099999\cdots=0,99999\cdots\times10^{-1}=0,11111\cdots\times9\times10^{-1}=\frac{1}{9}\times9\times10^{-1}=10^{-1}=0,1\]

and so :

    \[ 0,499999\cdots=0,4+0,1=0,5\]

Convinced? From these two writings, we will retain the first, which constitutes the DDP of \frac{1}{2}.

Suppose now the existence of a bijection f:\mathbb{N}\rightarrow\left[0,1\right[. For each natural number n, the DDP of f\left(n\right) can be written:

    \[ f\left(n\right)=0,a_{0,n}a_{1,n}a_{2,n}\cdots\]

We must understand this notation with two indices: a_{i,n} means the i– number (the numbering starts from i=0 ) of the DDP f\left(n\right).

That’s where the great idea comes in brilliant idea of Cantor. He considers a real number \beta\in\left[0,1\right[ whose DDP is

    \[ \beta=0,b_{0}b_{1}b_{2}\cdots\]

with the condition: for everything n\in\mathbb{N},b_{n}\neq a_{n,n}.

In a more visual way, one can imagine a table containing, line by line, the DDP of f\left(0\right),f\left(1\right),f\left(2\right),...

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 b_{0},b_{1},b_{2},\cdots so that for all n\in\mathbb{N}, the number b_{n} be distinct from n-th term of the diagonal.

PICT

As b_{0}\neq a_{0,0} and given the uniqueness of the DDP, it is certain that \beta\neq f\left(0\right).

Likewise, as b_{1}\neq a_{1,1} and given the uniqueness of the DDP, it is certain that \beta\neq f\left(1\right).

The argument becomes general: whatever the natural integer n, we are certain that \beta\neq f\left(n\right).

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

Add a Comment

Your email address will not be published. Required fields are marked *