(b. St. Louis, Missouri, 8 Dezember 1919; d. Berkeley, Kalifornien, 30 Juli 1985), Mathematik, mathematische Logik, Zahlentheorie, Entscheidungsprobleme, Definierbarkeit.
Robinsons mathematische Arbeit zeigt Kraft und Charme. Sie packte schwierige Probleme an und strebte nach eleganten Lösungen. Ihr Leben und Werk kann nicht richtig gesehen werden, ohne zu bemerken, dass sie als Frau in einem von Männern dominierten Bereich so etwas wie eine Pionierin war. Ihr Métier war die Schnittstelle zwischen zwei Zweigen der Mathematik, der Logik und der Zahlentheorie, die normalerweise wenig miteinander zu tun hatten. Sie ist besonders bekannt für ihre Beiträge zur Lösung des zehnten Problems in einer berühmten Liste von dreiundzwanzig, die der Mathematiker David Hilbert 1900 vorschlug. Sie wurde gewählt, um die National Academy of Sciences und auch auf die Präsidentschaft der American Mathematical Society, in beiden Fällen die erste weibliche Mathematiker zu werden, so geehrt, und war auch ein Empfänger eines MacArthur Fellowship.
Frühes Leben Die geborene Julia Bowman erlitt früh im Leben zwei Katastrophen. Sie war erst zwei Jahre alt, als ihre Mutter starb und ihr Vater mit Julia und ihrer älteren Schwester Constance fertig wurde. Nach seiner Wiederverheiratung zog die Familie nach Westen, schließlich nach San Diego, wo ihre Stiefschwester Billie geboren wurde. Als Julia neun Jahre alt war, erlitt sie eine verheerende Krankheit: Scharlach, gefolgt von rheumatischem Fieber. Sie verpasste zwei Schuljahre und erlitt sehr schwere Herzschäden. Akademisch brillierte sie und machte bald ihren verlorenen Boden gut. In der High School war sie das einzige Mädchen, das die Kurse für fortgeschrittene Naturwissenschaften und Mathematik belegte und mit einer Reihe von Auszeichnungen abschloss. Im Jahr 1936 trat sie in San Diego State College, mit Schwerpunkt Mathematik. Auf der Suche nach weiteren Ausblicken wechselte sie für ihr Abschlussjahr an die University of California in Berkeley. Unter den fünf Mathematikkurse nahm sie in diesem Jahr war ein auf der Theorie der Zahlen gelehrt von Raphael Robinson. Beeindruckt von ihren Fähigkeiten überzeugte er sie, ihr Studium als Doktorandin fortzusetzen. Raphael war ein Mathematiker von breiten Interessen und Wissen und ein idealer Mentor. Aber bald wurde ihre Beziehung persönlicher und sie heirateten im Dezember 1941. Ihre Hoffnungen, eine Familie zu gründen, wurden zunichte gemacht, als Julia eine Fehlgeburt erlitt und von einem Arzt gewarnt wurde, dass eine Schwangerschaft aufgrund ihres schwer geschädigten Herzens äußerst gefährlich sein würde. Seine Meinung war, dass sie wahrscheinlich sterben würde, bevor sie vierzig war. Um Julia zu helfen, die tiefe Depression zu überwinden, in die sie geschleudert wurde, ermutigte Raphael sie, Trost in der Mathematik zu suchen.
Mathematischer Hintergrund In den 1930er Jahren gab es revolutionäre Entwicklungen auf dem alten Gebiet der Logik, die sich drastisch von dem traditionellen Gebiet des Aristoteles unterschieden. Kurt Gödels berühmter Unvollständigkeitssatz hatte auf die inhärenten Einschränkungen formaler Logiksysteme bei der Verkapselung der mathematischen Praxis hingewiesen. Arbeiten von Alonzo Church, Alan Turing und Emil Post sowie Gödel selbst hatten gezeigt, dass die Frage nach der Existenz algorithmischer Lösungen für spezifische mathematische Probleme präzise formuliert werden konnte. Dies eröffnete die Möglichkeit, dass in bestimmten Fällen solche algorithmischen Lösungen möglicherweise nicht existieren und dass dies in solchen Fällen sogar bewiesen werden könnte. Alfred Tarski hatte erklärt, wie man semantische Begriffe von Wahrheit und Definierbarkeit formaler Sprachen definiert. Dies waren die Entwicklungen, die den Kontext von Julia Robinsons Forschung bildeten.
Jeder bestimmte Zweig der Mathematik wird Symbole verwenden, um für die bestimmten Operationen und Beziehungen zu stehen, die für dieses Fach von grundlegender Bedeutung sind. Zusätzlich zu solchen Symbolen verwendet die moderne mathematische Logik die Sonderzeichen
zusammen mit dem bekannten = -Zeichen. Man spricht von diesen Symbolen zusammen mit denen, die einem bestimmten Zweig der Mathematik entsprechen, als eine Sprache konstituierend. Julia Robinsons Arbeit war weitgehend im Kontext der Sprache der Arithmetik, die die beiden Symbole + und × für Addition bzw. Multiplikation sowie Symbole für 0 und 1 verwendet. Buchstaben des Alphabets werden als Variablen verwendet, und im Falle der Sprache der Arithmetik werden sie normalerweise so verstanden, dass sie über die bekannten natürlichen Zahlen 0,1,2 variieren …… So drückt zum Beispiel der „Satz“
den wahren Satz aus, dass das Addieren von zwei ungeraden Zahlen eine gerade Zahl ergibt. Die Formel (u)(x = u + u+ 1)> selbst definiert die Menge der ungeraden Zahlen, dh wenn x durch eine bestimmte natürliche Zahl ersetzt wird, ist der resultierende Satz genau dann wahr, wenn diese Zahl ungerade ist. Fragen der Definierbarkeit und der Existenz von Algorithmen waren für Robinsons Arbeit von grundlegender Bedeutung.
Eine Menge natürlicher Zahlen S wird als berechenbar (oder rekursiv) bezeichnet, wenn es einen Algorithmus gibt, der für eine gegebene natürliche Zahl n bestimmen kann, ob n zu S gehört oder nicht. Eine Menge natürlicher Zahlen wird als aufzählbar (der von Julia Robinson bevorzugte Begriff) oder rekursiv aufzählbar bezeichnet, wenn es einen Algorithmus zum systematischen Erstellen einer Liste der Mitglieder von S gibt. Diese Fragen waren auch in Robinsons Arbeit sehr wichtig.
Julia Robinsons Dissertation In einem Seminar unter der Leitung des charismatischen Alfred Tarski, einem der großen Logiker des zwanzigsten Jahrhunderts, fand Robinson ihr Métier. Tarski hatte seine Heimat Polen im August 1939 auf einer kurzen Reise verlassen, um an einer Konferenz in den Vereinigten Staaten teilzunehmen, kurz bevor der deutsche Einmarsch in Polen den Zweiten Weltkrieg auslöste. Tarski stellte eine Reihe ungelöster Fragen zur Definierbarkeit in der Sprache der Arithmetik, zu der Robinson hingezogen wurde. In den 1940er Jahren war bekannt, dass es keinen Algorithmus gibt, um zu bestimmen, ob ein bestimmter Satz in der Sprache der Arithmetik mit den Variablen, die über die natürlichen Zahlen reichen, wahr ist. Wie man sagt, ist dies ein algorithmisch unlösbares Problem. Tarski wollte wissen, ob dasselbe gilt, wenn in derselben Sprache Variablen über alle rationalen Zahlen anstatt nur über die natürlichen Zahlen reichen dürfen. (Die rationalen Zahlen sind diejenigen, die als Brüche m / n oder -m / n ausgedrückt werden können, wobei m eine natürliche Zahl und n eine natürliche Zahl ungleich Null ist.) Es wurden Techniken entwickelt, um ein solches „Entscheidungsproblem“ auf ein anderes zu „reduzieren“. In diesem Fall würde man zeigen, dass, wenn es einen Algorithmus zum Testen der Wahrheit eines Satzes der Sprache der Arithmetik gäbe, bei dem die Variablen dazu gezwungen wären, über die rationalen Zahlen zu variieren, ein solcher Algorithmus verwendet werden könnte, um einen Algorithmus bereitzustellen, der dasselbe tut, wenn die Variablen reichen über die natürlichen Zahlen. Da es also keinen solchen Algorithmus für letzteres gibt, würde daraus folgen, dass es auch keinen für ersteres geben könnte.
Das Hauptergebnis von Robinsons Dissertation war eine explizite Formel in der Sprache der Arithmetik, bei der die Variablen über die rationalen Zahlen variieren müssen und die genau die Menge der ganzen Zahlen definiert (dh die Menge der natürlichen Zahlen und ihre Negative). Daraus folgte, dass das Problem der Bestimmung der Wahrheit eines Satzes der Arithmetik auch dann unlösbar bleibt, wenn die Variablen über den rationalen Zahlen liegen. Andere Unlösbarkeitsergebnisse folgten ebenfalls. Robinsons Ansatz war kompliziert, elegant und genial, wobei er einige ziemlich tiefe Ideen aus der Zahlentheorie verwendete.
Elegante Charakterisierungen Robinson suchte immer Eleganz und Einfachheit in ihrer mathematischen Arbeit. Eine ihrer frühen Arbeiten zeigte, wie man auf besonders einfache Weise die algorithmisch berechenbaren Funktionen (auch rekursive Funktionen genannt) charakterisiert, die die natürlichen Zahlen in sich selbst abbilden. Ihre schöne Charakterisierung beinhaltet zwei Anfangsfunktionen und drei Operationen zum Erhalten neuer Funktionen aus gegebenen Funktionen. Eine der Anfangsfunktionen ist nur die Nachfolgefunktion S(x)= x+1. Der andere, den Robinson E nennt, ist definiert als die Differenz zwischen einer gegebenen Zahl und dem größten perfekten Quadrat, das sie nicht überschreitet. (Also E(19) = 19 – 16 = 3 und E(25) = 25 -25 = 0.) Die drei Operationen sind wie folgt: (1) Erhalten Sie aus gegebenen Funktionen F und G die Funktion H (x) = F (G (x)); (2) erhalten Sie aus gegebenen Funktionen F und G die Funktion H (x) = F (x) + G (x); und (3) erhalten Sie aus einer gegebenen Funktion F, deren Werte alle natürlichen Zahlen enthalten, die Funktion H, wobei H (x) die kleinste Zahl t ist, für die F (t) = x ist.
Es ist wirklich bemerkenswert, dass alle berechenbaren Funktionen (von den natürlichen Zahlen bis zu den natürlichen Zahlen) erhalten werden können, indem man mit den beiden Anfangsfunktionen beginnt und diese drei Operationen immer wieder anwendet.
Viel später zeigte Robinson die gleiche Eleganz und Verve bei der Suche nach neuen Charakterisierungen einer Domäne, die weit vom Berechenbaren entfernt war. Die Existenz einer listenbaren Menge K, die nicht berechenbar ist, wurde bereits erwähnt. Es gibt also keinen Algorithmus zur Bestimmung der Mitgliedschaft in K. Durch die Berücksichtigung von Mengen, die von Algorithmen aufgelistet werden können, die Zugriff auf Mitgliedschaftsinformationen über solche Mengen haben (metaphorisch über ein „Orakel“), können zusätzliche Mengen in die Falte gebracht werden, und dieser Prozess kann iteriert werden. Indem diese Iteration beliebig oft durchgeführt werden kann, erweisen sich die erhaltenen Mengen als genau die als arithmetisch bezeichneten Mengen, die in der Sprache der Arithmetik mit Variablen definiert werden können, die über die natürlichen Zahlen reichen. Aber hier muss man nicht aufhören. Man kann eine nicht-arithmetische Menge definieren und diese dann als „Orakel“ verwenden, um noch mehr Mengen aufzulisten. Es gibt einen natürlichen Ort, an dem dieser Prozess zu Ende geht, und die so erhaltenen Mengen natürlicher Zahlen werden als hyperarithmetisch bezeichnet. Es war dieses verdünnte Reich, für das Robinson eine einfache und direkte Charakterisierung lieferte.
Existenzielle Definierbarkeit und Hilberts zehntes Problem Die Arbeit, für die Julia Robinson am meisten in Erinnerung ist, entstand mit einem scheinbar einfachen Problem von Alfred Tarski. Tarski wollte wissen, welche Mengen natürlicher Zahlen durch Formeln der Sprache der Arithmetik definierbar sind, wenn die Symbole und ausgeschlossen sind. Er nannte solche Mengen existenziell definierbar und schlug das Problem vor, zu beweisen, dass die Menge {1,2,4,8,16, ….} von Potenzen von 2 ist nicht existentiell definierbar. Das war genau die Art von Problem, die Robinson mochte. Der Begriff der existenziellen Definierbarkeit könnte leicht als eng mit Problemen verwandt angesehen werden, die Zahlentheoretiker untersuchen, sogenannte Diophantische Probleme. Diese haben typischerweise mit einer Polynomgleichung p(a, x, y, z,u, v,w,….) = 0 mit ganzzahligen Koeffizienten, wobei a ein Parameter ist und x, y, z, u,v,w,…. sind „Unbekannte.“ (Denken Sie daran, dass ein solches Polynom nur die Summe von Begriffen wie 5a3x2v5 und -7a4x3z6 ist.) Für bestimmte diophantische Gleichungen dieser Art versuchen Zahlentheoretiker zu bestimmen, für welche natürlichen Zahlenwerte des Parameters a die Gleichung natürliche Zahlenlösungen in den Unbekannten aufweist. Nun ist durch einfache Standardmethoden leicht zu erkennen, dass eine Menge natürlicher Zahlen S genau dann existenziell definierbar ist, wenn es eine Polynomgleichung dieser Art gibt, so dass S genau die Menge von Werten des Parameters ist, für die die Gleichung natürliche Zahlenlösungen hat. Aus diesem Grund werden existentiell definierbare Mengen auch als Diophantin bezeichnet, und dies ist der Begriff, der in der späteren Literatur verwendet wurde.
Da es Robinson nicht gelang, Tarskis Vermutung zu beweisen, dass die Menge der Potenzen von 2 nicht diophantin ist, begann er die Möglichkeit in Betracht zu ziehen, dass Tarskis Vermutung falsch gewesen sein könnte. Um irgendwelche Fortschritte zu machen, musste sie eine bestimmte Hypothese annehmen, die zu dieser Zeit unbewiesen war und J.R. hieß; grob gesagt J.R. besagt, dass es eine diophantische Gleichung mit zwei Parametern a,b mit der Eigenschaft gibt, dass die Paare (a, b), für die die Gleichung Lösungen hat, so sind, dass b exponentiell als Funktion von a wächst. Es ist leicht zu erkennen, dass alle diophantischen Mengen listenfähig sind, aber jetzt fragte sie sich, ob das Gegenteil wahr sein könnte, ob alle listenfähigen Mengen diophantisch sein könnten. Sie wusste, dass dies tiefgreifende Konsequenzen haben würde.
Um das neue Jahrhundert zu begrüßen, schlug der große Mathematiker David Hilbert 1900 eine Liste von dreiundzwanzig Problemen vor, die als Herausforderung dienen sollten. Der zehnte auf seiner Liste bestand darin, einen Algorithmus bereitzustellen, um zu bestimmen, ob eine gegebene polynomische diophantische Gleichung Lösungen aufweist. Wenn tatsächlich alle auflistbaren Mengen diophantisch wären, erkannte sie, dass es insbesondere eine nicht berechenbare diophantische Menge geben würde, was impliziert, dass es keinen Algorithmus geben könnte, wie ihn Hilbert verlangt hatte. Dies würde eine negative Lösung des zehnten Problems von Hilbert darstellen.
Im Sommer 1959 erhielt Robinson per Post einen Vorabdruck eines Papiers von Martin Davis und Hilary Putnam. Das Papier enthielt einen Beweis dafür, dass, unter der Annahme J.R., alle listable Sets sind in der Tat Diophantin. Der Beweis hatte jedoch eine wichtige Lücke. Es nutzt die Tatsache, dass es beliebig lange Sequenzen von Primzahlen mit der besonderen Eigenschaft gibt, dass die Differenz zwischen aufeinanderfolgenden Termen der Sequenz konstant ist. Obwohl dies wahr ist, war es 1959 nur eine Hypothese; es wurde erst 2004 bewiesen. Robinson kannte die früheren Arbeiten von Davis und Putnam sehr gut und zeigte sich überrascht und erfreut über ihre Leistung. In sehr kurzer Zeit zeigte sie, wie man auf die zusätzliche Hypothese über Primzahlen verzichten kann, und fand sogar eine kurze Version des Beweises. Um die erwartete negative Lösung von Hilberts zehntem Problem zu erhalten, musste nur noch J.R.
Dies wurde im Januar 1970 vom zweiundzwanzigjährigen Yuri Matiyasevich unter Verwendung der berühmten Fibonacci-Sequenz 1,1,2,3,5,8,13,…. Er fand eine diophantische Gleichung mit zwei Parametern a,b , die er beweisen konnte, hat Lösungen nur für den Fall, dass b die Fibonacci-Zahl an der 2a-ten Stelle in dieser Sequenz ist. Da die Fibonacci-Zahlen exponentiell wachsen, war dies ein Beweis dafür, dass J.R. Robinson von Matiyasevichs genialem Beweis begeistert war und nach Leningrad reiste, wo sich ihre Familien trafen. Ihre Zusammenarbeit war fruchtbar; Gemeinsam konnten sie zeigen, dass Hilberts zehntes Problem selbst für Gleichungen in 13 Unbekannten unlösbar ist. (Später konnte Matiyasevich die Zahl auf 9 reduzieren.)
Coda Die an der University of California geltenden „Nepotismus“ -Regeln hätten Robinson einen regelmäßigen Fakultätstermin unmöglich gemacht, solange ihr Ehemann an der Fakultät war. In jedem Fall kann es gut sein, dass ihre gesundheitlichen Probleme eine Vollzeitstelle ausgeschlossen hätten. Sie unterrichtete gelegentlich einen Kurs als Hilfskraft und war de facto Beraterin von zwei hervorragenden Doktoranden, Leonard Adleman und Kenneth Manders. Robinson widersetzte sich der Vorhersage des Arztes, dass sie nicht vierzig werden würde, aber an ihrem einundvierzigsten Geburtstag hatte ihr geschädigtes Herz sie dem Invaliditätsstatus nahe gebracht. Sie wurde durch einen erst kürzlich verfügbaren chirurgischen Eingriff gerettet, der ihre Situation erheblich verbesserte und es ihr ermöglichte, weitere fünfundzwanzig Jahre ein aktives Leben zu führen.
Ihre herausragende Arbeit wurde durch ihre Wahl 1975 in die National Academy of Sciences anerkannt, die erste Frau, die in die Mathematikabteilung gewählt wurde. Im selben Jahr wurde ihr schließlich eine Professur an der University of California in Berkeley angeboten.
Auf ihren Wunsch war es ein Vierteltermin. Ein MacArthur-Stipendium kam 1983. Sie wurde zur Präsidentin der American Mathematical Society für 1983-1984, die erste Frau, die dieses Amt innehatte. Tragischerweise konnte sie ihre Amtszeit nicht beenden. Im Sommer 1984 erkrankte sie an Leukämie. Nach einer kurzen Remission starb Julia Robinson am 30.Juli 1985 an der Krankheit.
BIBLIOGRAPHIE
WERKE VON ROBINSON
„Definierbarkeit und Entscheidungsprobleme in der Arithmetik.“ Zeitschrift für symbolische Logik 14 (1949): 98-114. Dies war Robinsons Dissertation. „Allgemeine rekursive Funktionen.“ Proceedings der American Mathematical Society 1 (1950): 703-718. Neben der oben beschriebenen Charakterisierung berechenbarer Funktionen eines Arguments werden in diesem Artikel viele andere interessante Ergebnisse diskutiert. „Existenzielle Definierbarkeit in der Arithmetik.“ Transaktionen der American Mathematical Society 72 (1952): 437-449. Ein grundlegendes Papier, in dem gezeigt wurde, dass das, was als JR bezeichnet wurde, die existenzielle Definierbarkeit der Potenzen von 2, der Primzahlen und tatsächlich der vollständigen Exponentialfunktion impliziert.
Mit Martin Davis und Hilary Putnam.“Das Entscheidungsproblem für exponentielle diophantische Gleichungen.“ Annalen der Mathematik 74 (1961): 425-436. In dieser Arbeit wurde bewiesen, dass J.R. impliziert die Unlösbarkeit von Hilberts zehntem Problem. „Eine Einführung in hyperarithmetische Funktionen.“ Zeitschrift für symbolische Logik 32 (1967): 325-342. Dies war Robinsons ein Ausflug in die sehr uncomputable.
Mit Juri Matijasewitsch. „Reduktion einer beliebigen diophantischen Gleichung auf eine von 13 Unbekannten.“ Acta Arithmetica 27 (1975): 521-553. Virtuose Zahlentheorie! Mit Martin Davis und Yuri Matiyasevich. „Hilberts zehntes Problem. Diophantische Gleichungen: Positive Aspekte einer negativen Lösung.“ In Mathematical Developments Arising from Hilbert Problems, herausgegeben von Felix Browder. Providence, RI: Amerikanische Mathematische Gesellschaft, 1976.
Verfahren der Symposien in der Reinen Mathematik 28 (1976): 323-378. Ein Überblick über den Beweis für die Unlösbarkeit von Hilbert’s zehnten Problem sowie der mathematischen Entwicklungen, die sich aus ihm von drei der vier Mathematiker, deren Arbeit führte zu diesem Beweis.
Die gesammelten Werke von Julia Robinson. Herausgegeben von Solomon
Feferman. Providence, RI: Amerikanische Mathematische Gesellschaft, 1996. Alle fünfundzwanzig Veröffentlichungen von Robinson werden hier vollständig nachgedruckt. Darüber hinaus gibt es den schönen biografischen Aufsatz über sie, den Feferman für die National Academy of Sciences geschrieben hat.
ANDERE QUELLEN
Davis, Martin. „Hilberts zehntes Problem ist unlösbar.“
American Mathematical Monthly 80 (1973): 233-269; nachgedruckt als Anhang in Computability and Unsolvability, herausgegeben von Martin Davis. New York: Dover, 1983. Ein mit dem Steele-Preis ausgezeichneter Aufsatz, der den vollständigen Beweis für die Unlösbarkeit von Hilberts zehntem Problem bietet. Der Dover-Nachdruck ist eine der ersten buchlangen Behandlungen der Berechenbarkeitstheorie.
—, und Reuben Hersh. „Hilberts zehntes Problem.“
Scientific American 229 (November 1973): 84-91. Veröffentlicht in: The Chauvenet Papers, Vol. 2, herausgegeben von J. C. Abbott. Washington, DC: Mathematische Vereinigung von Amerika, 1978. Ein mit dem Chauvenet-Preis ausgezeichneter Artikel für die breite Öffentlichkeit.
Matijasewitsch, Juri. „Meine Zusammenarbeit mit Julia Robinson.“
Der mathematische Intelligenzgeber 14 (1992): 38-45. Seine Geschichte, wie ein junger Russe und eine viel ältere Amerikanerin kamen, um gemeinsam elegante Mathematik zu produzieren.
———. Hilberts zehntes Problem. Cambridge, MA: MIT Press,
1993. Eine ausgezeichnete Einführung und Umfrage geeignet für Bachelor-Mathematik Majors, mit einer sehr umfassenden Bibliographie.
Reid, Konstanz. Julia, ein Leben in Mathematik. Washington, DC:
Mathematische Vereinigung von Amerika, 1996. Von Robinsons Schwester, es hat Fotografien, Reids nützliche Biographie, mit dem Titel „Die Autobiographie von Julia Robinson,Und eine kurze Notiz von Martin Davis über seine Arbeit mit Hilary Putnam.
Martin Davis
