On part du point de vue élémentarien où tout est calcul. Puis dans une spirale exploratrice ascendante, on revisite les bases de l'algèbre en réordonnant les définitions et en créant des interconnexions à chaque tour. Ainsi, à chaque tour de la spirale, nous revisitons des thèmes récurrents, et pour chacun d'eux nous refrayons sans cesse nos pérégrinations en les complétants du savoir des autres thèmes.
Les mathématiques élémentariennes sont jumelles de l'informatique, n'usant comme seul fondement le langage et la programmation.
La formalisation des démonstrations entraine une complexité qui nuit à la compréhension globale noyant l'important dans le détail. Mais le choix d'un langage adapté résoud d'autant cette complexité. Ne dit-on pas que l'exposé d'un problème dans un langage adapté constitue la moitier de sa résolution ?
Nous procèdons à une construction rigoureuse des mathématiques, comme l'on fait le groupe N. Bourbaki, mais avec une autre optique basée sur la construction des objets et des programmes plutôt que sur celle des démonstrations, la construction d'une sructure constituant la démonstration de son existence. Cela passe par la construction de structures de données et d'un langage formel.
Au départ, toutes les structures sont finies, et il n'y a pas de doute sur la pertinence et l'existence des objets et algorithmes ainsi décrits tant que l'on applique la mécanique classique. Puis, usant de la capacité énumérative des programmes, on construit des structures infinies, désignées par les programmes qui les énumèrent, et qui eux, sont de taille finie.
Un élément est une construction dans un langage d'opérateurs, qui sert de référence pour désigner toute chose que nous créons.
Du point de vue élémentarien, on constatera qu'un élément ne peut contenir qu'une quantité finie d'information.
Le premier type d'assemblage que l'on conçoit sont les listes. Et dans un premier temps on ne concidèrera que des listes dont les éléments ne sont pas des listes.
On note entre parenthèse `(a,b,a)` les éléments d'une liste sachant qu'ils peuvent être répétés plusieurs fois et que l'ordre compte. Autrement dit, la liste n'est pas commutative, ses éléments sont mis dans un ordre précis, toutes permutations de deux de ses éléments distincts change la liste, et dans l'exemple `(a,b,a)`, rien n'empêche que `a` puisse être égale à `b`.
Chaque liste finie possède un cardinal entier qui est le nombre de cases qu'elle contient, c'est à dire le nombre d'éléments, égaux ou distincts, qu'elle contient. Soit une liste `L`, on note sa taille ou son cardinal `|L|`. Exemple `|"("a,b,a")"|"="3`.
En faisant abstraction de l'ordre, chaque liste `L` correspond à un sac notée `"Sac"(L)`, qui est la liste à l'ordre près de ses éléments. Par exemple, le sac de `"("a,b,a")"`, est égale à `"⟅"a,a,b"⟆"`.
En faisant abstraction des répétitions, chaque liste `L` correspond à un arrangement notée `"Arrt"(L)`, qui est l'arrangement des éléments défini selon l'ordre de leur première apparition dans la liste `L`. Par exemple, l'arangement de `"("a,b,a")"`, est égale à `(:a,b:)`, où est ainsi ignoré toute répétition ultérieure d'élément.
En faisant abstraction de l'ordre et des répétitions, chaque liste `L` correspond à un ensemble notée `"Ens"(L)`, C'est l'ensemble des éléments présents au moins une fois dans la liste. Cet ensemble est aussi appelé le support de `L`. Par exemple, le support de `"("a,b,a")"`, si `a"≠"b`, est égale à `{a,b}`.
Les listes sont construites par des programmes. Un programme est par principe de taille finie, mais il peut énumérer une liste infinie. Dans le cas des listes finies, la liste elle-même constitue un programme qui l'énumére.
La liste vide se note `()` et constitue un élément particulier, et nous avons `|()|"="0`.
Il y a deux définitions de l'ensemble :
Ces deux définitions rendent pertinente la définition de deux objets de domaines intermédiaires que sont la liste d'éléments distincts appelé arrangement, et le multiensemble appelé sac.
On note entre accolades `{...}` les éléments d'un ensemble sachant que l'ordre n'y a pas d'importance mais que les éléments doivent nécessairement être deux à deux distincts. Ainsi l'expression `{a,b,c}`, en plus de définir un ensemble, signifie une condition supplémentaire portée à l'hypothèse, qui est que `a"≠"b` et `a"≠"c` et `b"≠"c`.
Chaque ensemble fini possède un cardinal entier qui est le nombre d'éléments qu'il contient. Soit un ensemble `E`, on note son cardinal `|E|`. Exemple `|{a,b}|"="2`.
L'ensemble vide se note `{ }` et se note aussi parfois par `Ø"="{ }`. Il constitue un élément particulier, et nous avons `|{ }| "=" |Ø| "=" 0`.
Un sac est une liste d'éléments à l'ordre près. On note entre double accolades `"⟅"a,a,b"⟆"` les éléments d'un sac sachant qu'ils peuvent être répétés plusieurs fois. L'ordre n'y a pas d'importance. Et dans l'exemple, rien n'empêche que `a` puisse être égale à `b`.
Chaque sac fini possède un cardinal entier qui est le nombre d'éléments, égaux ou distincts, qu'il contient. Soit un sac `S`, on note son cardinal `|S|`. Exemple `|"⟅"a,a,b"⟆"|"="3`
En faisant abstraction des répétitions, chaque sac `S` correspond à un ensemble notée `"Ens"(S)`, qui est l'ensemble des éléments présents au moins une fois dans le sac. Cet ensemble est aussi appelé le support de `S`. Par exemple, le support de `"⟅"a,a,b"⟆"`, si `a"≠"b`, est égale à `{a,b}`.
Le sac vide se note par `"⟅⟆"`, et nous avons `|"⟅⟆"|"="0`
Notez qu'un ensemble est un sac.
Un arrangement est une liste d'éléments distincts. On note entre chevrons `(:a,b,c:)` les éléments d'un arrangement sachant qu'ils doivent nécessairement être distincts et que l'ordre compte, autrement dit l'arrangement n'est pas commutatif, ses éléments sont mis dans un ordre précis. Toutes permutations de deux de ses éléments change l'arrangement. Par exemple, l'expression `(:a,b,c:)`, en plus de définir un arrangement, signifie une condition supplémentaire portée à l'hypothèse, qui est que `a"≠"b` et `a"≠"c` et `b"≠"c`. Et on constatera que cet arrangement consitue un arrangement distinct de `(:b,a,c:)`.
Chaque arrangement fini possède un cardinal entier qui est le nombre d'éléments qu'il contient. Soit un arrangement `A`, on note son cardinal `|A|`. Exemple `|(:a,b,c:)|"="3`
En faisant abstraction de l'ordre, chaque arrangement `A` correspond à un ensemble notée `"Ens"(A)`, qui est l'ensemble des éléments présents dans l'arrangement. Cet ensemble est aussi appelé le support de `A`. Par exemple, le support de l'arrangement `(:c,a,b:)`, est égale à `{a,b,c}`.
L'arrangement vide se note par `(::)`, et nous avons `|(::)|"="0`
Notez qu'un arrangement est une liste.
On doit pouvoir écrire sans ambiguité une opération fondamentale qu'est l'ajout d'un nouvel élément à un ensemble. L'ajout d'un nouvel élément `e` à un ensemble `A` se note :
`A+{e}`
Mais attention, cette expression affirme en même temps que `e"∉"A`. Et d'une manière plus générale, la somme de deux ensembles `A"+"B` signifie en même temps que `B` est disjoint de `A`. Il s'agit en cela d'une somme exacte.
De même, on doit pouvoir écrire sans ambiguité une opération fondamentale qu'est le retrait d'un élément présent dans un ensemble. Le retrait d'un élément présent `e` d'un ensemble `A` se note :
`A-{e}`
Mais attention, cette expression affirme en même temps que `e "∈" A`. Et d'une manière plus générale, la différence de deux ensembles `A"-"B` signifie en même temps que `B` est inclus dans `A`.
Les opérations d'union disjointe `"+"` et de différence exacte `"-"` ont une priorité syntaxique égale et s'évaluent conventionnellement de gauche à droite faisant que l'expression `A"-"B"+"C` signifie précisement `(A"-"B)"+"C` et `B "⊆" A` et `C` disjoint de `A"-"B`, et finalement correspond à la substitution dans l'ensemble `A` de la partie `B` par la partie `C`.
Par exemple, l'expression `E"-"{a}"+"{b}` correspond à une substitution dans `E` de l'élément `a` par l'élément `b`, et affirme que `a "∈" E` et que `b "∉" E"-"{a}`.
On verra plus-tard comment cette notion de somme exacte et de différence exacte peut s'étendre et se définir à d'autre structure.
Il est utile d'adopter une notation de la relation d'ordre qu'est l'inclusion sur le même modèle de la relation d'ordre sur les entiers. C'est pourquoi on réseve le symbole `sub` pour désigner l'inclusion stricte de façon analogue au symbole `<`, et le symbole `sube` pour désigner l'inclusion de façon analogue au symbole `<=`. Notez que cela change la signification du symbole `sub` tel qu'il était jusqu'alors utilisé.
La priorité syntaxique des relations d'ordre est la plus faible, juste au dessus des relations d'égalité, d'équivalence et d'implication.
Ainsi pour tout ensemble `A`, nous avons :
`A sub A+{e}`
`A sube A uu {e}`
Les formes négatives s'expriment en barrant par un slash le symbole.
L'expression `A ⊄ B` signifie que `A` n'est pas inclus strictement dans `B`, c'est à dire que soit `A` est égale à `B` ou soit il existe un élément de `A` qui n'est pas dans `B`.
L'expression `A ⊈ B` signifie que `A` n'est pas inclus dans `B`, c'est à dire qu'il existe un élément de `A` qui n'est pas dans `B`.
Peut-t-on créer quelque chose ex nihilo ? on ne répondra pas à cette question. L'approche mathématique est plus prudente. Elle utilise l'extension élémentaire c'est à dire l'ajout d'un nouvel opérateur qui enrichie son langage. Et cette création peut être répétée par un programme.
On crée 3 éléments en les nommant pour la première fois, par exemple `u, v, w`, ce qui enrichie le langage de trois opérateurs générateurs d'arité zéro. L'extension est intérieur à un ensemble `A` si on ajoute la condition `(u in A)` et `(v in A)` et `(w in A)`, auquel cas ces 3 éléments jouent le rôle de variables désignant des éléments inconnues dans `A`. Et la plus part du temps cette condition est implicite, les éléments inconnues étant considérés appartenant à la structure. Il n'y a donc pas de création d'éléments ni d'extension élémentaire. Par contre, en l'absence de telles conditions, l'extension est dite potentiellement extérieur, c'est à dire qu'elle ouvre la possibilité de désigner d'autres éléments, non encore désignables jusqu'a présent, bien entendu si cela ne contredit pas la théorie de la structure en cours.
Et dans l'optique d'accéder à de nouvelles structures mathématiques on peut même être amené dans le cadre de ces extensions élémentaire à renoncer à des portions de la théorie de la structure initiale.
Les éléments calculables étants des compositions closes d'opérateurs générateurs, l'ajout d'opérateurs générateurs au langage va démultiplier les possibilités de construction. Et si la théorie de la structure en question ne reduit pas toutes ces constructions à des éléments déjà existant alors cela crée de nouveaux éléments calculables. Autrement dit le langage s'agrandit et la structure calculable également. L'extension élémentaire correspond donc à l'agrandissement d'une structure, de sa partie calculable, en ajoutant des éléments générateurs à son langage.
Souvent on a recours à une numérotation des nouvelles variables telle que par exemple `e_1, e_2, e_3, ...` qui peuvent être en nombre infini mais énuméré, et on les délimite comme appartenant à un ensemble connue ou bien implicitement comme appartenant à la structure. Dans ce cas, il ne s'agit pas d'une extension élémentaire. Cela correspond à une application de `NN` vers l'ensemble en question ou vers la structure, `n|->e_n`, associant à chaque entier `n` un élément inconnu de l'ensemble ou la structure, dénommé `e_n`.
Mais on peut aller au delà et procéder à une extension élémentaire. Cela associe alors à chaque entier `n` un nouvel opérateur générateur d'arité zéro `e_n` qui est ajouté au langage de la structure. Tout se passe comme si `e` était une application de `NN` vers une structure plus vaste, et que `"⟅"e_1,e_2,e_3,..."⟆"` formait un sac. Notez qu'il n'y a aucune théorie nouvelle concernant ces éléments et qu'ils peuvent donc être égaux entre eux d'où le regroupement en sac, et qu'ils peuvent aussi être égaux à des éléments déjà connus. On les qualifies d'extérieurs car ils ont la possibilité de constituer de nouveaux éléments n'appartenant pas à la structure initale (en tout cas à sa partie calculable), si la théorie en cours le permet (car en effet, il existe des théories qui forcent ces nouveaux éléments à être contenus dans la structure initiales). On procède à l'extension élémentaire en agrandissant la structure par l'ajout à son langage, de ces nouveaux opérateurs générateurs.
On définit souvent nos structures mathématiques dans un langage logique du premier ordre, qui constitue une vision plate et limitée par ce qui est exprimable dans ce langage, et où les éléments calculables sont tous des compositions closes d'opérateurs générateurs, et où les variables sont toutes du même type, des variables universelles pouvant s'unifier avec n'importe quelle terme désignant un élément calculable.
Mais même avec ce cadre limité, Kurt Gödel démontra l'incomplétude inhérente à toute théorie du premier ordre contenant l'arithmétique, et l'incapacité même de démontrer la cohérence de l'arithmétique.
C'est pourquoi on fait le choix de fonder la cohérence de la structure par sa construction. On ajoute à la structure une théorie d'engendrement, une théorie qui n'est pas du premier ordre mais qui reste indispenssable pour fonder la construction et qui affirme que la structure ne contient que ses éléments calculables.
Chaque structure possède ainsi en plus une théorie d'engendrement qui explique comment sont énumérés tous ses éléments. Et les théories d'engendrement ne sont pas du premier ordre. Ainsi une structure comprend 3 théories : sa théorie du premier ordre, sa théorie d'engendrement, et sa théorie globale qui est la conjonction des deux précédentes.
Puis il est nécessaire de renouer avec le prinicpe de relativité. Une même structure peut être vue différement selon où se trouve l'observateur. Ainsi on se libèrera en partie de la rigidité de l'engendrement tout en l'utilisant comme fondation, dévoilant ainsi une notion de structure plus générale.
Nous pensons qu'il n'y a pas de différence de nature entre théorie et règles de déduction. Délors, de même que toute théorie du premier ordre est incomplète et que tout langage est complétable, tout sytème de déduction peut être considéré comme incomplet.
à l'aide même de la logique du premier ordre, la seul façon de fonder les mathématiques, est la mécanique classique vérifiée localement.
C'est pourquoi on commence par décrire les objets mathématiques finis, et on s'autorise à utiliser des langages logiques d'ordre supérieur si nécessaire, introduisant la récurrence et les théories d'engendrement, ainsi que différents types d'éléments et de variables pouvant possèder des arités supérieures à zéro.
Et on munit le langage d'un mécanisme d'inférence des types selon des techniques utilisés par la programmation, afin d'obtenir un langage mathématique moins verbeux qui aille à l'essentiel.
Le langage est composé d'opérateurs générateurs et de prédicats générateurs. Les éléments sont des constructions finies du langage, et forment ce que l'on appelle en informatique, une implémentation des données, une façon de mémoriser les données par le biais d'un langage.
Il est toujours possible de créer une structure par duplication, simplement en dupliquant tous les termes du langage utilisé.
Considérons un ensemble `A = {a,b,c}`. Notez que cette expression affirme que les éléments `a,b,c` sont distincts. On crée un double de cet ensemble en le nommant pour la première fois par exemple : `A'`.
`A={a,b,c}`
`A'={a',b',c'}`
Pour cela nous avons utilisé un foncteur, c'est à dire une application qui à chaque opérateur générateur ou prédicat générateur du langage renvoie un opérateur générateur ou prédicat générateur d'un autre langage. Le foncteur permet ainsi de traduire les données et propositions d'un langage à un autre.
La duplication de l'ensemble `A` en l'ensemble `A'` correspond à une bijection de `A` vers `A'` définie par `AAx"∈"A, x"↦"x'`. L'apostrophe constitue le foncteur, il est ici à prendre comme une fonction en notation française de `A` vers `A'`. L'ensemble d'arrivé n'est pas défini dans la première structure mais dans la seconde structure, c'est pourquoi elle correspond à une extension potentiellement exterieure `A'`. La dénomination différente de ces nouveaux éléments `a',b',c'` n'entraine pas qu'ils soient distincts entre eux, mais la propriété d'ensemble de `A` qui est transportée par le foncteur en la propriété d'ensemble de `A'` entraine qu'ils sont distincts entre eux.
Dans les mathématiques élémentariennes, le langage étant le seul fondement, il joue un rôle crucial. Il va, entre autre, permettre de formaliser complètement les démonstrations comme l'on fait le groupe N.Bourbaki, mais sans introduire l'immanence, l'infini inné, puisque tout doit être construit, puisque tout est langage. En ce sens davantage intuitionniste, la formalisation s'orientera d'abord dans la construction des structures et des programmes avant celles des autres démonstrations, sachant que la construction d'une structure constitue déjà la preuve de son existence.
De même qu'en programmation où l'on se dote d'outils permettant d'effectuer des calculs itératifs, on se dote en mathématique d'opérateurs appelés itérateurs qui transcrivent ces calculs itératifs, telles notamment des énumérations et des sommations.
On adopte une convention d'écriture qui réduit le nombre de variables muettes apparentes, dans le but de simplifier la complexité des formules.
Les itérateurs, telle que l'énumération ou la sommation, possédant des déclarations de variables, peuvent déclarer des variables déjà présentes dans le contexte parent, ce qui occasionne un masquage de celles-ci, non pas dans leur déclaration, mais dans le corps de l'itération. Exemple :
`sum_(k=1)^k k = 1+2+...+k = (k(k+1))/2`
L'itérateur de somme définie une nouvelle variable `k` en précisant qu'elle va de `1` à `k`, mais ce dernier `k` fais référence au `k` d'un contexte parent. Et ce `k` du contexte parent va être masqué par la définition de ce nouveau `k` qui va être utilisé dans la formule de la somme.
`sum_(k=1)^k sum_(k=1)^k k = (1+2+...+k) + (2+3+...+k) + (3+4+...+k) ... + (k) = (k(k+1)(k+2))/(3!)`
Dans cette expression il y a trois niveaux de contexte, un `k` parent, un `k` définie dans la première sommation, et un `k` définie dans la seconde sommation.
Ce mécanisme d'empilement des contextes, permet d'écrire une telle sommation sous forme d'un opérateur pouvant être répété par exemple 3 fois comme suit, et qui constitue une factorisation programmative :
`(sum_(k=1)^k)^3 k = (k(k+1)(k+2)(k+3))/(4!)`
Et on peut utiliser une convention d'écriture pour désigner si de besoin, une variable du contexte au dessus d'un masquage, en la préfixant du symbole `"↑"`. Exemple :
`U_k = sum_(k=1)^k k/("↑"k-k+1) = sum_(j=1)^k j/(k-j+1)`
`U_k = 1/k + 2/(k-1) + 3/(k-2) + ... + (k-2)/3 + (k-1)/2 + k`
La construction de listes peut se programmer itérativement. On peut répéter une duplication pour produire une liste. Par exemple voici une liste `U_k` de `k` éléments inconnus :
`U_k = (e_k)_(k=1)^k`
`U_k = (e_1,e_2,...,e_k)`
De même pour les sacs, voici un sac `S_k` de `k` éléments inconnus :
`S_k = "⦃"e_k"⦄"_(k=1)^k`
`S_k = "⦃"e_1,e_2,...,e_k"⦄"`
La différence entre le sac et la liste est que dans un sac l'ordre de la disposition des éléments n'a pas d'importance.
Ces éléments sont-ils nouveaux ? Oui en dénomination, mais rien n'indique qu'ils soient différents entre eux ou avec des éléments déjà connus. Mais ils peuvent constituer une extension élémentaire si on les ajoute au langage de la structure comme éléments générateurs, et constituer des éléments nouveaux si la théorie en cours le permet. Dans ce cas là, on parlera de `k` nouveaux éléments.
De même pour les ensembles, voici un ensemble `A_k` de `k` éléments inconnus.
`A_k = {e_k}_(k=1)^k`
`A_k = {e_1,e_2,...,e_k}`
Notez alors que l'énumération se faisant entre accolades `{}`, cela signifie en plus que :
`AA i "∈"{1..k} AA j "∈" {1..k}"-"{i}, e_i"≠"e_j`
Notez que `{1..n}` désigne l'ensemble des entiers allant de `1` à `n`. Mais on notera souvant cette propriété comme suit :
`AAiAAj, e_i"="e_j <=> i"="j`
L'union disjointe d'ensembles peut se répéter à l'aide de l'itérateur `sum`.
Cette sommation permet de programmer l'énumération d'un ensemble à partir de sa définition. Ainsi par exemple, l'ensemble des couples composés d'un premier élément appartenant à `A` et d'un second élément appartenant à `B` est égal à :
`{(x,y) "/" x "∈" A, y "∈" B} = sum_(x in A) sum_(y in B) {(x,y)}`
Considérons un ensemble fini `A`. Voici un ensemble `B` composé d'éléments inconnus distincts en nombre égale au cardinal de l'ensemble `A` :
`B = {e_k}_(k in A)`
Cela signifie qu'il existe une bijection de `A` vers `B` définie par `AAk"∈" A, k"↦"e_k`. L'ensemble d'arrivé `B` regroupe les éléments inconnus, supposés distincts puisque énumérés entre accolades. Nous avons :
`B = sum_(k in A) {e_k}`
Voici un sac `S` composé d'éléments inconnus, mais non nécessairement distincts, en nombre égale au cardinal de l'ensemble `A`
`S = "⦃"e_k"⦄"_(k in A)`
Cela signifie qu'il existe une application de `A` vers le support de `S` définie par `k|->e_k`. Les éléments `e_k` avec `k` parcourant `A` peuvent être égaux entre eux puisque réunis dans un sac. Nous avons :
`S = uuu_(k in A) "⦃"e_k"⦄"`
Etant donné deux ensembles `A` et `B`. Le produit cartésien `A"×"B` désigne l'ensemble des couples composés d'un premier élément appartenant à `A` et d'un second élément appartenant à `B`.
`A"×"B = {(x,y) "/" x "∈" A, y "∈" B}`
Si les ensembles `A` et `B` sont finis, nous avons :
`|A"×"B|` = `|A| |B|`
Si on effectue le produit avec le même ensemble `A` on écrira le résultat à l'aide d'une puissance.
`A^2 = A"×"A` `|A^2| = |A|^2`
Et pour les puissances plus grandes, l'expression `A^n` désigne l'ensemble des `n`-uplets d'éléments de `A`.
`A^n = A"×"A"×"A"×"... n "fois" ...` `|A^n| = |A|^n`
Règles de grammaire :
L'expression « un élément de `A` » signifie un élément appartenant à `A`. Et la notion d'élément n'impose aucune restriction, elle constitue le genre le plus générale possible d'élément. Il n'en est pas tout a fait de même pour un couple, car un couple dans l'absolu ne constitue pas un genre d'élément. La définition du genre « couple » doit être faite préalablement et doit être portée par le contexte, pour pouvoir l'utiliser seul comme un genre. Alors dans ces conditions, la signification de couple sans autre précision est définie par le contexte, et la même syntaxe est mise en oeuvre, faisant que l'expression « un couple de `A` » signifit un élément qui est de genre couple et qui appartenant à `A`.
Puis il est possible de spécifier une condition sur les composantes du couple. Ainsi, l'expression « un couple d'éléments de `A`» désignera un élément de `A"×"A`. Et si les éléments de `A`s'appellent des bidules et qu'il n'y en a pas d'autre ailleurs, faisant que le genre bidules coïncide avec l'ensemble `A`, l'expression « un couple de bidules » désignera un élément de `A"×"A`. L'ambiguité ne se produit pas car la syntaxe distingue toujours les nom d'ensemble des noms de genre. Par exemple on évoquera le genre des entiers et l'ensemble `NN`, le genre des réels et l'ensemble `RR`, etc..
Ainsi, lorsqu'est prédéfinie un genre d'élément appelé « couple », alors l'expression « un couple de X » a un sens différent selon que X est un ensemble ou un genre d'élément. Si c'est un ensemble, cela signifie que l'on désigne un élément qui est de genre couple et qui appartient à X. Si c'est un genre d'élément, cela signifie un couple d'éléments de ce genre.
Par exemples : Le terme `(2,5)` est un couple d'entiers, et c'est aussi un couple de `NN^2`. Le terme `"("(1,2),(3,4)")"` est un couple de couples d'entiers, ou un couple de couples de `NN^2`.
S'il nous faut définir la multiplication sur les entiers `f(a,b)=ab` à partir de la seul addition, on peut le faire de deux façons différentes, soit par récurrence :
`f(a"+"1,b)=f(a,b)+b` `f(0,b)=0`
ou soit par itération :
`f(a,b)=sum_(a=1)^a b`
Cela correspond à 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 la décomposition des entiers en une liste de chiffres selon une base donnée et qui partage le travail et les résultats intermédiaires évitant ainsi d'avoir à les recalculer plusieurs fois.
Le même raisonnement peut être fait à partir des ensembles `A` et `B` et à partir du procédé de construction des couples `A"×"B`.
On dévoile la programmation de l'énumération de `A"×"B` :
`A"×"B = {(x,y) "/" x "∈" A, y "∈" B}` `A"×"B = sum_(x in A) {(x,y) "/" y "∈" B}` `A"×"B = sum_(x in A) sum_(y in B) {(x,y)}` `|A"×"B| = sum_(x in A) sum_(y in B) |{(x,y)}|` `|A"×"B| = sum_(x in A) sum_(y in B) 1` `|A"×"B| = sum_(x in A) b` `|A"×"B| = ab`
On note :
`a = |A|` `b= |B|` `f(a,b) = |A"×"B|`
`f(a,b)` désigne le nombre de couples composés d'un élément d'un ensemble de cardinalité `a` et d'un élément d'un ensemble de cardinalité `b`.
En bref : Si on ajoute un nouvel élément `e`, les couples de `(A"+"{e})"×"B` comprennent les couples ne contenant pas `e`, c'est à dire les couples de `A"×"B`, et comprennent les couples contenant `e`, c'est à dire les couples de `{e}"×"B`. Cela se traduit par la relation de récurrence suivante : `f(a"+"1,b) = f(a,b)+b`
On dévoile la relation de récurrence sur les ensembles :
`(A"+"{e})"×"B = A"×"B + {e}"×"B` `|(A"+"{e})"×"B| = |A"×"B| + |B|` `f(a"+"1,b) = f(a,b) + b` `{}"×"B = {}` `|{}"×"B| = |{}|` `f(0,b) = 0`
Conclusion :
`f(a"+"1,b) = f(a,b) + b` `f(0,b) = 0`
Vous pourrez vérifier que cela définit bien le produit `f(a,b) = ab`
D'une manière générale, la distributivité de `**` par rapport à `+` au niveau des entiers se retrouve au niveau des ensembles en la distributivité de `×` par rapport à `+` où le `"+"` désigne l'union disjointe. Nous avons par exemple :
`(A"+"B)"×"C = A"×"C+B"×"C`
Et on accorde une priorité syntaxique au produit d'ensemble `×` plus forte que celle qu'on accorde à la somme disjointe `+`.
Soit un ensemble `E`, on note `ccP(E)` l'ensemble des parties de `E`. Et on note `E "→" {0,1}` l'ensemble des applications de `E` vers `{0,1}`. Si `E` est un ensemble de `n` éléments alors nous avons :
`|E|=n` `|ccP(E)| = |E"→"{0,1}| = 2^n`
On note `ccP_k(E)` l'ensemble des parties de cardinalité `k`. Le nombre de parties de `k` éléments d'un ensemble de `n` éléments correspond au coefficient binomial :
`|E|=n` `|ccP_k(E)| = ((n),(k)) = (n!)/(k!(n-k)!)`
On note `ccP_(<=k)(E)` l'ensemble des parties de cardinalité au plus égale à `k`. Donc d'après les égalités précédentes nous avons :
`|E|=n` `|ccP_(<=k)(E)| = sum_(k=0)^k |ccP_k(E)| = sum_(k=0)^k ((n),(k))`
Notez que par convention d'écriture, les opérateurs de somme possédant une déclaration de variables peuvent déclarer des variables déjà présentes dans le contexte parent, ce qui occasionne un masquage de celles-ci, non pas dans leur déclaration, mais dans le corps de la somme. Ainsi dans l'exemple, la somme déclare une variable `k` qui varie de `0` à `k`. La deuxième variable `k` fait donc référence à un contexte parent. Puis dans la somme, cette variable parente est masquée par la nouvelle variable `k` qui vient d'être définie par la somme, et qui joue le rôle d'index.
Règles de grammaire :
Même remarque qu'avec la notion de couple, il n'existe pas dans l'absolu de notion générale d'ensemble. Si celle-ci doit être employée, elle doit alors être préalablement définie et portée par le contexte. Dans ce cas, l'expression « une partie de `E` » est ambiguë, désignant soit un sous-ensemble de `E, ou soit un élément de `E` qui a le genre ensemble tel que défini par le contexte. Pour remédier à cela, on pose une priorité syntaxique. La règle est la suivante : Quant les deux sens portées par la particule « de » sont possibles ; le sens d'appartenance directe « une partie appartenant à `E` » et le sens complètant le genre partie « une partie de `E` », alors c'est le sens complètant le genre qui est prioriraire.
Ainsi, on dira « l'ensemble de parties, `E` » pour désigner `E` en rappelant que c'est un ensemble de parties, et on dira « l'ensemble des parties de `E` » pour désigne `ccP(E)`.
La fonction caractéristique d'un sous-ensemble `A` de `E` est par définition une application `f` de `E"→"{0,1}` vérifiant :
`AA x "∈" E, ((x "∈" A <=>f(x)"="1),(x "∉" A <=> f(x)"="0))`
Pour chaque ensemble `A` inclus dans `E`, il y a une et une seul application de `E` vers `{0,1}` qui soit une fonction caractéristique de `A`. Pour chaque application `f` de `E` vers `{0,1}`, il y a un et un seul ensemble caractérisé `A={x "/" f(x)"="1}` qui est inclus dans `E`. Donc il existe bien une bijection canonique entre l'ensemble des parties de `E` noté `ccP(E)` et l'ensemble des aplications de `E"→"{0,1}`.
Notez qu'en notation ensembliste, `2` représente l'ensemble `{0,1}`, et `2^E` représente l'ensemble `ccP(E)` et représente également l'ensemble `E"→"{0,1}` .
S'il nous faut définir l'élèvation de `2` à une puissance entière `f(n)=2^n` à partir de l'addition et de la multiplication, on peut le faire de deux façons différentes, soit par réccurence :
`f(n"+"1)=2f(n)` `f(0)=1`
ou soit par itération :
`f(n)=prod_(n=1)^n 2`
Cela correspond à 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 en produit pour partager le travail et qui permet ainsi de partager les résultats intermédiaires évitant ainsi d'avoir à les recalculer plusieurs fois.
Le même raisonnement peut être fait à partir de l'ensembles `E` et à partir du procédé de construction de l'ensemble des parties `ccP(E)`. Dans un premier temps on ne s'intéressera qu'à la programmation récurvive qui ne nécessite pas de développer un langage de programmation très riche. On note :
`n = |E|` `f(n) = |ccP(E)|`
`f(n)` désigne le nombre de parties d'un ensemble de `n` éléments.
En bref : Si nous ajoutons un nouvel élément `e`, l'ensemble des parties de `E"+"{e}` comprend les parties ne contenant pas `e`, c'est à dire les parties de `E`, et comprend les parties comprenant `e`, c'est à dire les parties de `E` chacune complétée avec l'élément `e`. Cela se traduit par la relation de récurrence suivante : `f(n"+"1) = f(n)+f(n)`
On dévoile la relation de récurrence sur les ensembles :
`ccP(E"+"{e}) = ccP(E) + {F "+" {e} "/" F "∈" ccP(E)}` `ccP(E"+"{e}) = ccP(E) + sum_(F in ccP(E)) {F"+" {e}}` `|ccP(E"+"{e})| = |ccP(E)| + sum_(F in ccP(E)) 1` `|ccP(E"+"{e})| = |ccP(E)| + |ccP(E)|` `f(n"+"1) = f(n) + f(n)` `f(n"+"1) = 2f(n)` `ccP({ }) = {{ }}` `|ccP({ })| = 1` `f(0) = 1`
Conclusion :
`f(n"+"1) = 2f(n)` `f(0) = 1`
Vous pourrez vérifier que cela définit bien l'élévation à la puissance `f(n) = 2^n`
On note :
`n = |E|` `f(n,k) = |ccP_k(E)|`
`f(n,k)` désigne le nombre de parties de `k` éléments d'un ensemble de `n` éléments.
En bref : Si nous ajoutons un nouvel élément `e`, l'ensemble des parties de `E"+"{e}` de `k` éléments comprent les parties ne contenant pas `e`, c'est à dire les parties de `E` de `k` éléments, et comprent les parties contenant `e`, c'est à dire les parties de `E` de `k"-"1` éléments, chacune complétée avec l'élément `e`. Cela se traduit par la relation de récurrence suivante : `f(n"+"1,k) = f(n,k) + f(n,k"-"1)`
On dévoile la relation de récurrence sur les ensembles :
`ccP_k(E"+"{e}) = ccP_k(E) + {F "+" {e} "/" F "∈" ccP_(k"-"1)(E)}` `ccP_k(E"+"{e}) = ccP_k(E) + sum_( F in ccP_(k"-"1)(E)) {F "+" {e}}` `|ccP_k(E"+"{e})| = |ccP_k(E)| + sum_( F in ccP_(k"-"1)(E)) 1` `|ccP_k(E"+"{e})| = |ccP_k(E)| + |ccP_(k"-"1)(E)|` `f(n"+"1,k) = f(n,k) + f(n,k"-"1)` `ccP_0(E) = {Ø}` `|ccP_0(E)| = |{Ø}|` `f(n,0)=1` `ccP_n(E) = {E}` `|ccP_n(E)| = |{E}|` `f(n,n)=1`
Conclusion :
`f(n"+"1,k) = f(n,k) + f(n,k"-"1)` `f(n,0)=1` `f(n,n)=1`
Cela correspond à la formule de Pascal pour calculer le coefficient binomial. `f(n,k) =((n),(k))`
Notez que sa forme récurcive représentée par la formule de Pascal est de complexité plus faible que sa forme itérative habituelle. Définir une fonction par des règles de récurrences permettant de la calculer est aussi pertinent que de définir la fonction par un calcul itératif. C'est pourquoi on se satisfait de ce résultat.
On note :
`n = |E|` `f(n,k) = |ccP_(<=k)(E)|`
`f(n,k)` désigne le nombre de parties d'au plus `k` éléments d'un ensemble de `n` éléments.
En bref : Si nous ajoutons un nouvel élément `e`, l'ensemble des parties de `E"+"{e}` d'au plus `k` éléments comprend les parties ne contenant pas `e`, c'est à dire les parties de `E` d'au plus `k` éléments, et comprend les parties contenant `e`, c'est à dire les parties de `E` d'au plus `k-1` éléments chacune complétée avec l'élément `e`. Cela se traduit par la relation de récurrence suivante : `f(n"+"1,k) = f(n,k) + f(n,k"-"1)`
On dévoile la relation de récurrence sur les ensembles :
`ccP_(<=k)(E"+"{e}) = ccP_(<=k)(E) + {F "+" {e}" / " F "∈" ccP_(<=k"-"1)(E)}` `ccP_(<=k)(E"+"{e}) = ccP_(<=k)(E) + sum_(F in ccP_(<=k"-"1)(E)){F "+" {e}}` `|ccP_(<=k)(E"+"{e})| = |ccP_(<=k)(E)| + |ccP_(<=k"-"1)(E)|` `f(n"+"1,k) = f(n,k) + f(n,k"-"1)` `ccP_(<=0)(E) = ccP_0(E) = {Ø}` `|ccP_(<=0)(E)| = |{Ø}|` `f(n,0)=1` `ccP_(<=n)(E) = ccP(E)` `|ccP_(<=n)(E)| = |ccP(E)|` `f(n,n)=2^n`
Conclusion :
`f(n"+"1,k) = f(n,k) + f(n,k"-"1)` `f(n,0)=1` `f(n,n)=2^n`
Vous pourrez vérifier que cela définit bien `f(n,k) =k!((n),(k))= (n!)/((n-k)!)`
La construction de listes d'ensembles peut se programmer itérativement. Par exemple voici une liste `bbbU_k` de `k` nouveaux ensembles :
`bbbU_k = (A_k)_(k=1)^k = (A_1,A_2,...,A_k)`
De même pour les sacs d'ensembles, voici un sac `bbbS_k` de `k` nouveaux ensembles :
`bbbS_k = "⦃"A_k"⦄"_(k=1)^k = bbbS_k = "⦃"A_1,A_2,...,A_k"⦄"`
La différence entre le sac et la liste est que dans un sac, l'ordre n'a pas d'importance. De même pour les ensembles d'ensembles, voici un ensemble `bbbF_k` de `k` nouveaux ensembles :
`bbbF_k = {A_k}_(k=1)^k = bbbF_k = {A_1,A_2,...,A_k}`
Notez alors que l'énumération étant entre accolades `{}`, cela signifie en plus que :
`AAiAAj, i"="j <=> A_i"="A_j`
L'union d'ensembles peut se répéter à l'aide de l'itérateur `uuu`. Ainsi par exemple :
`uuu_(E in bbbF_k)E = uuu_(k=1)^k {A_k} = A_1uuA_2uuA_3uu ... uuA_k`
L'union disjointe d'ensembles peut se répéter à l'aide de l'itérateur `sum`. Ainsi par exemple :
`sum_(E in bbbF_k)E = sum_(k=1)^k {A_k} = A_1+A_2+A_3+ ... +A_k`
Notez alors que cette expression affirme également que les ensembles `A_1, A_2, A_3, ..., A_k` sont disjoints, ce qui se note :
`AA i AA j, i"≠"j => A_i "⋂" A_j"="{}`
Le produit d'ensembles peut s'itérer et forme alors un produit présidée par l'itérateur `prod`. Ainsi par exemple :
`prod_(E in bbbF_k)E = prod_(k=1)^k A_k = A_1"×"A_2"×"..."×"A_k` .
Etant donné un ensemble `E` de `n` éléments. Un partitionnement est une subdivision de l'ensemble `E` en `k` parties non vides, disjointes deux à deux, et dont la somme est égale à `E`. Le nombre de parties `k` est donc compris entre `0` et `|E|`. Un partitionnement est constitué de l'ensemble de ces `k` parties. Considérons l'exemple générale de partitionnement suivant :
`{A_i}_(i=1)^k`
La sommes disjointes des parties doit être égale à `E` :
`sum_(i=1)^k A_i = E`
Noter que la somme ` sum` désigne l'union disjointe, et donc signifie que les ensembles `(A_i)_(i=1)^k` sont deux à deux disjoints. Puis dans une partition, il ne doit pas y avoir de partie vide :
`AAi "∈" {1..k} A_i"≠"Ø`
L'ensemble de tous les partitionnements possibles de `E` se note `bbbP(E)` :
`bbbP(E) = {{A_i}_(i=1)^k" / " k "∈"{0..|E|}, AAi "∈" {1..k} A_i"≠"Ø, sum_(i=1)^k A_i = E }`
L'ensemble de tous les partitionnements en `k` parties de `E` se note `bbbP_k(E)`
`bbbP_k(E) = {{A_i}_(i=1)^k" / " AAi "∈" {1..k} A_i"≠"Ø, sum_(i=1)^k A_i = E }`
Le nombre de Stirling de seconde espèce `S(n,k)` correspond au nombre de partitionnements possibles en `k` parties d'un ensemble de `n` élements.
`S(n,k) = |bbbP_k({1..n})|`
Un ensemble d'ensembles s'appel une famille (ou de façon redondante une famille d'ensembles). Les éléments d'une famille sont donc des ensembles et s'appellent les membres de la famille.
Un ensemble de familles s'appel une clique (ou de façon redondante une clique de familles). Les éléments d'une clique sont donc des familles et s'appellent les composantes de la clique.
Considérons une famille d'ensembles quelconques telle que par exemple `bbbF = {A,B,C}`, et considérons un élément quelconque `e` n'appartenant à aucun membre de cette famille.
Pour désigner la famille d'ensembles obtenue en ajoutant à chacun de ses membres l'élément `e`, on procède par une définition d'ensemble utilisant une variable `X` qui va parcourir tous les membres de la famille :
`{A"+"{e},B"+"{e},C"+"{e}} = {X"+"{e}" / "X"∈" bbbF}`
Cette expression peut être mis sous forme itérative :
`{A"+"{e},B"+"{e},C"+"{e}} = sum_(X in bbbF){X"+"{e}}`
Pour désigner la clique de toutes les familles d'ensembles que l'on peut obtenir en ajoutant l'élément `e` à un seul membre de la famille `bbbF` à la fois, on procède par une définition d'ensemble utilisant une variable `X` qui va parcourir tous les membres de la famille :
`{{A"+"{e},B,C},{A,B"+"{e},C},{A,B,C"+"{e}}} = {bbbF-{X}+{X"+"{e}}" / "X "∈" bbbF}`
Cette expression peut être mis sous forme itérative :
`{{A"+"{e},B,C},{A,B"+"{e},C},{A,B,C"+"{e}}} = sum_(X in bbbF){bbbF-{X}+{X"+"{e}}}`
On rappel que dans un partitionnement, les parties considérées ne doivent pas être vides, doivent être disjointes deux à deux, et leur union doit être égale à l'ensemble partitionné.
On note :
`n = |E|` `S(n,k) = |bbbP_k(E)|`
`S(n,k)` désigne le nombre de partitionnements en `k` parties d'un ensemble de `n` éléments. Il est appellé nombre de Stirling de seconde espèce.
On pose `n>=1`.
En bref : Si nous ajoutons un nouvel élément `e`, l'ensemble des partionnements de `E"+"{e}` en `k` parties comprend les partitionnements où `e` est dans une partie singleton `{e}` et comprend les partitionnements où `e` n'est pas dans une partie singleton. Autrement dit, l'ensemble des partionnements de `E"+"{e}` en `k` parties comprend les partitionnements de `E` en `k"-"1` parties dans lesquels on ajoute la partie singleton `{e}`, et comprend les partitionnements de `E` en `k` parties dans lesquels on ajoute l'élément `e` dans une quelconque des `k` parties, et il y a exactement `k` façons distinctes d'ajouter cet élément. Cela se traduit par la relation de récurrence suivante :
`S(n"+"1,k) = S(n,k"-"1) + kS(n,k)`
On dévoile la relation de récurrence sur les ensembles :
| `bbbP_k(E"+"{e}) = {bbbF"+"{{e}}" / "bbbF "∈" bbbP_(k"-"1)(E)} + {bbbF-{X}+{X"+"{e}}}" / "X"∈" bbbF, bbbF "∈" bbbP_k(E)}` |
| `bbbP_k(E"+"{e}) = sum_(bbbF in bbbP_(k"-"1)(E)) {bbbF"+"{{e}}} + sum_(bbbF in bbbP_k(E)) {bbbF-{X}+{X"+"{e}}" / "X"∈" bbbF}` |
| `bbbP_k(E"+"{e}) = sum_(bbbF in bbbP_(k"-"1)(E)) {bbbF"+"{{e}}} + sum_(bbbF in bbbP_k(E)) sum_(X"∈" bbbF){bbbF-{X}+{X"+"{e}}}` |
| `|bbbP_k(E"+"{e})| = |bbbP_(k"-"1)(E)| + |bbbP_k(E)||bbbF|` |
| `S(n"+"1,k) = S(n,k"-"1) + kS(n,k)` |
| `bbbP_0(E) = Ø` |
| `|bbbP_0(E)| = |Ø|` |
| `S(n,0)=0` |
| `bbbP_n(Ø) = Ø` |
| `|bbbP_n(Ø)| = |Ø|` |
| `S(0,n)=0` |
| `bbbP_0(Ø) = {Ø}` |
| `|bbbP_0(Ø)| = |{Ø}|` |
| `S(0,0)=1` |
Conclusion :
`S(n"+"1,k) = S(n,k"-"1) + kS(n,k)` `S(n,0)=0` `S(0,n)=0` `S(0,0)=1`
Notez que `n>=1`
Cela définit le nombre de Stirling de seconde espèce `S(n,k)`
On calcul le nombre de partitionnement ordonnées en `k` partie ordonnées de `s` éléments, en les énumérants. Le premier élément de la première partition est choisie dans `E`, il y a donc `n` choix possibles. Le second élément est choisie parmi les éléments restant, il y a donc `n"-"1` choix possibles. Et ainsi de suite, faisant que le nombre de premières partitions ordonnées possibles est :
`n(n-1)(n-2)...(n-s+1)`
Si on ne tient pas compte de l'ordre dans la partition, alors le nombre de premières partitions possibles est :
`(n(n-1)(n-2)...(n-s+1))/(s!)`
Et pour la deuxième partition, ce nombre est :
`((n-s)(n-s-1)...(n-2s+1))/(s!)`
Et ainsi de suite, faisant que le nombre de partitionnement ordonnées possibles est :
`(n!)/((s!)^k)`
Et donc que le nombre de partitionnement possibles est :
`bbbP_k^s(E)=(n!)/(k! (s!)^k) `
A condition bien entendu que `n"="ks`