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

Element

aussi bien qu'une suite infinie d'éléments telle que `(e_0, e_1, e_2,..., e_n...)`. Néanmoins une telle suite doit être calculable, c'est à dire produite par un programme de taille finie.

Et nous rappellons que l'ensemble des suites calculables est également énumérable comme le sont les programmes de taille finie qui les produisent. Pour le démontrer il y a une petite subtilité. Il faut mettre en oeuvre un algorithme de minimalisation ce qui nécessite une mémoire de taille non bornée. On commence par énumérer les programmes au travers un processus parallèle qui nous permet de faire progressivement en même temps une autre tâche qui consiste à éxecuter ces programmes jusqu'à ce que le début des suites qu'ils produisent diffère des autres suites déjà retournées, et la retourne lorsque cela se produit. Notez qu'on ne retourne pas la suite proprement dite mais le programme qui l'énumère. Ainsi l'algorithme énumère des programmes de taille fini qui produisent des suites distinctes. Et toutes les suites calculables sont ainsi couvertes.

Ces programmes peuvent énumérer une suite finie d'éléments telle que `(e_0, e_1, e_2,..., e_n)`

Notez alors que ccccc

2) Ensemble

"Dans un monde élémentarien on ne conçoit que des éléments calculables,
et on ne conçoit que des ensembles énumérables ou de complément énumérable."

Un ensemble est une énumération d'éléments, ou bien le complément d'une énumération d'éléments, dans laquelle on fait abstraction de l'ordre d'énumération, et dans laquelle les éléments énumérés sont tous distincts.

D'un point de vue élémentarien, chaque élément doit être calculable, c'est à dire doit être produit en un temp fini par un programme qui, exprimé dans un langage de programmation, doit être de taille finie mais qui peut utiliser pour son éxecution une taille mémoire non bornée.

Une suite est énumérable si et seulement si pour chaque entier `n`, la suite des `n` premiers éléments doit être calculable ce qui signifie qu'elle doit être produite en un temp fini par un programme de taille finie.

On note entre accolades `{...}` les éléments d'un ensemble sachant qu'ils sont nécessairement distincts.

Chaque ensemble possède un cardinal parmi `0,1,2,3...` ou `card(NN)`. Sont ainsi exclus les infinis autre que `card(NN)` notée simplement `oo`.

Soit un ensemble `E`, on note son cardinal `|E|`.

`|E| in NNuu{oo}`

Notez que l'ensemble vide `Ø = { }` constitue un élément particulier.

3) Produit directe d'ensembles

 

Et pour les puissances `n` supérieurs, `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`

Et pour la puissances `oo`, l'ensemble `A^oo` désigne l'ensemble des suites infinies calculables d'éléments de `A`.

`A^oo = A×A×A×... `
`|A^oo| = oo` si et seulement si `|A|>1`

 

 

2.1) Suites finies d'ensembles

Etant donné une suite calculable d'ensembles `(A_0, A_1, A_2,..., A_n...)`. Le produit fini de ces ensembles dans cet ordre désigne l'ensemble des suites finies telle que le `n`-ième élément de la suite, s'il existe, appartient à `A_n`. Ce produit fini se note comme suit :

`A_0×A_1×A_2×... " fini"`

Si on effectue le produit fini avec le même ensemble `A` alors on le note en utilisant l'opérateur de Kleene  :

`A"*"`

`x inA"*"` signifie que `x` est une suite finie d'éléments de `A`. Notez que `x` peut être égal à la suite vide `( )`.

2.2) Suites infinies d'ensembles

Etant donné une suite calculable d'ensembles `(A_0, A_1, A_2,..., A_n...)`. Le produit infini de ces ensembles dans cet ordre désigne l'ensemble des suites calculables telles que le n-ième élément de la suite appartient à `A_n`. On le note comme suit :

`prod_(i in NN) A_i `

Si on effectue le produit avec le même ensemble `A` alors on le note comme suit :

`A^oo`

Un élément `a` est dit être un caractère constant d'une suite infinie d'ensemble si et seulement si il apparait membre d'une infinité d'ensemble de la suite.

2.1) Suites finies de relations

De même qu'avec les ensembles il est possible de concevoir des compositions infinis. Etant donné une suite calculable de relations `R_0, R_1, R_2,..., R_n...`.

Le produit fini de ces relations dans cet ordre désigne la relation reliant `a` à `b` si et seulement s'il existe un chemin allant de `a` à `b` composé d'une suite finie d'arêtes adjacentes appartenant dans l'ordre aux `R_i`. On écrit cette relation comme suit :

En notation droite : `A_0A_1A_2...fi\ni`
En notation gauche : `fi\ni...A_2@A_1@A_0`

Si on effectue le produit fini avec la même relation `R` alors on le note en utilisant l'opérateur de Kleene  :

`R"*"`

`aR"*"b` signifie qu'il existe un chemin partant de `a` et arrivant en `b`, formé d'un nombre d'arêtes fini appartenant à `R` et qui sont deux à deux adjacentes. Notez que le chemin en question peut être vide et que dans ce cas il part d'un point initial pour finir au mêm point initial. Donc nous avons pour toute relation `R` et pour tout élément `a` la propriété `aR"*"a`.

Le contexte devra lever l'ambiguité, ici à savoir, qu'il ne sagit pas du produit d'ensemble `R×R` mais de la composition de relations `R\R`.

 

 

 

Dénombrement des arbres, des graphes (multi-ensemble)

Tout groupe est le groupe d'automorphisme d'un graphe

 

 

 

Langage régulier (succession, réunion, intercection)