Les théories mathématiques

 

1) Introduction

Qu'est-ce qu'une théorie mathématique ? C'est en voulant répondre à cette question que l'on va décrire les règles du raisonnement, en partant de son aspect purement mécanique. Et à bien y regarder, il s'agit plus précisement d'une mécanique classique.

Les mathématiques sont un jeu de construction, un jeu de légo, où chaque pièce s'encastre exactement dans un édifice servant de démonstration. Rien ne relève du mystère, tout est trivial..., c'est l'aspect exacte de la science. Le démonstrateur n'est finalement qu'une machine, une machine idéale, composée de rouages parfaitement emboités et sans aucun jeu. Ces machines sont décrites à l'aide du langage formel.

Les règles du raisonnement se fondent sur le langage formel et sur son aspect purement calculatoire.

Le processus de démonstration s'inscrit dans un processus plus général de construction. Ainsi une démonstration est une construction n'utilisant que des règles de raisonnement que nous allons décrire.

La logique est la science du raisonnement exacte. Et on ne peut concevoir de raisonnement exacte sans langage exacte ni règles de démonstration exactes.

Le langage exacte est le langage des propositions. L'ensemble des règles de démonstration exactes s'appelle le système de démonstration. La conclusion d'une démonstration sans hypothèse s'appelle une tautologie.

Il existe un processus de construction de toutes les propositions. Autrement dit, il existe une machine qui énumère toutes les propositions dans le langage en question. Et de même, il existe un processus de construction de toutes les démonstrations. Autrement dit, il existe une machine qui énumère toutes les démonstrations faisables dans le langage en question. Et comme l'extraction de la conclusion d'une démonstration se fait également par un procédé trivial, il existe donc une machine qui énumère toutes les tautologies.

Pour résumer nous dirons que le langage des tautologies, qui est inclus dans le langage des propositions, est engendré mécaniquement par le système de démonstration.

L'élémentarisme se construit à partir du fait essentiel que quelque soit le langage des propositions choisi et quelque soit l'ensemble des règles de démonstration choisi, du moment qu'ils sont tous deux énumérables, l'ensemble des tautologies est énumérable.

Nous allons construire petit à petit, et en parallèle, le langage des propositions et le système de démonstration en ajoutant un à un les connecteurs, et une à une les règles de démonstration en s'assurant à chaque fois qu'elles sont toutes nécessaires c'est à dire qu'elles forment une axiomatique, et qu'elles sont suffisantes c'est à dire qu'elles démontrent toutes les propositions vrais selon une sémantique définie.

Le symbole de départ que nous utiliserons, et qui constitura un méta-connecteur, est la relation binaire de démontrabilité `"⊢"`. Elle est définie dans le langage des propositions. Et elle se détermine mécaniquement par le système de démonstration.

A ce stade, même si on utilise un vocabulaire propre à la logique, la matière étudiée n'est pas encore celle de la logique mais plutôt celle des langages. Car il manque des éléments essentiels que sont les valeurs de vérité vrai et faux transcrite en deux propositions, la tautologie `"⊤"` et l'antilogie `"⊥"` , et il manque ce qu'est la négation, une symétrie qui permet de passer de l'une à l'autre c'est à dire la capacité expressive totale de dire « non ».

2) Langage

On commence par le langage des propositions, un langage logique dit d'ordre zéro car il ne contient pas de variable élémentaire, juste des variables booléennes c'est à dire des mémoires contenant une valeur `0` ou `1`. Une proposition est donc une équation booléenne.

Par convention la valeur booléenne `0` est définie comme étant la valeur de vérité faux et la valeur booléenne `1` comme étant la valeur de vérité vrai.

On construit le langage des propositions petit à petit, par l'ajout de connecteur logique. Un connecteur logique d'arité `n` est une application de `{0,1}^n"→"{0,1}`. Voici des exemples de connecteurs logique : `"⊤"`, `"⊥"`, `"¬(.)"`, `"⇒(.,.)"`, `"⇔(.,.)"`, et`"(.,.)"`, ou`"(.,.)"`. Si on se limite à l'arité `0`, `1` ou `2`, il y a exactement `2+2^2+2^(2^2)` `=` `22` connecteurs logiques distincts.

Le suffixe `"(.)"` apposé à un connecteur, est utilisé pour rappeler que le connecteur est unaire, c'est à dire qu'il prend `1` argument. Le suffixe `"(.,.)"` apposé à un connecteur, est utilisé pour rappeler que le connecteur est binaire, c'est à dire qu'il prend `2` arguments. S'il n'y a pas de suffixe, cela signifie que le connecteur est d'arité nulle c'est à dire qu'il constitue une valeur booléenne inconnue (identique à une variable booléenne).

Si on s'intéresse à la valeur de vérité d'une proposition non pas dans un monde particulier mais dans l'univers, alors la proposition si elle n'est pas tautologique ne peut pas se résumer en une valeur booléenne, elle se définie en soi comme une expression du langage des propositions `ccL`. Tout se passe comme si les connecteurs prennaient leurs arguments parmi `ccL`.

Le langage `ccL` est l'ensemble des termes clos par composition de connecteurs à partir des connecteurs générateurs du langage. C'est pourquoi il s'appelle langage de connecteurs. Et il constitue l'ensembles des propositions, c'est pourquoi il s'appelle aussi langage des propositions.

Une théorie est une proposition. Et il n'y a pas de différence entre théorie et proposition. Elles doivent appartenir au langage des propositions, et donc en particulier être de taille finie, être concrètement écrivables.

3) Méta-langage

Pour étudier les théories, il faut être en dehors de celles-ci, en dehors de leur langage propre. Pour cela on utilise un autre langage que celui des théories étudiées, un langage mathématique que l'on formalise sous l'appellation de méta-langage. Le système de démonstration, qui constitue en quelque sorte le pilote de toutes les théories, est écrit dans ce méta-langage. Et ce méta-langage va englober le langage initial.

Le méta-langage est une extension du langage par l'ajout de trois méta-connecteurs `"⊢(.)","⊢(.,.)","⊢(.,.,.)"`, d'arité respective `1`, `2` et `3`. Le méta-langage est l'ensemble des termes clos par composition de connecteurs et méta-connecteurs à partir des connecteurs générateurs du langage et des méta-connecteurs générateurs du méta-langage. C'est pourquoi il s'appelle langage de connecteurs et méta-connecteurs. Et il constitue l'ensembles des règles exprimables, c'est pourquoi il s'appelle aussi langage des règles. Néanmoins on ne s'interessera qu'à un genre simple de règle composée d'une seul occurence de méta-connecteur. Le méta-connecteur traduira la production mécanique d'une déduction.

Le méta-langage est aussi un langage de propositions un peu plus générales appelées méta-propositions, c'est pourquoi il s'appelle aussi langage des méta-propositions.

L'univers associé aux méta-propositions et le même que celui associé aux propositions, les méta-connecteurs étant des fonctions déterminées par l'ensemble des règles de déductions choisies `ccD`.

Le cadre pour définir les théories est d'abord posé en choisissant un langage de connecteurs `ccL` et un ensemble de règles de déduction `ccD`. Le système de démonstration `ccD` définie mécaniquement les relations de démontrabilité `"⊢(.)","⊢(.,.)","⊢(.,.,.)"`, dans l'ensemble `ccL`. Le système de démonstration peut être vu comme associé à un moteur qui constitue son aspect dynamique. Le moteur est un programme informatique capable d'énumérer toutes les déductions possibles à partir soit d'aucune hypothèse ou soit d'une proposition appartenant à `ccL` , ou soit de deux propositions appartenant à `ccL`, et de l'ensemble des règles de déductions appartenant à `ccD`.

On pose un langage de connecteurs `ccL` et une méta-théorie `ccD` toutes deux vides au départ. Et on se propose d'ajouter les éléments de construction du langage et de construction des démonstrations petit à petit selon un ordre, si j'ose dire, presque « naturel ».

4) Application des règles de déduction

On accumule dans un ensemble appelé réserve toutes les propositions que l'on démontre. Une règle de déduction prend comme argument des propositions dans la réserve, et produit une nouvelle proposition que l'on rajoute dans la réserve.

Les règles de déduction se présente comme des fonctions d'arité `0`, `1` ou `2` définie sur `ccL`. Elle ne produisent de résultat que si l'unification de l'entête réussit. Voici par exemple la règle du modus ponens utilisant un méta-connecteur ternaire : `A, (A"⇒"B) |-- B`. Pour appliquer cette règle au couple de propositions suivant `( (X "⇔" Y),  (X"⇔"Y)"⇒"X )`, on procède à l'unification de l'entête, `A = (X"⇔"Y)` et `B = X`, puis on produit le corps de la règle, `B`, en remplaçant les variables muettes par leur valeur d'affectation. Cela produit la proposition `X`.

5) La relation de démontrabilité

Déjà, sans avoir besoin de définir et d'utiliser la négation dans `ccL`, un certain nombre de principes peuvent être révélés. On les qualifiera de pré-logiques.

Par convention, dans une règle de démonstration, toute nouvelle variable est notée en majuscules `A,B,C,...`, et est implicitement quantifiée universellement sur l'ensemble des propositions `ccL`. Ces nouvelles variables représentent donc des propositions appartenant à `ccL`

On constate dans la mise en oeuvre du processus de déduction, que la relation de démontrabilité, `"⊢(.,.)"` , appellée aussi relation de conséquence logique est réflexive et transitive :

Réflexif : `A"⊢"A`
Transitif :     `(A"⊢"B)` et `(B"⊢"C) => (A"⊢"C)`

Ces deux propriétés qui ne font pas intervenir la négation, permettent de définir le préordre logique, puis la relation d'équivalence logique, puis l'ordre logique.

6) La relation d'équivalence

A partir de la relation de démontrabilité `"⊢(.,.)"` on définie sa symétrisée, la relation d'équivalence `"↔(.,.)"` :

`A harr B` si et seulement si `(A|--B)` et `(B|--A)`

La relation `"↔(.,.)"` constitue bien une relation d'équivalence :

Réflexif : `A"↔"A`
Symétrique :    `(A"↔"B) => (B"↔"A)`
Transitive : `(A"↔"B)` et `(B"↔"C) => (A"↔"C)`

La relation `"⊢(.,.)"` constitue un préordre sur `ccL` :

Réflexif : `A"⊢"A`
Transitive :    `(A"⊢"B)` et `(B"⊢"C) => (A"⊢"C)`

Et donc la relation `"⊢(.,.)"` constitue un ordre sur la structure quotient `ccL"/↔"` :

Réflexif : `ccA"⊢"ccA`
Antisymétrique : `(ccA"⊢"ccB)` et `(ccB"⊢"ccA) => (ccA"="ccB)`
Transitive : `(ccA"⊢"ccB)` et `(ccB"⊢"ccC) => (ccA"⊢"ccC)`

`ccA = A ["↔"],  ccB = B  ["↔"],  ccC = C  ["↔"]`, c'est à dire où `ccA, ccB, ccC` sont définis à équivalence près.

L'ordre dont il est question est évidement partiel (non total) dans les cas non triviaux

Dans ces expressions, on considère que les connecteurs `<=>` et `=>` ont une priorité syntaxique inférieure au connecteur et, ce qui nous permet d'omettre un certain nombre de parenthèses sans introduire d'ambiguïté.

On associe à chaque théorie `T` sa cloture `"<"T">"` qui est l'ensemble de toutes les propositions qu'elle peut démontrer. Ainsi `T|--A` qui signifie que `T` démontre `A`, est équivalent à l'appartenance `A in "<"T">"`, et est aussi équivalente à l'inclusion `"<"A">" sub "<"T">"`.

`A ↔ B` si et seulement si `"<"A">=<"B">"`
`A ↔ B` si et seulement si `("<"B">⊂<"A">")` et `("<"A">⊂<"B">")`
`A ↔ B`
si et seulement si `(A"⊢"B)` et `(B"⊢"A)`

Les méta-connecteurs `↔"(.,.)"` et `|--"(.,.)"` sont tous deux des fonctions de `ccL^2"→"{0, 1}`. Et donc la définition du connecteur `↔"(.,.)"` peut se noter par l'égalité suivante :

`A"↔"B  =  (A"⊢"B)` et `(B"⊢"A)`

Dans cette expression, on considère que l'opération `"="` a une priorité syntaxique inférieure aux opérations et, `"↔"`.

L'expression `A"⊢"B` signifie que `A` démontre `B`. L'expression `A"↔"B` signifie que `A` démontre `B` et que `B` démontre `A`. Ces deux méta-connecteurs `"↔"` et `"⊢"` vont nous servir pour définir les règles de démonstrations.

7) Les modèles pré-logiques

Le langage ne se suffit pas à lui-même car sa raison d'être, est justement de désigner autre chose que lui-même. Il y a donc une distinction nécessaire, qu'il faut établir d'emblés, entre le signifiant et le signifié, entre la proposition désignante et la réalité désignée. La proposition désignante fait partie du langage, la réalité désignée fait partie d'un modèle, qui est ici pré-logique puisque la négation n'y est pas encore définie.

Une proposition externe est caractérisée par son nom, `X`, connecteur d'arité zéro qui est ajoutée au langage des propositions, et par ce qu'elle désigne, `X`, qui est une partie d'un modèle, ou qui caractérise un monde qui réalise justement et concrètement ce que désigne cette proposition, `X`. Dans un cas, c'est la syntaxe, le nom `X` qui désigne.... Dans l'autre cas c'est la sémantique, une réalité `X` qui est désignée dans un monde la réalisant.

Ce monde, qui peut réaliser ce que désigne une proposition du langage, s'appelle classiquement un modèle. L'ensemble de tous les mondes possibles s'appel l'univers. Il est dit pré-logique car la négation n'existe pas encore.

La syntaxe préside le langage tandis que la sémantique préside l'univers.

8) Les propositions externes `X,Y,Z,...`

Les premiers éléments de langage que nous incorporons sont des propositions externes, qui sont des connecteurs d'arité zéro (c'est à dire des variables booléennes ayant une valeur dans chaque monde) et que l'on ajoute en nombre fini `X,Y,Z...`, comme une extension élémentaire, à part que ce ne sont pas des éléments mais des propositions que nous ajoutons. Remarquer alors que l'information ne se trouve pas dans leur contenue mais dans leur nom qui étend l'univers.

La proposition externe `X` possède une valeur prés-logique vrai ou faux dans chaque monde de l'univers, et qui peut être librement choisie sur les mondes avant extension puisque la création de cette variable va rajouter un champ des possibles et ainsi augmenter de `1` la dimension de l'univers.

Le nombre `n` de propositions externes rajoutées (dans un langage n'en possèdant aucune) s'appelle la dimension du langage des propositions et s'appelle aussi la dimension de l'univers. A chaque langage de proposition, est associé un univers. Remarquez que le langage des méta-propositions est associés au même univers.

A ce stade, le langage de dimension `3` s'écrit :

`ccL="{"X, Y, Z"}"`

Et la seul règle de démonstration dont nous avons besoin est la règle d'identité :

`ccD={A"⊢"A}`

Rappelons que dans la méta-théorie, toute nouvelle variable est implicitement quantifiée universellement sur `ccL`, c'est à dire qu'elle représente toutes les propositions de `ccL`. Le système de démonstration s'écrit donc explicitement comme suit :

`ccD={AA A"∈"ccL, A"⊢"A}`

Le langage des propositions quotienté par la relation d'équivalence forme une structure, et dans cette structure, les éléments désignent des propositions à équivalence près. Les connecteurs d'arité zéro `X,Y,Z`, qui sont des propositions, peuvent être égaux entre eux c'est à dire équivalent entre eux. Autrement dit, on n'a pas ajouter à la théorie de la structure le fait que ces propositions doivent être distinctes c'est à dire non équivalentes.

Deux propositions seront dites égales si et seulement elles sont équivalentes, c'est à dire si l'une démontre l'autre et que l'autre démontre l'une, et ont utilise pour exprimer cela le méta-connecteur `"=(.,.)"` qui est identique au méta-connecteur `"↔(.,.)"`.

Deux propositions seront dites identiques si et seulement si elles ont même expression dans le langage `ccL`, et ont utilise pour exprimer cela le méta-connecteur `"≡(.,.)"`

9) Le paradigme conjonctif

On considère qu'une théorie est un ensemble fini de petites théories. Pour cela, il nous faut formaliser une opération logique fondamentale que nous n'avons pas encore définie dans notre langage des propositions, qu'est la conjonction et, avec comme principe qu'elle est commutative et associative, faisant qu'une conjonction correspond à un sac non vide, et avec deux autres règles de démonstration : la règle de l'introduction du et, qui affirme que si on a deux propositions dans notre réserve alors cela démontre leur conjonction, et la règle de l'élimination du et, qui affirme qu'une conjonction démontre chaque partie qu'elle contient.

Ce paradigme nous fait rajouter le connecteur et`"(.,.)"` au langage des propositions, ainsi que les règles de raisonnement suivantes au système de démonstration `ccD` :

Commutatif : `A` et `B   |--  B` et `A`
Associatif : `A` et `(B` et `C)   |--  (A` et `B)` et `C`
Elimination : `A` et `B  |--  A`
Introduction : `A,  B  |--  A` et `B`

Ces règles de démonstrations sont dites pré-logiques car elles n'utilisent pas la négation.

Noter que les trois premières règles de déduction sont unaires et correspondent à des meta-connecteurs binaires, et la quatrième règle de déduction est binaire et correspond à un méta-connecteur ternaire.

On considère que les méta-connecteurs `"↔(.,.)"` et `"⊢(.,.)"` et `"⊢(.,.,.)"` ont une priorité syntaxique inférieur au connecteur et`"(.,.)"`.

On remarque que la règle d'identité découle de la règle d'élimination du et. En effet `A` et `A  |--  A` entraine que A"⊢"A

On remarque que l'associativité à droite entraine l'associativité à gauche grace à la commutativité.

On remarque que le système de règles ainsi défini constitue une axiomatique c'est à dire qu'aucune règle ne peut être déduite des autres règles.

On remarque que la propriété d'invariance `A` et `A  |--  A` découle des deux règles, d'élimination et d'introduction du et. Cela a pour conséquence qu'une conjonction correspond à un ensemble et non un sac (multiensemble), et d'autre part il n'est pas possible à ce stade que cet ensemble soit vide.

Par commodité on définie dans un langage plus général, le connecteur d'arité variable non nul `{...}` pour désigner une conjonction. Ainsi étant donnée des propositions quelconques `A,B,C,...` appartenant à `ccL`, nous avons :

`A = {A}`
`A` et `B = {A,B}`
`A` et `B` et `C = {A,B,C}`
...

Notez que dans ces expressions, le méta-connecteur `"=(.,.)"` a une priorité syntaxique inférieur au connecteur et`"(.,.)"`.

Mais on n'ajoute pas ce connecteur d'arité variable non nulle au langage `ccL` afin de rester dans un type de langage de connecteurs d'arité fixe plus apte a possèder des aptitudes calculatoires efficaces qui nous seront utiles par la suite.

Le choix de commencer par introduire ce connecteur et`"(.,.)"` qui est commutatif, associatif, qui démontre les propositions qu'il contient, et qui démontre les conjonctions de propositions déjà démontrés, relève d'une conception accumulative des connaissances désignées sous le nom de paradigme conjonctif.

A ce stade, le langage de dimension 3 devient :

`ccL="<"X,Y,Z,`et`"(.,.)>"`

Les crochets `"< >"` signifient la cloture par composition close, c'est à dire l'ensemble de tous les termes clos constructibles à partir des connecteurs générateurs présentés entre ces crochets.

Et le système de démonstration est  :

`ccD={`
    `A` et `B  |--  B` et `A`
    `A` et `(B` et `C)  |--  (A` et `B)` et `C`
    `A` et `B  |--  A`
    `A,  B  |--  A` et `B`
`}`

Notez que implicitement toute nouvelle variable apparaissant dans la méta-théorie est quantifiée universellement sur le langage `ccL`. Donc il faut entendre que ces règles de démonstrations sont valables quelques soient `A, B, C`, trois propositions quelconques appartenant à `ccL`.

On remarque que l'ensemble `ccL` quotienté par la relation d'équivalence est identifiable à l'ensemble des parties non vides de `E`, avec `E={X,Y,Z}`, ce qui se note :

`ccL"/↔"  ~=  ccP(E)-{Ø}`

Tout langage est le reflet d'une réalité hypothètique désigné sous le nom d'univers. A quoi ressemble donc ici l'univers ? à `ccP(E)-{Ø}`. Autrement dit, un monde est un sous-ensemble non vide de E.

Nous nous intéressons à la recherche d'une axiomatique, c'est à dire à un ensemble de règles génératrices dans lequel aucune ne peut être supprimée sans réduire le pouvoir de démonstration du système. C'est le cas avec ces 4 règles de déduction :

`r_1`
Commutativité du et : `A` et `B  |--  B` et `A`
`r_2`
Asociativité gauche du et : `A` et `(B` et `C)  |--  (A` et `B)` et `C`
`r_3`
Elimination du et : `A` et `B  |--  A`
`r_4`
Introduction du et : `A,  B  |--  A` et `B`

Par exemple voici une démonstration de `(A` et `A)` et `A` à partir de l'hypothèse `A` :

`r_4` : `A, A  |--  A` et `A`
`r_4` : `A` et `A,  A` et `A |--  (A` et `A)` et `(A` et `A)`
`r_2` : `(A` et `A)` et `(A` et `A)  |--  ((A` et `A)` et `A)` et `A`
`r_3` : `((A` et `A)` et `A)` et `A  |--  (A` et `A)` et `A`

La démonstration semble complexe car elle détaille toutes les opérations jusqu'aux plus petites. Démontrer qu'un ensemble est inclus dans un autre peut demander de vérifier que chaque élément du premier ensemble appartient bien au second. Et cette vérification peut constituer un processus trés long qui sera exécuté par un programme. Ce processus constitue la démonstration.

10) Définition du faux et du vrai  `"⊥","⊤"`

Comme nous l'avons précisé en introduction, pour que notre étude soit celle de la logique et non seulement celle des langages, il faut ajouter les valeurs de vérité vrai et faux transcrite en deux propositions que sont la tautologie `"⊤"` et l'antilogie `"⊥"`, et ce qu'est la négation, une symétrie qui permet de passer de l'une à l'autre, c'est à dire la capacité complète de dire « non ».

Il existe un moyen intérieur au langage pour définir de façon absolue, le faux, grâce au concept d'incohérence. Une théorie `T` est dite incohérente si et seulement si `T` démontre tout, `"<"T">"=ccL`. Et donc elle est dite cohérente si et seulement si il existe au moins une proposition `A` que `T` ne peut pas démontrer, `T⊬A`.

On définie le faux comme une proposition incohérente, et on définie le vrai comme une proposition nécessaire.

Ainsi nous avons :

Une proposition sera dite fausse si et seulement si elle démontre tout.
Une proposition sera dite vrai si et seulement si elle est démontrée sans hypothèse.

On définie la proposition `"⊥"` avec comme seul définition d'être fausse c'est à dire telle que quelque soit une proposition `A`, la proposition `"⊥"` démontre la proposition `A`, ce qui se note :

`AA A,  "⊥⊢"A`

On définie la proposition `"⊤"` avec comme seul définition d'être vrai c'est à dire telle que

`"⊢⊤"`

Au stade pré-logique, il existe donc déjà le vrai qu'est la tautologie `"⊤"`, et le faux qu'est l'antilogie `"⊥"`

`AA A,  "⊥⊢"A` `"⊢⊤"`
`"<⊥>"=ccL`   C'est l'ensemble des propositions. `"<⊤>"`   C'est l'ensemble des tautologies.
`AA A,  "<"A">" sub "<⊥>"` `AA A,  "<⊤>" sub "<"A">"`

Le faux `"⊥"` est ainsi défini intérieurement au langage comme étant l'incohérence, et représente la borne supérieure d'un treillis que constitue la relation d'ordre logique. C'est une proposition que l'on ajoute par extension élémentaire au langage `ccL` et en quotientant la structure par `AA A,  "⊥⊢"A`

Le vrai `"⊤"` est ainsi défini intérieurement au langage comme engendrant le nécessaire c'est à dire l'ensemble des tautologies, et représente la borne inférieure du treillis que constitue la relation d'ordre logique. C'est une proposition que l'on ajoute par extension élémentaire au langage `ccL` et en quotientant la structure par `"⊢⊤"`

La proposition tautologie `"⊤"` est démontrée sans hypothèse, et la proposition antilogie `"⊥"` démontre tous les propositions.

Le langage de dimension 3 devient :

`ccL="<⊥", "⊤", X, Y, Z, `et`"(.,.)>"`

Et le système de démonstration est  :

`ccD={`
    `A` et `B  |--  B` et `A`
    `A` et `(B` et `C)  |--  (A` et `B)` et `C`
    `A` et `B  |--  A`
    `A,  B  |--  A` et `B`
    `"⊥⊢"A`
    `"⊢⊤"`
`}`

11) Interaction de `"⊥"` et `"⊤"` avec la conjonction

La tautologie `"⊤"` correspond à l'élément neutre pour le connecteur et.

l'antilogie `"⊥"` correspond à l'élément absorbant pour le connecteur et.

Par commodité on définie dans un langage plus général, le connecteur d'arité variable `{...}` pour désigner une conjonction. Ainsi étant donnée des propositions quelconques `A,B,C,...` appartenant à `ccL`, nous avons :

`"⊤" = Ø`
`A = {A}`
`A` et `B = {A,B}`
`A` et `B` et `C = {A,B,C}`
...

La tautologie correspond à la proposition vide `Ø`, qui constitue la conjonction vide, l'ensemble vide. Et l'antilogie correspond à l'ensemble `{X,Y,Z}`

`"⊤"= Ø`
`"⊥"= {X,Y,Z}`

`Ø` est démontrée par toutes les propositions, et la proposition `{X,Y,Z}` démontre toutes les autres propositions.

On remarque que l'ensemble `ccL` quotienté par la relation d'équivalence est identifiable à l'ensemble des parties de `E`, avec `E={X,Y,Z}`, ce qui se note :

`ccL"/↔"  ~=  ccP(E)`

Tout langage est le reflet d'une réalité hypothètique désigné sous le nom d'univers. A quoi ressemble donc ici l'univers ? à `ccP(E)`. Autrement dit, un monde est un sous-ensemble de `E`.

L'expresssion `"⊢"A` est équivalente à l'expression `Ø"⊢"A`. Et comme la proposition vide correspond à la proposition vrai notée `"⊤"`, l'expression `"⊢"A` correspondra à l'expression `"⊤⊢"A`.

L'ajout du connecteur de négation va engendrer toute la logique propositionnelle car tous les connecteurs booléens peuvent être définis à partir des deux connecteurs booléens `{¬"(.)", `et`"(.,.)"}`. Il est possible néanmoins de choisir une voie plus progressive et de commencer par l'ajout d'un second connecteur qui ne permet pas d'engendrer tous les connecteurs logiques.

12) Les systèmes minimaux de connecteurs

Un système minimal de connecteurs est un ensemble de connecteurs tel qu'aucun d'eux ne peut être calculer par une combinaison des autres. Pour trouver tous les systèmes minimaux de connecteurs, il faut développer un programme informatique qui passe en revue toutes les combinaisons possibles de connecteurs, c'est à dire qui sache énumèrer toutes les compositions closes d'opérateurs qu'il est possible de construire à partir d'opérateurs générateurs d'arité fixe.

Pour concevoir intelligemment ce programme, il convient de chercher en même temps que le programme, le langage de programmation le plus adapté à ce type de programme. C'est pourquoi nous ouvrons au chapitre 13 une discussion informatique.

13) Langage de programmation pour énumérer tous les termes

On pose les bases d'un langage de programmation permettant de programmer l'énumération de tous les termes du langage choisi pour l'exemple `{a,f"(.)",g"(.,.)"}`.

D'un point de vue informatique, une énumération est un processus qui émet un flux de données. On parlera de flux de sortie. On est donc amené à considérer des processus de calcul pouvant posséder non seulement des entrées et des sorties, qualifiées d'individuelles car ne contenant qu'un seul terme, mais également des flux d'entrée et des flux de sortie.

Un flux peut se terminer par la méta-donnée `"FIN"`, on dira alors qu'il est fermé. Toute entrée ou sortie peut être considérée comme un flux, ce qui a l'avantage d'unifier les procédés d'entrée-sortie. Ceci est d'autant plus pertinent que les données ne sont pas bornées en taille et donc a priori ne peuvent qu'être transmises qu'à travers un flux.

Le processus s'arrête lorsque tous ses flux de sortie sont fermées c'est à dire ont émit la méta-donnée `"FIN"`.

Les entrées individuelles peuvent être transmises au début d'un flux d'entré. De même, les sorties individuelles peuvent être transmises au début d'un flux de sortie. Ce faisant, les processus les plus courants auront exactement un flux d'entrée et un flux de sortie.

L'hypothèse de créer des flux parallèles n'apportent pas grand chose, en tout cas dans cette première partie où on ne s'interesse pas intensément à l'efficacité et à la complexité du calcul, sachant que deux flux parallèles peuvent se fusionner parallèlement sans difficulté en un seul flux, alternant les données de l'un à l'autre, tant que l'un ou l'autre n'est pas fermé, et de continuer seul le flux restant ouvert. C'est pourquoi il est intéressant de modéliser un langage de programmation mettant en oeuvre un seul type de processus possédant un flux d'entrée et un flux de sortie.

On nommera ces processus par une majuscule.

On utilise le symbole pipe `¦`, symbole utilisé historiquement par le shell Unix, pour signifier que le flux de sortie du processus situé à gauche du symbole est relié au flux d'entrée du processus situé à droite du symbole. Exemple : `A¦B¦C` signifie que le processus `A` produit un flux de sortie qui est relié au flux d'entrée de `B` qui possède un flux de sortie relié au flux d'entré de `C`.

Si un processus possède un flux d'entrée qui n'est raccordé à rien, alors le flux est par principe fermé, et cela revient au même à ce qu'il soit raccordé à un flux de sortie n'émettant que la seule méta-donnée `"FIN"`.

Puis il faut pouvoir composer ces flux de façon parallèle ou de façon série. Parce que notre langage de programmation est focalisé sur les processus qu'il nomme par des lettres majuscules, et que nous ne nommons pas les flux, nous allons concevoir ces deux opérations sur les processus eux-mêmes.

On compose les processus `A, B, C` de façon parallèle par l'expression `(A,B,C)`. Le flux d'entrée est démultiplié et envoyé pareillement sur chacun des processus `A, B, C`. Et le flux de sortie correspond à la fusion des flux de sortie de chacun des processus `A, B, C`. Et, la manière par défaut de construire ce flux fusionné, consiste à alterner les données provenant de `A` puis de `B` puis de `C` et de recommencer ainsi de suite, comme une distribution en règle, et lorsqu'un flux se ferme, de retirer la méta-donnée `"FIN"` émise et de continuer pareillement avec les flux réstants.

On compose les processus `A, B, C` de façon série par l'expression `[A,B,C]`. Le flux d'entrée est démultiplié et envoyé sur chacun des processus `A, B, C`. Et le flux de sortie correspond au flux de `A` qui s'il se termine, alors la méta-donnée `"FIN"` est retirée et le flux se prolonge avec celui émit par `B`, puis si la méta-donnée `"FIN"` apparait, alors celle-ci est retirée et le flux se prolonge avec celui émit par `C`.

Puis il existe une opération de produit d'espaces qui consiste à générer tous les produits possibles sous forme de couples. Etant donné deux flux de données `tau_1,tau_2,tau_3,tau_4,...` et `sigma_1, sigma_2, sigma_3,sigma_4,...`, le flux produit d'espace est un flux qui énumère tous les couples possibles d'un élément du premier flux et d'un élément du second flux. Et, la manière par défaut de construire ce flux, consiste à parcourir le plan par des diagonales, et cela produit le flux de couples suivant :

`(tau_1,sigma_1), (tau_2,sigma_1),(tau_1,sigma_2),(tau_3,sigma_1),(tau_2,sigma_2),(tau_1,sigma_3), ...`

On compose les processus `A, B` en produit d'espaces par l'expression `A"×"B`. Le flux d'entrée est démultiplié et envoyé sur chacun des processus `A, B`. Et le flux de sortie correspond au balayage de l'espace à deux dimensions des couples de données `(x,y)` `x` est émit par `A` indépendamment de l'autre processus, et où `y` est émit par `B` indépendamment de l'autre processus.

Puis il faut pouvoir appliquer un opérateur générateur unaire tel que `f"(.)"` à un flux pour produire le même flux mais dans lequel chaque élément, que nous désignons par `tau`, est remplacé par `f(tau)`. Parce que nous ne nommons pas les flux mais les processus qui les crée, on conçoit cet opération sur les processus. On note `f(A)` le processus qui effectue le même calcul que le processus `A` mais qui va en modifier le flux de sortie en remplaçant chaque élément du flux, que nous désignons par `tau`, par `f(tau)`.

De même, il faut pouvoir appliquer un opérateur générateur binaire tel que `g"(.,.)"` à un flux de couples pour produire le même flux mais dans lequel chaque couple d'éléments, que nous désignons par `(tau,sigma)`, est remplacé par `g(tau,sigma)`. On note `g(A"×"B)` le processus qui effectue le même calcul que le processus `A"×"B` mais qui va en modifier le flux de sortie en remplaçant chaque couple d'éléments du flux, que nous désignons par `(tau,sigma)`, par `g(tau,sigma)`.

De même, il faut pouvoir donner un sens à un opérateur générateur d'arité zéro tel que `a`. Dans le langage de programmation, un élément générateur tel que `a` désigne un processus émettant le flux `a, "FIN"`.

Pour finir, il faut pouvoir programmer récurcivement, c'est à dire construire un programme qui s'appelle lui-même sachant qu'a chaque appel, un nouveau processus est créé dans un nouvel environnement. On note la création d'un programme à l'aide du symbole d'égalité et d'une lettre majuscule désignant son processus relativement à l'environnement en cours. Tout ça pour préciser que si cette lettre est répétée dans le programme, cela correspond à un appel récurcif et donc à la création d'un nouveau processus de même nom mais dans un nouvel environnement empilé dans la pile des appels.

Le programme d'énumération des termes du langage `{a,f"(.)",g"(.,.)"}` s'écrit alors comme suit :

`H = (a,f(H),g(H"×"H))`

14) Logique polonaise

Chaque terme du langage `L={a,f"(.)",g"(.,.)"}` tel que par exemple le terme `g(a,f(a))` se note en logique polonaise en une séquence d'opérateurs `"gafa"`. On enlève les parenthèses et les virgules qui n'apportent pas d'information car on connait les arités des opérateurs générateurs.

Considérons un terme où il y a `n_0` opérateurs d'arité nulle, `n_1` opérateurs unaires, `n_2` opérateurs binaires, ..., `n_i` opérateurs d'arité `i`. Ces nombres doivent vérifier l'équation suivante :

`n_0 - n_2 - 2n_3 - 3n_4 - 4n_5 ... =1`

D'autre part, la logique polonaise permet non seulement d'énumérer les termes mais aussi d'énumérer les listes de termes. Par exemple la séquence afaRaa désigne la liste de trois termes `a,f(a),R(a,a)`. Chaque liste de terme telle que par exemple `a,f(a),R(a,a)` se note en logique polonaise en une séquence d'opérateurs `"afaRaa"`. On enlève les parenthèses et les virgules qui n'apportent pas d'information car on connait les arités des opérateurs générateurs.

Considérons une liste de `m` termes où il y a `n_0` opérateurs d'arité nulle, `n_1` opérateurs unaires, `n_2` opérateurs binaires, ..., `n_i` opérateurs d'arité `i`. Ces nombres doivent vérifier l'équation suivante :

`+1n_0 - 0n_1 - 1n_2 - 2n_3 - 3n_4 - 4n_5 ... = m`

`sum_(i=0)^(i=oo) (1-i)n_i = m`

Et pour chaque sous-séquence stricte accolée sur le bord gauche, cette somme doit être inférieure à `m`. Et pour chaque sous-séquence accolée sur le bord droit, cette somme doit être supérieur ou égale à `1`.

On appel opérateur-droit, un terme pouvant être non clos c'est à dire dans lequel tout les arguments ne sont pas forcement déterminés mais tel que tous les arguments non déterminés sont à la fin du terme c'est à dire placés à sa droite sans qu'il y ait le moindre opérateur intercalé. Un tel opérateur-droit possède une arité égale au nombre d'arguments non déterminés et constitue une fonction s'appliquant à la liste des arguments non déterminés dans l'ordre de leur apparition dans le terme, de gauche à droite. Par exemple `g(f(a),g(f(.),.))` est un opérateur-droit et correspond à la fonction `(x,y)|->g(f(a),g(f(x),y))`. Par contre `g(.,f(.))` n'est pas un opérateur-droit car l'opérateur `f` est intercalé entre deux arguments indéterminés.

Pareillement on appel liste-droite, une liste composée de termes sauf pour le dernier qui est un opérateur-droit.

Chaque liste-droite, telle que par exemple `f(a),a,g(a,g(f(.),.)))` se note en logique polonaise en une séquence d'opérateurs `"faagagf"`. Une liste-droite possède un couple d'arités ; une arité d'entrée et une arité de sortie. L'arité d'entrée est celle de l'opérateur-droit. L'arité de sortie est le nombre de termes et d'opérateur-droit dans la liste-droite.

L'ensemble des listes-droites de taille `n` correspond à `L^n`. L'ensemble des listes-droites de taille finie correspond à `L"*"``"*"` est le symbole de Kleene. `L"*"` est l'ensemble des listes finies d'opérateurs de `L`.

15) Programmation pragmatique

Il existe un moyen simple de générer la plus part des termes. Il suffit de choisir au hasard les opérateurs.

Pour avoir un aperçu de tous les termes, on liste dans l'ordre lexicographique des arités, les modèles de terme définis par l'arité de chacun des opérateurs qui les composent. Par exemple pour un langage comprenant des opérateurs zéro-aires, unaires et binaires :

Taille 1 : 0.
Taille 2 : 10.
Taille 3 : 110, 200.
Taille 4 : 1110, 1200, 2010, 2100.
Taille 5 : 11110, 11200, 12010, 12100, 20110, 20200, 21010, 21100, 22000.
Taille 6 : 111110, 111200, 112010, 112100, 120110, 120200, 121010, 121100, 122000, 201110, 201200, 202010, 202100, 210110, 210200, 211100, 212000, 220010, 220100, 221000.

Les liste suivantes deviennent vite longue et fastidieuse. Il semble plus simple de faire une énumération au hasard. Une heuristique consiste à choisire une probabilité d'apparition d'un opérateur d'arité `i` qui soit `i` fois plus faibles que celle d'un opérateur zéro-aire. Puis lors de la lecture du terme construit au hasard, en lisant les `k` premiers opérateurs, on calcule les nombres d'opérateur d'arité i noté n_i, et on calcul le nombre caractéristique suivant :

`sum_(i=0)^(i=oo) (1-i)n_i`

Si ce nombre caractéristique devient égale à `1`, alors on déplace cette première partie du terme (les `k` premiers opérateurs) à la fin du terme et on recommence la lecture. Si on retrouve une même situation alors que tout le terme à déjà été déplacé à la fin alors on coupe le terme à ce niveau. Et par contre, si à la fin de la lecture du terme, le nombre caractéristique reste inférieur à `1`, on ajoute au hasard des opérateurs d'arité nulles en nombre suffisant. Ainsi avons-nous un algorithme assez efficace générant au hasard des termes ayant approximativement une taille voulue.

16) Enumération exacte

Intéressons-nous à l'énumération exacte des termes, ordonnée selon la taille des termes et selon l'ordre lexicographique des opérateurs générateurs ordonnés selon un ordre arbitraire. L'énumération s'applique de manière plus générale à un `m`-uplet de termes avec `m` constant. Et elle est ordonnée selon la taille des listes et selon l'ordre lexicographique des opérateurs générateurs ordonnés selon un ordre arbitraire. La taille est le nombre d'occurences d'opérateurs.

L'énumération des listes de `m` termes en logique polonaise est comparable à un compteur que l'on incrémenterait, mais dans lequel l'incrémentation serait plus complexe que celle d'un entier écrit en décimal. Néanmoins cette énumération respecte un principe fondamental, propre aux compteurs, à savoir que les derniers digits (ici, des opérateurs) forment des séquences qui se décomptent toujours de la même façon, principe que nous admettons pour l'instant et que nous démontrerons plus tard.

On procède donc à l'énumération en s'assurant que l'énumération des `t` derniers opérateurs, c'est à dire, ceux qui sont le plus à droite, s'effectuent toujours de la même façon. Ainsi lorsque l'énumération des termes de taille `t` est faite, l'énumération des termes de taille `t+1` pourra être décrite plus concisément en une suite de bloques désignant les énumérations de sous-termes de taille `t`, `t"-"1`, `t"-"2`, ..., `3`, `2`, `1`.

On note `E_t` l'énumération de tous les termes de taille `t`.

On note `E_t^m` l'énumération de toutes les listes de tailles `t` contenant exactement `m` termes.

Dans un premier temps on choisira un ordre des opérateurs compatible avec leur arité. Mais l'algorithme d'énumération s'applique pour un nordre arbitraire des opérateurs générateur. Considérons le langage ordonné suivant :

`(a, b, f"(.)", g"(.)", R"(.,.)", S"(.,.)")`

Considérons le terme composé de `n` opérateurs disposés en logique polonaise, `x_n...x_3x_2x_1`. On cherche l'algorithme pour incrémenter ce compteur. Voici comment commence cette énumération :

`E_1` 
a
b

`E_2` 
fa
 `E_1` 
fb
ga
 `E_1` 
gb

`E_3` 
ffa
 `E_2`  
 
fgb
 
gfa
 `E_2` 
 
ggb
 
Raa
 `E_1` 
 `E_2^2`
Rab
Rba
 `E_1` 
Rbb
Saa
 `E_2^2` 
 
Sbb
 
`E_4` 
fffa
 `E_3` 
fSbb
 
gffa
 `E_3` 
 
gSbb
 
Rafa
 `E_2` 
 `E_3^2`
Ragb
Rbfa
 `E_2` 
Rbgb
Rfaa
 `E_1` 
Rfab
Rfba
 `E_1` 
Rfbb
Rgaa
 `E_1` 
Rgab
Rgba
 `E_1` 
Rgbb
Safa
 `E_3^2`
 
Sgbb
 
`E_5` 
ffffa
`E_4` 
fSgbb
gfffa
`E_4`
gSgbb
Raffa
`E_3`
 
`E_4^2`
RaSbb
Rbffa
`E_3`
RbSbb
RRaaa
`E_2^2`
`E_3^3`
RRabb
RRbaa
`E_2^2`
RRbbb
RSaaa
`E_3^3`
RSbbb
SRaaa
`E_3^3`
SRbbb
SSaaa
`E_3^3`
SSbbb
`E_6` 
fffffa
  `E_5` 
   
fSSbbb
   
gffffa
  `E_5` 
   
gSSbbb
   
Rafffa
`E_4`
`E_5^2` `E_5^2`
RaSgbb
Rbfffa
`E_4`
RbSgbb
RRaafa
`E_3^2`
`E_4^3`
RRagbb
RRbafa
`E_3^2`
RRbgbb
RRfaaa `E_3^3`
RRfbbb
RRgaaa `E_3^3`
RRgbbb
RSaafa `E_4^3`  
RSgbbb  
SSaafa `E_4^3`    
SSgbbb    
 
`E_1` 
a ... b
`E_2` 
fa ... gb
`E_2^2`
aa ... bb
`E_3` 
ffa ... Sbb
`E_3^2`
afa ... gbb
`E_4` 
fffa ... Sgbb
`E_3^3`
aaa ... bbb
`E_4^2` 
affa ...Sbbb
`E_5`
ffffa ... SSbbb
`E_4^3`
aafa ... gbbb
`E_5^2`
afffa ... Sgbbb
`E_6`
fffffa ... SSgbbb

 

17) Le langage des arités

Considérons un langage possédant un unique opérateur générateur pour chaque arité, et dans lequel les opérateurs générateurs sont ordonnés selon leur arité. On désigne ces opérateurs générateurs par des chiffres, puis au delà du chiffre 9 par les lettres de l'alphabet. On donne comme nom à ce langage : le langage des arités.

`{0,1"(.)",2"(.,.)",3"(.,.,.)",...}`

L'énumération des termes du langage des arités  :

0
Nouveau digit

 

10
Nouveau digit

 

110
Nouveau digit
200
Incrémentation de `x_3`

 

1110
Nouveau digit
1200
Incrémentation de `x_3`
2010
Incrémentation de `x_4`
2100
Incrémentation de `x_3`
3000
Incrémentation de `x_4`

 

11110
Nouveau digit
11200
Incrémentation de `x_3`
12010
Incrémentation de `x_4`
12100
Incrémentation de `x_3`
13000
Incrémentation de `x_4`
20110
Incrémentation de `x_5`
20200
Incrémentation de `x_3`
21010
Incrémentation de `x_4`
21100
Incrémentation de `x_3`
22000
Incrémentation de `x_4`
30010
Incrémentation de `x_5`
30100
Incrémentation de `x_3`
31000
Incrémentation de `x_4`
40000
Incrémentation de `x_5`
 
111110
Nouveau digit
111200
Incrémentation de `x_3`
112010
Incrémentation de `x_4`
112100
Incrémentation de `x_3`
113000
Incrémentation de `x_4`
120110
Incrémentation de `x_5`
120200
Incrémentation de `x_3`
121010
Incrémentation de `x_4`
121100
Incrémentation de `x_3`
122000
Incrémentation de `x_4`
130010
Incrémentation de `x_5`
130100
Incrémentation de `x_3`
131000
Incrémentation de `x_4`
140000
Incrémentation de `x_5`
201110
Incrémentation de `x_6`
201200
Incrémentation de `x_3`
202010
Incrémentation de `x_4`
202100
Incrémentation de `x_3`
203000
Incrémentation de `x_4`
210110
Incrémentation de `x_5`
210200
Incrémentation de `x_3`
211100
Incrémentation de `x_4`
212000
Incrémentation de `x_4`
220010
Incrémentation de `x_5`
220100
Incrémentation de `x_3`
221000
Incrémentation de `x_4`
230000
Incrémentation de `x_5`
300110
Incrémentation de `x_6`
300200
Incrémentation de `x_3`
301010
Incrémentation de `x_4`
301100
Incrémentation de `x_3`
302000
Incrémentation de `x_4`
310010
Incrémentation de `x_5`
310100
Incrémentation de `x_3`
311000
Incrémentation de `x_4`
320000
Incrémentation de `x_5`
400010
Incrémentation de `x_6`
400100
Incrémentation de `x_3`
401000
Incrémentation de `x_4`
410000
Incrémentation de `x_5`
500000
Incrémentation de `x_6`

 

18) Le langage Alpha

Le langage Alpha est un langage beaucoup plus générale, qui englobe le langage d'opérateurs d'arité fixe. Le langage Alpha utilise un unique opérateur générateur, l'opérateur alpha noté `alpha`, qui est d'arité variable, c'est à dire qui s'applique à une liste finie d'arguments qui sont des termes du langage Alpha.

Pour des raisons propres à la théorie de l'information, on estime que l'opérateur alpha appliqué à une liste vide d'argument retourne lui-même, ce qui se note `alpha()=alpha`

La représentation des termes du langage Alpha ne peut pas se faire en logique polonaise du fait que l'arité est variable.

Voici comment commence l'énumération du langage Alpha :

a
a(a)
a(a,a)
a(a(a))
a(a,a,a)
a(a,a(a))
a(a(a),a)
a(a(a,a))
a(a(a(a)))
a(a,a,a,a)
a(a,a,a(a))
a(a,a(a),a)
a(a(a),a,a)
a(a,a(a,a))
a(a,a(a(a)))
a(a(a,a),a)
a(a(a(a)),a)
a(a(a(a(a))))

Etant donné un ensemble d'opérateurs d'arité fixe et variable, cet ensemble constitue un système minimal si et seulement si aucun opérateurs ne peut être calculer par une combinaison des autres.

Pour rechercher les systèmes minimaux, il faut développer un programme informatique qui passe en revue toutes les combinaisons possibles d'opérateurs d'arité fixe et variable, c'est à dire qui sache énumèrer toutes les compositions closes d'opérateurs qu'il est possible de construire à partir d'opérateurs générateurs d'arité fixe et variable.

20) Langage de programmation pour énumérer le langage Alpha

On veut programmer un énumèrateur de toutes les termes du langage alpha. Pour concevoir intelligemment ce programme, il convient de chercher en même temps que le programme, le langage de programmation le plus adapté à ce type de programme. C'est pourquoi nous ouvrons au chapitre 20 une discussion informatique faisant suite du chapitre 13.

Etant donné un processus `A` qui énumère une liste d'éléments qui peut être infinie `e_1,e_2,e_3,...`. Remaquer que l'on n'a pas précisé la syntaxe des éléments c'est à dire la façon dont ils sont représentés dans le flux de données de sortie du processus `A`.

Il existe une opération d'espace, dite opération de Kleene, qui énumère toutes les listes finie d'éléments appartenant à un ensemble. Le processus `A"*"` va énumérer les listes finies d'éléments produits par `A`.

Le programme d'énumération des termes du langage alpha s'écrit alors comme suit :

`H = alpha(H"*")`

Etant donné le langage `L = {a,f(.),,R(.,.),varphi(...)}` où les opérateurs suffixés par `(...)` sont d'arité variable. Le programme d'énumération des termes du langage `L` s'écrit alors comme suit :

`H = (a,f(H),R(H"×"H),varphi(H"*"))`

Le processus d'énumération de `ZZ"×"ZZ` est assez simple, il s'effectue par diagonales successives, et peut donc être réitéré pour produire une puissance plus élevées telle que `ZZ^3`. Parcontre le processus d'énumération de `ZZ"*"` est un peu plus complexe. On recherche donc à préciser un algorithme qui énumère `ZZ"*"`.

Néanmoins une autre méthode est possible se basant sur le fait que tout opérateur d'arité variable peut être remplacé par deux opérateurs binaires.

20) Programmation en go

Afin de rendre les mathématiques moins ingrates, et de concrétiser de façon exacte notre propos, et ainsi d'en vérifier sa véracité, on programme le compteur en Go. Mais le langage Go met en exergue les flux qui sont appelés des canaux. Cela nous oblige à réécrire le programme en créant et pilotant chaque canaux.

---- 25 mai 2018 ----

 


Dominique Mabboux-Stromberg