(ur. St. Louis, Missouri, 8 grudnia 1919; zm. Berkeley, Kalifornia, 30 lipca 1985) – matematyka, logika matematyczna, teoria liczb, problemy decyzyjne, definiowalność.
matematyczne prace Robinsona wykazują siłę i urok. Stawiała czoła trudnym problemom i dążyła do eleganckich rozwiązań. Jej życie i praca nie mogą być właściwie postrzegane, nie zauważając, że jako kobieta w dziedzinie zdominowanej przez mężczyzn była czymś w rodzaju pionierki. Jej metier był stykiem dwóch gałęzi matematyki, logiki i teorii liczb, Zwykle uważanych za niewiele wspólnego ze sobą. Jest szczególnie znana ze swojego wkładu w rozwiązanie dziesiątego problemu na słynnej liście dwudziestu trzech zaproponowanej przez matematyka Davida Hilberta w 1900 roku. Została wybrana do National Academy of Sciences, a także do prezydentury American Mathematical Society, w obu przypadkach pierwszą kobietą matematykiem, który został tak uhonorowany, a także był stypendystą MacArthur Fellowship.
Wczesne życie Urodzona Julia Bowman, cierpiała dwie klęski na początku życia. Miała tylko dwa lata, gdy zmarła jej matka, pozostawiając ojca Julii i jej starszej siostrze Konstancji. Po powtórnym ślubie rodzina przeniosła się na zachód, ostatecznie do San Diego, gdzie urodziła się jej przyrodnia siostra Billie. Gdy Julia miała dziewięć lat przeszła wyniszczającą chorobę: szkarlatynę, a następnie gorączkę reumatyczną. Opuściła dwa lata szkoły i doznała bardzo poważnych uszkodzeń serca. Pod względem akademickim była znakomita i wkrótce nadrobiła stratę. W liceum była jedyną dziewczyną, która uczęszczała na zaawansowane kursy z zakresu nauk ścisłych i matematyki i ukończyła je z szeregiem wyróżnień. W 1936 roku wstąpiła do San Diego State College, specjalizując się w matematyce. Szukając szerszych perspektyw, przeniosła się na Uniwersytet Kalifornijski w Berkeley na ostatni rok. Wśród pięciu kursów matematyki, które odbyła w tym roku był jeden na teorii liczb prowadzonych przez Raphaela Robinsona. Pod wrażeniem jej umiejętności, przekonał ją do kontynuowania studiów jako absolwentka. Rafał był matematykiem o szerokich zainteresowaniach i wiedzy oraz idealnym mentorem. Wkrótce jednak ich związek stał się bardziej osobisty i pobrali się w grudniu 1941 roku. Ich nadzieje na założenie rodziny zostały zerwane, gdy Julia poroniła i została ostrzeżona przez lekarza, że z powodu jej poważnie uszkodzonego serca ciąża będzie niezwykle niebezpieczna. Jego zdaniem prawdopodobnie umrze zanim skończy czterdzieści lat. Aby pomóc Julii przezwyciężyć głęboką depresję, w którą została rzucona, Rafał zachęcał ją do szukania pocieszenia w matematyce.
Matematyczne tło w latach 30. XX wieku nastąpił rewolucyjny rozwój starożytnego przedmiotu logiki, drastycznie zmieniony od tradycyjnej dziedziny zapoczątkowanej przez Arystotelesa. Słynne twierdzenie Kurta Gödla o niekompletności wskazywało na nieodłączne ograniczenia formalnych systemów logiki w hermetyzacji praktyki matematycznej. Prace Alonzo Churcha, Alana Turinga i Emila Posta oraz samego Gödla pokazały, że kwestia istnienia algorytmicznych rozwiązań konkretnych problemów matematycznych może być precyzyjnie sformułowana. Otworzyło to możliwość, że w konkretnych przypadkach takie algorytmiczne rozwiązania mogą nie istnieć, a nawet, że w takich przypadkach może to zostać udowodnione. Alfred Tarski wyjaśnił, jak definiować semantyczne pojęcia prawdy i definiowalność języków formalnych. Były to wydarzenia, które stanowiły kontekst badań Julii Robinson.
każda konkretna gałąź matematyki będzie używać symboli do oznaczania poszczególnych operacji i relacji, które są fundamentalne dla tego przedmiotu. Oprócz takich symboli, nowoczesna Logika matematyczna używa specjalnych symboli
wraz ze znanym znakiem=. Mówi się o tych symbolach wraz z tymi, które odpowiadają danej gałęzi matematyki jako stanowiące język. Prace Julii Robinson były w dużej mierze w kontekście języka arytmetyki, który używa dwóch symboli + i × dla dodawania i mnożenia, odpowiednio, a także symboli dla 0 i 1. Litery alfabetu są używane jako zmienne, a w przypadku języka arytmetyki są one zwykle rozumiane jako różne w stosunku do znanych liczb naturalnych 0,1,2…… więc na przykład „zdanie”
wyraża prawdziwe twierdzenie, że dodanie dwóch nieparzystych liczb daje liczbę parzystą. Formuła (U) (x = U+u+1)> sama definiuje zbiór liczb nieparzystych, tzn. jeśli x zostanie zastąpione przez konkretną liczbę naturalną, wynikowe zdanie będzie prawdziwe wtedy i tylko wtedy, gdy ta liczba jest nieparzysta. Kwestie definiowalności i istnienia algorytmów były fundamentalne dla pracy Robinsona.
zbiór liczb naturalnych S nazywa się obliczalnym (lub rekurencyjnym), jeśli istnieje algorytm, który może określić dla danej liczby naturalnej n, czy n należy do S. zbiór liczb naturalnych nazywa się listowalnym (termin preferowany przez Julię Robinson) lub rekurencyjnie wyliczalnym, jeśli istnieje algorytm systematycznego tworzenia listy członków S. wszystkie wyniki nierozwiązalności można uznać za konsekwencje twierdzenia klucza: istnieje zestaw listowalny, który nie jest obliczalny. Sprawy te były również bardzo ważne w pracy Robinsona.
rozprawa Julii Robinson To właśnie w seminarium prowadzonym przez charyzmatycznego Alfreda Tarskiego, jednego z wielkich logików XX wieku, Robinson znalazł jej metier. Tarski opuścił rodzimą Polskę w sierpniu 1939 r.w czasie krótkiej podróży na konferencję w Stanach Zjednoczonych, tuż przed niemiecką inwazją na Polskę, która przyspieszyła II Wojnę Światową. Tarski postawił szereg nierozwiązanych pytań o definiowalność w języku arytmetyki, do którego przyciągnął Robinsona. Do lat czterdziestych XX wieku wiadomo było, że nie istnieje algorytm pozwalający ustalić, czy dane zdanie w języku arytmetyki, ze zmiennymi przechodzących przez liczby naturalne, jest prawdziwe. Jak mówi się, jest to problem algorytmicznie nierozwiązywalny. Tarski chciał wiedzieć, czy to samo jest prawdziwe, gdy w tym samym języku zmienne mogą przechodzić przez wszystkie liczby wymierne, a nie tylko liczby naturalne. (Liczby wymierne to te, które można wyrazić jako ułamki m / N lub-M / N, gdzie M jest liczbą naturalną, a n jest niezerową liczbą naturalną.) Opracowano techniki „redukcji” jednego takiego „problemu decyzyjnego” do drugiego. W tym przypadku można by pokazać, że gdyby istniał algorytm do testowania na prawdę zdanie języka arytmetyki ze zmiennymi ograniczonymi do różnic w liczbach wymiernych, taki algorytm mógłby być użyty do dostarczenia algorytmu do zrobienia tego samego, gdy zmienne wahają się nad liczbami naturalnymi. Tak więc, ponieważ nie ma takiego algorytmu dla tego drugiego, wynika z tego, że nie może być ani jednego dla pierwszego.
głównym rezultatem pracy Robinsona była wyraźna formuła w języku arytmetyki, z zmiennymi ograniczonymi do różnic w liczbach wymiernych, która dokładnie definiuje zbiór liczb całkowitych (czyli zbiór liczb naturalnych i ich negatywów). Następnie okazało się, że problem określenia prawdziwości zdania arytmetycznego pozostaje nierozwiązywalny nawet wtedy, gdy zmienne przestawiają się na Liczby wymierne. Następowały również inne wyniki nierozwiązywalności. Podejście Robinsona było skomplikowane, eleganckie i pomysłowe przy użyciu raczej głębokich pomysłów z teorii liczb.
eleganckie charakteryzacje Robinson zawsze poszukiwała elegancji i prostoty w swojej matematycznej pracy. Jedna z jej wczesnych prac pokazała, jak scharakteryzować, w szczególnie prosty sposób, algorytmicznie obliczalne funkcje (zwane również funkcjami rekurencyjnymi), które mapują liczby naturalne w siebie. Jej piękna charakterystyka obejmuje dwie funkcje początkowe i trzy operacje uzyskiwania nowych funkcji z danych funkcji. Jedną z początkowych funkcji jest właśnie następcza funkcja S (x)= x+1. Druga, którą Robinson nazywa E, jest zdefiniowana jako różnica między daną liczbą a największym kwadratem idealnym, który jej nie przekracza. (Zatem E(19) = 19 – 16 = 3 i E(25) = 25 -25 = 0.) Trzy operacje są następujące: (1) z podanych funkcji F I G uzyskaj funkcję H(x)=F(G (x)); (2) z podanych funkcji F I G uzyskaj funkcję H(x)=F(x) + G (x); oraz(3) z danej funkcji f, której wartości obejmują wszystkie liczby naturalne, uzyskaj funkcję H, gdzie H(x) jest najmniejszą liczbą t, dla której F (t)=x.
to naprawdę niezwykłe, że wszystkie funkcje obliczeniowe (od liczb naturalnych do liczb naturalnych) można uzyskać, zaczynając od dwóch funkcji początkowych i stosując te trzy operacje w kółko.
znacznie później Robinson wykazał się tą samą elegancją i werwą w znajdowaniu nowych cech domeny dalekiej od obliczeniowej. O istnieniu wyliczalnego zbioru K, który nie jest obliczalny, już wspomniano. Nie ma więc algorytmu określającego przynależność do K. Rozważając zestawy, które mogą być wymienione przez algorytmy mające dostęp do informacji o takich zestawach (metaforycznie za pośrednictwem” oracle”), można wprowadzić dodatkowe zestawy, a proces ten można iterować. Pozwalając tej iteracji na dowolną skończoną liczbę razy, uzyskane zbiory okazują się dokładnie tymi, które nazywamy arytmetycznymi, zbiorami definiowalnymi w języku arytmetyki o zmiennych przechodzących przez liczby naturalne. Ale nie ma potrzeby, aby zatrzymać się tutaj. Można zdefiniować zbiór Nie-arytmetyczny, a następnie użyć go jako „wyroczni”, aby móc wymienić jeszcze więcej zbiorów. Istnieje naturalne miejsce, w którym proces ten dobiega końca, a tak otrzymane zbiory liczb naturalnych nazywane są hiperarithmeticami. To było to rozrzedzone królestwo, dla którego Robinson przedstawił prostą i bezpośrednią charakterystykę.
Definiowalność egzystencjalna i dziesiąty Problem Hilberta praca, do której najbardziej zapamiętana jest Julia Robinson, powstała z pozornie prostego problemu, jaki postawił Alfred Tarski. Tarski chciał wiedzieć, które zbiory liczb naturalnych można definiować formułami języka arytmetyki, jeśli Symbole i są wykluczone. Nazwał takie zbiory egzystencjalnie definiowalne i zaproponował problem udowodnienia, że zbiór {1,2,4,8,16, … } potęgi 2 nie jest definiowalna egzystencjalnie. Dokładnie taki problem lubił Robinson. Pojęcie definiowalności egzystencjalnej można łatwo uznać za ściśle związane z problemami tego rodzaju, które badają teoretycy liczb, tzw. problemami Diofantycznymi. Zazwyczaj mają one związek z równaniem wielomianowym P(A,x,y,z,u,v,w,….) = 0 ze współczynnikami całkowitymi,gdzie A jest parametrem i x,y,z,u,v, w,…. są ” nieznane.”(Przypomnijmy, że taki wielomian jest tylko sumą wyrażeń takich jak 5a3x2v5 i-7a4x3z6.) Dla poszczególnych równań tego rodzaju teoretycy liczb próbują ustalić, dla których wartości liczb naturalnych parametru a równanie ma rozwiązania liczb naturalnych w niewiadomych. Teraz za pomocą prostych standardowych metod łatwo zauważyć, że zbiór liczb naturalnych S jest definiowalny egzystencjalnie wtedy i tylko wtedy, gdy istnieje równanie wielomianowe tego rodzaju, takie, że S jest dokładnie zbiorem wartości parametru, dla którego równanie ma rozwiązania liczb naturalnych. Z tego powodu zbiory definiowalne egzystencjalnie nazywane są również diofantyną i jest to termin, który został przyjęty w późniejszej literaturze.
Nie udowadniając tezy Tarskiego, że zbiór potęg 2 nie jest Diofantyną, Robinson zaczął rozważać możliwość, że przypuszczenie Tarskiego mogło być błędne. Aby osiągnąć jakikolwiek postęp, musiała przyjąć pewną hipotezę, niesprawdzoną w tym czasie, która została nazwana J. R.; z grubsza mówiąc J. R. stwierdza, że istnieje równanie Diofantyny o dwóch parametrach a, b o własności,że pary (a, b), dla których równanie ma rozwiązania, są takie, że b rośnie wykładniczo jako funkcja a. zakładając J. R. i przeprowadzając złożoną i pomysłową analizę, udowodniła nie tylko, że potęgi 2 są Diofantyną, ale także, że zbiór liczb pierwszych, jak i wiele innych, jest również. Łatwo widać, że wszystkie zestawy Diofantynowe są listowalne, ale teraz zastanawiała się, czy konwersja może być prawdziwa, czy wszystkie zestawy do listy mogą być Diofantynowe. Wiedziała, że to będzie miało głębokie konsekwencje.
w 1900 roku, aby powitać nowy wiek, wielki matematyk David Hilbert zaproponował listę dwudziestu trzech problemów, które mają stanowić wyzwanie. Dziesiąty na jego liście miał dostarczyć algorytm do ustalenia, czy dane wielomianowe równanie Diofantyny ma rozwiązania. Gdyby rzeczywiście wszystkie zbiory listowalne były Diofantyną, zdała sobie sprawę, że w szczególności istniałby niezliczalny zbiór Diofantyny, co sugerowałoby, że nie może istnieć algorytm, o który prosił Hilbert. Stanowiłoby to negatywne rozwiązanie dziesiątego problemu Hilberta.
latem 1959 roku Robinson otrzymał pocztą preprint papieru autorstwa Martina Davisa i Hilary Putnam. Artykuł zawierał dowód, że, zakładając, że J. R., wszystkie listy są rzeczywiście Diofantyną. Jednak dowód miał ważną lukę. Wykorzystał on fakt, że istnieją arbitralnie długie ciągi liczb pierwszych o specjalnej własności, że różnica między kolejnymi wyrazami ciągu jest stała. Chociaż jest to prawdą, w 1959 r.była to tylko hipoteza; udowodniono ją dopiero w 2004 r. Robinson bardzo dobrze znał wcześniejsze prace Davisa i Putnama i wyraził zdziwienie i przyjemność z ich realizacji. W bardzo krótkim czasie pokazała, jak obyć się bez dodatkowej hipotezy o liczbach pierwszych, a nawet znalazła krótką wersję dowodu. Tak więc, aby uzyskać oczekiwane negatywne rozwiązanie dziesiątego problemu Hilberta, pozostało tylko udowodnić J. R.
to zostało osiągnięte w styczniu 1970 roku przez dwudziestodwuletniego Jurija Matijasewicza przy użyciu słynnej sekwencji Fibonacciego 1,1,2,3,5,8,13,…. Znalazł równanie Diofantynowe o dwóch parametrach a i b, które był w stanie udowodnić, że ma rozwiązania w przypadku, gdy B jest liczbą Fibonacciego W 2a-tym miejscu w tym ciągu. Ponieważ liczby Fibonacciego rosną wykładniczo, stanowiło to dowód na to, że J. R. Robinson był zachwycony pomysłowym dowodem Matijasewicza i udał się do Leningradu, gdzie spotkali się ich rodziny. Ich współpraca była owocna; razem byli w stanie pokazać, że dziesiąty problem Hilberta jest nierozwiązywalny nawet dla równań w 13 niewiadomych. (Później Matijasewicz był w stanie zmniejszyć liczbę do 9.)
Coda Zasady” nepotyzmu ” obowiązujące na Uniwersytecie Kalifornijskim uniemożliwiłyby regularne mianowanie Robinsona na wydział tak długo, jak długo jej mąż był na Wydziale. W każdym razie może być tak, że jej problemy zdrowotne wykluczyłyby pełnoetatową posadę. Okazjonalnie prowadziła kurs jako adiunkt, a de facto była doradcą dwóch znakomitych doktorantów, Leonarda Adlemana i Kennetha Mandersa. Robinson sprzeciwił się przewidywaniom lekarza, że nie dożyje czterdziestu lat, ale w czterdziestych pierwszych urodzinach jej uszkodzone serce zbliżyło ją do stanu nieważności. Została uratowana przez zabieg chirurgiczny, który dopiero niedawno stał się dostępny i który znacznie poprawił jej sytuację, umożliwiając jej aktywne życie przez dodatkowe dwadzieścia pięć lat.
jej wybitna praca została uznana przez jej wybór w 1975 do National Academy of Sciences, pierwsza kobieta, która została wybrana do sekcji matematyki. W tym samym roku zaproponowano jej nominację profesorską na University of California w Berkeley.
na jej prośbę była to kadencja. MacArthur Fellowship przyszedł w 1983 roku. Została wybrana na przewodniczącą American Mathematical Society w latach 1983-1984, jako pierwsza kobieta sprawująca ten urząd. Niestety nie udało jej się dokończyć kadencji. Latem 1984 roku wykryto u niej białaczkę. Po krótkiej remisji, Julia Robinson zmarła na chorobę 30 lipca 1985 roku.
Bibliografia
prace Robinsona
„Definiability and Decision Problems in arytmetyka.”Journal of Symbolic Logic 14 (1949): 98-114. To była dysertacja Robinsona. „Ogólne Funkcje Rekurencyjne.”Proceedings of the American Mathematical Society 1 (1950): 703-718. Oprócz opisanej powyżej charakterystyki funkcji obliczeniowych jednego argumentu, w niniejszym artykule omówiono wiele innych interesujących wyników. „Definiowalność egzystencjalna w arytmetyce.”Transactions of the American Mathematical Society 72 (1952): 437-449. Fundamentalny dokument, w którym to, co zostało nazwane J. R., pokazano, że implikuje egzystencjalną definiowalność potęg 2, liczb pierwszych, a właściwie pełnej funkcji wykładniczej.
z Martinem Davisem i Hilary Putnam.”The Decision Problem for Exponential Diophantine Equations.”Annals of Mathematics 74 (1961): 425-436. To właśnie w tej pracy udowodniono, że J. R. implikuje nierozwiązalność dziesiątego problemu Hilberta. „Wprowadzenie do funkcji Hiperaarytmicznych.”Journal of Symbolic Logic 32 (1967): 325-342. To była jedyna wyprawa Robinsona do nieskomplikowanego.
Z Jurijem Matijasewiczem. „Redukcja arbitralnego równania Diofantynowego do jednej na 13 niewiadomych.”Acta Arithmetica 27 (1975): 521-553. Wirtuozowska teoria liczb! Z Martinem Davisem i Jurijem Matijasewiczem. „Dziesiąty Problem Hilberta. Równania diofantynowe: pozytywne aspekty rozwiązania negatywnego.”In Mathematical Developments resulting from Hilbert Problems, edited by Felix Browder. Providence, Ri: American Mathematical Society, 1976.
Proceedings of Sympozjum in Pure Mathematics 28 (1976): 323-378. Badanie dowodu nierozwiązalności dziesiątego problemu Hilberta, jak również rozwoju matematycznego wynikającego z niego przez trzech z czterech matematyków, których praca doprowadziła do tego dowodu.
Dzieła zebrane Julii Robinson. Autor: Salomon
Feferman. Providence, Ri: American Mathematical Society, 1996. Wszystkie dwadzieścia pięć publikacji Robinsona zostało przedrukowanych tutaj w całości. Ponadto istnieje świetny esej biograficzny o niej napisany przez Fefermana dla Narodowej Akademii Nauk.
inne źródła
Davis, Martin. „Dziesiąty Problem Hilberta jest nierozwiązywalny.”
American Mathematical Monthly 80 (1973): 233-269; reprinted as an appendix in Computability and Unsolvability, edited by Martin Davis. New York: Dover, 1983. Wielokrotnie nagradzany esej, który stanowi kompletny dowód nierozwiązalności dziesiątego problemu Hilberta. Przedruk Dover jest jednym z pierwszych zabiegów książki długości teorii obliczeniowej.
—, i Reuben Hersh. „Dziesiąty Problem Hilberta.”
Scientific American 229 (November 1973): 84-91. Reprinted in the Chauvenet Papers, Vol. 2, red. J. C. Abbott. Washington, DC: Mathematical Association of America, 1978. Chauvenet – nagrodzony artykuł przeznaczony dla ogółu wykształconego społeczeństwa.
Matijasewicz, Jurij. „Moja współpraca z Julią Robinson.”
The Mathematical Intelligencer 14 (1992): 38-45. Jego historia o tym, jak Młoda Rosjanka i dużo starsza Amerykanka wspólnie tworzyły elegancką matematykę.
———. Dziesiąty Problem Hilberta. Cambridge, MA: MIT Press,
1993. Doskonałe wprowadzenie i ankieta odpowiednia dla studentów kierunków matematycznych, z bardzo obszerną bibliografią.
Julia, życie z matematyki.
Mathematical Association of America, 1996. Przez siostrę Robinsona zawiera fotografie, przydatną biografię Reida, zatytułowaną „The Autobiography of Julia Robinson”, oraz krótką notatkę Martina Davisa o jego pracy z Hilary Putnam.
Martin Davis
