(N. St. Louis, Missouri, 8 decembrie 1919; d.Berkeley, California, 30 iulie 1985), matematică, logică matematică, teoria numerelor, probleme de decizie, definabilitate.
lucrarea matematică a lui Robinson prezintă putere și farmec. A abordat probleme dificile și s-a străduit să găsească soluții elegante. Viața și munca ei nu pot fi văzute în mod corespunzător fără a observa că, în calitate de femeie într-un domeniu dominat de bărbați, a fost un fel de pionier. Ea era interfața dintre două ramuri ale matematicii, logicii și teoriei numerelor, despre care se credea că au prea puțin de-a face una cu cealaltă. Este cunoscută în special pentru contribuțiile sale la soluționarea celei de-a zecea probleme într-o faimoasă listă de douăzeci și trei propusă de matematicianul David Hilbert în 1900. A fost aleasă la Academia Națională de științe și, de asemenea, la președinția Societatea Americană de matematică, în ambele cazuri prima femeie matematician care a fost atât de onorată și a fost, de asemenea, beneficiară a unei burse MacArthur.
născut Julia Bowman, ea a suferit două calamități devreme în viață. Avea doar doi ani când mama ei a murit, lăsându-l pe tatăl ei să se descurce cu Julia și sora ei mai mare Constance. După recăsătorirea sa, familia s-a mutat spre vest, în cele din urmă la San Diego, unde s-a născut sora ei vitregă Billie. Când Julia avea nouă ani, a suferit o boală devastatoare: scarlatină urmată de febră reumatică. A ratat doi ani de școală și a suferit daune foarte grave inimii. Din punct de vedere academic, a excelat și, în curând, și-a recuperat terenul pierdut. În liceu a fost singura fată care a urmat cursurile de științe avansate și matematică și a absolvit cu o serie de onoruri. În 1936 a intrat în San Diego State College, specializându-se în matematică. Căutând perspective mai largi, s-a transferat la Universitatea din California la Berkeley pentru ultimul an. Printre cele cinci cursuri de matematică pe care le-a urmat în acel an a fost unul Despre teoria numerelor predate de Raphael Robinson. Impresionat de abilitatea ei, el a convins-o să-și continue studiile ca student absolvent. Rafael a fost un matematician cu interese și cunoștințe largi și un mentor ideal. Dar în curând relația lor a devenit mai personală și s-au căsătorit în decembrie 1941. Speranțele lor de a începe o familie au fost spulberate când Julia a suferit un avort spontan și a fost avertizată de un medic că, din cauza inimii sale grav afectate, sarcina ar fi extrem de periculoasă. Părerea lui era că probabil va muri înainte de a împlini patruzeci de ani. Într-un efort de a o ajuta pe Julia să depășească depresia profundă în care a fost aruncată, Raphael a încurajat-o să caute consolare în matematică.
context matematic anii 1930 au văzut evoluții revoluționare în subiectul antic al logicii, schimbat drastic față de domeniul tradițional originar de Aristotel. Faimoasa teoremă a incompletenței lui Kurt G a indicat limitările inerente ale sistemelor formale de logică în încapsularea practicii matematice. Lucrările lui Alonzo Church, Alan Turing și Emil Post, precum și ale lui G. C. D. D. însuși au arătat că problema existenței soluțiilor algoritmice la probleme matematice specifice ar putea primi o formulare precisă. Acest lucru a deschis posibilitatea ca, în cazuri specifice, astfel de soluții algoritmice să nu existe și chiar că, în astfel de cazuri, acest lucru ar putea fi dovedit. Alfred Tarski explicase cum să definească noțiunile semantice de adevăr și definibilitatea limbajelor formale. Acestea au fost evoluțiile care au oferit contextul cercetării lui Julia Robinson.
orice ramură particulară a matematicii va folosi simboluri pentru a reprezenta operațiunile și relațiile particulare care sunt fundamentale pentru acel subiect. În plus față de astfel de simboluri, logica matematică modernă folosește simbolurile speciale
împreună cu semnul familiar=. Se vorbește despre aceste simboluri împreună cu cele corespunzătoare unei anumite ramuri a matematicii ca constituind o limbă. Lucrarea Juliei Robinson a fost în mare parte în contextul limbajului aritmeticii care folosește cele două simboluri + și, respectiv, pentru înmulțire și înmulțire, precum și simboluri pentru 0 și 1. Literele alfabetului sunt folosite ca variabile, iar în cazul limbajului aritmetic, se înțelege de obicei că variază în funcție de numerele naturale familiare 0,1,2 …… deci, de exemplu, „propoziția”
exprimă adevărata propoziție conform căreia adăugarea a două numere impare produce un număr par. Formula (u) (x = u+u+1)> de la sine definește setul de numere impare, adică dacă x este înlocuit cu un anumit număr natural, propoziția rezultată va fi adevărată dacă și numai dacă acel număr este impar. Întrebările de definibilitate și existența algoritmilor au fost fundamentale pentru munca lui Robinson.
un set de numere naturale S se numește calculabil (sau recursiv) dacă există un algoritm care poate determina pentru un anumit număr natural n dacă n aparține sau nu lui S. un set de numere naturale se numește listabil (termenul preferat de Julia Robinson) sau recursiv enumerabil dacă există un algoritm pentru realizarea sistematică a unei liste a membrilor lui S. toate rezultatele nesolvabilității pot fi considerate consecințe ale teoremei cheie: există un set listabil care nu este calculabil. Aceste chestiuni au fost, de asemenea, foarte importante în munca lui Robinson.
disertația Juliei Robinson a fost într-un seminar condus de carismaticul Alfred Tarski, unul dintre marii logicieni ai secolului al XX-lea, că Robinson a găsit-o mai mult. Tarski își părăsise Polonia natală în August 1939 într-o scurtă călătorie pentru a participa la o conferință în Statele Unite, chiar înainte ca invazia germană a Poloniei să precipite al doilea Razboi Mondial. Tarski a pus o serie de întrebări nerezolvate despre definabilitate în limbajul aritmeticii la care a fost atras Robinson. Până în anii 1940 era bine cunoscut faptul că nu există un algoritm care să determine dacă o propoziție dată în limbajul aritmeticii, cu variabilele variind peste numerele naturale, este adevărată. După cum se spune, Aceasta este o problemă de nerezolvat algoritmic. Tarski a vrut să știe dacă același lucru este adevărat atunci când în aceeași limbă, variabilelor li se permite să varieze peste toate numerele raționale în loc de doar numerele naturale. (Numerele raționale sunt cele expresibile ca fracții m/n sau-m / n unde m este un număr natural și n este un număr natural diferit de zero.) Au fost dezvoltate tehnici pentru ” reducerea „unei astfel de” probleme de decizie ” la alta. În acest caz, s-ar arăta că, dacă ar exista un algoritm pentru testarea adevărului, o propoziție a limbajului aritmeticii cu variabilele constrânse să varieze în funcție de numerele raționale, un astfel de algoritm ar putea fi folosit pentru a furniza un algoritm pentru a face același lucru atunci când variabilele variază peste numerele naturale. Deci, din moment ce nu există un astfel de algoritm pentru acesta din urmă, ar rezulta că nici nu ar putea exista unul pentru primul.
rezultatul principal al disertației lui Robinson a fost o formulă explicită în limbajul aritmeticii, cu variabilele constrânse să varieze în funcție de numerele raționale, care definește exact setul de numere întregi (adică setul de numere naturale și negativele lor). Apoi a urmat că problema determinării adevărului unei propoziții de aritmetică rămâne de nerezolvat chiar și atunci când variabilele variază peste numerele raționale. Au urmat și alte rezultate de insolvență. Abordarea lui Robinson a fost complicată, elegantă și ingenioasă folosind câteva idei destul de profunde din teoria numerelor.
caracterizări elegante Robinson a căutat întotdeauna eleganță și simplitate în munca ei matematică. Una dintre lucrările sale timpurii a arătat cum să caracterizeze, într-un mod deosebit de simplu, funcțiile calculabile algoritmic (numite și funcții recursive) care mapează numerele naturale în ele însele. Caracterizarea ei frumoasă implică două funcții inițiale și trei operații pentru obținerea de noi funcții din funcțiile date. Una dintre funcțiile inițiale este doar funcția succesoare S(x)= x+1. Celălalt, pe care Robinson îl numește E, este definit ca diferența dintre un număr dat și cel mai mare pătrat perfect care nu îl depășește. (Astfel E (19) = 19 – 16 = 3 și E(25) = 25 -25 = 0.) Cele trei operații sunt următoarele: (1) din funcțiile date F și G obțin funcția H(x)=F(g(x)); (2) din funcțiile date F și G obțin funcția H(x)=F(x) + G(x); și (3) dintr-o funcție dată f ale cărei valori includ toate numerele naturale obțin funcția H unde H(x) este cel mai mic număr t pentru care F(t)=x.
este cu adevărat remarcabil faptul că toate funcțiile calculabile (de la numerele naturale la numerele naturale) pot fi obținute începând cu cele două funcții inițiale și aplicând aceste trei operații din nou și din nou.
mult mai târziu, Robinson a arătat aceeași eleganță și vervă în găsirea de noi caracterizări ale unui domeniu departe de calculabil. Existența unui set listabil K care nu este calculabil a fost deja menționată. Deci nu există un algoritm pentru determinarea apartenenței la K. Luând în considerare seturile care pot fi listate de algoritmi care au acces la informații de membru despre astfel de seturi (metaforic printr-un „oracol”) seturi suplimentare pot fi aduse în pliu, iar acest proces poate fi iterat. Permițând acestei iterații să apară de orice număr finit de ori, mulțimile obținute se dovedesc a fi exact cele numite aritmetice, mulțimile definibile în limbajul aritmeticii cu variabile variind peste numerele naturale. Dar nu este nevoie să ne oprim aici. Se poate defini un set non-aritmetic și apoi se poate folosi ca „oracol” pentru a putea lista și mai multe seturi. Există un loc natural în care acest proces se încheie, iar seturile de numere naturale astfel obținute sunt numite hiperaritmetice. A fost acest tărâm rarefiat pentru care Robinson a oferit o caracterizare simplă și directă.
Definibilitatea existențială și a zecea problemă a lui Hilbert lucrarea pentru care Julia Robinson este cea mai amintită își are originea într-o problemă aparent simplă pusă de Alfred Tarski. Tarski a vrut să știe ce seturi de numere naturale sunt definibile prin formule ale limbajului aritmeticii dacă simbolurile și sunt excluse. El a numit astfel de seturi definibile existențial și a propus problema dovedirii faptului că setul {1,2,4,8,16, ….} de puteri de 2 nu este existențial definibil. Acesta a fost exact genul de problemă care i-a plăcut lui Robinson. Noțiunea de definibilitate existențială ar putea fi văzută cu ușurință ca fiind strâns legată de probleme de un fel pe care teoreticienii numerelor le studiază, așa-numitele probleme diofantine. Acestea au de obicei de a face cu o ecuație polinomială p (A,x,y,z,u,v, w,….) = 0 cu coeficienți întregi unde A este un parametru și x,y,z,u,v,w,…. sunt „necunoscute”.”(Amintiți-vă că un astfel de polinom este doar suma termenilor precum 5a3x2v5 și-7a4x3z6.) Pentru anumite ecuații diofantine de acest fel, teoreticienii numerelor încearcă să determine pentru ce valori ale numărului natural ale parametrului a, ecuația are soluții de număr natural în necunoscute. Acum, prin metode standard simple, este ușor de văzut că un set de numere naturale S este definibil existențial dacă și numai dacă există o ecuație polinomială de acest fel, astfel încât S este exact setul de valori ale parametrului pentru care ecuația are soluții de numere naturale. Din acest motiv, seturile definibile existențial sunt numite și diofantine, iar acesta este termenul care a fost adoptat în literatura ulterioară.
neavând niciun succes în a dovedi presupunerea lui Tarski că setul de puteri din 2 nu este Diofantin, Robinson a început să ia în considerare posibilitatea ca presupunerea lui Tarski să fi fost greșită. Pentru a face progrese, a trebuit să-și asume o anumită ipoteză, nedovedită la acea vreme, care a ajuns să fie numită J. R.; aproximativ vorbind J. R. afirmă că există o ecuație Diofantină cu doi parametri A,b cu proprietatea că perechile (a,b) pentru care ecuația are soluții sunt de așa natură încât b crește exponențial în funcție de a. presupunând J. R. și efectuând o analiză complexă și ingenioasă, ea a dovedit nu numai că puterile lui 2 sunt diofantine, ci și că setul de numere prime, precum și multe altele sunt, de asemenea. Se vede cu ușurință că toate mulțimile diofantine sunt listabile, dar acum se întreba dacă conversa ar putea fi adevărată, dacă toate mulțimile listabile ar putea fi diofantine. Acest lucru, știa ea ar avea consecințe profunde.
în 1900, pentru a saluta noul secol, marele matematician David Hilbert a propus o listă de douăzeci și trei de probleme pentru a fi o provocare. Al zecelea de pe lista sa a fost să furnizeze un algoritm pentru a determina dacă o ecuație diofantină polinomială dată are soluții. Dacă într-adevăr toate seturile listabile ar fi diofantine, și-a dat seama, atunci în special ar exista o mulțime Diofantină necomputabilă, ceea ce înseamnă că nu ar putea exista un algoritm precum îl ceruse Hilbert. Aceasta ar constitui o soluție negativă a celei de-a zecea probleme a lui Hilbert.
în vara anului 1959, Robinson a primit prin poștă o preimprimare a unei lucrări de Martin Davis și Hilary Putnam. Lucrarea conținea o dovadă că, presupunând J. R., toate seturile listabile sunt într-adevăr diofantine. Cu toate acestea, dovada a avut un decalaj important. A folosit faptul că există secvențe arbitrare lungi de numere prime cu proprietatea specială că diferența dintre termenii consecutivi ai secvenței este constantă. Deși acest lucru este adevărat, în 1959 a fost o simplă ipoteză; a fost dovedit abia în 2004. Robinson cunoștea foarte bine lucrările anterioare ale lui Davis și Putnam și și-a exprimat surpriza și plăcerea față de realizarea lor. În ordine foarte scurtă, ea a arătat cum să se descurce fără ipoteza suplimentară despre numerele prime și chiar a găsit o versiune scurtă a dovezii. Deci, pentru a obține soluția negativă anticipată a celei de-a zecea probleme a lui Hilbert, a rămas doar să demonstreze J. R.
Acest lucru a fost realizat în ianuarie 1970 de către Yuri Matiyasevich, în vârstă de douăzeci și doi de ani, folosind celebra secvență Fibonacci 1,1,2,3,5,8,13,…. El a găsit o ecuație Diofantină cu doi parametri a, b pe care a reușit să demonstreze că are soluții doar în cazul în care b este numărul Fibonacci în locul 2a din această secvență. Deoarece numerele Fibonacci cresc exponențial, aceasta a constituit o dovadă a lui J. R. Robinson a fost încântat de dovada ingenioasă a lui Matiyasevich și a călătorit la Leningrad unde s-au întâlnit familiile lor. Colaborarea lor a fost fructuoasă; împreună au reușit să demonstreze că a zecea problemă a lui Hilbert este de nerezolvat chiar și pentru ecuațiile din 13 necunoscute. (Mai târziu, Matiyasevich a reușit să reducă numărul la 9.)
Coda Regulile „nepotismului” în vigoare la Universitatea din California ar fi făcut imposibilă o numire regulată a Facultății pentru Robinson atâta timp cât soțul ei era la facultate. În orice caz, este posibil ca problemele ei de sănătate să fi împiedicat o poziție cu normă întreagă. Ea a predat ocazional un curs ca adjuvant și a servit ca consilier de facto pentru doi doctoranzi excelenți, Leonard Adleman și Kenneth Manders. Robinson a sfidat prezicerea doctorului că nu va trăi până la patruzeci de ani, dar până la patruzeci și unu de ani, inima ei deteriorată o adusese aproape de statutul de invalid. Ea a fost salvată printr-o procedură chirurgicală care a devenit recent disponibilă și care i-a îmbunătățit foarte mult situația, permițându-i să trăiască o viață activă încă douăzeci și cinci de ani.
munca ei remarcabilă a fost recunoscută prin alegerea ei în 1975 la Academia Națională de științe, prima femeie care a fost aleasă la secția de matematică. În același an i s-a oferit în cele din urmă o programare profesorală la Universitatea din California la Berkeley.
la cererea ei a fost o întâlnire de un sfert de oră. O bursă MacArthur a venit în 1983. A fost aleasă președinte al American Mathematical Society pentru 1983-1984, prima femeie care a deținut această funcție. În mod tragic, nu a reușit să-și finalizeze mandatul. S-a constatat că suferă de leucemie în vara anului 1984. După o scurtă remisiune, Julia Robinson a murit de boală la 30 iulie 1985.
bibliografie
lucrări de ROBINSON
„Definabilitate și probleme de decizie în aritmetică.”Jurnalul logicii simbolice 14 (1949): 98-114. Aceasta a fost disertația lui Robinson. „Funcții Recursive Generale.”Proceedings of the American Mathematical Society 1 (1950): 703-718. În plus față de caracterizarea funcțiilor calculabile ale unui argument descris mai sus, multe alte rezultate interesante sunt discutate în această lucrare. „Definibilitatea existențială în aritmetică.”Tranzacțiile Societății Americane de matematică 72 (1952): 437-449. O lucrare fundamentală în care ceea ce a ajuns să fie numit J. R. s-a dovedit a implica definibilitatea existențială a puterilor lui 2, Primii și, de fapt, funcția exponențială completă.
cu Martin Davis și Hilary Putnam.”Problema deciziei pentru ecuațiile diofantine exponențiale.”Analele matematicii 74 (1961): 425-436. În această lucrare s-a dovedit că J. R. implică nesolvabilitatea celei de-a zecea probleme a lui Hilbert. „O introducere în funcțiile Hiperaritmetice.”Jurnalul logicii simbolice 32 (1967): 325-342. Aceasta a fost o excursie Robinson la foarte necomputabil.
Cu Yuri Matiyasevich. „Reducerea unei ecuații diofantine arbitrare la una din 13 necunoscute.”Acta Aritmetica 27 (1975): 521-553. Teoria numerelor virtuoase! Cu Martin Davis și Yuri Matiyasevich. „A zecea problemă a lui Hilbert. Ecuații diofantine: aspecte pozitive ale unei soluții Negative.”În evoluțiile matematice care decurg din problemele Hilbert, editat de Felix Browder. Providence, RI: Societatea Americană de matematică, 1976.
lucrările simpozioanelor în matematică pură 28 (1976): 323-378. Un studiu al dovezii nesolvabilității celei de-a zecea probleme a lui Hilbert, precum și a evoluțiilor matematice care decurg din aceasta de către trei dintre cei patru matematicieni a căror muncă a dus la această dovadă.
lucrările colectate de Julia Robinson. Editat de Solomon
Feferman. Providence, RI: Societatea Americană de matematică, 1996. Toate cele douăzeci și cinci de publicații ale lui Robinson sunt retipărite aici în întregime. În plus, există eseul biografic fin despre ea scris de Feferman pentru Academia Națională de științe.
alte surse
Davis, Martin. „A zecea problemă a lui Hilbert este de nerezolvat.”
American Mathematical Monthly 80 (1973): 233-269; retipărit ca apendice în calculabilitate și Nesolvabilitate, editat de Martin Davis. New York: Dover, 1983. Un eseu câștigător al Premiului Steele care oferă dovada completă a nesolvabilității celei de-a zecea probleme a lui Hilbert. Retipărirea Dover este una dintre primele tratamente de lungime de carte ale teoriei calculabilității.
—, și Reuben Hersh. „A zecea problemă a lui Hilbert.”
Scientific American 229 (Noiembrie 1973): 84-91. Retipărit în ziarele Chauvenet, Vol. 2, editat de J. C. Abbott. Washington, DC: Asociația matematică a Americii, 1978. Un articol câștigător al Premiului Chauvenet destinat publicului larg educat.
Matiyasevich, Yuri. „Colaborarea mea cu Julia Robinson.”
Inteligentul Matematic 14 (1992): 38-45. Povestea lui despre cum o tânără rusă și o femeie americană mult mai în vârstă au ajuns să producă împreună matematică elegantă.
———. A zecea problemă a lui Hilbert. Cambridge, MA: MIT Press,
1993. O introducere excelentă și sondaj potrivit pentru specializări de matematică universitare, cu o bibliografie foarte incluzivă.
Reid, Constance. Julia, o viață în matematică. Washington, DC:
Asociația matematică a Americii, 1996. De sora lui Robinson, are fotografii, biografia utilă a lui Reid, intitulată” autobiografia Juliei Robinson ” și o scurtă notă a lui Martin Davis despre munca sa cu Hilary Putnam.
Martin Davis
