Bärparadox

Berry -paradoxen är en självrefererande paradox som härrör från ett uttryck som "Det minsta positiva heltal som inte kan definieras med mindre än sextio bokstäver" (en fras med femtiosju bokstäver).

Bertrand Russell , den förste som diskuterade paradoxen i tryck, tillskrev den till GG Berry (1867–1928), en yngre bibliotekarie vid Oxfords Bodleian Library . Russell kallade Berry "den enda personen i Oxford som förstod matematisk logik". Paradoxen kallades "Richards paradox" av Jean-Yves Girard.

Översikt

Tänk på uttrycket:

"Det minsta positiva heltal som inte kan definieras med mindre än sextio bokstäver."

Eftersom det bara finns tjugosex bokstäver i det engelska alfabetet, finns det ändligt många fraser på under sextio bokstäver, och därmed ändligt många positiva heltal som definieras av fraser på under sextio bokstäver. Eftersom det finns oändligt många positiva heltal, betyder det att det finns positiva heltal som inte kan definieras av fraser på under sextio bokstäver. Om det finns positiva heltal som uppfyller en given egenskap, så finns det ett minsta positivt heltal som uppfyller den egenskapen; därför finns det ett minsta positivt heltal som uppfyller egenskapen "ej definierbar med mindre än sextio bokstäver". Detta är det heltal som uttrycket ovan refererar till. Men uttrycket ovan är bara femtiosju bokstäver långt, därför kan det definieras med mindre än sextio bokstäver och är inte det minsta positiva heltal som inte kan definieras med mindre än sextio bokstäver och definieras inte av detta uttryck. Detta är en paradox: det måste finnas ett heltal definierat av detta uttryck, men eftersom uttrycket är självmotsägande (vilket heltal det definierar kan definieras med mindre än sextio bokstäver), kan det inte finnas något heltal definierat av det.

En annan användbar analogi till Berry's Paradox skulle kanske vara frasen "obeskrivlig känsla". Om känslan verkligen är obeskrivlig, skulle ingen beskrivning av känslan vara sann. Men om ordet "obeskrivligt" kommunicerar något om känslan, så kan det betraktas som en beskrivning: detta är självmotsägelsefullt.

Matematikern och datavetaren Gregory J. Chaitin i The Unknowable (1999) lägger till denna kommentar: "Tja, den mexikanske matematikhistorikern Alejandro Garcidiego har gjort sig besväret att hitta det brevet [av Berry's från vilket Russell skrev sina kommentarer], och det är ganska en annan paradox. Berrys bokstav talar faktiskt om den första ordinalen som inte kan benämnas i ett ändligt antal ord. Enligt Cantors teori måste en sådan ordningsstav existera, men vi har precis döpt den i ett ändligt antal ord, vilket är en motsägelse."

Upplösning

Berry-paradoxen som formulerats ovan uppstår på grund av systematisk tvetydighet i ordet "definierbar". I andra formuleringar av Berry-paradoxen, t.ex. en som istället lyder: "...inte kan namnges i mindre..." är termen "namnbar" också en som har denna systematiska tvetydighet. Termer av detta slag ger upphov till ond cirkelfel . Andra termer med denna typ av tvetydighet är: tillfredsställande, sann, falsk, funktion, egenskap, klass, relation, kardinal och ordinal. Att lösa en av dessa paradoxer innebär att precisera var vår användning av språket gick fel och att ge begränsningar för språkanvändningen som kan undvika dem.

0 Denna familj av paradoxer kan lösas genom att införliva meningsskiktningar i språket. Termer med systematisk tvetydighet kan skrivas med indikationer som anger att en betydelsenivå anses ha högre prioritet än en annan i sin tolkning. "Numret som inte går att namnge i mindre än elva ord" kan vara namnbart 1 på mindre än elva ord enligt detta schema.

Däremot kan man läsa Alfred Tarskis bidrag till lögnarparadoxen för att se hur denna upplösning i språken misslyckas. Alfred Tarski diagnostiserade att paradoxen endast uppstod i språk som är "semantiskt stängda", med vilket han menade ett språk där det är möjligt för en mening att predika sanning (eller osanning) i en annan mening på samma språk (eller till och med i sig själv). ). För att undvika självmotsägelse är det nödvändigt när man diskuterar sanningsvärden att föreställa sig språknivåer, som var och en kan predikera sanning (eller lögn) endast för språk på en lägre nivå. Så när en mening hänvisar till en annans sanningsvärde är den semantiskt högre. Den mening som avses är en del av "objektspråket", medan den refererande meningen anses vara en del av ett "metaspråk" med avseende på objektspråket. Det är legitimt att meningar i "språk" högre upp i den semantiska hierarkin hänvisar till meningar lägre i "språk"-hierarkin, men inte tvärtom. Detta förhindrar ett system från att bli självrefererande.

Detta system är dock ofullständigt. Man skulle vilja kunna göra påståenden som "För varje påstående på nivå α i hierarkin finns det ett påstående på nivå α +1 som hävdar att det första påståendet är falskt." Detta är ett sant, meningsfullt uttalande om hierarkin som Tarski definierar, men det hänvisar till uttalanden på alla nivåer i hierarkin, så det måste ligga över varje nivå i hierarkin, och är därför inte möjligt inom hierarkin (även om avgränsade versioner av meningen är möjliga). Saul Kripke är krediterad för att ha identifierat denna ofullständighet i Tarskis hierarki i hans mycket citerade artikel "Outline of a theory of truth", och det anses vara ett allmänt problem i hierarkiska språk.

Formella analoger

Med hjälp av program eller bevis av begränsade längder är det möjligt att konstruera en analog av Berry-uttrycket i ett formellt matematiskt språk, vilket har gjorts av Gregory Chaitin . Även om den formella analogen inte leder till en logisk motsägelse, bevisar den vissa omöjlighetsresultat.

George Boolos (1989) byggde på en formaliserad version av Berrys paradox för att bevisa Gödels ofullständighetsteorem på ett nytt och mycket enklare sätt. Grundtanken med hans bevis är att en proposition som gäller x om och endast om x = n för något naturligt tal n kan kallas en definition för n , och att mängden {( n , k ): n har en definition som är k symboler långa} kan visas som representerbara (med Gödel-tal ) . Sedan kan påståendet " m är det första talet som inte kan definieras i mindre än k symboler" formaliseras och visa sig vara en definition i den betydelse som just angavs.

Förhållande med Kolmogorov komplexitet

Huvudartikel: Kolmogorovs komplexitet

Det är inte generellt möjligt att entydigt definiera vad som är det minimala antalet symboler som krävs för att beskriva en given sträng (med tanke på en specifik beskrivningsmekanism). I detta sammanhang kan termerna sträng och nummer användas omväxlande, eftersom ett tal faktiskt är en sträng av symboler, t.ex. ett engelskt ord (som ordet "elva" som används i paradoxen) medan det å andra sidan är möjligt att hänvisa till ett ord med ett nummer, t.ex. genom numret på dess position i en given ordbok eller genom lämplig kodning. Vissa långa strängar kan beskrivas exakt med färre symboler än de som krävs för deras fullständiga representation, vilket ofta uppnås med datakomprimering . Komplexiteten hos en given sträng definieras sedan som den minimala längd som en beskrivning kräver för att (otvetydigt) referera till den fullständiga representationen av den strängen.

Kolmogorov-komplexiteten definieras med formella språk eller Turing-maskiner som undviker oklarheter om vilken sträng som är resultatet av en given beskrivning. Det kan bevisas att Kolmogorov-komplexiteten inte är beräkningsbar. Motsägelsebeviset visar att om det var möjligt att beräkna Kolmogorov-komplexiteten, så skulle det också vara möjligt att systematiskt generera paradoxer liknande denna, dvs beskrivningar som är kortare än vad komplexiteten hos den beskrivna strängen antyder. Det vill säga, definitionen av Berry-talet är paradoxal eftersom det faktiskt inte är möjligt att beräkna hur många ord som krävs för att definiera ett tal, och vi vet att sådan beräkning inte är möjlig på grund av paradoxen.

Se även

Anteckningar

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Berry_paradox&oldid=1125180434 "