Précédent
 
Suivant
De l'algèbre
et du dénombrement
(2ème partie)

 

1) Relation

Une relation `R` est un ensemble de couples d'éléments.

Une relation `R` de `A` vers `B` est un sous-ensemble de `A×B`. Autrement dit, l'ensemble des relations de `A` vers `B` est l'ensembles des parties `ccP(A×B)`. L'ensemble des relations de `A` vers `B` se note en bisymbole par `A "××" B`.

`(A "××" B) = ccP(A×B)`

Lorsque `A` et `B` sont des ensembles finis, le nombre de relations distinctes de `A` vers `B` est égal à :

|ccP(A×B)| = 2^(|A| |B|)`

On dira que la relation `R` part de `A` pour aller vers `B`, ou simplement que c'est une relation de `A` vers `B`. L'ensemble `A` s'appelle l'ensemble de départ et se note Dép`(R)`. L'ensemble `B` s'appelle l'ensemble d'arrivé et se note Arr`(R)`.

On pourrait penser qu'une relation d'un ensemble `A` vers un ensemble `B` est une notion mathématique plus générale qu'une relation d'un ensemble `E` vers lui-même. Il n'en est rien. Car `A` peut être égal à `B` et réciproquement, une relation de `E` vers lui-même peut partir d'un sous-ensemble de `E` pour aller sur un autre sous-ensemble de `E`. Les deux notions se contiennent mutuellement. Donc, celle qui est la plus simple, est la plus générale.

Lorsque l'ensemble de départ et d'arrivé ne sont qu'un seul ensemble `E`, la relation est dite sur `E`.

Une relation `R` sur `E` est un ensemble de couples d'éléments de `E`. Autrement dit, l'ensemble des relations sur `E` est `E "××" E = ccP(E^2)`.

Lorsque `E` est un ensemble fini, le nombre de relations distinctes sur `E` est égal à :

`|E "××" E| = |ccP(E^2)| = 2^(|E|^2)`

Lorqu'on pose une relation `R` sans préciser les ensembles de départ et d'arrivé, la relation `R` étant un ensemble de couples, elle induit un ensemble des éléments apparaissant comme premier élément dans au moins un couple de `R`. On appel cet ensemble, la base de départ de `R` ou encore le domaine de définition de `R`, et on le note Dom`(R)`. Et elle induit un ensemble des éléments apparaissant comme second élément dans au moins un couple de `R`. On appel cet ensemble, la base d'arrivée de `R` ou encore l'image de `R`, et on le note Im`(R)`. Et on appel la base de `R`, la réunion des deux.

Afin de pouvoir dénombrer les relations, on les munie d'un ou de deux ensembles supports ; d'un ensemble de départ et d'un ensemble d'arrivé, qui peut être le même sans altérer nullement la généralité tout au contraire, et qui pose ainsi un cadre, une délimitation, définissant un ensemble de relations pouvant être dénombrées le cas échéant, et définissant un type qui permettra le typage des arguments par inférence comme on le verra au chapitre n°5. Par définition nous avons :

Dom`(R) sube` Dép`(R)`
Im`(R) sube` Arr`(R)`

Une relation `R` est un 1-graphe orienté c'est à dire un graphe où les arêtes sont orientées et appelé arcs c'est à dire ont un sens de circulation, et où quelque soit deux sommets `a,b`, il n'y a au plus qu'un seul arc partant de `a` pour aller sur `b`. Chaque éléments `x` de l'ensemble de départ ou de l'ensemble d'arrivé, est un sommet. Chaque couple `(a,b) in R` est un arc partant du sommet `a` et allant sur le sommet `b` et que l'on note `aRb`. Cette expression a aussi une interprétation logique : `aRb` signifie qu'il existe un arc de `R` passant de `a` à `b`, et l'expression `¬ aRb` signifie qu'il n'existe pas d'arc de `R` passant de `a` à `b`.

`aRb    <=>    (a,b) "∈" R`

Etant donné un arc `aRb`, l'élément `b` est dit un successeur de `a`, et l'élément `a` est dit un prédécesseur de `b`.

La relation complémentaire de `R` : ...

La relation vide : ...

La relation pleine : ...

La relation binaire est la pierre de voûte du modèle mathématique, réunissant les trois pans du langage : le langage de donné, le langage de propriété et le langage de programmation. En effet les relations désignent à la fois des arcs qui constituent des éléments, des prédicats qui constituent des propriétés, et des graphes qui constitue des programmes. C'est pourquoi il est utile d'étudier les relation binaires de façon exhaustive, c'est à dire en parcourant tous ce qu'il est possible de construire en commençant par les constructions les plus simples.

2) Composition de relations

Deux arcs sont adjacents si et seulement si l'un arrive sur un sommet et l'autre part de ce même sommet. Mis bout à bout dans l'ordre de leur adjacence, ils forment un chemin orienté.

Un chemin orienté est une succession d'arcs, le premiers est quelconque et les suivants partent du sommet d'arrivé de leur précédent.

Etant donné deux relations `R` et `S`, on note `SR`, la relation composée qui relie deux éléments quelconques `a` à `b` par un chemin orienté de deux arcs, pris dans le bon sens et dont le premier arc appartient à `S` et le second arc appartient à `R` :

`SR = {(a,b) "/" EEx,  aSx,  xRb}`

Quelque soit deux éléments `a` et `b` l'expression `aSRb` signifie que l'on peut se déplacer continûment de `a` en `b`, en empruntant un arc de `S` dans son sens de circulation, suivie d'un arc de `R` dans sons sens de circulation. Ces deux arcs sont dits adjacents.

On attribue naturellement, comme ensemble de départ et d'arrivé à la composition de relations `SR`, respectivement l'ensemble de départ de `S` et l'ensemble d'arrivé de `R`.

Si on effectue la composition avec la même relation `R` on écrit le résultat à l'aide d'une puissance :

`R^2 = R\R`

Pour les puissances supérieures, la relation `R^n` désigne la relation reliant les sommets par des chemins orientés pris dans le bon sens, composés de `n` arcs appartenant à `R`.

Puis on définie l'opérateur de Kleene, l'étoile, `R^**` :

La relation `R^**` désigne la relation reliant les sommets par des chemins orientés pris dans le bon sens, composés d'un nombre quelconque d'arcs appartenant à `R`. Le chemin orienté de zéro arc est considéré comme un chemin de taille zéro ne permettant que de rester sur place. Aussi nous avons :

`AAx,  xR^**x`

Notez que si `R` est défini sur un ensemble, alors le `AAx` évoqué dans cette expression doit être appliqué à cet ensemble. Nous expliquerons plus tard cette interprétation dans le chapitre n°5 sur l'inférence des types.

L'élèvation à la puissance zéro d'une relation `R` produit la relation d'égalité, c'est à dire vérifie :

`AAxAAy,  xR^0y <=> (x=y)`

L'élèvation à la puissance `-1` d'une relation `R` produit la relation inverse notée `R^-1`, c'est à dire la relation dans laquelle on a inversé le sens de tous les arcs.

L'élèvation à une puissance négative `-n` d'une relation `R` produit la relation inverse à la puissance `n` notée `R^-n`.

3) Application

Une application `f` de l'ensemble `A` vers l'ensemble `B` est une relation de l'ensemble `A` vers l'ensemble `B`, qui, à chaque élément `a` appartenant a `A`, associe un et un seul élément `b` appartenant a `B`. Cette association correspond à un arc de `f` partant de `a` et allant sur `b` et que l'on note par l'égalité `f(a)=b`. L'élément `b` est appelé l'image de `a` par `f` et se note `f(a)` ou bien en notation française `a^f` (ou encore `a_f`). Tandis que l'élément `a` s'appel l'antécédent de `f(a)`.

On note l'ensemble des applications de `A` vers `B` de trois façons possibles, soit en notation algèbrique avec le symbole de la flêche `A->B`, ou soit en notation ensembliste avec le symbole de puissance, l'ensemble d'arrivé à la puissance l'ensemble de départ : `B^A`, ou encore en bisymbole par `A "=×" B`.

`(A "=×" B) = (A->B) = B^A

La théorie de l'application est la suivante :

`(A->B) = { R"∈"ccP(A×B) "/"` Chaque application est une relation vérifiant :
        `AAx"∈"A, AA(y,z)"∈"B^2,  xRy` et `xRz => y"="z`   Chaque élément de l'ensemble de départ a zéro ou un seul successeur.
        `AAx"∈"A, EEy"∈"B,  xRy,`     Chaque élément de l'ensemble de départ a un ou plusieur successeurs.
`}`  

Notez que dans les formules, les quantifications universelles et existencielles des variables ont une portée par défaut qui s'étend sur le reste de la formule jusqu'à une parenthèse englobante fermante ou ici jusqu'à un passage à la ligne.

Notez que la priorité syntaxique de l'égalité `=` est posée comme la plus faible au dessus de celles des quantificateurs, et que la priorité syntaxique de l'implication `=>` et de l'équivalence `<=>` sont posées de force juste au-dessus. Ainsi l'expression `H = P" et "Q => R` signifie `H = ((P" et "Q) => R)`.

La décomposition en axiomes dans le langage logique du premier ordre, de la définition d'une application, fait apparaitre deux axiomes. On les désigne chacun par un nom ou un qualificatif, et la réunion des deux se désigne également par un nom et un qualificatif comme suit :

Nom
Qualificatif
Description
Transformation
Partout définie
Chaque élément de l'ensemble de départ a un ou plusieur successeurs.
Fonction
Déterministe
Chaque élément de l'ensemble de départ a zéro ou un seul successeur.
Application
Applicatif
Chaque élément de l'ensemble de départ a exactement un successeur.

Les noms présentés ici sont plus riches que les seuls qualificatifs qui, eux, peuvent s'appliquer sur des objects plus généraux que les relations comme on le verra plus tard. Le terme de transformation désigne une relation partout définie, il regroupe donc le fait d'être une relation et le fait d'être partout définie. De même le terme de fonction désigne une relation déterministe, il regroupe donc le fait d'être une relation et le fait d'avoir la propriété déterministe. De même le terme d'application désigne une relation applicative, il regroupe donc le fait d'être une relation et le fait d'avoir la propriété applicative.

L'application `f` constitue une transformation déterministe ou encore une fonction partout définie. L'image d'un élément `x` par l'application `f` est le résultat de la transformation de `x` par `f`, et cette transformation étant déterministe ne produit qu'un et un seul résultat noté `f(x)`. L'image d'un élément `x` par l'application `f` est le résultat de la fonction `f`, qui étant défini partout, peut s'appliquer à `x` pour produire le résultat `f(x)`.

Les fonctions se différencient des applications en ce qu'elles ne sont pas forcement définies partout sur leur ensemble de départ.

Les termes d' « élément image » et d' « élément antécédent » sont utilisés avec les fonctions. Tandis que les termes de « successeur » et de « prédécesseur » sont utilisés d'une façon plus générale avec toutes les relations. Ils constituent donc des synonymes à ceci près que l'usage des premiers précise que la relation sur laquelle ils portent est déterministe c'est à dire constitue une fonction.

Si les ensembles `A` et `B` sont finis, le nombre d'applications distinctes est égal à :

`|A "=×" B| = |A->B| = |B^A| = |B|^(|A|)`

Lorsque l'ensemble de départ et d'arrivé ne sont qu'un seul ensemble `E`, on dit que l'application `f` est définie sur `E`. L'ensemble des applications sur `E` se note de façon algèbrique par `E->E` ou bien de façon ensembliste par `E^E`, ou bien encore en bisymbole par `E "=×" E`.

Lorsque `E` est un ensemble fini, le nombre d'applications distinctes sur `E` est égal à :

`|E "=×" E| = |E->E| = |E^E| =|E|^|E|`

3.1) Calcul du nombre d'applications `|A->B|`

S'il nous faut définir la puissance à partir de la multiplication et de l'adition des entiers `f(a,b)=b^a`, on peut le faire de deux façons différentes, soit par réccurence :

`f(a"+"1,b)=bf(a,b)`
`f(0,b)=1`

ou soit par itération :

`f(a,b)=prod_(a=1)^a b`

Cela correspond a deux types de programmation ; la programmation récurcive et la programmation itérative, ici de complexité égale. Mais on est encore loin de l'algorithme de calcul plus efficace qui utilise une décomposition des entiers pour partager le travail et qui en partage ainsi les résultats intermédiaires en évitant ainsi de les recalculer plusieurs fois.

Le même raisonnement peut être fait à partir des ensembles `A` et `B` et à partir du procédé de construction des applications de `A->B`.

Dans un premier temps, on ne s'intéresse qu'à la programmation récurvive qui ne nécessite pas de développer un langage de programmation très riche.

3.2) Calcul par récurrence de `|A->B|`

On note :

`a = |A|`
`b= |B|`
`f(a,b) = |A->B|`

`f(a,b)` désigne le nombre d'applications distinctes d'un ensemble de `a` éléments vers un ensemble de `b` éléments.

En bref : Si on ajoute un nouvel élément `e`, les applications de `(A"+"{e})->B` se construisent à partir des applications de `A->B`, en les complétant par n'importe quelle application de `{e}->B`. Cela se traduit par la relation de récurrence suivante : `f(a"+"1,b) = bf(a,b)`

Etant donné deux applications `h,g`. Ce sont des ensembles de couples. On peut donc les réunir si ils sont disjoints à l'aide de l'union disjointe `h+g`. Et si l'ensemble de départ de `h` noté Dép`(h)` est disjoint de l'ensemble de départ de `g` noté Dép`(g)`, alors la relation `h+g` est encore une application mais dont l'ensemble de départ est naturellement Dép`(h+g) =` Dép`(h)+`Dép`(g)`.

On dévoile la relation de récurrence sur les ensembles :

`(A"+"{e}->B)   =   {h + g "/" h"∈" (A->B), g"∈"({e}->B)}`
`(A"+"{e}->B)   =   sum_(h in (A->B)) sum_(g in ({e}->B)) {h + g}`
`|A"+"{e}->B|   =   |A->B| |B|`
`f(a"+"1,b)   =  b f(a,b)`
 
`Ø->B   =   {Ø}`
`|Ø->B|  =   1`
`f(0,b)   =   1`

Conclusion :

`f(a"+"1,b)   =  b f(a,b)`
`f(0,b)   =   1`

Vous pourrez vérifier que cela définit bien l'élévation à la puissance `f(a,b) = b^a`

3.3) Composition des applications

L'image de `x` par l'application `f` se note de deux façons, soit à l'anglaise dite gauche, par `f(x)`, soit à la française dite exponentielle, par `x^f` (ou quelque fois indicielle, par `x_f`).

Les applications se composent pour produire d'autres applications si les ensembles d'arrivés s'emboitent dans les ensembles de départ des applications suivantes. La composition des applications peut s'écrire de deux façons, de gauche à droite, ou de droite à gauche. C'est pourquoi il existe deux lois de composition, une gauche et une droite, soit avec l'opération de composition à l'anglaise, dite gauche, notée `@`, et qui s'écrit de droite à gauche, soit avec l'opération de composition à la française, dite droite, notée `*`, et également notée par absence de symbole, et qui s'écrit de gauche à droite. Par exemple considérons deux applications `f, g` sur `E` , nous avons :

                                    `g(f(x))=(x^f)^g`

Notation anglaise
Notation française
`(g@f)(x) = g(f(x))`
`x^(fg) = (x^f)^g`

On remarquera que la composition d'applications est une opération associative. Par exemple considérons trois applications `f, g, h`. Nous avons `(fg)h = f(gh)` et donc on notera simplement `fgh`.

Notation anglaise
Notation française
`(h@g@f)(x) = h(g(f(x))`
`x^(fgh) = ((x^f)^g)^h`

Conformément à la composition de relations, les ensembles de départ et d'arrivé d'une composition d'applications sont respectivement l'ensemble de départ de la première application et l'ensemble d'arrivé de la dernière application. Puis grâce au typage par inférence mis en oeuvre par le langage, une application de `A->B` peut être percu comme un opérateur permettant de convertir un élément de type `A` en un élément de type `B`.

Considérons une application `f` sur `E`. Autrement dit `f in (E->E)`. On note :

`f^2= f@f`
`f^n = f@f@f... n "fois" ...`

ou en notation française :

`f^2=ff`
`f^n =fff... n "fois" ...`

Et cela correspond exactement à la même notation que pour les relations.

Parcontre la relation inverse d'une application n'est pas forcement une application, c'est le cas seulement lorsque la relation en question est une bijection.

4) Le langage logique du premier ordre

Le langage logique du premier ordre, augmenté du prédicat `R"(.,.)"` définissant une relation `R` quelconque, permet d'exprimer les théories du premier ordre sur les relations `R`.

D'après l'étude de ce langage, toute expression d'une théorie du premier ordre admet une forme prénexe (c'est à dire avec tout les quantificateurs placés en premier), en une conjonction de clauses de littéraux, à l'ordre près des clauses, à l'ordre près des littéraux, et à l'ordre près des variables universelles dans chaque clause, les variables universelles n'ayant de portée qu'à l'intérieur d'une clause.

Dans notre premier exemple qu'est la théories des applications de `A->B`, Le prédicat `A"(.)"` désigne l'ensemble `A`, cela signifie que `A(x)` est équivalent à `x"∈"A` , de même pour le prédicat `B"(.)"` qui désigne l'ensemble `B`. La théorie d'une application `R` s'exprime sous forme normale comme suit :

Relation de `A` vers `B` : `((AAxAAy,  ¬xRy" ou "A(x)),(AAxAAy,  ¬xRy" ou "B(y)))`
Partout définie : `AAxEEe,  ¬A(x)" ou "xRe`     
Déterministe : `AAxAAyAAz,  ¬A(x)" ou " ¬B(y)" ou "¬B(z)" ou "¬R(x,y)" ou "¬R(x,z)" ou "y"="z`  

La décomposition en axiomes se fait sans introduire d'arbitraire. Ainsi l'application est gouvernée par ces deux axiomes, et est couramment dénommée transformation déterministe ou bien fonction partout définie.

5) L'inférence de type

En séparant ce qui peut s'écrire dans le langage logique du premier ordre du reste, on met en exhergue des énoncées d'une logique supérieure fixant le cadre du langage logique du premier ordre utilisé. L'usage des types en fait partie et constitue la première étape la plus simple à mettre en oeuvre.

Dans l'exemple précédent présentant la théorie de l'application, la première proposition qui affirme que `R` est une relation de `A` vers `B`, et qui est pourtant du premier ordre, va être interprété d'un ordre un peu au delà en forçant les variables appelées par `R` à respecter implicitement ses deux limitations. Considérons la proposition suivante :

`R"∈"ccP(A×B)`
`Ax, xRx`

Au regard du cadre définissant `R`, cette expression est identique à la suivante :

`R"∈"ccP(A×B)`
`Ax"∈"(AnnB), xRx`

La notion d'ensemble de tous les ensembles ou de tous les éléments est trop globale et révèle davantage les paradoxes de la logique utilisée (ici le paradoxe de Russel) que les propriétés des objets étudiés. Puis, nous voulons dénombrer, c'est pourquoi il nous faut limiter les tailles des ensembles utilisés et même davantage commencer par le cas fini. L'expression `Ax` doit faire référence à un ensemble circonscrit. Mais lequel ? C'est là qu'intervient le mécanisme d'inférence des types, un mécanisme utilisé dans de nombreux langages de programmation évolués, permettant de ne pas répéter plusieurs fois la définition des domaines parcourus par les variables. Les opérations contiennent dans leur définition les domaines autorisés pour chacun de leurs arguments. Le domaine d'une variable sera égal à l'intersection des domaines alloués par les opérations qui lui font appel, dans une même portée.

En adoptant le mécanisme d'inférence de type, la théorie précédente se réécrit plus simplement comme suit :

Relation de `A` vers `B` `R in ccP(A×B)`
Partout définie : `AAx,  "xRf(x)`     
Déterminisme `AAxAAyAAz, ¬R(x,y)" ou "¬R(x,z)" ou "y"="z`  

6) Relation étendue aux ensembles

On utilise pour les relations, une notation étendue aux ensembles. Étant donné une relation `R` de `A` vers `B`, cette relation peut être interprétée comme une application de `ccP(A)->ccP(B)` comme suit : Pour chaque ensemble `X` inclus dans `A`, la relation `R` se comporte comme une application et transforme cet ensemble en un ensemble image noté `R(X)` qui est évidement inclus dans `B`. Cet ensemble est l'ensemble de tous les éléments atteignables en choisissant un élément de `X` et en parcourant un arc de `R` dans le sens de la flêche.

Et il y a deux notations possibles soit l'anglaise dite gauche, ou soit la française, dite exponentielle :

Notation anglaise
Notation française
`R(X)`
`X^R`

Dans ce mode interprétatif, `R` est une application de `ccP(A)` vers `ccP(B)`. Notez que pour un élément `a in A`, l'expression `R(a)` n'est pas autorisée (sauf si `a` est également un ensemble inclus dans `A`).

À ce stade de notre discussion, la notation `f(x)` signifie que `f` est une application et que `x` appartient à l'ensemble de départ de `f`. C'est pourquoi on ne peut pas utiliser cette notation pour des relations sauf dans le mode étendue aux ensembles où la relation est alors vue comme une application sur l'ensemble des parties et où `x` est un sous-ensemble.

La relation inverse `R^(-1)` correspond à la relation `R` dans laquelle on a inversé le sens de tous les arcs. Elle devient aussi une application de `ccP(B)` vers `ccP(A)`. Mais attention dans le cas générale elle ne constitue pas l'application inverse.

Notation anglaise
Notation française
`X sube R^-1(R(X))`
`X sube (X^R)^(R^-1)`

L'expression `R^(-1)(Y)` désigne l'ensemble de tous les éléments atteignables en choisissant un élément de `Y` et en parcourant un arc de `R` dans le sens inverse de la flêche.

Pour alléger l'écriture, on s'autorise à simplifier les formes d'appel étendue aux ensembles, lorsque l'argument d'appel est un ensemble énuméré entre braquettes tel que par exemple `{a,b}`. Dans ce cas, on enleve les parenthèses de l'appel qui joue un rôle superflu. Ainsi l'expression `R({a,b})` se notera plus simplement `R{a,b}`. L'expression `R{a}` représente l'ensemble des éléments atteignables à partir de `a` en empruntant un arc quelconque de `R` dans son sens autorisé. Notez que l'expression `R(a)` n'est pas autorisée, sauf si `a` est également un ensemble inclus dans `A`, car `R` n'est pas une application.

7) Ensemble image

Une application étant une relation, toutes les notations relatives aux relations s'appliquent également aux applications. Néanmoins, étant donné une application `f` de `A` vers `B`, si `a` est à la fois un élément de `A` et un ensemble d'éléments de `A` , alors il y a une ambiguité dans l'expression `f(a)`, car `f` peut être intérprétée de deux façons différentes soit comme une application de `A` vers `B` ou soit comme une application de `ccP(A)` vers `ccP(B)`. Alors dans ce cas là, le contexte devra préciser laquelle des interprétations doit être faite.

Étant donné une application `f` et un ensemble `X` d'éléments appartenant à l'ensemble de départ de `f`, l'expression `f(X)` désigne l'ensemble image de `X` par `f`, c'est à dire l'ensemble des images des élements de `X` par `f`. Et il y a deux notations possibles soit l'anglaise dite gauche, ou soit la française dite exponentielle :

Notation anglaise
Notation française
`f(X) = {f(x) " / " x in X}`
`X^f = {x^f" / " x in X}`

L'expression `f^(-1)(X)` désigne l'ensemble des éléments atteignables à partir de l'ensemble `X` en prenant un arc de `f` dans le sens inverse :

Notation anglaise
Notation française
`f^(-1)(Y) = {x" / " f(x) in Y }`
`Y^(f^(-1)) = {x" / " x^f in Y }`

Remarquez que `f` est une application et que `f^(-1)` est la relation inverse, et que cette relation inverse n'est pas forcement une application. On ne peut donc pas l'appliquer à un élément `x` de l'ensemble d'arrivé. Mais on peut l'appliquer dans la notation étendue aux ensembles, on peut l'appliquer au singleton `{x}`. L'expression `f^(-1){x}` représente alors l'ensemble des antécédents de `x`, c'est à dire l'ensemble des éléments dont l'image par `f` est `x`.

Étant donné une application `f` sur `E`. C'est à dire que `f in (E->E)`. L'application `f` peut être composée avec elle-même `n` fois pour produire l'application `f^n`.

Par convention `f^0 = id`, l'application identité `(x|->x)` définie sur `E`.

L'application `f` étant aussi une relation, les notations `f^**` et `f^+` désignent les relations suivantes. Soit `x` un élément de l'ensemble de départ de `f`, nous avons :

`f^**{x} = {x, f(x), f^2(x),...f^n(x),...}` `f^**{x} = uuu_(n=0)^oo {f^n(x)}`
`f^+{x} = {x, f(x), f^2(x),...f^n(x),...}` `f^**{x} = uuu_(n=1)^oo {f^n(x)}`

soit `X` un ensemble inclus dans l'ensemble de départ de `f`, nous avons :

`f^**(X) = uuu_(n=0)^oo uuu_(x inX){f^n(x)}`
`f^+(X) = uuu_(n=1)^oo uuu_(x inX){f^n(x)}`

8) Fonction

Une fonction `f` de `A` vers `B` est une relation de `A` vers `B` où chaque élément de l'ensemble de départ doit avoir zéro ou un seul arc qui part.

On note l'ensemble des fonctions de `A` vers `B` de deux façons possibles, soit en notation algébrique avec le symbole de la flêche pointillée `A⇢B`, ou en bisymbole par `A ":×" B`.

La théorie de la fonction est la suivante :

`(A ":×" B) = (A⇢B) = B^A = { R"∈"ccP(A×B)" / "` // Chaque fonction est une relation vérifiant :
        `AAx"∈"A, AA(y,z)"∈"B^2,  xRy` et `xRz => y"="z`   // Chaque élément de l'ensemble de départ a zéro ou un seul successeur.
`}`  

Autrement dit, pour tout élément `x` de l'ensemble de départ, soit il n'y a aucun arc qui part de cet élément ou soit il y a un seul arc qui part de cet élément, et cet arc aboutit alors à une image de `x` par `f` que l'on note `f(x)`. Mais cette notation pose problème, car on peut ainsi exprimer un élément image qui n'existe pas forcement.

L'ensemble des éléments ayant une image par `f` est appelé le domaine de `f` et se note Dom`(f)`. C'est la base de départ de `f`.

Une fonction, à la différence d'une application, peut ne pas être définie partout sur son ensemble de départ. Etant donnée une fonction et un élément `x` de l'ensemble de départ, il se peut que `x` n'est pas d'image et donc que `f(x)` n'existe pas, ce qui se note par `f{x}=Ø`. Notez dans cette expression l'usage des braquettes `{}` qui signifie que l'on se place dans la relation étendue aux ensembles.

Une fonction est une relation déterministe. C'est à dire qu'il n'y a pas plusieurs choix possibles pour se déplacer d'un éléments de l'ensemble de départ en empruntant un arc de `f` dans le sens autorisé. Car, en effet, chaque élément de l'ensemble de départ a zéro ou un seul arc qui part.

8.1) Fonction méta-étendue en application

Les applications sont plus pratiques que les fonctions, car pour les fonctions, il est nécessaire à chaque fois de vérifier l'existence d'une image avant de pouvoir l'utiliser. C'est pourquoi il existe un procédé classique pour transformer une fonction en une application sans qu'il n'y ait aucune perte d'information. On utilise un nouveau symbôle, le symbole `sf"FAIL"` pour désigner l'absence d'image. Délors la fonction devient une application et l'ensemble d'arrivé est augmenté d'un méta-élément, le méta-élément `sf"FAIL"`.

Toute fonction s'étend à la valeur `sf"FAIL"` comme suit : lorsqu'elle est appliquée à `sf"FAIL"` elle retourne `sf"FAIL"`, ainsi l'ensemble de départ est augmenté du méta-élément `sf"FAIL"`. Ainsi il est toujours possible de composer des fonctions comme on compose des applications dont l'ensemble d'arrivé s'emboite par inclusion dans l'ensemble de départ de la suivante.

Chaque fonction `f` de A⇢B s'étend en une application de même nom `f` de `(A+{sf"FAIL"})->(B+{sf"FAIL"})` comme suit :

`f (sf"FAIL")=sf"FAIL"`
`x !in `Dom`(f)    <=>   f(x)=sf"FAIL"`

Et pour faire la distinction entre les attributs de la fonction et les attributs de la fonction méta-étendue, on suffixe par le caractère `"_"` le nom de l'attribut pour spécifier qu'il s'applique à la fonction méta-étendue. Ainsi nous avons :

Dép_`(f)= `Dép`(f) + {sfFAIL}`
Dom_`(f) = `Dom`(f) + {sfFAIL}`
Arr_`(f) = `Arr`(f) + {sfFAIL}`

Si la fonction `f` est une application c'est à dire si `f` est définie partout alors :

Im_`(f) = `Im`(f)`

Et si la fonction `f` n'est pas une application c'est à dire si `f` n'est pas définie partout alors :

Im_`(f) = `Im`(f) + {sfFAIL}`

La fonction est un programme de calcul, qui appliqué à un élément `e` de son ensemble de départ, retourne soit une image si le calcul aboutit, ou soit `sf"FAIL"` si le calcul échoue. Dans ce dernier cas l'élément `e` n'a pas d'image par la fonction `f`, mais, possède une image par la fonction étendue, et cette image est le méta-élément `sf"FAIL"`.

Les fonctions méta-étendues peuvent s'étendrent encore davantage à tous les éléments en retournant `sf"FAIL"` si l'élément n'est pas dans son ensemble de départ. Dans cette interprétation encore plus générale, les fonctions peuvent se composer quelque soit leur ensemble de départ et d'arrivé. Et conformément à la composition de relations, les ensembles de départ et d'arrivé d'une composition de fonctions sont respectivement l'ensemble de départ de la première fonction et l'ensemble d'arrivé de la dernière fonction.

8.2) Calcul du nombre de fonctions `|A⇢B|`

Le nombre de fonctions distinctes de `A` vers `B` est égal au nombre d'applications de `A->(B+{sf"FAIL"})` :

`|A ":×" B| = |A⇢B| = |A->(B+{sf"FAIL"})| = (|B|+1)^|A|`

Le nombre de fonctions distinctes sur un ensemble de `n` éléments est égal à `(n+1)^n`

9) Bijection

Une bijection `f` de l'ensemble `A` vers l'ensemble `B` est une application de l'ensemble `A` vers l'ensemble `B` qui est injective et surjective

On note l'ensemble des bijections de `A` vers `B` en bisymbole par le signe double égale `A "==" B`. On note l'ensemble des bijections sur `A` par `A "==" A` et aussi par `frS_A`.

Si l'ensemble `A` est fini alors `frS_A` s'appel l'ensemble des permutations sur `A` et est également fini. Le nombre de permutations distinctes sur `A` est donné par la formule suivante :

`|A "==" A| = |frS_(A)| = |A|!`

La théorie de la bijection est la suivante :

`(A "==" B) = { R"∈"ccP(A×B)" / "` // Chaque bijection est une relation vérifiant :
        `AAx"∈"A, EEy"∈"B,  xRy,`     // Chaque élément de l'ensemble de départ a un ou plusieur successeurs.
        `AAx"∈"A, AA(y,z)"∈"B^2,  xRy` et `xRz  =>  y"="z`   // Chaque élément de l'ensemble de départ a zéro ou un seul successeur.
        `AA x "∈"B, EE y "∈"A,  yRx` // Chaque élément de l'ensemble d'arrivé a un ou plusieur prédécesseur.
        `AA(x,y)"∈"A^2, AAz"∈"A,  xRz` et `yRz  =>  x"="y` // Chaque élément de l'ensemble d'arrivé a zéro ou un seul prédécesseur.
`}`  

La décomposition en axiomes, dans le langage logique du premier ordre, de la définition d'une bijection, fait apparaitre 4 axiomes. On les désigne chacun par un nom ou un qualificatif comme suit :

Nom
Qualificatif
Description
Transformation
Partout définie
Chaque élément de l'ensemble de départ a un ou plusieur successeurs.
Fonction
Déterministe
Chaque élément de l'ensemble de départ a zéro ou un seul successeur.
 
Surjective
Chaque élément de l'ensemble d'arrivé a un ou plusieur prédécesseur.
 
Injective
Chaque élément de l'ensemble d'arrivé a zéro ou un seul prédécesseur.

Le qualificatif « bijectif » signifie injectif et surjectif. Mais attention, le nom « bijection » signifie « application bijective ».

Une bijection est une fonction partout définie et injective et surjective, ou encore, une transformation déterministe injective et surjective, mais le plus courament dit, est une application bijective.

Les 4 axiomes de la bijection peuvent être combinées de `2^4 = 16` façons possibles. Cela va donner lieu à la définition de 16 types de relations.

Il exite une symétrie entre ces 4 axiomes. Si une relation vérifie un axiome, la relation inverse vérifie son axiome symétrique. L'inverse d'une transformation est une relation surjective, et réciproquement. L'inverse d'une fonction est une relation injective, et réciproquement.

Il va donc nous falloir étudier 8 types de relations. Ce sera la liste suivante : (application, fonction, bijection, injection, fonction injective, surjection, transformation, transformation surjective).

9.1) Calcul par récurrence du nombre de permutations `|frS_(A)|`

On note :

`a = |A|`
`f(a) = |frS_(A)|`

`f(a)` désigne le nombre de permutations distinctes sur un ensemble de `a` éléments.

En bref : Si nous ajoutons un nouvel élément `e`, l'ensemble des bijections sur `(A"+"{e})` comprennent les bijections composées d'une bijection de `A` vers `A"+"{e}"-"{x}`, où `x` est un élément quelconque de `A"+"{e}`, que l'on complète par `(e|->x)`. Cela se traduit par la relation de récurrence suivante : `f(a"+"1) = (a"+"1)f(a)`

On dévoile la relation de récurrence sur les ensembles :

`frS_(A"+"{e})  =   {h + (e|->x) " / "x "∈" (A"+"{e}), h"∈"(A "==" A"+"{e}"-"{x})}`
`frS_(A"+"{e})  =   sum_(x in (A"+"{e})) sum_(h"∈" (A "==" A"+"{e}"-"{x})) {h + (e|->x)}`
`|frS_(A"+"{e})|   =   |A"+"{e}| |A "==" A"+"{e}"-"{x}|`
`f(a"+"1)   =  (a"+"1) f(a)`
 
`frS_({x})   =   {(x|->x)}`
`f(1)   =   1`
 
`frS_(Ø)   =   {Ø}`
`f(0)   =   1`

Conclusion :

`f(a"+"1)   =  (a"+"1) f(a)`
`f(1)   =   1`
`f(0)   =   1`

Vous pourrez vérifier que cela définit bien le factroriel `f(a) = a!`

Notez que le calcul de `|frS_(A)|` peut s'écrire plus simplement de façon itérative si on choisie un langage adapté. L'idée est simple, elle consiste à énumérer toutes les permutations de `frS_(A)`. L'ensemble `A` étant fini, on numérote ses éléments de telles sortes que `A = {1,2,3,...,a}``a=|A|`. Puis on programme un énumérateur des bijections appartenant à `frS_(A)`. Le premier élément peut avoir `a` images possibles, le second élément peut avoir `a-1` images possibles, et pour `n` variant de `1` à `a`, le `n`-ième élément peut avoir `a-n+1` images possibles. Il y a donc `a(a-1)(a-2)(a-3)...1` `=` `a!` bijections distinctes de `A` vers `A`.

10) Injection

Une injection est une application injective. On note l'ensemble des injections de `A` vers `B` de deux façons, soit en notation algébrique par `A ↪ B`, ou en bisymbole par `A "=:" B`.

La théorie de l'injection est la suivante :

`(A "=:" B) = (A ↪ B) = { R"∈"ccP(A×B)" / "` // Chaque injection est une relation vérifiant :
        `AAx"∈"A, EEy"∈"B,  xRy,`     // Chaque élément de l'ensemble de départ a au moins une image.
        `AAx"∈"A, AA(y,z)"∈"B^2,  xRy` et `xRz  =>  y"="z` // Chaque élément de l'ensemble de départ a zéro ou une seul image.
        `AA(x,y)"∈"A^2, AAz"∈"B,  xRz` et `yRz  =>  x"="y` // Chaque élément de l'ensemble d'arrivé a zéro ou un seul antécédent.
`}`  

Une injection est une transformation déterministe injective ou encore une fonction partout définie et injective, mais le plus courament dit, est une application injective.

Le nombre d'injections distinctes de `A` vers `B` est donné par la formule suivante :

`|A "=:" B| = |A ↪ B| = (|B|!)/((|B|-|A|)!)`

10.1) Calcul par récurrence du nombre d'injections `|A ↪ B|`

On note :

`a = |A|`
`b = |B|`
`f(a,b) = |A ↪ B|`

`f(a,b)` désigne le nombre d'injections possibles d'un ensemble de `a` éléments vers un ensemble de `b` éléments.

En bref : Si nous ajoutons un nouvel élément `e`, l'ensemble des injections de `(A"+"{e}↪B)` comprennent les injections composées d'une injection de `A` vers `B-{x}`, où `x` est un élément quelconque de ` B`, que l'on complète par `(e|->x)`. Cela se traduit par la relation de récurrence suivante : `f(a"+"1,b) = bf(a,b"-"1)`

On rappel ce que signifie le symbole de différence `-`. Ainsi `A-B` représente l'ensemble des éléments de `A` qui ne sont pas dans `B` et en même temps, affirme que `B sube A`.

On dévoile la relation de récurrence sur les ensembles :

`(A"+"{e}↪B)={h + (e|->x)" / "x in B,  h in (A↪B"-"{x})}`
`(A"+"{e}↪B)=sum_(x in B)sum_(h in (A↪B"-"{x})) h + (e|->x)`
`|A"+"{e}↪B|=|B||A↪B"-"{x}|`
`f(a"+"1,b) = bf(a,b"-"1)`
 
`(Ø↪B) = {Ø}`
`|Ø↪B| = |{Ø}|`
`f(0,b)=1`
 
`(A↪A) = frS_A`
`|A↪A| = a!`
`f(a,a)=a!`

Conclusion :

`f(a+1,b) = b f(a,b-1)`
`f(0,b)=1`
`f(a,a)=a!`

Vous pourrez vérifier que cela définit bien le coefficient `f(a,b) = (b!)/((b-a)!)`

11) Fonction injective

On note l'ensemble des fonctions injectives de `A` vers `B` de deux façons, soit en notation algébrique avec le symbole de l'inclusion en flêche pointillée `A``B`, ou en bisymbole par `A "::" B`. Une fonction injective `f` de `A` vers `B` est une relation de `A` vers `B` satisfaisant seulement deux propriétés, à savoir que chaque élément de l'ensemble de départ doit avoir zero ou un seul arc qui part, et chaque élément de l'ensemble d'arrivé doit avoir zéro ou un seul arc qui arrive :

La théorie de la fonction injective est :

`(A "::" B) = (A` `B) = { R"∈"ccP(A×B)" / "` // Chaque injection est une relation vérifiant :
        `AAx"∈"A, AA(y,z)"∈"B^2,  xRy` et `xRz  =>  y"="z` // Chaque élément de l'ensemble de départ a zéro ou un seul successeur.
        `AA(x,y)"∈"A^2, AAz"∈"B,  xRz` et `yRz  =>  x"="y` // Chaque élément de l'ensemble d'arrivé a zéro ou un seul prédécesseur.
`}`  

Une fonction injective est une relation déterministe injective.

Le nombre de fonctions injectives distinctes de `A` vers `B` se note donc comme suit : `"|"A` ` B"|"`. On remarque que la définition est symétrique, et donc que la relation inverse d'une fonction injective est une fonction injective. Nous avons donc :

`"|"A` `B"|" = "|"B` `A"|"`

C'est pourquoi le symbole symétrique `A "::" B` est plus approprié pour désigner les fonctions injectives.

11.1) Calcul par récurrence du nombre de fonctions injectives `"|"A` `B"|"`

On note :

`a = |A|`
`b = |B|`
`f(a,b) = "|"A` `B|`

`f(a,b)` désigne le nombre de fonction injectives possibles d'un ensemble de `a` éléments vers un ensemble de `b` éléments.

En bref : Si nous ajoutons un nouvelle élément `e`, l'ensemble des fonctions injectives de `(A"+"{e})` vers `B` comprennent les fonctions injectives de `(A"+"{e})` vers `B``e` possède une image, et les fonctions injective de `(A"+"{e})` vers `B``e` ne possède pas d'image. Dans le premier cas, il a y `b` images possibles pour `e` et il y a `f(a,b-1)` fonctions injectives de `A` vers l'ensemble `B` dont on a enlevé l'image de `e`, ce qui donne `bf(a,b-1)` fonctions injectives possibles. Dans le second cas, il y a `f(a,b)` fonctions injectives de `A` vers `B`. Cela se traduit par la relation de récurrence : `f(a"+"1,b) = f(a,b) + bf(a,b"-"1)`

D'autre part, la relation inverse d'une fonction injective est une fonction injective. La définition étant symétrique nous avons :

`"|"A` `B"|" = "|"B` `A"|"`
`f(a,b)= f(b,a)`

On dévoile la relation de récurrence sur les ensembles :

`(A"+"{e}` `B) = {g "∈" (A"+"{e}` `B)" / "E y "∈" B, (e,y) "∈" g} + {g "∈" (A"+"{e}` `B)" / "A y "∈" B, (e,y) "∉" g}`
`(A"+"{e}` `B) = {h+(e|->y)" / " E y "∈" B, h "∈" (A` `B"-"{y})} + (A` `B)`
`(A"+"{e}` `B) = ( A` `B ")" + sum_(y in B){h+(e|->y)" / "h "∈" (A` `B"-"{y})}`
`"|"A"+"{e}` `B"|" = "|"A` `B"|" + sum_(y in B) "|"{h+(e|->y)" / "h "∈" (A` `B"-"{y})}"|"`
`"|"A"+"{e}` `B"|" = "|"A` `B"|" + sum_(y in B) "|"A` `B"-"{y}"|"`
`f(a+1,b) = f(a,b) + bf(a,b-1)`
 
`(Ø` `B) = {Ø}`
`"|"Ø` `B"|" = |{Ø}|`
`f(0,b)=1`

Conclusion :

`f(a+1,b) = f(a,b) + bf(a,b-1)`
`f(a,b) = f(b,a)`
`f(0,b)=1`

Cela définit le coefficient `f(a,b)` en en donnant un moyen efficace de calcul par récurrence.

12) Surjection

Une surjection est une application surjective. Une relation `R` de `A` vers `B` est surjective si et seulement si `R(A)=B`

L'ensemble des surjections de `A` vers `B` se note de deux façon, soit en notation algébique par `A "↠" B`, ou soit en bisymbole par `A "=>" B`.

La théorie de la surjection est la suivante :

`(A "=>" B) = (A "↠" B) = { R"∈"ccP(A×B)" / "` // Chaque surjection de `A->B` est une relation vérifiant :  
        `AAx"∈"A, EEy"∈"B,  xRy,`     // Chaque élément de `A` a au moins un successeur. // Transformation
        `AAx"∈"A, AA(y,z)"∈"B^2,  xRy` et `xRz  =>  y"="z`   // Chaque élément de `A` a zéro ou un seul successeur. // Déterministe
        `AA y "∈"B, EE x "∈"A,  xRy` // Chaque élément de `B` a au moins un prédécesseur. // Surjective
`}`    

Une surjection est une transformation déterministe surjective ou encore une fonction partout définie et surjective, mais le plus courament dit, est une application surjective.

Le nombre de surjections possibles de `A` vers `B` est donné par la formule suivante :

`|A "=>" B| = |A "↠" B| = |B|! S(|A|,|B|)`

`|A "=>" B| = |A "↠" B| = sum_(j=0)^|B| (-1) ^(|B|-j)((|B|),(j))j^|A|`

où les `S(a,b)` s'appellent « les nombres de Stirling de seconde espèce ».

12.1) Calcul par récurrence du nombre de surjections `|A"↠"B|`

On note :

`a = |A|`
`b = |B|`
`f(a,b) = |A"↠"B|`

`f(a,b)` désigne le nombre de surjections distinctes d'un ensemble de `a` éléments vers un ensemble de `b` éléments.

En bref : Si nous ajoutons un nouvel élément `e`, l'ensemble des surjections de `(A"+"{e}↠B)` se scinde en deux parties ; une première partie regroupant les surjections qui, si on enlève l'élément `e` sont encore des surjections, et une seconde une partie regroupant les surjections qui, si on enlève l'élément `e` ne sont plus des surjections. La première partie comprend les surjections de `(A↠B)` que l'on complète de `b` façons possibles avec `(e|->x)` pour `x in B`. La seconde partie comprend pour chaque élément `x in B`, les surjections de `(A↠(B"-"{x}))` complété par `(e|->x)`. Cela se traduit par la relation de récurrence suivante :
`f(a"+"1,b) = b(f(a,b) "+" f(a,b"-"1))`.

On dévoile la relation de récurrence sur les ensembles :

`(A"+"{e}↠B) = {g+(e"↦"x)" / " g"∈"(A"↠"B), x"∈"B} + {h+(e"↦"x)" / "h"∈"(A↠B"-"{x}), x"∈"B}`
`(A"+"{e}↠B) = sum_(g in (A↠B)) sum_(x in B){g"+"(e"↦"x)} + sum_(x in B)sum_(h in (A↠B"-"{x})){h+(e"↦"x)}`
`|A"+"{e}↠B| = |A"↠"B| |B| + |B| |A↠B"-"{x}|`
`f(a+1,b) = b f(a,b) + b f(a,b-1)`
 
Si `|A|<|B|` alors `(A"↠"B) = Ø`
Si `a <b` alors `f(a,b) = 0`
 
`({a}↠{b}) = {a"↦"b}`
`|{a}↠{b}| = |{a"↦"b}|`
`f(1,1) = 1`
 
`(Ø↠Ø) = {Ø}`
`|(Ø↠Ø)| = |{Ø}|`
`f(0,0)=1`

Conclusion :

`f(a+1,b) = b(f(a,b) + f(a,b-1))`
Si `a"<"b` alors `f(a,b) = 0`
`f(0,0)=1`

Cela définit le coefficient `f(a,b)` en en donnant un moyen efficace de calcul par récurrence. Vous pouvez vérifier que ce coefficient est égal à :

Pour `a">"0` et `b">"0` nous avons `f(a,b) = sum_(n=1)^b ("-"1)^(b-n)((b),(n))n^a`
Si `a"<"b` alors `f(a,b) = 0`
`f(0,0)=1`

La formule itérative de `f(a,b)` est plus complexe que la formule récurcive de `f(a,b)`. De plus, le calcul basé sur cette formule itérative peut-être de complexité plus grande que celui basé sur la formule récurcive précédente. C'est pourquoi il peut-être plus judicieux de définir le coefficient `f(a,b)` par sa formule récurcive.

13) Transformation

Une transformation est une relation partout définie. Une relation `R` de `A` vers `B` est transformante ou partout définie si et seulement si chaque élément de l'ensemble de départ possède un ou plusieurs arcs partant.

L'ensemble des transformations de `A` vers `B` se note en bisymbole par `A "<×" B`

13.1) Calcul par récurrence du nombre de transformations `|A "<×" B|`

On note :

`a = |A|`
`b= |B|`
`f(a,b) = |A "<×" B|`

`f(a,b)` désigne le nombre de transformations distinctes d'un ensemble de `a` éléments vers un ensemble de `b` éléments.

En bref : Si nous ajoutons un nouvel élément `e`, l'ensemble des transformations de `(A+{e})` vers `B` est égale à l'ensemble des transformations de `A` vers `B` complétées par les transformations possibles de `{e}` vers `B`. Donc nous avons la relation de récurence suivante : `f(a+1,b) = f(a,b) f(1,b)`.

On dévoile la relation de récurrence sur les ensembles :

`(A+{e}) "<×" B = {f+g " / " f "∈"(A "<×" B), g"∈"({e} "<×" B)`

`(A+{e}) "<×" B = sum_(f "∈"(A "<×" B))sum_(g"∈"({e} "<×" B)){f+g}`
`(A+{e}) "<×" B| = |A "<×" B| |{e} "<×" B|`
`f(a+1,b) = f(a,b) f(1,b)`
 
`{} "<×" B = {{}}`
`|{} "<×" B| = |{{}}|`
`f(0,b) = 1`

Conclusion :

`f(a+1,b) = f(a,b) f(1,b)`
`f(0,b) = 1`

Cette relation de récurrence se resoud est donne :

`f(a,b) = f(1,b)^a`

13.2 Calcul par récurrence de `|{a} "<×" B|`

On note :

`b = |B|`
`f(1,b) = |{u} "<×" B|`

`f(1,b)` désigne le nombre de transformations distinctes d'un ensemble singleton vers un ensemble de `b` éléments.

En bref : Si nous ajoutons un nouvel élément `e`, l'ensemble des transformations `R` de `{u} "<×" (B+{e})` comprend les transformations vérifiant `uRe` et celle vérifiant `¬uRe`. Les premières sont composées d'une relation quelconque de `{u} "××" B` complété par `(u|->e)`, les secondes sont les transformations de `{u} "<×" B`. Donc nous avons la relation de récurrence suivante : `f(1,b+1) = 2^b + f(1,b)`.

On dévoile la relation de récurrence sur les ensembles :

`{a} "<×" (B+{e}) = {g+(a|->e) " / " g "∈"({e} "××" B)} + ({a} "<×" B)`
`{a} "<×" (B+{e}) = sum_(g in({e} "××" B)){g+(a|->e)} + ({a} "<×" B)`
`|{a} "<×" (B+{e})| = |{e} "××" B| + |{a} "<×" B|`
`f(1,b+1) = 2^b + f(1,b)`
 
`(a "<×" {}) = {}`
`|{a} "<×" {}| = |{}|`
`f(1,0) = 0`

Conclusion :

`f(1,b+1) = 2^b + f(1,b)`
`f(1,0) = 0`

Cette relation de récurrence se resoud est donne :

`f(1,b) = 2^(b-1) + 2^(b-2) +...+1 = (2^b-1)/(b-1)`

En conclusion générale, le nombre de transformations distinctes d'un ensemble de `a` éléments vers un ensemble de `b` éléments est égale à :

`f(a,b) = ((2^b-1)/(b-1))^a`

14) Transformation surjective

Une transformation surjective est une relation partout définie surjective. Une relation `R` de `A` vers `B` est partout défini et surjective si et seulement si chaque élément de l'ensemble de départ possède un ou plusieurs arcs partant et chaque élément de l'ensemble d'arrivé possède un ou plusieurs arcs entrant.

L'ensemble des transformations surjectives de `A` vers `B` se note en bisymbole par `A "<>" B`

14.1) Calcul par récurrence du nombre de transformations surjectives `|A "<>" B|`

On note :

`a = |A|`
`b= |B|`
`f(a,b) = |A "<>" B|`

`f(a,b)` désigne le nombre de transformations surjectives distinctes d'un ensemble de `a` éléments vers un ensemble de `b` éléments.

L'inverse d'une transformation surjective et une transformation surjective, donc d'après cette symétrie, nous avons l'égalité suivante :

`|A "<>" B| = |B "<>" A|`
`f(a,b) = f(b,a)`

En bref : Si nous ajoutons un nouvel élément `e`, l'ensemble des transformations surjectives de `(A+{e}) "<>" B` se subdivise en `|ccP(B)|` parties. Pour chaque partie `X sube B`, on définie une partie regroupant les transformations surjectives qui restreinte à `A` sont encore des transformations surjectives de `A "<>" (B-X)`. Dans chacune des parties ainsi définie, chaque transformation surjective peut être complété par n'importe quel transformation surjective de `{e} "<>" (B-X)`, puis peut être complété par n'importe quelle relation de `{e} "××" X`. Cela se traduit par la relation de récurrence suivante : `f(a+1,b) = sum_(X sube B)f(a,b-|X|) f(1,b-|X|) 2^|X|`.

---- 3 mai 2017 ----

On dévoile la relation de récurrence sur les ensembles :

 
 
 

Conclusion :

 
 

Cette relation de récurrence se resoud est donne : ...

 

15) Les relations binaires

Parceque notre analyse consiste à diviser tout problème complexe en parties plus simples (voir chapitre Philosophie et construction), il est opportun de bien connaître l'usage des graphes orientés biparties, qui peuvent être vus comme des relations binaires et aussi comme des prédicats binaires. Ceci afin de pouvoir bien mener l'art de la subdivision des problèmes.

Une relation `R` de l'ensemble `A` vers l'ensemble `B` est une partie de `A×B`. La relation binaire `R` peut être vue comme ; un ensemble de couples, un prédicat binaire, un graphe. Et chacune de ces vues correspond à une notation :

Ensemble
Prédicat
Graphe
La relation `R` possède un arc
partant de `x` et allant sur `y`
`(x,y) in R`
`R(x,y)`
`xRy`
La relation `R` ne possède pas d'arc
partant de `x` et allant sur `y`
`(x,y) !in R`
`¬ R(x,y)`
`¬ xRy`

On définie la relation complémentaire de `R` que l'on note `barR` comme suit :

`xbarRy <=> ¬ xRy`

On définie la relation inverse de `R` que l'on note `R^(-1)` comme suit :

`xR^(-1)y <=> yRx`

On définie la composition de deux relations `R, S` que l'on note `RS` comme étant tous les liens possibles composé d'un lien de la première relation suivi d'un lien de la seconde relation :

`xRSy <=> EEz, xRz" et " zRy`

L'ensemble de départ et d'arrivé de la relation `RS` est respectivement l'ensemble de départ de `R` et l'ensemble d'arrivé de `S`.

On définie l'ensemble des successeurs de `x` que l'on note `R{x}`, comme étant l'ensemble des éléments `y` tel que `xRy`. Et on définie de l'ensemble des antécédants de `y` que l'on note `R^(-1){y}`, comme étant l'ensemble des éléments `x` tel que `xRy`.

`R{x} = {y " / " xRy}`
`R^(-1){y} = {x " / " xRy}`

On définie l'ensemble des successeurs d'un ensemble `X` que l'on note `R(X)`, et l'ensemble des antécédants d'un ensemble `Y` que l'on note `R^(-1)(Y)`.

`R(X) = {y " / " EEx "∈" X, xRy}`
`R^(-1)(Y) = {x " / " EEy"∈" Y, xRy}`

16) Décomposition de la théorie de la bijection

En étudiant la théorie de la bijection, on trouve les 4 axiomes de la bijections dont 2 font référence à l'ensemble de départ que sont les qualités d'être partout définie et d'etre déterministe, et 2 autres font référence à l'ensemble d'arrivé que sont la surjectivité et l'injectivité. L'inverse d'une relation surjective est une relation partout définie. L'inverse d'une relation injective est une relation déterministe.

Ces 4 axiomes ont la propriétée de se conserver par composition, c'est à dire si `R` et `S` vérifie un axiome alors `RS` vérifie encore cette axiome.

Ces deux axiomes peuvent s'appliquer pour l'ensemble de départ en inversant le sens des arcs. On trouve alors les propriétées symétriques, d'être partout définie et d'être déterministe. :

On définie les termes suivants :

On définie les termes raccourcis suivants :

Etant donné une relation de `A` vers `B`, on symbolise ces propriétés à l'aide d'un symbole prefixe et d'un symbole suffixe.

Symbole préfixe
Symbole suffixe
`"×"` Relation
`"×"` Relation
`"<"` Partout définie `"<"` Surjectif
`":"` Deterministe `":"` Injectif
`"="` Applicatif `"="` Bijectif

Ainsi par exemples, l'ensemble des relations de `A` vers `B` se note `(A "**" B)`, et l'ensemble des surjections de `E` vers `F` se note `(E "=> " F)`.

On pose `|A|=a` et `|B|=b`. Voici le dénombrement pour les 16 types de relations :

Symbole
Nom commun
Nom commun de
la relation inverse
Cardinal
Calcul itératif
Cardinal
Calcul récurcif
`A "××" B`
Relation
Relation
`2^(ab)`
`f(a"+"1,b)=f(a,b) (1,b)`
`f(a,b)=f(b,a)`
`f(1,1)=2`
`f(0,1)=0`
`A "×>" B`
Relation surjective
Transformation
`((2^b-1)/(b-1))^a`
`f(a,b+1) = f(a,b) f(a,1)`
`f(a+1,1) = 2^a +f(a,1)`
`f(a,0) = 1`
`A "×:" B`
Relation injective
Fonction
`(a+1)^b`
 
`A "×=" B`
Relation bijective
Application
`a^b`
 
`A "<×" B`
Transformation
Relation surjective
`((2^b-1)/(b-1))^a`
 
`A "<>" B`
Transformation surjectif
Transformation surjective
 
`A "<:" B`
Transformation injectif
Fonction surjective
 
`A "<=" B`
Transformation bijectif
Surjection
`a! S(b,a)`
 
`A ":×" B`
Fonction
Relation injective
`(b+1)^a`
 
`A ":>" B`
Fonction surjective
Transformation injective
 
`A "::" B`
Fonction injective
Fonction injective
 
`A ":=" B`
Fonction bijective
Injection
`(a!)/(a-b)!`
 
`A "=×" B`
Application
Relation bijective
`b^a`
 
`A "=>" B`
Surjection
Transformation bijective
`b! S(a,b)`
 
`A "=:" B`
Injection
Fonction bijective
`(b!)/(b-a)!`
 
`A "==" B`
Bijection
Bijection
`a!`
 

 

 


Dominique Mabboux-Stromberg
 
Précédent
 
Suivant