(née à Saint-Louis, Missouri, 8 décembre 1919; décédée à Berkeley, Californie, 30 juillet 1985), mathématiques, logique mathématique, théorie des nombres, problèmes de décision, définissabilité.
Le travail mathématique de Robinson montre puissance et charme. Elle s’est attaquée à des problèmes difficiles et s’est efforcée de trouver des solutions élégantes. Sa vie et son travail ne peuvent être correctement vus sans noter qu’en tant que femme dans un domaine dominé par les hommes, elle était en quelque sorte une pionnière. Son métier était l’interface entre deux branches des mathématiques, la logique et la théorie des nombres, généralement considérées comme ayant peu à voir l’une avec l’autre. Elle est particulièrement connue pour ses contributions à la solution du dixième problème dans une célèbre liste de vingt-trois proposée par le mathématicien David Hilbert en 1900. Elle a été élue à l’Académie nationale des sciences et à la présidence de l’American Mathematical Society, dans les deux cas la première femme mathématicienne à être ainsi honorée, et a également reçu une bourse MacArthur.
Jeunesse Née Julia Bowman, elle a subi deux calamités très tôt dans sa vie. Elle n’avait que deux ans lorsque sa mère est morte, laissant son père faire face à Julia et à sa sœur aînée Constance. Après son remariage, la famille a déménagé à l’ouest, finalement à San Diego, où sa belle-sœur Billie est née. Quand Julia avait neuf ans, elle a subi une maladie dévastatrice: la scarlatine suivie d’un rhumatisme articulaire aigu. Elle a raté deux années d’école et a subi de très graves dommages au cœur. Sur le plan académique, elle a excellé et a rapidement rattrapé son terrain perdu. Au lycée, elle était la seule fille à suivre les cours avancés de sciences et de mathématiques et a obtenu son diplôme avec un certain nombre d’honneurs. En 1936, elle entre au San Diego State College, se spécialisant en mathématiques. Cherchant des perspectives plus larges, elle a été transférée à l’Université de Californie à Berkeley pour sa dernière année. Parmi les cinq cours de mathématiques qu’elle a suivis cette année-là, il y en avait un sur la théorie des nombres enseigné par Raphael Robinson. Impressionné par ses capacités, il l’a convaincue de poursuivre ses études en tant qu’étudiante diplômée. Raphaël était un mathématicien aux vastes intérêts et connaissances et un mentor idéal. Mais bientôt leur relation est devenue plus personnelle et ils se sont mariés en décembre 1941. Leurs espoirs de fonder une famille ont été anéantis lorsque Julia a fait une fausse couche et a été avertie par un médecin que, en raison de son cœur gravement endommagé, la grossesse serait extrêmement dangereuse. Son opinion était qu’elle mourrait probablement avant l’âge de quarante ans. Dans un effort pour aider Julia à surmonter la profonde dépression dans laquelle elle a été plongée, Raphaël l’a encouragée à chercher du réconfort en mathématiques.
Contexte mathématique Les années 1930 avaient vu des développements révolutionnaires dans l’ancien sujet de la logique, radicalement changé par rapport au domaine traditionnel créé par Aristote. Le célèbre théorème d’incomplétude de Kurt Gödel avait mis en évidence les limites inhérentes aux systèmes formels de logique dans l’encapsulation de la pratique mathématique. Les travaux d’Alonzo Church, d’Alan Turing et d’Emil Post ainsi que de Gödel lui-même avaient montré que la question de l’existence de solutions algorithmiques à des problèmes mathématiques spécifiques pouvait recevoir une formulation précise. Cela a ouvert la possibilité que dans des cas spécifiques, de telles solutions algorithmiques puissent ne pas exister, et même que dans de tels cas, cela puisse être prouvé. Alfred Tarski avait expliqué comment définir les notions sémantiques de vérité et de définissabilité des langages formels. Ce sont les développements qui ont fourni le contexte de la recherche de Julia Robinson.
Toute branche particulière des mathématiques utilisera des symboles pour représenter les opérations et les relations particulières qui sont fondamentales pour ce sujet. En plus de ces symboles, la logique mathématique moderne utilise les symboles spéciaux
avec le signe familier =. On parle de ces symboles avec ceux correspondant à une branche particulière des mathématiques comme constituant un langage. Le travail de Julia Robinson s’inscrivait en grande partie dans le contexte du langage arithmétique qui utilise les deux symboles + et × pour l’addition et la multiplication, respectivement, ainsi que les symboles pour 0 et 1. Les lettres de l’alphabet sont utilisées comme variables, et dans le cas du langage arithmétique, elles sont généralement comprises comme variant sur les nombres naturels familiers 0,1,2 …… Ainsi, par exemple, la « phrase »
exprime la proposition vraie que l’ajout de deux nombres impairs donne un nombre pair. La formule (u) (x = u + u + 1) > définit elle-même l’ensemble des nombres impairs, c’est-à-dire que si x est remplacé par un nombre naturel particulier, la phrase résultante sera vraie si et seulement si ce nombre est impair. Les questions de définissabilité et d’existence d’algorithmes étaient fondamentales pour le travail de Robinson.
Un ensemble de nombres naturels S est dit calculable (ou récursif) s’il existe un algorithme qui peut déterminer pour un nombre naturel donné n si n appartient ou non à S. Un ensemble de nombres naturels est appelé listable (le terme préféré par Julia Robinson) ou récursivement énumérable s’il existe un algorithme permettant de faire systématiquement une liste des membres de S. Tous les résultats d’invisibilité peuvent être considérés comme des conséquences du théorème clé : Il existe un ensemble listable qui n’est pas calculable. Ces questions étaient également très importantes dans le travail de Robinson.
La thèse de Julia Robinson C’est dans un séminaire animé par le charismatique Alfred Tarski, l’un des grands logiciens du XXe siècle, que Robinson a trouvé son métier. Tarski avait quitté sa Pologne natale en août 1939 pour ce qui devait être un bref voyage pour assister à une conférence aux États-Unis, juste avant que l’invasion allemande de la Pologne ne précipite la Seconde Guerre mondiale. Tarski posa un certain nombre de questions non résolues sur la définissabilité dans le langage arithmétique auquel Robinson était attiré. Dans les années 1940, il était bien connu qu’il n’y avait pas d’algorithme pour déterminer si une phrase donnée dans le langage de l’arithmétique, avec les variables allant au-dessus des nombres naturels, était vraie. Comme on le dit, c’est un problème algorithmiquement insoluble. Tarski voulait savoir si la même chose est vraie lorsque, dans ce même langage, les variables sont autorisées à s’étendre sur tous les nombres rationnels au lieu des nombres naturels. (Les nombres rationnels sont ceux exprimables sous forme de fractions m / n ou -m /n où m est un nombre naturel et n est un nombre naturel non nul.) Des techniques avaient été développées pour « réduire » un tel « problème de décision » à un autre. Dans ce cas, on montrerait que s’il existait un algorithme pour tester la vérité d’une phrase du langage arithmétique avec les variables contraintes de varier sur les nombres rationnels, un tel algorithme pourrait être utilisé pour fournir un algorithme pour faire de même lorsque les variables s’étendent sur les nombres naturels. Donc, comme il n’y a pas d’algorithme de ce type pour ce dernier, il s’ensuivrait qu’il n’y en aurait pas non plus pour le premier.
Le principal résultat de la thèse de Robinson était une formule explicite dans le langage de l’arithmétique, avec les variables contraintes de varier sur les nombres rationnels, qui définit précisément l’ensemble des entiers (c’est-à-dire l’ensemble des nombres naturels et leurs négatifs). Il s’ensuit alors que le problème de la détermination de la vérité d’une phrase arithmétique reste insoluble même lorsque les variables s’étendent sur les nombres rationnels. D’autres résultats non résolvables ont également suivi. L’approche de Robinson était complexe, élégante et ingénieuse en utilisant des idées assez profondes de la théorie des nombres.
Caractérisations élégantes Robinson a toujours recherché l’élégance et la simplicité dans ses travaux mathématiques. L’un de ses premiers articles a montré comment caractériser, d’une manière particulièrement simple, les fonctions calculables algorithmiquement (également appelées fonctions récursives) qui mappent les nombres naturels en eux-mêmes. Sa belle caractérisation implique deux fonctions initiales et trois opérations pour obtenir de nouvelles fonctions à partir de fonctions données. L’une des fonctions initiales est juste la fonction successeur S(x) = x + 1. L’autre, que Robinson appelle E, est défini comme la différence entre un nombre donné et le plus grand carré parfait qui ne le dépasse pas. (Donc E(19) = 19 – 16 = 3 et E(25) = 25 -25 = 0.) Les trois opérations sont les suivantes : (1) à partir de fonctions données F et G obtenir la fonction H(x) = F(G(x)) ; (2) à partir de fonctions données F et G obtenir la fonction H(x) = F(x) + G(x) ; et (3) à partir d’une fonction donnée F dont les valeurs incluent tous les nombres naturels obtenir la fonction H où H(x) est le plus petit nombre t pour lequel F(t) = x.
Il est vraiment remarquable que toutes les fonctions calculables (des nombres naturels aux nombres naturels) puissent être obtenues en commençant par les deux fonctions initiales et en appliquant ces trois opérations encore et encore.
Beaucoup plus tard, Robinson a fait preuve de la même élégance et de la même verve pour trouver de nouvelles caractérisations d’un domaine très éloigné du calculable. L’existence d’un ensemble listable K non calculable a déjà été mentionnée. Il n’y a donc pas d’algorithme pour déterminer l’appartenance à K. En considérant les ensembles qui peuvent être répertoriés par des algorithmes ayant accès aux informations d’adhésion sur ces ensembles (métaphoriquement via un « oracle »), des ensembles supplémentaires peuvent être introduits dans le pli, et ce processus peut être itéré. En permettant à cette itération de se produire n’importe quel nombre fini de fois, les ensembles obtenus se révèlent être exactement ceux appelés arithmétiques, les ensembles définissables dans le langage de l’arithmétique avec des variables allant sur les nombres naturels. Mais il n’est pas nécessaire de s’arrêter ici. On peut définir un ensemble non arithmétique, puis l’utiliser comme un « oracle » pour pouvoir lister encore plus d’ensembles. Il y a un endroit naturel où ce processus prend fin, et les ensembles de nombres naturels ainsi obtenus sont appelés hyperarithmétiques. C’est ce royaume raréfié pour lequel Robinson a fourni une caractérisation simple et directe.
Définissabilité existentielle et Dixième problème de Hilbert Le travail pour lequel Julia Robinson est la plus connue a pour origine un problème apparemment simple posé par Alfred Tarski. Tarski voulait savoir quels ensembles de nombres naturels sont définissables par des formules du langage arithmétique si les symboles et sont exclus. Il a qualifié de tels ensembles de définissables existentiellement et a proposé le problème de prouver que l’ensemble {1,2,4,8,16, ….} de puissances de 2 n’est pas définissable existentiellement. C’était exactement le genre de problème que Robinson aimait. La notion de définissabilité existentielle pourrait facilement être considérée comme étroitement liée à des problèmes d’un type que les théoriciens des nombres étudient, appelés problèmes diophantiens. Ceux-ci ont généralement à voir avec une équation polynomiale p (a, x, y, z, u, v, w, ….) = 0 avec des coefficients entiers où a est un paramètre et x, y, z, u, v, w, …. sont des « inconnus. »(Rappelons qu’un tel polynôme n’est que la somme de termes comme 5a3x2v5 et -7a4x3z6.) Pour des équations diophantiennes particulières de ce type, les théoriciens des nombres essaient de déterminer pour quelles valeurs de nombres naturels du paramètre a, l’équation a des solutions de nombres naturels dans les inconnues. Or, par des méthodes classiques simples, il est facile de voir qu’un ensemble de nombres naturels S est définissable existentiellement si et seulement s’il existe une équation polynomiale de ce genre telle que S est exactement l’ensemble des valeurs du paramètre pour lequel l’équation a des solutions de nombres naturels. Pour cette raison, les ensembles définissables existentiellement sont également appelés Diophantiens, et c’est le terme qui a été adopté dans la littérature ultérieure.
N’ayant pas réussi à prouver la conjecture de Tarski selon laquelle l’ensemble des puissances de 2 n’est pas Diophantien, Robinson commença à envisager la possibilité que la supposition de Tarski ait pu être fausse. Pour avancer, elle a dû assumer une certaine hypothèse, non prouvée à l’époque, qui a fini par s’appeler J.R.; en gros J.R. affirme qu’il existe une équation diophantienne à deux paramètres a, b avec la propriété que les couples (a, b) pour lesquels l’équation a des solutions sont tels que b croît exponentiellement en fonction de a. En supposant J.R. et en effectuant une analyse complexe et ingénieuse, elle a prouvé non seulement que les puissances de 2 sont diophantiennes, mais aussi que l’ensemble des nombres premiers ainsi que beaucoup d’autres le sont également. On voit facilement que tous les ensembles diophantiens sont listables, mais maintenant elle se demandait si l’inverse pouvait être vrai, si tous les ensembles listables pouvaient être diophantiens. Elle savait que cela aurait de profondes conséquences.
En 1900, pour saluer le nouveau siècle, le grand mathématicien David Hilbert a proposé une liste de vingt-trois problèmes à relever comme défi. Le dixième de sa liste était de fournir un algorithme pour déterminer si une équation diophantienne polynomiale donnée a des solutions. Si en effet tous les ensembles listables étaient diophantiens, elle s’est rendu compte, alors en particulier il y aurait un ensemble diophantien non calculable, ce qui implique qu’il ne pourrait pas y avoir d’algorithme tel que Hilbert l’avait demandé. Cela constituerait une solution négative du dixième problème de Hilbert.
À l’été 1959, Robinson a reçu par la poste une préimpression d’un article de Martin Davis et Hilary Putnam. L’article contenait une preuve que, en supposant J.R., tous les ensembles listables sont bien diophantiens. Cependant, la preuve comportait une lacune importante. Il a utilisé le fait qu’il existe des séquences arbitrairement longues de nombres premiers avec la propriété spéciale que la différence entre les termes consécutifs de la séquence est constante. Bien que cela soit vrai, en 1959, c’était une simple hypothèse; cela n’a été prouvé qu’en 2004. Robinson connaissait très bien le travail précédent de Davis et Putnam et a exprimé sa surprise et son plaisir de les accomplir. En très peu de temps, elle a montré comment se passer de l’hypothèse supplémentaire sur les nombres premiers, et a même trouvé une version courte de la preuve. Ainsi, pour obtenir la solution négative anticipée du dixième problème de Hilbert, il ne restait plus qu’à prouver J.R.
Cela a été accompli en janvier 1970 par Yuri Matiyasevich, âgé de vingt-deux ans, en utilisant la célèbre séquence de Fibonacci 1,1,2,3,5,8,13, …. Il a trouvé une équation diophantienne avec deux paramètres a, b qu’il a pu prouver a des solutions juste au cas où b est le nombre de Fibonacci à la 2a-th place dans cette séquence. Parce que les nombres de Fibonacci augmentent de façon exponentielle, cela constitue une preuve de J.R. Robinson a été ravi par la preuve ingénieuse de Matiyasevich et s’est rendu à Leningrad où leurs familles se sont rencontrées. Leur collaboration a été fructueuse; ensemble, ils ont pu montrer que le dixième problème de Hilbert est insoluble même pour des équations à 13 inconnues. (Plus tard, Matiyasevich a pu réduire le nombre à 9.)
Coda Les règles de « népotisme » en vigueur à l’Université de Californie auraient rendu impossible une nomination régulière à la faculté pour Robinson tant que son mari était à la faculté. Dans tous les cas, il se pourrait bien que ses problèmes de santé aient empêché un poste à temps plein. Elle a parfois donné un cours en tant qu’auxiliaire, et elle a été de facto conseillère de deux excellents étudiants au doctorat, Leonard Adleman et Kenneth Manders. Robinson a défié la prédiction du médecin selon laquelle elle ne vivrait pas jusqu’à l’âge de quarante ans, mais à son quarante et unième anniversaire, son cœur endommagé l’avait rapprochée du statut d’invalide. Elle a été sauvée par une intervention chirurgicale qui n’était disponible que récemment et qui a grandement amélioré sa situation, lui permettant de mener une vie active pendant vingt-cinq ans supplémentaires.
Son travail exceptionnel a été reconnu par son élection en 1975 à l’Académie nationale des sciences, la première femme à être élue à la section de mathématiques. La même année, on lui a finalement proposé un poste de professeur à l’Université de Californie à Berkeley.
À sa demande, il s’agissait d’un rendez-vous trimestriel. Une bourse MacArthur est venue en 1983. Elle a été élue présidente de l’American Mathematical Society pour 1983-1984, la première femme à occuper ce poste. Malheureusement, elle n’a pas pu terminer son mandat. On a découvert qu’elle souffrait de leucémie au cours de l’été 1984. Après une brève rémission, Julia Robinson est décédée de la maladie le 30 juillet 1985.
BIBLIOGRAPHIE
TRAVAUX DE ROBINSON
« Problèmes de définissabilité et de décision en Arithmétique. »Journal of Symbolic Logic 14 (1949): 98-114. C’était la thèse de Robinson. » Fonctions récursives générales. »Proceedings of the American Mathematical Society 1 (1950): 703-718. En plus de la caractérisation des fonctions calculables d’un argument décrit ci-dessus, de nombreux autres résultats intéressants sont discutés dans cet article. « Définissabilité existentielle en Arithmétique. »Transactions of the American Mathematical Society 72 (1952): 437-449. Un article fondamental dans lequel il a été démontré que ce qui est devenu J.R. impliquait la définissabilité existentielle des puissances de 2, des nombres premiers et, en fait, de la fonction exponentielle complète.
Avec Martin Davis et Hilary Putnam. »Le problème de décision pour les Équations Diophantiennes exponentielles. »Annales de mathématiques 74 (1961): 425-436. C’est dans cet article qu’il a été prouvé que J.R. implique la non-résolvabilité du dixième problème de Hilbert. « Une introduction aux Fonctions hyperarithmétiques. »Journal of Symbolic Logic 32 (1967): 325-342. Ce fut la seule excursion de Robinson dans le très intransigeant.
Avec Yuri Matiyasevich. » Réduction d’une Équation Diophantienne Arbitraire à Une Inconnue sur 13. » Acta Arithmetica 27 (1975): 521-553. Virtuose de la théorie des nombres! Avec Martin Davis et Yuri Matiyasevich. » Le dixième Problème de Hilbert. Équations Diophantiennes: Aspects positifs d’une Solution Négative. »Dans Les Développements mathématiques découlant des problèmes de Hilbert, édité par Felix Browder. Providence, RI : Société mathématique américaine, 1976.
Proceedings of Symposia in Pure Mathematics 28 (1976): 323-378. Une étude de la preuve de l’inviolabilité du dixième problème de Hilbert ainsi que des développements mathématiques qui en découlent par trois des quatre mathématiciens dont les travaux ont conduit à cette preuve.
Les Œuvres rassemblées de Julia Robinson. Édité par Solomon
Feferman. Providence, RI : Société mathématique américaine, 1996. Les vingt-cinq publications de Robinson sont réimprimées ici dans leur intégralité. En outre, il y a le bel essai biographique sur elle écrit par Feferman pour l’Académie nationale des Sciences.
AUTRES SOURCES
Davis, Martin. « Le Dixième Problème De Hilbert Est Insoluble. »
American Mathematical Monthly 80 (1973): 233-269; réimprimé en annexe dans Computability and Unsolvability, édité par Martin Davis. New York : Douvres, 1983. Un essai primé par Steele qui offre la preuve complète de l’inviolabilité du dixième problème de Hilbert. La réimpression de Douvres est l’un des premiers traitements de longueur de livre de la théorie de la calculabilité.
—, et Reuben Hersh. » Le dixième Problème de Hilbert. »
Scientific American 229 (novembre 1973): 84-91. Réimprimé dans Les Journaux Chauvenet, Vol. 2, édité par J. C. Abbott. Washington, DC: Association mathématique d’Amérique, 1978. Un article lauréat du prix Chauvenet destiné au grand public.
Matiyasevich, Yuri. » Ma collaboration avec Julia Robinson. »
The Mathematical Intelligencer 14 (1992): 38-45. Son histoire raconte comment une jeune Russe et une Américaine beaucoup plus âgée en sont venues à produire ensemble des mathématiques élégantes.
———. Le Dixième Problème de Hilbert. Cambridge, MA: MIT Press,
1993. Une excellente introduction et enquête adaptée aux majors de mathématiques de premier cycle, avec une bibliographie très inclusive.
Reid, Constance. Julia, une vie en mathématiques. Washington, DC:
Association mathématique d’Amérique, 1996. Par la sœur de Robinson, il contient des photographies, la biographie utile de Reid, intitulée « L’autobiographie de Julia Robinson », et une brève note de Martin Davis sur son travail avec Hilary Putnam.
Martin Davis
