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`. L'ensemble des relations de `A` vers `B` se note `A"××"B` et correspond donc à l'ensemble des parties `ccP(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 donc égal à :
`|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. Une relation de `E` vers `E` est appelée une relation sur `E`. C'est un ensemble de couples d'éléments de `E` :
`E"××"E = ccP(E^2)`
Lorsque `E` est un ensemble fini, le nombre de relations sur `E` est donc égal à :
`E"××"E = 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 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 plus riche qui permettra le typage des arguments par inférence comme on le verra au chapitre « L'inférence de type ». Délors, selon le contexte, l'égalité de deux relations `R"="S` peut avoir deux significations : soit c'est une égalité de graphe limité aux seuls arcs, une égalité d'ensemble de couples, soit c'est un petit peu plus que cela, les relations ont en plus le même ensemble de départ et le même ensemble d'arrivé. Si la relation `R` possède un ensemble de départ et un ensemble d'arrivé, alors nous avons nécessairement :
`"Dom"(R) sube "Dép"(R)` `"Im"(R) sube "Arr"(R)`
Il est possible de développer l'analogie jusqu'à la superposition totale de telle sorte qu'il n'y a pas de différence entre un graphe et une relation. Aussi, tout l'apport de l'étude des graphes s'ajoute dans l'étude des relations. 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. L'ensemble des sommets du graphe `R` est `"Dép"(R)"∪""Arr"(R)`. Chaque couple `(a,b) "∈" 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`
On adopte également une notation plus évocatrice des arcs à l'aide du symbole `"↦"`. L'arc partant de `a` et allant sur `b` pourra être noté de deux façons :
`(a,b) = (a"↦"b)`
L'ensemble des sommets atteints, soit par un arc arrivant ou soit par un arc partant, correspond à la base de `R` qui est `"Dom"(R) "∪" "Im"(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` sur `E`. Nous avons :
La relation binaire est une 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, et en commençant par les constructions les plus simples.
De la même façon que le type ensemble est associé aux types sac, arrangement et liste, le type relation est associé aux types multirelation (sac de couples), ordo-relation (arrangement de couples), ordo-multirelation (liste de couples). La relation définissant une famille d'ensemble que sont les ensembles d'arcs partant d'un sommet, on décline également cette typologie sur ce composant, définissant en plus les relations ou multirelation à fraterie ordonnées.
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` signifie `EEx in "Arr"(R)"∩""Dép"(S)`. Nous expliquerons plus tard cette interprétation dans le chapitre n°5 sur l'inférence de type. 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. La composition est associative, c'est d'ailleurs pour cela que ça s'appelle une composition :
`(RS)T = R(ST)`
On peut le démontrer de façon formelle comme suit :
`EEx, aRSx "et" xTb` `EEx, (EEy, aRy "et" ySx) "et" xTb` `EExEEy, aRy "et" ySx "et" xTb`
`EEx, aRx "et" xSTb` `EEx, aRx "et" (EEy, xSy "et" yTb)` `EExEEy, aRx "et" xSy "et" yTb` `EEyEEx, aRy "et" ySx "et" xTb` `EExEEy, aRy "et" ySx "et" xTb`
Notez que naturellement l'ensemble de départ de `RS` est égale à l'ensemble de départ de `R`, et l'ensemble d'arrivé de `RS` est égale à l'ensemble d'arrivé de `S`. 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 d'exactement `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. Puis on définie l'opérateur de Kleene, étoile, `R^**`, qui reprend la même définition que `R^+` mais qui autorise en plus le chemin composé de zéro arc, autrement dit le chemin vide. Pour introduire cette possibilité, on ajoute comme première relation, la relation d'égalité de `"Dép"(R)` vers `"Im"(R)`, que l'on note `R^(+0)`. c'est la fonction identité suivante :
`R^(+0)={(x,x) "/" x "∈" "Dép"(R), x "∈" "Im"(R)}`
Elle permet d'appliquer un premier arc qui correspond au chemin vide, qui fait du surplace. Ainsi l'opérateur de Kleene, étoile, `R^**` se définie comme suit :
`R^** = R^(+0) uu 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 orienté de zéro arc est considéré comme un chemin de taille zéro ne permettant que de rester sur place, mais valable que pour les éléments de l'ensemble de départ de `R` qui sont déjà dans l'ensemble d'arrivé de `R`. Nous avons :
`AAx, xR^(+0)x`
`AAx, xR^**x`
Notez que dans ces deux expressions, les `AAx` signifient `AAx in "Dép"(R)"∩""Arr"(R)`. Nous expliquerons plus tard cette interprétation dans le chapitre n°5 sur l'inférence de type. Par convention `R^1` désigne la relation `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 naturellement 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`. Remarquez la petite différence qui existe entre `R^(+0)` et `R^(-0)`. Ce sont des relations de graphe identique, faisant que l'égalité `R^(+0)=R^(-0)` reste valable au cadrage près. Mais le cadrage est différent, l'une est définie de `"Dép"(R)` vers `"Arr"(R)`, et l'autre est définie de `"Arr"(R)` vers `"Dép"(R)`.
`R^(+0) in "Dép"(R)"××""Arr"(R)`
`R^(-0) in "Arr"(R)"××""Dép"(R)`
On remarque que :
`AAxAAy, xR^(+0)y <=> x"="y`
Dans cette expression, le `AAx` signifie `AAx in "Dép"(R)"∩""Arr"(R)` et le `AAy` signifie `AAy in "Dép"(R)"∩""Arr"(R)`. Nous expliquerons plus tard cette interprétation dans le chapitre n°5 sur l'inférence de type.
Souvent on ne différenciera pas l'ensemble d'arrivé de l'ensemble de départ, distinction qui s'avère dans les cas généraux superfetatoire. À partir d'une relation `R` sur `E`, on définie l'opérateur de Kleene, plus-moins étoile, `R^"±∗"`, qui reprend la même définition que `R^**` mais qui autorise en plus les chemins inverses. Cela revient à considérer la relation symétrique engendrée par `R` que l'on note `R^"±"` et à effectuer l'opération de Kleene, étoile :
`R^"±"=R uu R^-1 = {(x,y) "/" (x,y)"∈"R "ou" (y,x)"∈"R)}`
`R^"±∗"= (R uu R^-1)^** = ... uu RR^-n uu ... uu R^-2 uu R^-1 uu R^0 uu R^1 uu R^2 uu R^3 uu ... uu R^n uu ...`
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`, associe un et un seul élément `b` appartenant à `B`. Ce lien correspond à l'arc de `f` partant de `a` et allant sur `b`. Lorsque `f` est considéré comme une relation, on parlera dans ce cas de relation applicative, cet arc se note `afb`. Lorsque `f` est considéré comme une application, cet arc se note par l'égalité `f(a)"="b`. L'élément `b` qui est le seul successeur de `a` est appelé l'image de `a` par `f` et se note `f(a)` ou bien en notation française `a^f`. Tandis que l'élément `a` qui est un prédécesseur de `b` s'appelle un antécédent de `b`. On note l'ensemble des applications de `A` vers `B` de trois façons possibles, soit en notation flêchée `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 à l'aide du bisymbole `"=×"` comme suit, `A"꞊×"B`.
` A"=×"B = A"→"B = B^A`
La théorie de la relation applicative `R` de `A` vers `B` est la suivante :
`A"→"B = { R"∈"ccP(A"×"B) "/"` Relation `AAxAAyAAz, xRy` et `xRz => y"="z` Déterministe `AAxEEy, xRy` Partout définie `}`
On l'a séparée ainsi en trois axiomes :
Chaque application de `A` vers `B` est une relation de `A` vers `B`. Chaque élément de l'ensemble de départ a zéro ou un seul successeur. Chaque élément de l'ensemble de départ a un ou plusieur successeurs.
Une application est une relation déterministe, partout définie.
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 5 intitulé "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 par exemple 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 les axiomes, déterministe et partout définie.
Les propriétés concernant seulement l'ensemble de départ vont être utilisées pour classifier les relations, et on donnera un nom à chaque tel type de relation. Les relations déterministes sont appelées des fonctions. Les relations partout définies sont appelées des transformations parceque chaque élément de l'ensemble de départ a au moins un successeur et peut donc opérer une transformation. Les relations déterministe et partout définies sont appelées des applications :
Relation partout définie
Chaque élément de l'ensemble de départ a un ou plusieur successeurs.Relation déterministe
Chaque élément de l'ensemble de départ a zéro ou un seul successeur.Relation Applicative
Chaque élément de l'ensemble de départ a exactement un successeur.
Une transformation est une relation partout définie, elle regroupe le fait d'être une relation et le fait d'être partout définie. Une fonction est une relation déterministe, elle regroupe le fait d'être une relation et le fait d'avoir la propriété déterministe. De même une application est une relation applicative, elle regroupe le fait d'être une relation et le fait d'avoir la propriété applicative, c'est à dire partout définie et déterministe.
L'application `f` constitue donc 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)`.
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 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 `f` est une application sur `E`. L'ensemble des applications sur `E` se note de façon fléchée par `E"→"E` ou bien de façon ensembliste par `E^E`, ou bien en bisymbole par `E"꞊×"E`.
Lorsque `E` est un ensemble fini, le nombre d'applications distinctes sur `E` est égal à :
`|E"→"E| = |E|^|E|`
Etant donné un graphe tel que par exemple `{a"↦" u, b "↦" v, c"↦"w}`. Ce graphe, s'il n'est pas muni par le contexte d'un type plus riche, constitura une relation de sa base de départ vers sa base d'arrivé.
Si l'on souhaite affirmer qu'il s'agit d'une application, cela se fait par convention en utilisant des parenthèses à la place des accolades. Par exemple, si la liste `(a"↦" u, b "↦" v, c"↦"w)` est interprétée comme une application (c'est à dire est munie du type application), cela entraine de facto que `a"≠"b`, `a"≠"c`, `b"≠"c`, et que son ensemble de départ est `{a,b,c}`.
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 partage les résultats intermédiaires en évitant ainsi 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.
Etant donné un élément `e`. Toute application `f` du singleton `{e}` vers l'ensemble `E` est exactement déterminée par son image Im`(f)` qui constituent le singleton `{f(e)}`. Il y a donc une bijection entre l'ensemble des applications de `{e}"→"E` et l'ensemble `E`. Et donc si `E` est fini, le nombre de telles applications est égale au nombre d'éléments de `E`.
`|{e}"→"E| = |E|`
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 considère un nouvel élément `e`, les applications de `(A"+"{e})"→"B` se construisent à partir des applications de `A"→"B`, en les complétant par union disjointe de graphe avec n'importe quelle application de `{e}"→"B`. Cela se traduira 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 `f(0,0)"="1`.
L'image de `x` par l'application `f` se note de deux façons, en notation anglaise par `f(x)` et en notation française par `x^f`.
Deux applications se composent pour produire une fonction qui est une application lorsque l'ensemble d'arrivé de la première est incluse dans l'ensemble de départ de la seconde. 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 : l'opération de composition anglaise, notée `"∘"`, et qui s'écrit de droite à gauche, l'opération de composition française, 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)=g(f(x))=(x^f)^g=x^(fg) `
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`.
Naturellement l'ensemble de départ d'une composition d'applications est l'ensemble de départ de la première application `"Dép"(fgh)"=""Dép"(f)`, et de même l'ensemble d'arrivé dune composition d'application est l'ensemble d'arrivé de la dernière application `"Arr"(fgh)"=""Arr"(h)`. Puis grâce au typage par inférence mis en oeuvre par le langage, une application de `A"→"B` peut être perçu comme un opérateur permettant de convertir un élément de type `A` en un élément de type `B`.
La logique formelle utilise des langages d'opérateurs. Et ces opérateurs constituent des applications. C'est pourquoi l'application joue un rôle particulier dans le langage. Elle peut être utilisée comme un opérateur et opérer une conversion de type. Ainsi étant donné deux types `A` et `B`, le type `A"→"B` désignera les opérateurs qui appliqués aux éléments de type `A` produisent des élèments de type `B`. La notion de type est plus large que celle d'ensemble.
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.
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éorie des relations applicatives `R` 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, le prédicat `B"(.)"` 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`. Le prédicat binaire `R"(.,.)"` désigne l'ensemble de couples `R`, cela signifie que `R(x,y)` est équivalent à `(x,y)"∈"R`, de même l'expression `barR(x,y)` signifie `¬R(x,y)` c'est à dire que `(x,y)"∉"R`. Une relation `R` de `A` vers `B` est un prédicat. Ainsi donc l'expression `R(x,y)` signifie que `(x,y)"∈""R` c'est à dire `xRy`, et l'expression `barR"(x,y)"` signifie que `(x,y)"∉"R`, c'est à dire `¬xRy`.
L'expression de la théorie des relations applicatives `R` de `A` vers `B` précédement décrite, s'exprime sous forme normale comme suit :
|
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 :
|
On complète le langage en ajoutant un type à chaque variable. Se constitue donc en parallèle du langage logique, un second langage dit langage des types. De plus chaque type décrit un comportement syntaxique qui peut être spécifique et qui enrichie le langage logique.
Considérons un élément `x` sans autre précision. Cet élément est en faite une variable, puisqu'on lui a donné un nom, qui désigne un élément, et son type, appelé le type Élément, est le plus général qui puisse être, puisque tout ce qui est désignable peut constituer un élément. On désigne ce type par l'ensemble vide `Ø`. Le type est représenté par sa compréhension, et s'il n'y a aucun critère de sélection comme dans le cas présent, il est normal qu'il apparaisse comme étant l'ensemble vide.
Considérons maintenant un ensemble `E` sans autre précision. Même topo, cet ensemble est en faite une variable qui désigne un ensemble, c'est à dire une variable de type ensemble que l'on note par le symbole `ccE`. Ce type est néanmoins incomplet car nous n'avons pas définie ce qu'était un ensemble. Mais qu'importe, continuons. Ce type semble plus précis que le type Élément. Nous dirons que `ccE"≺"Ø`.
Considérons maintenant, non pas un élément quelconque, mais un élément `e` appartenant à `E`. Cet élément est une variable qui a un type plus précis désigné par l'ensemble `E`. Et nous avons cette hierarchie des types : `E"≺"ccE"≺"Ø`.
La variable typée désigne un élément défini dans un cadre qui constitue son type. Comme l'élément existe indépendament du cadre, il y a deux sortes d'égalité, l'égalité complète `"≡"` comprenant l'élément et son cadre, et l'égalité simple `"="` ne comprenant que l'élément sans son cadre. Par exemple si `x` est de type `E`, et si `y` est de type `F`, alors l'expression `x"≡"y` entraine `x"="y` et `E"="F`.
Considérons maintenant une relation `R` de `A` vers `B`. Le type de `R` précise donc que c'est une relation de `A` vers `B`, et détermine ainsi son comportement, à savoir entre autre qu'elle s'applique à un couple composé d'un élément de `A` et d'un élément de `B` pour produire une valeur logique vrai ou faux selon que l'arc en question appartient à `R` ou non. Considérons maintenant deux variables `x` et `y` sans autre précision. Cela signifie que leur type est `Ø`. L'expression `R(x,y)` n'est alors pas autorisée car l'éléments `x` peut être en dehors de l'ensemble de départ de `R` c'est à dire en dehors de `A`, et de même l'élément `y` peut être en dehors de l'ensemble d'arrivé de `R` c'est à dire en dehors de `B`. L'interpréteur rigide, détectera une erreur de syntaxe, et affichera comme message d'erreur "Non concordance des types !". Pour que l'expression soit syntaxiquement correcte aux yeux de l'interpréteur rigide, il faut que le type de `x` soit égale à `A` et que le type de `y` soit égale à `B`, et pour le démontrer, il ne s'autorise comme raisonnement aucune règle autre que l'égalité de leur expression. Nous pourrions simplement exiger que le type de `x` soit inclus dans le type de `A`, et cette condition deviendrait alors une propriété non triviale qui s'ajoute à la théorie. L'ensemble de ces propriétés forment un système d'équation qui peut être résolue partiellement. C'est ce que fera un interpréteur non rigide.
Le typage par inférence constitue un mécanisme d'adaptabilité du type pour rendre la formule syntaxiquement correcte. Elle résoud partiellement le système d'équation traduisant les contraintes sur les types. Et on peut faire cela prudamment en ne s'autorisant à spécialiser que deux sortes de types, les types minimums et les types maximums, les types minimums ne s'adaptant que par réduction qu'est l'intersection, tandis que les types maximums s'adaptant que par augmentation qu'est l'union. Par exemple considérons une relations `R` de type `A"→"B`. Considérons un élément `x` de type `X`. Et considérons la formule suivante :
`AAx, xRx`
Afin que la formule soit syntaxiquement correcte, il est nécessaire de réduire le type de `x` à `X "∩""Dep"(R) "∩""Arr"(R)`, c'est à dire à `X "∩" A "∩" B`. Ou de façon duale, il est nécessaire d'accroitre le type de `R` à `(A "∪" X)"→"(B "∪" X)`. La contrainte sur les types se traduit par le système d'équations :
`X sube A`
`X sube B`
L'algorithme de résolution reprend l'algorithme d'unification qu'il généralise. L'algorithme d'unification s'applique à des égalités. Notre algorithme de résolution s'applique à des inclusions.
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 symboles, à la base des langages de programmation évolués souhaités.
La notion de type apparaît quelque fois plus générale que celle d'ensemble. Il existe un type Elément, qui s'avère être le plus générale qui soit, tandis qu'il n'existe pas d'ensemble de tous les éléments.
Mais la notion apparaît également quelque fois plus spécifique que celle d'ensemble. On peut créer des types différents recouvrant un même ensemble, leur différence tient alors dans le comportement syntaxique différents (dans le langage logique) qu'ils attribuent à ces mêmes éléments.
Le type est déclaré directement ou indirectement par inférance, tandis que l'ensemble, comme l'élément, existe indépendament des déclarations. Aussi, le typage qui s'applique ne résulte pas de l'appartenance réel à un ensemble ou à un type, mais de l'appartenance déclarée par le contexte.
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 partant de cet élément en question, si un tel arc existe.
Dans ce mode interprétatif, `R` est une application de `ccP(A)` vers `ccP(B)`. Notez que pour un élément `a"∈"A`, l'expression `R(a)` n'est pas autorisée sauf si `a` est également déclaré comme étant 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` doit être déclaré comme étant un sous-ensemble de l'ensemble de départ.
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, elle ne constitue l'inverse que lorsque l'application est injective. En effet, nous avons :
`X sube (R^-1"∘"R)(X)`
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 déclaré comme un ensemble inclus dans `A`, car `R` n'est pas une application de `A"→"B` mais seulement une relation de `A` vers `B`, et est en même temps une application de `ccP(A)"→"ccP(B)`.
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 déclaré à la fois comme un élément de `A` et comme 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`.
`f(X) = {f(x) "/" x"∈"X}`
L'expression `f^(-1)(Y)` désigne l'ensemble des éléments atteignables à partir de l'ensemble `Y` en prenant un arc de `f` dans le sens inverse :
`f^(-1)(Y) = {x "/" f(x) "∈" Y }`
Dans cette expression, le typage par inférence assigne `x` du type `"Dép"(f)`. L'expression `f(x)` en mode non étendu suppose que `x in Dép(f)`, et ceci sans que l'on est besoin de le mentionner.
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. Elle ne l'est que lorsque l'application est injective. On ne peut donc pas l'appliquer à n'importe quel é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é définie sur `E`:
`{x "↦" x "/" x inE}`
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 `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. Les relations `f^**` et `f^+` sont des applications sur `E`. La relation `f^+0` est l'application identité sur `E`.
`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` sont par définition les mêmes que ceux de `f`, et ceux de `f^+0`
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 dit que la relation est déterministe. 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ément 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.
On note l'ensemble des fonctions de `A` vers `B` de deux façons possibles, soit avec le symbole de la flêche pointillée `A"⇢"B`, ou en bisymbole par `A":×"B`.
`A":×"B = A"⇢"B`
La théorie des relations déterministes `R` de `A` vers `B` est la suivante :
`A"⇢"B = { R"∈"ccP(A"×"B) "/"` Relation `AAxAAyAAz, xRy` et `xRz => y"="z` Déterministe `}`
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 la relation `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}=Ø`.
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 étendre 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"`
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`
Une bijection `f` de l'ensemble `A` vers l'ensemble `B` est une application de l'ensemble `A` vers l'ensemble `B` où chaque élément de l'ensemble d'arrivé a exactement un prédécesseur. On dira que la relation est applicative et bijective. On note l'ensemble des bijections de `A` vers `B` de deux façons possibles, soit en notation flêchée `A"↔"B`, ou à l'aide du bisymbole `"=="` comme suit, `A"=="B`.
`A"=="B = A"↔"B`
On note l'ensemble des bijections sur `A` par `A"=="A` et aussi par `frS_A`.
`A"=="A = A"↔"A = 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 :
`|A"=="A| = |A"↔"A| = |frS_(A)| = |A|!`
La théorie de la relation applicative et bijective `R` de `A` vers `B` est la suivante :
`A"=="B = { R"∈"ccP(A"×"B) "/ "` Relation `AAxEEy, xRy,` Partout définie `AAxAAyAAz, xRy` et `xRz => y"="z` Déterministe `AAxEEy, yRx` Surjective `AAxAAyAAz, xRz` et `yRz => x"="y` Injective `}`
On l'a séparée ainsi en cinq axiomes :
Chaque application de `A` vers `B` est une relation de `A` vers `B`. Chaque élément de l'ensemble de départ a zéro ou un seul successeur. Chaque élément de l'ensemble de départ a un ou plusieur successeurs. Chaque élément de l'ensemble d'arrivé a zéro ou un seul prédécesseur. Chaque élément de l'ensemble d'arrivé a un ou plusieur prédécesseurs.
Une bijection est une relation déterministe, partout définie, injective, surjective, mais le plus couramment dit, est une application bijective. Il apparait une symétrie des propriétés selon qu'elles concernent l'ensemble de départ ou l'ensemble d'arrivé :
de départ
d'arrivé
Applicative veut dire déterministe et partout définie. Symétriquement, bijective veut dire injectif et surjectif. Une relation applicative est une application. Une relation déterministe est une fonction. Une relation partout définie est une transformation.
Conventionellement une injection est une application injective, et donc, la relation injective qui n'est pas forcement une application est plus générale. Conventionnellement une surjection est une application surjective, et donc, la relation surjective qui n'est pas forcement une application est plus générale. Conventionellement une bijection est une application bijective, et donc, la relation bijective qui n'est pas forcement une application est plus générale.
Ces 4 propriétés concernant l'ensemble de départ se combinent avec les 4 propriétés symétriques concernant l'ensemble d'arrivé pour produire 16 types de relations désignés par les bisymboles suivants : `"××"`, `"×∘"`, `"×:"`, `"×="`, `"∘×"`, `"∘∘"`, `"∘:"`, `"∘="`, `":×"`, `":∘"`, `"::"`, `":="`, `"=×"`, `"=∘"`, `"=:"`, `"=="`. Et nous avons les relations d'inclusion suivantes :
Et nous avons par symétrie 10 règles d'égalités :
Les propriétés concernant l'ensemble de départ donne lieu à 4 noms de relation que sont : Relation, Fonction, Tansformation, Application. Et nous avons les relations d'inclusion suivantes : les applications sont à la fois des fonctions et des transformations, les fonctions et les transformations sont des relations.
En considérant le passage à la relation inverse, on définie 7 types de relations :
(Chaque élément de l'ensemble de départ a 0 ou 1 successeur.)
(Chaque élément de l'ensemble de départ a 1 ou plusieurs successeurs.)Relation déterministe partout définie
(Chaque élément de l'ensemble de départ a exactement 1 successeur.)
(Chaque élément de l'ensemble d'arrivé a 0 ou 1 prédécesseur.)
(Chaque élément de l'ensemble d'arrivé a 1 ou plusieurs prédécesseurs.)
(Chaque élément de l'ensemble d'arrivé a exactement 1 prédécesseur.)
Les 4 axiomes évoqués par la bijection peuvent être combinées de `2^4 = 16` façons possibles, donnant lieu à la définition de 16 types de relations. Il existe une symétrie entre ces 4 axiomes qui est explicite à l'aide de la notation des relations en bisymbole. Si une relation vérifie un axiome, la relation inverse vérifie son axiome symétrique :
Il convient donc d'étudier 8 types de relations. Ce sera la liste des relations suivantes : application, fonction, bijection, injection, fonction injective, surjection, transformation, transformation surjective.
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 considérons un nouvel élément `e`, l'ensemble des bijections sur `A"+"{e}` comprend 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 en ajoutant l'arc `e"↦"x`. Cela se traduira par la relation de récurrence suivante :
`f(a"+"1) = (a"+"1)f(a)`
Notez que l'expression `(e"↦"x)` peut désigner (selon la convention vue au chapitre 3.1) l'application qui ne possède que l'arc `e"↦"x`. Et donc `(e"↦"x)` signifie `{e"↦"x}`.
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!`
Le calcul de `|frS_(A)|` peut s'écrire de façon itérative. L'idée 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}` où `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`.
`frS_(A) = a!`
Une injection est une application injective. C'est à dire une application où chaque élément de l'ensemble d'arrivé a zero ou un seul prédécesseur. On dira que la relation est applicative et injective. On note l'ensemble des injections de `A` vers `B` de deux façons possibles, soit en notation flêchée `A"↪"B`, ou soit en bisymbole `A"꞊:"B`.
`A"=:"B = A"↪"B`
Le nombre d'injections de `A` vers `B` est donné par la formule suivante :
`|A"=:"B| = |A"↪"B| = (|B|!)/((|B|-|A|)!)`
La théorie de la relation applicative injective `R` de `A` vers `B` est la suivante :
`A"↪"B = { R"∈"ccP(A"×"B "/"` Relation `AAxEEy, xRy` Déterministe `AAxAAyAAz, xRy` et `xRz => y"="z` Définie partout `AAxAAyAAz, xRz` et `yRz => x"="y` Injective `}`
Une injection est une relation déterministe, partout définie, injective, mais le plus couramment dit, est une application injective.
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 considérons un nouvel élément `e`, l'ensemble des injections de `A"+"{e}` vers `B` comprend les injections composées d'une injection de `A` vers `B"-"{x}` où `x` est un élément quelconque de ` B` et que l'on complétera en ajoutant l'arc `e"↦"x`. Cela se traduira 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 exacte `"-"`. L'expression `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 "∈" 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)!)`
Une fonction injective `f` de `A` vers `B` est une relation de `A` vers `B` satisfaisant deux propriétés : 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 première propriété est désignée par le qualificatif déterministe. La seconde propriété est désigné par le qualificatif injectif. Une fonction injective est une relation déterministe 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`.
`A"::"B = A`
La théorie de la relation déterministe injective `R` de `A` vers `B` est :
`(A` Relation `AAxAAyAAz, xRy` et `xRz => y"="z` Déterministe `AAxAAyAAz, xRz` et `yRz => x"="y` 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 encore une fonction injective. Et donc nous avons :
`|A"::"B| = "|"A`
`B"|"`On note :
`a = |A|` `b = |B|` `f(a,b) = "|"A`
`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 considérons un nouvel élément `e`, l'ensemble des fonctions injectives de `A"+"{e}` vers `B` comprend les fonctions injectives de `A"+"{e}` vers `B` où `e` possède une image, et les fonctions injectives de `A"+"{e}` vers `B` où `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 traduira 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` `f(a,b)= f(b,a)`
On dévoile la relation de récurrence sur les ensembles :
| `(A"+"{e})``B = {g∈(A"+"{e})``B "/" EEy, (e,y)"∈"g} + {g∈(A"+"{e})``B "/" AA 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 `f(a,b)`, le nombre de fonctions injectives d'un ensemble de `a` éléments vers un ensemble de `b` éléments, en en donnant un moyen efficace de calcul par récurrence.
`B"|"`On comptabilise les fonctions injectives en fonction de leur domaine de définition. Comme les fonctions injectives restreintes à leur domaine de définition deviennent des applications injective, nous avons l'union disjointe suivante :
`A"::"B = sum_(X in ccP(A)) X"=:"B`
On comptabilise les fonctions injectives en fonction du cardinal du domaine de définition. Pour un cardinal zéro, il y a la relation vide, pour un cardinal `1`, il y a `a"="|A|` domaines de définition possibles, et pour chacun il y `b"="|B|` applications injectives possibles, pour un cardinal `2`, il y a `a(a"-"1)"/"2!` domaines de définition possibles, et pour le premier élément il y a `b` images possibles et pour le second élément il y a `(b"-"1)` images possibles non déjà prises, il y a donc `b(b"-"1)` applications injectives possibles. Et ainsi de suite :
`|A"::"B| = 1 + ab + (a(a"-"1)b(b"-"1))/(2!) + (a(a"-"1)(a"-"2)b(b"-"1)(b"-"2))/(3!) + ...`
`+ (a(a"-"1)(a"-"2)...(a"-"n"+"1) b(b"-"1)(b"-"2)...(b"-"n"+"1))/(n!)`
L'itération perdure jusqu'à ce que `n"="a` ou `n"="b`. On vérifie la conformité des résultats sur quelques valeurs particulières prises au hasard. Cela nous sert d'élément de preuve qu'il n'y a pas d'erreur de calcul ni d'erreur de raisonnement. Ainsi par exemple :
`f(4,3) = 1+ 3×4 + ((3×2)×(4×3))/2 + ((3×2×1)×(4×3×2))/6 = 73`
On comptabilise les fonctions injectives en fonction de leur l'image. Comme les fonctions injectives dont on restreint leur ensemble d'arrivé à leur image, deviennent des fonctions bijectives, qui constitue des injections inverses, nous avons l'union disjointe suivante :
`A"::"B = sum_(Y in ccP(B)) A":="Y = sum_(Y in ccP(B)) Y"=:"A`
Une surjection `f` de l'ensemble `A` vers l'ensemble `B` est une application de `A` vers `B` où chaque élément de l'ensemble d'arrivé a au moins un prédécesseur. On dira que la relation est applicative et surjective. On note l'ensemble des surjections de `A` vers `B` de deux façons possibles, soit en notation flêchée `A"↠"B`, ou soit en bisymbole par `A"=∘"B`
`A"=∘"B = A"↠"B`
La théorie de la relation applicative surjective `R` de `A` vers `B` est la suivante :
`A"↠"B = { R"∈"ccP(A"×"B) "/"` Relation `AAxEEy, xRy,` Définie partout `AAxAAyAAz, xRy` et `xRz => y"="z` Déterministe `AAyEEx, xRy` Surjectif `}`
Une surjection est une relation partout définie, déterministe, surjective, mais le plus couramment dit, est une application surjective.
En posant `a = |A|` et `b = |B|` et à condition que `a"⩾"b"⩾"0`, le nombre de surjections possibles de `A` vers `B` est donné par la formule suivante :
`|A"↠"B| = b! S(a,b)`
`|A"↠"B| = sum_(n=0)^b ("-"1) ^(b"-"n) ((b),(n)) n^a`
Où les `S(a,b)` s'appellent « les nombres de Stirling de seconde espèce ».
Et où `((b),(n)) = (b!)/(n!(b"-"n)!)` avec `n<=b`, sont les coefficients binomiaux.
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 considérons un nouvel élément `e`, l'ensemble des surjections de `A"+"{e}` vers `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 en ajoutant au graphe l'arc `e"↦"x` pour `x"∈"B`. La seconde partie comprend pour chaque élément `x "∈" B`, les surjections de `A"↠"(B"-"{x})` complétées avec l'arc `e"↦"x`. Cela se traduira par la relation de récurrence suivante : `f(a"+"1,b) = bf(a,b) "+" bf(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` |
| Si`B"="Ø` et `A"≠"Ø` alors `(A"↠"B) = Ø` |
| Si `b"="0` et `a">"0` 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` Si `b"="0` et `a">"0` 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 lorsque `a"⩾"b"⩾"0`, ce coefficient est égal à :
`f(a,b) = sum_(n=1)^b ("-"1)^(b-n)((b),(n))n^a`
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.
Une fonction surjective de `A` vers `B` est une relation `R` de `A` vers `B` qui est déterministe c'est à dire telle que chaque élément de `A` n'a au plus qu'une image par `R`, et qui est surjective c'est à dire telle que `R(A)"="B`.
L'ensemble des fonctions surjectives de `A` vers `B` se note en bisymbole par `A":∘"B` où à l'aide d'une double flêche pointillée.
La théorie de la relation déterministe surjective `R` de `A` vers `B` est la suivante :
`A":∘"B = { R"∈"ccP(A"×"B) "/ "` Relation `AAxAAyAAz, xRy` et `xRz => y"="z` Déterministe `AAyEEx, xRy,` Surjective `}`
Une fonction surjective est une relation déterministe, surjective.
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}` vers `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` vers `B` que l'on complète de `b+1` façons possibles en ajoutant l'arc `e"↦"x` pour `x"∈"B` ou bien en lui attribuant aucune image. La seconde partie comprend pour chaque élément `x"∈"B`, les fonctions surjectives de `A` vers `B"-"{x}` complétées en ajoutant l'arc `e"↦"x`. Cela se traduira par la relation de récurrence suivante :
`f(a"+"1,b) = (b+1)f(a,b) "+" bf(a,b"-"1)`
On dévoile la relation de récurrence sur les ensembles :
| `(A"+"{e})":∘"B = A":∘"B + {g"+"(e"↦"x) "/" g∈A":∘"B, x"∈"B} + {h"+"(e"↦"x) "/" h∈A":∘"(B"-"{x}), x"∈"B}` |
| `(A"+"{e})":∘"B = A":∘"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| + |A":∘"B| |B| + |B| |A":∘"(B"-"{x})|` |
| `f(a"+"1,b) = f(a,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"+"1)f(a,b) + bf(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.
On comptabilise les fonctions surjectives en fonction du domaine de définition. Comme les fonctions surjectives restreintes à leur domaine de définition deviennent des applications surjectives, nous avons l'union disjointe suivante :
`|A":∘"B| = sum_(X in ccP(A)) |X"=∘"B|`
`|A":∘"B| = sum_(n=0)^|A| sum_(X in ccP_n(A)) |X"=∘"B|`
`f(a,b) = sum_(n=0)^a ((a),(n)) g(n,b)`
où `f(a,b)` est le nombre de fonctions surjectives d'un ensemble de départ de `a` éléments vers un ensemble d'arrivé de `b` éléments, et où `g(a,b)` est le nombre d'applications surjectives d'un ensemble de départ de `a` éléments vers un ensemble d'arrivé de `b` éléments (tableau au chapitre 12.1). On vérifie la conformité des résultats sur quelque valeur prise au hasard. Cela nous sert d'élément de preuve qu'il n'y a pas d'erreur de calcul ni d'erreur de raisonnement. Ainsi par exemple :
`f(4,3) = ((4),(0)) g(0,3) + ((4),(1)) g(1,3) + ((4),(2)) g(2,3) + ((4),(3)) g(3,3) + ((4),(4)) g(4,3)`
`f(4,3) = 1"×"0 + 4"×"0 + 6"×"0 + 4"×"6 + 1"×"36 = 60`
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`
La théorie de la relation partout définie `R` de `A` vers `B` est la suivante :
`A"∘×"B = { R"∈"ccP(A"×"B) "/"` Relation `AAxEEy, xRy,` Partout définie `}`
Les transormations `R` d'un singleton vers un ensemble `E` sont exactement déterminées par leur image Im`(R)` qui peut être n'importe qu'elle partie non vide de `E`. Il y a donc une bijection entre `{u}"∘×"E` et `ccP(E)"-"Ø`. Et donc
`|{u}"∘×"E| = |ccP(E)| - 1 = 2^|E| - 1`
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. Nous avons :
`f(1,b) = 2^b-1`
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`. Cela se traduira par la relation de récurrence 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`
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`
La théorie de la relation partout définie surjective `R` de `A` vers `B` est la suivante :
`A"∘∘"B = { R"∈"ccP(A"×"B) "/"` Relation `AAxEEy, xRy,` Partout définie `AAyEEx, xRy,` Surjective `}`
On remarque que la définition est symétrique, et donc que la relation inverse d'une transformation surjective est une transformation surjective. Et donc nous avons :
`|A"∘∘"B| = |B"∘∘"A|`
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}"∘∘"Ø = Ø`
`Ø"∘∘"Ø = {Ø}`
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 d'autre part nous avons `f(1,b) "=" (b"≠"0)`, où l'expression `(b"≠"0)` vaut `1` lorsque `b"≠"0` et `0` lorsque `b"="0`.
En bref : Nous considérons un nouvel élément `e`, et nous analysons comment subdiviser l'ensemble des transformations surjectives `R` de `A"+"{e}` vers `B`. Même raisonnement que pour les fonctions surjectives, l'ensemble des transformation surjectives de `A"+"{e}` vers `B` se scinde en deux partie ; une première partie regroupant les transformations surjectives qui si on enlève l'élément `e` sont encore des transformations surjectives, et une seconde partie regroupant les transformations surjectives qui si on enlève l'élément `e` ne sont plus surjectives.
La première partie comprend les transformations surjectives de `A` vers `B` que l'on complète par union disjointe de graphe, avec n'importe quelle transformation de `{e}` vers `B` pour former une transformations surjectives de `A"+"{e}` vers `B`.
La seconde partie est un peu plus compliquées à définir. On considère l'ensemble `X sube B` des éléments qui n'ont comme seul prédécesseur `e`. La seconde partie comprend pour chaque partie non vide `X` de `B`, les transformations surjectives de `A` vers `(B"-"X)` complété avec les arcs `{e"↦"y "/" y "∈" Y}` où `Y` est une partie de `B` contenant `X`, c'est à dire la réunion de `X` et d'une partie de `(B"-"X)`. Et on considère les parties `X` à un élément, puis les parties `X` à deux éléments, etc..., jusqu'à la partie `X` à `b` éléments qui correspond à `B` entier. Cela se traduira par la relation de récurrence suivante :
`f(a"+"1,b)=(2^b"-"1)f(a,b) + b2^(b"-"1)f(a,b"-"1) + (b(b"-"1))/2 2^(b"-"2)f(a,b"-"2) + (b(b"-"1)(b"-"2))/(3!) 2^(b"-"3)f(a,b"-"3) ...`
`f(a"+"1,b)=(2^b"-"1)f(a,b) + sum_(n=1)^b ((b),(n)) 2^(b"-"n) f(a,b"-"n)`
Avec pour rappel `b>=n` :
`((b),(n)) = (b!)/((b"-"n)!n!) = (b(b"-"1)(b"-"2)...(b"-"n"+"1))/(n!)`
On dévoile la relation de récurrence sur les ensembles :
| `(A"+"{e})"∘∘"B = {f"+"g "/" f in A"∘∘"B, g in {e}"∘×"B} + {g + {e}"×"(X"+"Y) "/" g in A"∘∘"(B"-"X), Y "∈" ccP(B"-"X)}` |
| `(A"+"{e})"∘∘"B = sum_(f in A"∘∘"B) sum_(g in {e}"∘×"B) {f"+"g} + sum_(X in ccP(B)) sum_(g in A"∘∘"(B"-"X)) sum_(Y "∈" ccP(B"-"X)){g + {e}"×"(X"+"Y)}` |
| `(A"+"{e})"∘∘"B = sum_(f in A"∘∘"B) sum_(g in {e}"∘×"B) {f"+"g} + sum_(n=1)^|B| sum_(X in ccP_n(B)) sum_(g in A"∘∘"(B"-"X)) sum_(Y "∈" ccP(B"-"X)){g + {e}"×"(X"+"Y)}` |
| `|(A"+"{e})"∘∘"B| = sum_(f in A"∘∘"B) sum_(g in {e}"∘×"B) 1 + sum_(n=1)^|B| sum_(X in ccP_n(B)) sum_(g in A"∘∘"(B"-"X)) sum_(Y "∈" ccP(B"-"X)) 1` |
| `|(A"+"{e})"∘∘"B| = |A"∘∘"B| |{e}"∘×"B| + sum_(n=1)^|B| sum_(X in ccP_n(B)) |A"∘∘"(B"-"X)| |ccP(B"-"X)|` |
| `f(a"+"1,b) = f(a,b)(2^b"-"1) + sum_(n=1)^b ((b),(n)) f(a,b"-"n) 2^(b"-"n)` |
| `f(a"+"1,b) = (2^b"-"1)f(a,b) + sum_(n=1)^b 2^(b"-"n)((b),(n))f(a,b"-"n)` |
| Si `B!=Ø` alors `|{u}"∘∘"B| = 1` |
| Si `b>0` alors `f(1,b) = 1` |
| `{u}"∘∘"Ø = Ø` |
| `f(1,0)=0` |
| `Ø"∘∘"Ø = {Ø}` |
| `f(0,0)=1` |
Conclusion :
`f(a"+"1,b) = (2^b"-"1)f(a,b) + sum_(n=1)^b 2^(b"-"n)((b),(n))f(a,b"-"n)` Si `b>0` alors `f(1,b) = 1` `f(0,0)=1`
Cela définit le coefficient `f(a,b)` en en donnant un moyen de calcul par récurrence.
La propriété `f(a,b) "=" f(b,a)` est bien vérifiée. Cela constitue un élément de preuve comme quoi il n'y a pas d'erreur de calcul ni d'erreur de raisonnement.
Une ambiguité apparait dans l'usage des opérations d'union disjointe `"+"` et de différence exacte `"-"` entre ensembles, lorsque les éléments des ensembles en question peuvent également faire l'objet de l'opération de somme `"+"` ou de soustraction `"-"` . L'expression `A"+"B` peut avoir trois significations possibles. Soit c'est l'ensemble des éléments obtenus en soustrayant d'un élément de `A`, un élément de `B` :
`A"+"B= {a"+"b "/" a "∈" A, b "∈" B}`
Soit c'est l'union disjointe de `A` et de `B` :
`A"+"B= {a "/" a "∈" A "ou" a "∈" B} "et" AnnB=Ø`
Ou, si les ensembles en question sont des ensembles d'arcs représentant des applications sur `E`, soit c'est la somme des images :
`A"+"B= {x"↦"(A(x)"+"B(x)) "/" x"∈" E}`
On pourrait adopter un signe distinctif pour différentier ces trois opérations, mais dans un premier temps, on laissera au contexte le soin de lever l'ambiguité, par l'ajout d'un commentaire par exemple.
Etant donné une relation de `A` vers `B`, on symbolise les propriétés à l'aide d'un symbole prefixe et d'un symbole suffixe.
Relatif à l'ensemble de départ
Relatif à l'ensemble d'arrivé`"×"` Relation
`"×"` `"∘"` Transformation (Partout défini) `"∘"` Surjective `":"` Fonction (Deterministe) `":"` Injective `"="` Application `"="` Bijective
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 |
Cardinal Calcul itératif |
Cardinal `f(a,b)` Calcul récurcif |
`A "××" B` Relation Relation inverse |
`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 inverse |
`(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 inverse |
`(a+1)^b` |
`f(a,b"+"1) = f(a,b)(a"+"1)` `f(a,0) = 1` |
|
`A "×=" B` Relation bijective Application inverse |
`a^b` |
`f(a,b"+"1) = f(a,b)a` `f(a,0) = 1` |
|
`A "∘×" B` Transformation Relation surjective inverse |
`(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 surjective Transformation surjective inverse |
`f(a"+"1,b) = (2^b"-"1)f(a,b) + sum_(n=1)^b 2^(b"-"n)((b),(n))f(a,b"-"n)` Si `b>0` alors `f(1,b) = 1` `f(0,0)=1` |
||
`A "∘:" B`
Transformation injective Fonction surjective inverse |
`sum_(n=0)^b ((b),(n)) a! S(n,a)`
|
`f(a,b"+"1) = (b"+"1)f(a,b) + bf(a"-"1,b)` `f(a,b)=f(b,a)` Si `b"<"a` alors `f(a,b)"="0` |
|
`A "∘=" B`
Transformation bijective Surjection inverse |
`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 inverse |
`(b+1)^a` |
`f(a"+"1,b) = f(a,b)(b"+"1)` `f(0,b) = 1` |
|
`A ":∘" B` Fonction surjective Transformation injective inverse |
`sum_(n=0)^a ((a),(n)) b! S(n,b)` |
`f(a"+"1,b) = (b"+"1)f(a,b) + bf(a,b"-"1)` `f(a,b)=f(b,a)` Si `a"<"b` alors `f(a,b)"="0` |
|
`A "::" B` Fonction injective Fonction injective inverse |
`f(a"+"1,b) = f(a,b) + bf(a,b"-"1)` `f(a,b)=f(b,a)` `f(0,b)=1` |
||
`A ":=" B` Fonction bijective Injection inverse |
`(a!)/((a-b)!)`
|
`f(a,b"+"1)=f(a"-"1,b)a` `f(a,0)=1` `f(a,a)=a!` |
|
`A "=×" B` Application Relation bijective inverse |
`b^a` |
`f(a"+"1,b) = f(a,b)b` `f(0,b) = 1` |
|
`A "=∘" B` Surjection Transformation bijective inverse |
`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 inverse |
`(b!)/((b-a)!)` |
`f(a"+"1,b)=f(a,b"-"1)b` `f(0,b)=1` `f(a,a)=a!` |
|
`A "==" B` Bijection Bijection inverse |
`a! (a"="b)` |
`f(a"+"1)=f(a)(a+1)` `f(0) = 1` |
|
avec
`y! S(x,y) = sum_(n=0)^y ("-"1) ^(y"-"n) ((y),(n)) n^x`
---- 1 octobre 2020 ----