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`. Ainsi, 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`.

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 :

`ccP(E^2)`

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

`|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 ; un ensemble de départ et 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 « L'inférence de type ». 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ées 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` ou encore `a barR b` 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`.

Etant donné une relation `R` de Dép`(R)` vers Arr`(R)`. Nous avons :

La relation binaire est la clef de voûte du modèle mathématique, réunissant les trois pans du langage que sont: le langage de données, le langage de propriétés 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 constituent des programmes. C'est pourquoi il est utile d'étudier les relations binaires de façon exhaustive, c'est à dire en parcourant tout 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 le premier arrive sur un sommet et le second part de ce même sommet. Mis bout à bout dans cet ordre appelé 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 `RS`, 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 à `R` et le second arc appartient à `S` :

`RS = {(a,b) "/" EEx,  aRx "et" xSb}`

Notez que dans cette expression, le `EEx` évoqué s'applique à Arr`(R) nn `Dép`(S)`. Nous expliquerons plus tard cette interprétation dans le chapitre n°5 sur l'inférence des types.

Quelque soit deux éléments `a` et `b` l'expression `aRSb` signifie que l'on peut se déplacer continûment de `a` en `b`, en empruntant un arc de `R` dans son sens de circulation, suivie d'un arc de `S` 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 `RS`, l'ensemble de départ de `R` et l'ensemble d'arrivé de `S`.

La composition est associative, c'est d'ailleurs pour cela que ça s'appelle une composition :

`(RS)T = R(ST)`

Pour le démontrer on remarque que :

`a(RS)Tb`
  `<=>`  
`EEx,  aRSx "et" xTb`
 
`<=>`
`EEx,  (EEy,  aRy "et" ySx) "et" xTb`
 
`<=>`
`EExEEy,  aRy "et" ySx "et" xTb`

et que :

`aR(ST)b`
  `<=>`  
`EEx,  aRx "et" xSTb`
 
`<=>`
`EEx,  aRx "et" (EEy,  xSy "et" yTb)`
 
`<=>`
`EExEEy,  aRx "et" xSy "et" yTb`
 
`<=>`
`EEyEEx,  aRx "et" xSy "et" yTb`
 
`<=>`
`EExEEy,  aRy "et" ySx "et" xTb`

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, plus, `R^+` :

`R^+ = R uu R^2 uu R^3 uu ... uu R^n uu ...`

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 doit néanmoins comporter au moins un arc. Et nous avons par définition :

Dép`(R^+) = `Dép`(R)`
Arr`(R^+) = `Arr`(R)`

L'élèvation à la puissance zéro `R^0` produit la relation d'égalité de l'on définie conventionellement sur Dép`(R) uu `Arr`(R)`. Elle vérifie :

`AAxAAy,  xR^0y  <=>  x"="y`

Dans cette expression, le `AAx` évoqué s'applique à `"Dép"(R) uu "Arr"(R)` et le `AAy` évoqué également, car `R^0` est par définition la relation d'égalité sur Dép`(R) uu `Arr`(R)`.

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

`R^** = R^0 uu R uu R^2 uu R^3 uu ... uu R^n uu ...`

Avec pour ensemble de départ et d'arrivé :

Dép`(R^**)    =    `Arr`(R^**)    =    `Dép`(R) uu `Arr`(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, mais à condition que la place en question soit dans l'ensemble de départ ou d'arrivé de la relation `R`. Nous avons :

`AAx,  xR^0x`
`AAx,  xR^**x`

Notez que dans ces deux expressions, les `AAx` évoqués s'appliquent à Dép`(R) uu `Arr`(R)`.

Par convention `R^1 = R`

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. Notez alors que les ensembles de départ et d'arrivé sont par convention permutés :

Dép`(R^-1) = `Arr`(R)`
Arr`(R^-1) = `Dép`(R)`

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 `A` vers `B` qui pour chaque élément `a` appartenant a `A`, associe un et un seul élément `b` appartenant a `B`. Cette association correspond à l'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 `b`.

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`.

La théorie de l'application de `A` vers `B` est la suivante :

`A"→"B   =   { R"∈"ccP(A"×"B) "/"`      (1)
        `AAxAAyAAz,  xRy` et `xRz => y"="z`      (2)
        `AAxEEy,  xRy`      (3)
`}`  

(1). Chaque application de `A` vers `B` est une relation de `A` vers `B`.
(2). Chaque élément de l'ensemble de départ a zéro ou un seul successeur.
(3). 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 les variables `x,y,z` évoluent dans des ensembles spécifiques qui constituent leur type, et que ce typage est déterminé par la théorie par un procédé d'inférence de type, expliqué dans le chapitre "L'inférence de type".

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

Dans le langage logique du premier ordre, la décomposition en conjonction de clauses de la définition d'une application fait apparaitre deux axiomes. On les désigne chacun par un nom ou un qualificatif, et la conjonction des deux se désigne également 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.
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 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 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 le fait d'être une relation et le fait d'avoir la propriété applicative.

L'application `f` constitue une transformation déterministe. L'image d'un élément `x` par l'application `f` est le résultat de la transformation de `x` par `f`, elle produit donc au moins un résultat, et cette transformation étant déterministe elle ne produit qu'un seul résultat noté `f(x)`. Mais on peut dire également que l'application `f` constitue une fonction partout définie. L'image d'un élément `x` par l'application `f` est le résultat de la fonction `f`, qui étant définie 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| = |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|`

3.1 Application d'un singleton `{u}` vers un ensemble `E`

Les applications `f` d'un singleton `{u}` vers un ensemble `E` sont exactement déterminées par leur image Im`(f)` qui constituent des singletons `{f(u)}`. Il y a donc une bijection entre l'ensemble `{u}"→"E` et l'ensemble `E`. Et donc si `E` est fini alors le nombre de telles applications est égale au nombre d'éléments de `E`.

`|{u}"→"E|  =  |E|`

3.2) 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)=f(a,b)b`
`f(0,b)=1`

ou soit par itération :

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

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 les résultats intermédiaires en évitant de les recalculer plusieurs fois.

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

3.3) 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) = f(a,b)b`

Etant donné deux applications `h,g`. Ce sont des ensembles de couples. On peut donc les réunir s'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| |{e}"→"B|`
`|(A"+"{e})"→"B|   =   |A"→"B| |B|`
`f(a"+"1,b)   =   f(a,b)b`
 
`Ø"→"B   =   {Ø}`
`|Ø"→"B|  =   1`
`f(0,b)   =   1`

Conclusion :

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

Vous pourrez vérifier que cela définit bien l'élévation à la puissance `f(a,b) = b^a` et que cela la complète en `f(0,0)=1`.

3.4) 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.

D'après l'étude de ce langage, toute expression d'une théorie du premier ordre admet une forme normale, prénexe c'est à dire avec tout les quantificateurs placés en premier, constituée d'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 anonymisées dans chaque clause, les variables universelles n'ayant de portée qu'à l'intérieur d'une clause.

Considérons notre premier exemple qu'est la théories des applications de `A` vers `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`.

On note les prédicats négativés avec une barre, ainsi l'expression `barA"(x)"` signifie `¬ A(x)` c'est à dire que `x"∉"A` , de même l'expression `barR"(x,y)"` signifie qu'il n'existe pas d'arc dans `R` allant de `x` vers `y`, c'est à dire que `(x,y)"∉"R`.

La théorie des applications `R` de `A` vers `B` s'exprime sous forme normale comme suit :

Relation partant de `A` :     `AAxAAy,  xbarRy "ou" A(x)`
Relation allant vers `B` :     `AAxAAy,  xbarRy "ou" B(y)`
Partout définie : `AAxEEe,  barA(x) "ou" xRe`     
Déterministe : `AAxAAyAAz,  barR(x,y) "ou" barR(x,z) "ou" y"="z`  

La décomposition en axiomes se fait sans introduire d'arbitraire. Ainsi l'application est typée par les deux premiers axiomes, et est gouvernée par les deux derniers axiomes. C'est pourquoi l'application est aussi dénommée transformation déterministe ou bien fonction partout définie.

Une clauses de `n` littéraux peut se mettre de `n` façons différentes sous forme d'une clause de Horn. Ainsi la théorie peut se récrire comme suit :

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

5) L'inférence de type

Les ensembles de départ et d'arrivé des relations servent à typer les variables, et donc constitue le type de la relation. Considérons la proposition suivante :

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

Au regard de la définission de `R`, cette expression est identique à la suivante :

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

Le type non définie de `x` va être définie par la place que `x` utilise dans la formule. La variable `x` utilise la place réservée aux éléments de départ de `R` et également la place réservée aux éléments d'arrivé de `R`, c'est pourquoi le mécanisme d'inférence va attribuer à la variable `x` le type Dép`(R) nn `Arr`(R)`.

Nous voulons dénombrer, c'est pourquoi il nous faut limiter les tailles des ensembles utilisés. L'expression `AAx` 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, c'est à dire des ensembles de départs et d'arrivés. 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.

Mais l'inférence de type peut fonctionner également dans l'autre sens. Etant donné une relation `Z"(.,.)"` d'arité 2, dont on ne connait pas le type en dehors de son arité c'est à dire dont on ne connait pas son ensemble de départ ni son ensemble d'arrivé. Et considérons la proposition suivante :

`R"∈"ccP(A×B)`
`AAxAAy, xZy => xRy`

Ici `Z` va se comporter comme une variable d'un autre type désignant une relation et qui va se préciser selon l'énoncé avancé comme suit :

`x` est implicitement définie de type `A`.
`y` est implicitement définie de type `B`.
`Z` est implicitement définie de type `ccP(A×B)`.

Nous étudierons plus tard de façon plus approfondie cette inférence de type pour formaliser une logique d'ordre supérieur en un langage simple et économe en nombre de signes, à la base des langages de programmation évolués souhaités.

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 sous-ensembles de l'ensemble de départ 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)`
`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 accolades tel que par exemple `{a,b,c}`. Dans ce cas, on enleve les parenthèses de l'appel qui joue un rôle superflu. Ainsi l'expression `R({a,b,c})` se notera plus simplement `R{a,b,c}`. L'expression `R{a}` représente l'ensemble des éléments atteignables à partir de l'élément `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 définie comme application mais comme relation.

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, 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^+` sont valables et désignent des relations. Soit `x` un élément de `E`. L'ensemble `f^**{x}` est l'ensemble des éléments atteignables à partir de `x` en empruntant une succession d'arcs de `f` dans leur sens de circulation. Et en empruntant aucun arc, ce qui constitue le chemin vide, on reste sur place et on atteint `x` lui-même. L'ensemble de départ et d'arrivé de `f^**` est par définition Dep`(f)uu`Arr`(f)`. L'ensemble `f^+{x}` est l'ensemble des éléments atteignables à partir de `x` en empruntant une succession d'arcs de `f` dans leur sens de circulation et comprenant au moins un arc. L'ensemble de départ et d'arrivé de `f^+` sont respectivement ceux de `f`.

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

L'expression est plus simple en utiliant une variable ensemble. Soit `X` un sous-ensemble de `E`. Nous avons :

`f^**(X)   =   X uu f(X) uu f^2(X) uu ... uu f^n(X) uu ...  =   uuu_(n=0)^oo f^n(X)`
 `f^+(X)   =   f(X) uu f^2(X) uu ... uu f^n(X) uu ...  =   uuu_(n=1)^oo f^n(X)`

Notez que l'ensemble de départ et d'arrivé de la relation `f^0` est par définition Dep`(f)uu`Arr`(f)`.

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 de `A` vers `B` est la suivante :

`A"⇢"B  =  { R"∈"ccP(A×B) "/"`      (1)
        `AAxAAyAAz,  xRy` et `xRz => y"="z`
(2)
`}`  

(1). Chaque fonction de `A` vers `B` est une relation de `A` vers `B`.
(2). Chaque élément de l'ensemble de départ a zéro ou un seul successeur.

Autrement dit, pour tout élément `x` de `A`, 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, en notation étendue aux ensembles, par `f{x}=Ø`.

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 en empruntant un arc de `f` dans le sens autorisé. 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"`.

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

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

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` vers `B"+"{sf(FAIL)}` :

`|A"⇢"B| = |A"→"(B"+"{sf(FAIL)})|`

`|A"⇢"B| = (|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` est également fini et s'appel l'ensemble des permutations sur `A`. Le nombre de permutations distinctes sur `A` est donné par la formule suivante :

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

La théorie de la bijection de `A` vers `B` est la suivante :

`A"=="B  =   { R"∈"ccP(A×B) "/ "`      (1)
        `AAxEEy,  xRy,`    
(2)
        `AAxAAyAAz,  xRy` et `xRz  =>  y"="z`  
(3)
        `AAxEEy,  yRx`
(4)
        `AAxAAyAAz,  xRz` et `yRz  =>  x"="y`
(5)
`}`

(1). Chaque bijection de `A` vers `B` est une relation de `A` vers `B`.
(2). Chaque élément de l'ensemble de départ a un ou plusieur successeurs.
(3). Chaque élément de l'ensemble de départ a zéro ou un seul successeur.
(4). Chaque élément de l'ensemble d'arrivé a un ou plusieur prédécesseurs.
(5). Chaque élément de l'ensemble d'arrivé a zéro ou un seul prédécesseur.

Dans le langage logique du premier ordre, la décomposition en conjonction de clauses 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 couramment 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 :

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 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 de `A` vers `B` est la suivante :

`A"↪"B  =   { R"∈"ccP(A×B"/"`       (1)
        `AAxEE,  xRy`    
(2)
        `AAxAAyAAz,  xRy` et `xRz  =>  y"="z`
(3)
        `AAxAAyAAz,  xRz` et `yRz  =>  x"="y`
(4)
`}`  

(1). Chaque injection de `A` vers `B` est une relation de `A` vers `B`.
(2). Chaque élément de l'ensemble de départ a au moins une image.
(3). Chaque élément de l'ensemble de départ a zéro ou une seul image.
(4). 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 couramment dit, est une application injective.

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

`|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 de `A` vers `B` est :

`(A` `B)   =   { R"∈"ccP(A×B) "/"`       (1)
        `AAxAAyAAz,  xRy` et `xRz  =>  y"="z`
(2)
        `AAxAAyAAz,  xRz` et `yRz  =>  x"="y`
(3)
`}`  

(1). Chaque injection de de `A` vers `B` est une relation de `A` vers `B`.
(2). Chaque élément de l'ensemble de départ a zéro ou un seul successeur.
(3). 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 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. Et donc nous avons :

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

C'est pourquoi un symbole symétrique tel que `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 "/" Ey, (e,y)"∈"g} + {g∈(A"+"{e})``B" / "A y, (e,y)"∉"g}`
  `(A"+"{e})``B   =   { h"+"(e|->y) "/" EEy,  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.

 

--- 23 décembre 2017 ---

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çons, soit en notation algébique par `A"↠"B`, ou soit en bisymbole par `A"=>"B`.

`A"=>"B   =   A"↠"B`

La théorie de la surjection est la suivante :

`A"↠"B   =   { R"∈"ccP(A×B) "/ "`      (1)
        `AAxEEy,  xRy,`    
(2)
        `AAxAAyAAz,  xRy` et `xRz  =>  y"="z`  
(3)
        `AAyEEx,  xRy`
(4)
`}`  

(1). Chaque surjection de `A"↠"B` est une relation de `A` vers `B`.
(2). Transformation : Chaque élément de l'ensemble de départ a au moins un successeur.
(3). Déterministe : Chaque élément de l'ensemble de départ a zéro ou un seul successeur.
(4). Surjective : Chaque élément de l'ensemble d'arrivé a au moins un prédécesseur.

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| = |B|! S(|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`
Il arrive que le calcul itératif soit de complexité plus grande que calcul récurcif. C'est le cas ici. La formule itérative obtenue de `f(a,b)` est plus complexe que la formule récurcive obtenue de `f(a,b)`. C'est pourquoi il est judicieux de définir le coefficient `f(a,b)` par sa formule récurcive plutôt que par sa formule itérative.

13) Fonction surjective

Une fonction surjective de `A"⤐"B` est une relation `R` de `A` vers `B` surjective c'est à dire telle que `R(A)=B`, et déterministe c'est à dire telle que chaque élément de `A` n'a au plus qu'une image par `R`.

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

La théorie de la fonction surjective de `A"⤐"B` est la suivante :

`A"⤐"B   =   { R"∈"ccP(A×B) "/ "`      (1)
        `AAxAAyAAz,  xRy` et `xRz  =>  y"="z`  
(2)
        `AAyEEx,  xRy,`    
(3)
`}`  

(1). Chaque fonction surjective de `A"⤐"B` est une relation de `A` vers `B`.
(2). Déterministe : Chaque élément de l'ensemble de départ a zéro ou un seul successeur.
(3). Surjective : Chaque élément de l'ensemble d'arrivé a au moins un prédécesseur.

Une fonction surjective est une relation déterministe surjective.

13.1) Calcul par récurrence du nombre de fonctions surjectives `|A"⤐"B|`

On note :

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

`f(a,b)` désigne le nombre de fonctions surjectives 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 fonctions surjectives de `(A"+"{e})"↠"B` se scinde en deux parties ; une première partie regroupant les fonctions surjectives qui, si on enlève l'élément `e` sont encore surjectives, et une seconde une partie regroupant les fonctions surjectives qui, si on enlève l'élément `e` ne sont plus surjectives. La première partie comprend les fonctions surjectives 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 fonctions surjectives 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`

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 Transformation d'un singleton vers un ensemble `E`

Les transormations `R` d'un singleton vers un ensemble `E` sont exactement déterminées par leur image Im`(R)`. Il y a donc une bijection entre l'ensemble `{u}">⋇"E` et l'ensemble `ccP(E)-{}`. Et donc

`|{u}">⋇"E|  =  |ccP(E)| - 1  =  2^|E| - 1`

13.2) 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)`
`f(a+1,b)  =  f(a,b) (2^b - 1)`
 
`{} "<⋇" B  =  {{}}`
`|{} "<⋇" B|  =  |{{}}|`
`f(0,b) = 1`

Conclusion :

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

Cette relation de récurrence se resoud est donne :

`f(a,b) =(2^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éfinie 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`

On remarque que la définition est symétrique, et donc que la relation inverse d'une transformation surjective est une transformation surjectivee. Et donc nous avons :

`|A"<>"B|   =   |B"<>"A|`

14.1 Transformation surjective d'un singleton vers un ensemble `E`

Il n'y a qu'une seule transformation surjective partant d'un singleton `{u}` vers un ensemble `E` non vide. C'est la relation complète `{u}×E` qui associe l'éléments `u` à tous les élément de `E`.

Si  `E!={}`  Alors  `|{u}"<>"E|  =  1`
`{u}"<>"{}  =   {}`
`{}"<>"{}   =   {{}}`

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 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é `f(a,b) = f(b,a)`. Et `f(1,b)  =  (b!=0)`.

En bref : Nous ajoutons un nouvel élément `e`, et nous analysons comment subdiviser l'ensemble des transformations surjectives `R` de `(A+{e})"<>"B`. Si `R` restreint à `A` appartient à `A"<>"B` alors la relation `R` peut être complétée par n'importe quelle relation de `{e}"⋇⋇"X` pour former une transformations surjectives de `(A+{e})"<>"B`. Si `R` restreint à `A` n'appartient pas `A"<>"B` c'est que l'image de `e` par `R` atteint des éléments qui n'ont pas d'autre prédécesseur que `e` et qui forme donc une partie `X` non nulle de `B` telle que `R` restreint à `A` appartient à `A"<>"(B-X)`

Pour chaque partie `X` telle que `{} sub X sub B`, on considère l'ensemble des transformations surjectives de `A"<>"(B-X)`. Dans chacun de ces ensembles de transformations, chaque transformation surjective peut être complété par l'unique transformation surjective de `{e}"<>"X`, puis peut être complété par n'importe quelle relation de `{e}"⋇⋇"(B-X)`. Cela se traduit par la relation de récurrence suivante :

`f(a"+"1,b)   = sum_(X!={} ^^  X sub B)f(a,b"-"|X|) 2^(b-|X|)`

 

---- 20 décembre 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 `f(a,b)`
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^a-1)^b`
`f(a,b"+"1) = f(a,b)f(a,1)`
`f(a,1) = 2^a"-"1`
`f(a,0) = 1`
`A "×:" B`
Relation injective
Fonction
`(a+1)^b`
`f(a,b"+"1) = f(a,b)(a"+"1)`
`f(a,0) = 1`
`A "×=" B`
Relation bijective
Application
`a^b`
`f(a,b"+"1) = f(a,b)a`
`f(a,0) = 1`
`A "<×" B`
Transformation
Relation surjective
`(2^b-1)^a`
`f(a"+"1,b) = f(a,b)f(1,b)`
`f(1,b) = 2^b"-"1`
`f(0,b) = 1`
`A "<>" B`
Transformation surjectif
Transformation surjective
 
`A "<:" B`
Transformation injectif
Fonction surjective
 
`A "<=" B`
Transformation bijectif
Surjection
`a! S(b,a)`
`f(a,b"+"1) = (f(a,b)"+""f(a-"1",b))a`
`f(b,b)=b!`
`f(0,0)=1`
`A ":×" B`
Fonction
Relation injective
`(b+1)^a`
`f(a"+"1,b) = f(a,b)(b"+"1)`
`f(0,b) = 1`
`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`
`f(a"+"1,b) = f(a,b)b`
`f(0,b) = 1`
`A "=>" B`
Surjection
Transformation bijective
`b! S(a,b)`
`f(a+1,b) = (f(a,b)+f(a,b-1))b`
`f(a,a)=a!`
`f(0,0)=1`
`A "=:" B`
Injection
Fonction bijective
`(b!)/(b-a)!`
`f(a"+"1,b)=f(a,b"-"1)b`
`f(0,b)=1`
`f(a,a)=a!`
`A "==" B`
Bijection
Bijection
`a!`
`f(a"+"1)=f(a)(a+1)`
`f(0) = 1`

 

 


Dominique Mabboux-Stromberg
 
Précédent
 
Suivant