(f. St. Louis, Missouri, 8. desember 1919; D.Berkeley, California, 30. juli 1985), matematikk, matematisk logikk, tallteori, beslutningsproblemer, definerbarhet.
Robinsons matematiske arbeid viser kraft og sjarm. Hun taklet vanskelige problemer og strebet etter elegante løsninger. Hennes liv og arbeid kan ikke bli riktig sett uten å merke seg at som en kvinne i en mannsdominert felt, hun var noe av en pioner. Hennes mé var grensesnittet mellom to grener av matematikk, logikk og teorien om tall, vanligvis antatt å ha lite å gjøre med hverandre. Hun er spesielt kjent for sine bidrag til løsningen av det tiende problemet i en berømt liste over tjuefem foreslått Av matematikeren David Hilbert i 1900. Hun ble valgt til National Academy Of Sciences og også til presidentskapet I American Mathematical Society, i begge tilfeller den første kvinnelige matematikeren å bli så æret, og var også mottaker Av En MacArthur Fellowship.
Tidlig Liv Født Julia Bowman, hun led to ulykker tidlig i livet. Hun var bare to da moren døde, etterlot sin far til å takle Julia og hennes eldre søster Constance. Etter hans gjengifte, familien flyttet vest, til Slutt Til San Diego, hvor hennes stesøster Billie ble født. Da Julia var ni, gjennomgikk hun en ødeleggende sykdom: skarlagensfeber etterfulgt av revmatisk feber. Hun gikk glipp av to års skole og led svært alvorlig skade på hjertet hennes. Akademisk hun utmerket seg og snart gjort opp sin tapte bakken. I videregående skole var hun den eneste jenta til å ta avansert vitenskap og matematikk kurs og uteksaminert med en rekke æresbevisninger. I 1936 gikk Hun San Diego State College, hovedfag i matematikk. Søker bredere utsikt, hun overført til University Of California I Berkeley for hennes siste år. Blant de fem matematikk kurs hun tok det året var en på teorien om tall undervist Av Raphael Robinson. Imponert av hennes evne, overbeviste han henne om å fortsette sine studier som kandidatstudent. Raphael var en matematiker med brede interesser og kunnskap og en ideell mentor. Men snart ble forholdet deres mer personlig og de giftet seg i desember 1941. Deres håp om å starte en familie ble knust Da Julia led en spontanabort og ble advart av en lege som, på grunn av hennes alvorlig skadet hjerte, graviditet ville være ekstremt farlig. Hans mening var at hun sannsynligvis ville dø før hun var førti. I et forsøk På å hjelpe Julia overvinne den dype depresjonen som hun ble kastet, Oppmuntret Raphael henne til å søke trøst i matematikk.
Matematisk Bakgrunn 1930-tallet hadde sett revolusjonerende utviklingen i det gamle emnet logikk, drastisk endret fra det tradisjonelle feltet stammer Fra Aristoteles. Kurt Gö berømte ufullstendighetsteorem hadde pekt på de iboende begrensningene i formelle logikksystemer i innkapslingen av matematisk praksis. Arbeid av Alonzo Church, Alan Turing, Og Emil Post samt gö selv hadde vist at spørsmålet om eksistensen av algoritmiske løsninger på spesifikke matematiske problemer kunne gis en presis formulering. Dette åpnet muligheten for at slike algoritmiske løsninger i spesielle tilfeller kanskje ikke eksisterer, og selv i slike tilfeller kan dette bevises. Alfred Tarski hadde forklart hvordan man definerer semantiske forestillinger om sannhet og definerbarhet av formelle språk. Dette var utviklingen som ga sammenheng Med Julia Robinsons forskning.
enhver bestemt gren av matematikken vil bruke symboler for å stå for de spesielle operasjoner og relasjoner som er grunnleggende for det emnet. I tillegg til slike symboler bruker moderne matematisk logikk de spesielle symbolene
sammen med det kjente = tegnet. Man snakker om disse symbolene sammen med de som svarer til en bestemt gren av matematikk som utgjør et språk. Julia Robinsons arbeid var i stor grad i sammenheng med aritmetisk språk som bruker de to symbolene + og × som står for henholdsvis addisjon og multiplikasjon, samt symboler for 0 og 1. Bokstaver i alfabetet brukes som variabler, og i tilfelle av aritmetisk språk forstås de vanligvis å variere over de kjente naturlige tallene 0,1,2…… Så for eksempel uttrykker «setningen»
det sanne forslaget om at å legge til to odde tall gir et jevnt tall. Formelen (u) (x = u+u+1) > i seg selv definerer settet av odde tall, dvs. hvis x erstattes av et bestemt naturlig tall, vil den resulterende setningen være sant hvis og bare hvis det tallet er merkelig. Spørsmål om definerbarhet og eksistensen av algoritmer var grunnleggende For Robinsons arbeid.
et sett med naturlige tall S kalles computable (eller rekursive) hvis det er en algoritme som kan bestemme for et gitt naturlig tall n om n tilhører S. et sett med naturlige tall kalles listable (begrepet foretrukket Av Julia Robinson) eller rekursivt enumerable hvis det er en algoritme for systematisk å lage en liste over medlemmene Av S. alle unsolvability resultater kan betraktes som konsekvenser av nøkkelteoremet: det finnes et listable sett som ikke er computable. Disse sakene var også svært viktige i Robinsons arbeid.
Julia Robinson ‘ S Dissertation Det var i et seminar ledet av den karismatiske Alfred Tarski, en av de store logicians av det tjuende århundre, At Robinson fant henne mé. Tarski hadde forlatt sitt hjemland Polen i August 1939 på det som skulle ha vært en kort tur til å delta på en konferanse i Usa, like før den tyske invasjonen Av Polen utfelt Andre Verdenskrig. Tarski stilte en rekke uløste spørsmål om definerbarhet på aritmetisk språk Som Robinson ble tiltrukket av. Ved 1940-tallet var det velkjent at det ikke er noen algoritme for å avgjøre om en gitt setning i aritmetisk språk, med variablene som strekker seg over de naturlige tallene, er sant. Som man sier, er dette et algoritmisk uløselig problem. Tarski ønsket å vite om det samme er sant når det i samme språk er variabler tillatt å variere over alle rasjonelle tall i stedet for bare de naturlige tallene. (De rasjonale tallene er de uttrykkbare som fraksjoner m / n eller-m / n hvor m er et naturlig tall og n er et ikke-null naturlig tall.) Det hadde blitt utviklet teknikker for å «redusere» et slikt «beslutningsproblem» til et annet. I dette tilfellet ville man vise at hvis det var en algoritme for å teste for sannhet, en setning av aritmetisk språk med variablene begrenset til å variere over de rasjonelle tallene, kunne en slik algoritme brukes til å gi en algoritme for å gjøre det samme når variablene varierer over de naturlige tallene. Så, siden det ikke er en slik algoritme for sistnevnte, ville det følge at det heller ikke kunne være en for den tidligere.
hovedresultatet av Robinsons avhandling var en eksplisitt formel i aritmetisk språk, med variablene begrenset til å variere over de rasjonelle tallene, som definerer nøyaktig settet av heltall (det vil si settet av naturlige tall og deres negativer). Det fulgte da at problemet med å bestemme sannheten i en setning av aritmetikk forblir uløselig selv når variablene spenner over de rasjonelle tallene. Andre unsolvability resultater fulgte også. Robinsons tilnærming var intrikat, elegant og genial ved hjelp av noen ganske dype ideer fra tallteori.
Elegante Karakteriseringer Robinson alltid søkt eleganse og enkelhet i hennes matematiske arbeid. En av hennes tidlige papirer viste hvordan man på en spesielt enkel måte kan karakterisere de algoritmisk beregnede funksjonene (også kalt rekursive funksjoner) som kartlegger de naturlige tallene i seg selv. Hennes vakre karakterisering innebærer to innledende funksjoner og tre operasjoner for å skaffe nye funksjoner fra gitte funksjoner. En av de første funksjonene er bare etterfølgerfunksjonen S (x)= x+1. Den Andre, Som Robinson kaller E, er definert som forskjellen mellom et gitt tall og det største perfekte torget som ikke overskrider det. E (19) = 19-16 = 3 og E(25) = 25-25 = 0.) De tre operasjonene er som følger: (1) fra gitte funksjoner f og G får funksjonen H (x) = F (g (x)); (2) fra gitte funksjoner f og G får funksjonen H (x) = F (x) + G (x); og (3) fra en gitt funksjon F hvis verdier inkluderer alle naturlige tall får funksjonen H Der h(x) er det minste tallet t For Hvilket F(t)=x.
det er virkelig bemerkelsesverdig at alle beregningsbare funksjoner (fra de naturlige tallene til de naturlige tallene) kan oppnås ved å begynne med de to innledende funksjonene og bruke disse tre operasjonene om og om igjen.
Mye senere Robinson viste samme eleganse og verve i å finne nye karakteriseringer av et domene fjernt fra computable. Eksistensen Av et listbart sett K Som ikke kan beregnes, er allerede nevnt. Så det er ingen algoritme for å bestemme medlemskap I K. Ved å vurdere sett som kan listes av algoritmer som har tilgang til medlemsinformasjon om slike sett (metaforisk via et «oracle»), kan flere sett bringes inn i brettet, og denne prosessen kan itereres. Ved å la denne iterasjonen skje et begrenset antall ganger, viser de oppnådde settene seg å være nøyaktig de som kalles aritmetisk, settene definerbare i aritmetisk språk med variabler som spenner over de naturlige tallene. Men det er ikke nødvendig å stoppe her. Man kan definere et ikke-aritmetisk sett, og deretter bruke det som et» orakel » for å kunne liste enda flere sett. Det er et naturlig sted hvor denne prosessen kommer til en slutt, og settene med naturlige tall som er oppnådd, kalles hyperaritmetiske. Det var Dette sjeldne riket Som Robinson ga en enkel og direkte karakterisering.
Eksistensiell Definabilitet Og Hilbert Tiende Problem arbeidet Som Julia Robinson er mest husket oppsto med en tilsynelatende enkel problem stilt Av Alfred Tarski. Tarski ønsket å vite hvilke sett med naturlige tall som er definerbare med formler av aritmetisk språk hvis symbolene og er utelukket. Han kalte slike sett eksistensielt definerbare og foreslo problemet med å bevise at settet {1,2,4,8,16,….} av krefter av 2 er ikke eksistensielt definerbar. Dette var akkurat den typen problem Som Robinson likte. Begrepet eksistensiell definabilitet kan lett sees å være nært knyttet til problemer av et slag som tallteoretikere studerer, såkalte Diofantinproblemer. Disse har vanligvis å gjøre med en polynomligning p (a, x, y, z, u, v, w,….) = 0 med heltallskoeffisienter hvor a er en parameter og x, y, z, u , v, w,…. er » ukjente.»(Husk at et slikt polynom er bare summen av termer som 5a3x2v5 og-7a4x3z6.) For Bestemte Diofantinske ligninger av denne typen forsøker tallteoretikere å bestemme for hvilke naturlige tallverdier av parameteren a, ligningen har naturlige tallløsninger i de ukjente. Nå ved enkle standardmetoder er det lett å se at et sett med naturlige tall S er eksistensielt definerbart hvis og bare hvis Det er en polynomligning av denne typen slik At S er nøyaktig sett med verdier av parameteren som ligningen har naturlige tallløsninger for. Av denne grunn kalles eksistensielt definerbare sett Også Diofantin, og dette er begrepet som har blitt vedtatt i senere litteratur.
Robinson hadde Ingen suksess i å bevise Tarskis formodning om at settet av krefter av 2 ikke Er Diofantin, Og Begynte å vurdere muligheten For At Tarskis gjetning kunne ha vært feil. For å gjøre noen fremskritt måtte hun anta en viss hypotese, ubevisst på den tiden, som kom til å bli kalt Jr; grovt Sett Jr sier at Det Er En Diofantinligning med to parametere a, b med egenskapen at parene (a, b) som ligningen har løsninger for, er slik at b vokser eksponentielt som en funksjon av a. ved å anta Jr og utføre en kompleks og genial analyse viste hun ikke bare at kreftene til 2 Er Diofantin, men også at settet med primtall så vel som mange andre også er. Det er lett å se at Alle Diophantine sett er listable, men nå lurte hun på om det motsatte kan være sant, om alle listable sett kan Være Diophantine. Dette visste hun ville få store konsekvenser.
I 1900, for å hilse det nye århundret, den store matematikeren David Hilbert foreslått en liste over tjuetre problemer å stå som en utfordring. Den tiende på sin liste var å gi en algoritme for å avgjøre om en gitt polynom Diofantisk ligning har løsninger. Hvis faktisk alle listable sett Var Diofantin, skjønte hun, da ville det spesielt være et ikke-beregningsbart Diofantin sett, noe som innebar at Det ikke kunne være noen algoritme som Hilbert hadde bedt om. Dette ville utgjøre en negativ løsning På Hilberts tiende problem.
sommeren 1959 mottok Robinson i posten et preprint av et papir av Martin Davis og Hilary Putnam. Papiret inneholdt et bevis på at, forutsatt Jr, alle listbare sett er Faktisk Diofantin. Beviset hadde imidlertid et viktig gap. Det brukes det faktum at det er vilkårlig lange sekvenser av primtall med den spesielle egenskapen at forskjellen mellom påfølgende vilkår i sekvensen er konstant. Selv om dette er sant, var det i 1959 bare en hypotese; det ble kun bevist i 2004. Robinson kjente Davis og Putnams tidligere arbeid veldig bra og uttrykte overraskelse og glede over deres prestasjon. I svært kort rekkefølge viste hun hvordan man skulle gjøre uten den ekstra hypotesen om primtall, og til og med funnet en kort versjon av beviset. Så, for å oppnå den forventede negative løsningen Av Hilberts tiende problem, ble Det bare å bevise Jr
Dette ble oppnådd i januar 1970 av den tjueto år Gamle Yuri Matiyasevich ved hjelp av den berømte Fibonacci-sekvensen 1,1,2,3,5,8,13,…. Han fant En diofantisk ligning med to parametere a, b som han var i stand til å bevise har løsninger bare i tilfelle b Er Fibonacci-tallet i 2a-th sted i denne sekvensen. Fordi Fibonacci-tallene vokser eksponentielt, utgjorde dette et bevis På At Jr Robinson var glad av Matiyasevichs geniale bevis og reiste til Leningrad hvor deres familier møttes. Deres samarbeid var fruktbart; sammen var de i stand til å vise At Hilberts tiende problem er uløselig selv for ligninger i 13 ukjente. (Senere Var Matiyasevich i stand til å redusere tallet til 9.)
Coda» nepotisme » regler i kraft Ved University Of California ville ha gjort en vanlig fakultetet avtale For Robinson umulig så lenge hennes mann var på fakultetet. I alle fall kan det vel være at hennes helseproblemer ville ha utelukket en heltidsstilling. Hun gjorde tidvis undervise et kurs som et supplement, og hun fungerte som de facto rådgiver for To gode doktorgradsstudenter, Leonard Adleman og Kenneth Manders. Robinson trosset legens spådom om at hun ikke ville leve til å være førti, men ved hennes førtifemte bursdag hennes skadet hjerte hadde brakt henne nær ugyldig status. Hun ble reddet av en kirurgisk prosedyre som bare nylig hadde blitt tilgjengelig, og som i stor grad forbedret hennes situasjon, slik at hun kunne leve et aktivt liv i ytterligere tjuefem år.
hennes fremragende arbeid ble anerkjent av hennes valg i 1975 Til National Academy Of Sciences, den første kvinnen til å bli valgt til matematikk seksjon. Samme år ble hun endelig tilbudt en professoravtale ved University Of California I Berkeley.
på hennes forespørsel var det en kvart time avtale. En MacArthur Fellowship kom i 1983. Hun ble valgt til president I American Mathematical Society for 1983-1984, den første kvinnen til å holde dette kontoret. Tragisk, hun var ikke i stand til å fullføre sin periode. Hun ble funnet å lide av leukemi i løpet av sommeren 1984. Etter en kort remisjon døde Julia Robinson av sykdommen den 30. juli 1985.
BIBLIOGRAFI
VERK AV ROBINSON
«Definerbarhet Og Beslutningsproblemer I Aritmetikk.»Journal Of Symbolsk Logikk 14 (1949): 98-114. Dette var Robinsons avhandling. «Generelle Rekursive Funksjoner.»Proceedings Av American Mathematical Society 1 (1950): 703-718. I tillegg til karakteriseringen av beregningsbare funksjoner av ett argument beskrevet ovenfor, diskuteres mange andre interessante resultater i dette papiret. «Eksistensiell Definerbarhet I Aritmetikk.»Transaksjoner Av American Mathematical Society 72 (1952): 437-449. Et grunnleggende papir der det som kom til å bli kalt Jr, ble vist å innebære eksistensiell definabilitet av kreftene til 2, primene og faktisk den fulle eksponentielle funksjonen.
Med Martin Davis og Hilary Putnam.»Beslutningsproblemet For Eksponentielle Diophantine Ligninger.»Annaler Av Matematikk 74 (1961): 425-436 . Det var i dette papiret at Det ble bevist At Jr innebærer unsolvability Av Hilbert tiende problem. «En Introduksjon Til Hyperaritmetiske Funksjoner.»Journal Of Symbolsk Logikk 32 (1967): 325-342 . Dette var Robinsons en utflukt til det svært uforanderlige.
Med Yuri Matiyasevich. «Reduksjon Av En Vilkårlig Diofantinligning Til en av 13 Ukjente.»Acta Arithmetica 27 (1975): 521-553. Virtuos tallteori! Med Martin Davis og Yuri Matiyasevich. «Hilberts Tiende Problem. Diophantine Ligninger: Positive Aspekter Av En Negativ Løsning.»I Matematiske Utviklingen Som Følge Av Hilbert Problemer, redigert Av Felix Browder. Providence, RI: American Mathematical Society, 1976.
Proceedings Av Symposier I Ren Matematikk 28 (1976): 323-378. En undersøkelse av bevis På unsolvability Av Hilbert tiende problem samt matematiske utviklingen stammer fra det av tre av de fire matematikere hvis arbeid førte til at bevis.
De Samlede Verkene Til Julia Robinson. Redigert Av Solomon
Feferman. Providence, RI: American Mathematical Society, 1996. Alle tjuefem Av Robinsons publikasjoner er gjengitt her i sin helhet. I tillegg er det det fine biografiske essayet om Henne skrevet av Feferman for National Academy of Sciences.
Andre KILDER
Davis, Martin. «Hilberts Tiende Problem Er Uløselig.»
American Mathematical Monthly 80 (1973): 233-269; gjengitt som et tillegg I Computability and Unsolvability, redigert Av Martin Davis. New York: Dover, 1983. En Steele-Prisvinnende essay som tilbyr det komplette bevis På unsolvability Av Hilbert tiende problem. Dover opptrykk er av en av de første bok-lengde behandlinger av computability teori.
—, Og Ruben Hersh. «Hilberts Tiende Problem.»
Vitenskapelig Amerikansk 229 (November 1973): 84-91. The Chauvenet Papers, Vol. 2, redigert Av J. C. Abbott. Washington, DC: Matematisk Forening Av Amerika, 1978. En Chauvenet-Prisvinnende artikkel beregnet for det generelle utdannede publikum.
Matiyasevich, Yuri. «Mitt Samarbeid Med Julia Robinson.»
Den Matematiske Intelligencer 14 (1992): 38-45. Hans historie om hvordan en ung russisk og en mye eldre Amerikansk kvinne kom til å produsere elegant matematikk sammen.
———. Hilberts Tiende Problem. Cambridge, MA: MIT Press,
1993. En utmerket introduksjon og undersøkelse egnet for lavere matematikk hovedfag, med en svært inkluderende bibliografi.
Reid, Constance. Julia, Et Liv I Matematikk. Washington, DC:
Matematisk Forening Av Amerika, 1996. Ved Robinson søster, Den har fotografier, reid nyttig biografi, med tittelen «The Autobiography Of Julia Robinson,» Og En kort notat Av Martin Davis om sitt arbeid Med Hilary Putnam.
Martin Davis
