Lorsqu'on ne s'intéresse pas précisement à la complexité des fonctions, il est inutile de considérer des fonctions ayant plusieurs composantes résultats puisqu'elles sont alors décomposables en autant de fonctions qu'il y a de composantes résultats. C'est pourquoi les premiers types exposés traitent de fonction d'arité d'entré fixe mais ne produisant toujours qu'un seul resultat, c'est a dire d'arité de sortie égale à 1.
La structure définie un ensemble sous-jacent qui regroupe tous les éléments constructibles, tous les opérateurs constructibles d'arité zéro, c'est à dire tous les termes clos. Et le point "." désigne cet ensemble sous-jacent.
On utilise deux notations, une notation par entête qui consiste à visualiser les arguments attendus par des points, comme autant de places libres, et la notation applicative qui consiste à visualiser les arguments attendus par les ensembles auxquels ils appartiennent et à définir l'opérateur par le meta-opérateur ->. L'ensemble sous-jacent est désigné par E en notation applicative, et par le point "." en notation par entête. Par exemple un opérateur binaire se notera :
Notation applicative : (E,E) -> E
Notation par entête : .(.,.)
L'ensemble des fonctions d'arité 1 sur l'ensemble sous-jacent est noté .(.) puis l'ensemble des fonctions d'arité 2 est noté .(.,.) puis l'ensemble des fonctions d'arité 3 est noté .(.,.,.) et ainsi de suite. Mais on doit aussi considérer les fonctions prenant en argument d'autres fonctions de type précédemment défini et retournant d'autres fonctions de type précédemment défini. Cela correspond à toute les types de fonction que l'on peut construire à l'aide du méta opérateur -> et des variables appartenant à l'ensemble sous-jacent ou aux différents types en cours de construction.
par entête
applicative
f(.,.) désigne un opérateur de nom f, de type .(.,.) c'est à dire qui prend en argument 2 éléments et retournant 1 élément. En faite, il y a une contraction, le type de l'opérateur f est bien .(.,.) et le premier point indique que le résultat de la fonction est un élément, ce qui est dans les mono-structures toujours le cas, et qui justifie que le nom de l'opérateur puisse le remplacer.
g(.)(.,.) désigne un opérateur de nom g, de type .(.)(.,.) et donc qui prend en argument 2 éléments, et qui retourne comme résultat un opérateur de type .(.) qui lui-même prend un élément pour retourner un élément. Les places libres sont groupées entre parenthèses et forme des blocs qui sont sollicités de droite à gauche, chaque bloc étant rempli de gauche à droite. Ainsi l'expression g(.)(.,.) est d'arité 2, et appliquée à (x,y), l'appel devient g(.)(x,y) est retourne alors un opérateur d'arité 1 de type .(.)
Puis h(.(.,.),.(.,.)) désigne un opérateur de nom h, prenant en premier argument un opérateur d'arité 2 c'est à dire de type .(.,.) et comme second argument encore un opérateur de même type.(.,.) et retourne comme résultat un élément. Ainsi l'application h peut s'appliquer à (f,f) puisque f est de type .(.,.) et l'appel devient h(f,f) et retourne alors un élément.
D'un point de vue intuitioniste on accorde davantage de crédit au programme qu'à la fonction, car le programme est une implémentation de la fonction, et constitue donc quelque chose de quasi matériel contrairement à la fonction qui reste toujours abstraite.
Puisque qu'un opérateur f d'arité n est défini par un programme à n entrés, on peut scinder la liste des entrés en deux morceaux contigüs n1 + n2 = n, et considérer que f est une fonction d'arité n1 retournant une fonction d'arité n2. Et ce procédé peut être répété. Par exemple les définitions de fonction suivantes serons considérées comme équivalentes :
(x,y,z,t) -> f(x,y,z,t)
(x,y) -> ((z,t) -> f(x,y,z,t))
(x,y) -> (z -> (t-> f(x,y,z,t)))
x -> (y -> (z -> (t -> h(x,y,z,t))))
On peut ainsi regrouper les types en des types plus généraux, grace à la currification. La currification va rendre certains types équivalents entre eux. Toute application d'arité supérieur à 1 peut être décomposée en un emboitement d'applications unaires. Par exemple, si on s'autorise la currification, le type (A,B,C) -> D est équivalent au type (A -> (B -> (C -> D))), et inversement tout aplication d'arité n1 produisant une application d'arité n2 peut être fusionnée en une seul application d'arité n1+n2.
Ainsi avec la currification, les types admettent une forme normale dite "série" où il n'y a que des opérateurs -> binaire, et forme normale dite "liste" où chaque opérateur -> ne retourne pas d'autre application. Par exemple l'opérateur x-> ((y,z) -> h(x,y,z)) admet une forme normale série x -> (y -> (z -> h(x,y,z))) et admet une forme normale liste (x,y,z) -> h(x,y,z)
Le protocole de construction de fonction peut être simplifié en introduisant uniquement un opérateur binaire -> de construction d'opérateur, ce qui correspond à la forme normale série. Cela permet de parcourir plus facilement toutes les constructions possibles. Ce sont les arbres binaires nues.
série
liste
On pose une propriété syntaxique de l'opérateur -> : Il s'évalue de droite à gauche. Ainsi le type E->E->E->E est identique à E->(E->(E->E)) et est équivalent par currification au type (E,E,E)->E
On considére un object plus générale, parent de la fonction, qu'est la relation
---- 4 mai 2015 ----
Nous pourrions considérer un ensemble de départ et un ensemble d'arrivé pour établire nos fonctions et nos relations. Mais pour des raisons d'extension, on part d'une situation où l'ensemble de départ et l'ensemble d'arrivé sont le même ensemble. Cette situation qui parrait au première abord moins générale s'avère en faite plus générale. Car en procédant par la suite à une extension (en ajoutant un prédicat, l'élément FAIL et une théorie adéquate) on recrée les deux ensembles de départ et d'arrivé. Selon une argumentation juridique, en l'absence de motif on ne discrimine pas, et s'il advient un motif, celui-ci complètera la théorie.
Une relation R est un graphe orienté sur un ensemble E c'est à dire que R est un ensemble d'arrêtes, chaque arrête partant d'un élément de E pour aller sur un élément de E. Lorsqu'une arrête part de x pour aller sur y, on dit que x est en relation avec y, et on note xRy, et on note aussi (x,y)∈R.
R est un sous-ensemble de E2. Autrement dit R appartient à ℙ(E2) l'ensemble des parties de E2.
Une relation R est une fonction si et seullement si pour tout élément x appartenant à E, l'enemble des images de x par R noté R(x) = {y / xRy} contient au plus 1 élément.
D'un point de vue intuitioniste, on accorde davantage de crédit au programme qu'à la fonction, car le programme est une implémentation de la fonction, et constitue donc quelque chose de quasi matériel contrairement à la fonction qui reste toujours quelque peu abstraite. Le programme, qui est ici une implémentation de la fontion, met en oeuvre un processus déterministe, un calcul dont le cheminement est déterminé, dans le but de produire un résultat unique. Mais le calcul peut échouer sans que l'on puisse planifier cet échec, en ne s'arrétant jamais, c'est à dire en ne donnant aucune réponse, ce que nous appellons l'infini de Turing (et qui constitue un oracle). Il peut aussi échouer d'une manière conventionnelle en retournant FAIL ce qui correspond à un domaine de définition choisi conventionnellement permettant de manipuler les fonctions comme des applications et qui n'est pas un problème en soi. Le FAIL est une réponse unique et donc ne pose pas de problème. Parcontre l'infini de Turing est une non réponse et donc pose problème car cela bloc la suite du processus qui attend une réponse.
A la différence d'une fonction qui se présente comme un processus de calcul déterministe, une relation se présente comme un processus de calcul non-déterministe. Si tout est calculable, tout est déterministe, certe, mais les images de x selon R sont supposées d'égal statut, autrement dit elles ne doivent pas être discernables. Il n'y a pas d'ordre définie dans l'ensemble des images. Ce qui est une conséquence du fait que R est un sous-ensemble de E2 sans ordre défini. C'est donc la définition de l'ensemble sans ordre défini qu'il convient d'approfondire.
D'un point de vu intuitionniste un ensemble est implémenter sous forme d'un énumérateur, et est donc nécessairement ordonné canoniquement. Pour enlever cet ordre, on ajoute une propriété d'égalité de statut. Chaque élément à un statut égal et ne peut être discerné. Mais, pour un ensemble infini, la mise en oeuvre de cette propriété risque fort de sortir du domaine du calculable. On ne considèrera dans un premier temps que des ensembles finis d'indiscernables.
L'image d'un élément x par R est l'ensemble des éléments atteignables à partir de x en empruntant une arrête de R. On note R(x) l'ensemble des images de x par R. Et on note R-1(x) l'ensemble des images inverses de x par R.n
R(x) = {y / xRy}
R-1(x) = {y / yRx}
La relation symétrique se note R-1, et nous avons xRy <=> yR-1x ou dit autrement (x,y)∈R <=> (y,x)∈R-1
On note ℙ(E) l'ensemble des parties de E. Les relations sont identifiables aux élements de ℙ(E). Les relations sont identifiables aux fonctions de E vers ℙ(E). Les relations sont identifiables aux fonctionsde ℙ(E) vers E. Les relations sont aussi identifiables aux fonctions f de ℙ(E) vers ℙ(E) qui respectent l'union c'est à dire tel que ∀(A,B)∈ℙ(E)2, f(A∪B) = f(A) ∪ f(B). En effet, on étend chaque relations R définie de E vers ℙ(E) en une fonction de ℙ(E) vers ℙ(E) respectant l'union comme suit : R(A) = {y / ∃x∈A, xRy}. Et réciproquement si une fonction de type ℙ(E)-->ℙ(E) respecte l'union alors c'est une relation de type E-->ℙ(E), et la fonction est calculable ssi la relation est énumérable. Le type ℙ(E2) est donc égale au type E-->ℙ(E), égale au type ℙ(E)-->E et aussi égale au type ℙ(E)-->ℙ(E) / {respecte ∪}. Ces liens biunivoques se traduisent par des dénombrements combinatoires vérifiables.
Etant donné deux relations R et S, la composition notée à la française RS ou à l'anglaise S°R, est définie comme suit : xRSy <=> ∃u, xRu et uSy. Et nous avons S°R(x) = S(R(x)). Puis la relation symétrique de S°R est (S°R)-1 = R-1°S-1. Etant donné une relations f , pour tout ensemble A, les ensembles f-1(f(A)) et f(f-1(A)) peuvent être plus grand que A. Mais si la relation f est injective alors f-1(f(A)) = A et si f est fonctionnelle alors f(f-1(A))=A.
D'un point de vue intuitioniste E est énumérable, et on ne considérera que les parties énumérable de E et de E2. Ainsi on ne concidére que des relations énumérables.
Un ensemble est énumérable s'il existe un énumérateur qui énumère tous ses éléments, et l'énumérateur est un programme de taille finie. De même, R est énumérable s'il existe un énumérateur qui énumère toutes ses arrêtes.
Noter que le complémentaire d'un ensemble énumérable n'est pas nécessairement énumérable...
La seul énumération de R ne permet pas de décider si R est une fonction, mais elle peut semi-décide la propriété "R n'est pas une fonction".
A partir d'une relation R énumérable qui est de type E-->ℙ(E), on peut construire une fonction canonique R1 de type E-->E qui associe à tout élément, la première image apparaissant dans l'ordre d'énumération de R. Etant donné deux relations sur E, notées R et S. La relation R appliquée à x va produire une partie énumérable d'éléments images notés R1(x), R2(x), R3(x) .... Chacun de ces éléments images Ri(x) est en relation S avec une partie énumérable d'éléments notés S1(Ri(x)), S2(Ri(x)), S3(Ri(x)).... .
On considérer un object plus générale encore, mais toujours parent de la fonction, qu'est la relation d'arité variable.
Une relation ternaire R est un sous-ensemble de E3. Autrement dit R appartient à ℙ(E3) l'ensemble des parties de E3. Mais c'est aussi une fonction de E vers ℙ(E2), et une fonction de E2 vers ℙ(E).
Une relation d'arité variable est un sous-ensemble de E*-{ε} où * est l'opération de Kleene et où ε représente le mot vide. On retire le mot vide qui correspond à la relation d'arité nulle (car il y a deux relations d'arité nulles, celles qui à la valeur logique true et celle qui à la valeur logique false. Cet empressement à vouloir mettre un élément neutre n'est pas un bon choix.)
Si E est énumérable alors l'ensemble des relations d'arité variable sur E est également énumérable.