Tarskis odefinieringssats - Tarski's undefinability theorem

Tarskis odefinieringssats , uttalad och bevisad av Alfred Tarski 1933, är ett viktigt begränsande resultat i matematisk logik , grunden för matematik och i formell semantik . Informellt säger satsen att aritmetisk sanning inte kan definieras i aritmetik .

Satsen gäller mer generellt för alla tillräckligt starka formella system , vilket visar att sanningen i systemets standardmodell inte kan definieras inom systemet.

Historia

År 1931, Kurt Gödel publicerade ofullständig teorem , som han visat delvis genom att visa hur man kan representera syntax formell logik inom första ordningens aritmetik . Varje uttryck för det formella aritmetiska språket tilldelas ett tydligt nummer. Denna procedur är känd som Gödel-numrering , kodning och, mer allmänt, som aritmetisering. I synnerhet kodas olika uppsättningar av uttryck som uppsättningar av siffror. För olika syntaktiska egenskaper (som att vara en formel , att vara en mening , etc.), kan dessa uppsättningar beräknas . Dessutom kan vilken beräkningsbar mängd som helst definieras med någon aritmetisk formel. Till exempel finns det formler på aritmetikens språk som definierar uppsättningen koder för aritmetiska meningar och för bevisbara aritmetiska meningar.

Satsen för odefinierbarhet visar att denna kodning inte kan göras för semantiska begrepp som sanning. Det visar att inget tillräckligt rikt tolkat språk kan representera sin egen semantik. En följd är att varje metaspråk som kan uttrycka semantiken i något objektspråk måste ha en uttrycksfull kraft som överstiger objektets språk. Metalspråket innehåller primitiva föreställningar, axiomer och regler som saknas från objektspråket, så att det finns teorem som kan bevisas i metaspråket som inte kan bevisas i objektspråket.

Satsen för odefinierbarhet tillskrivs konventionellt Alfred Tarski . Gödel upptäckte också odefinieringssatsen 1930, samtidigt som han bevisade hans ofullständiga satser som publicerades 1931 och långt före publiceringen av Tarskis verk 1933 (Murawski 1998). Medan Gödel aldrig publicerade något som rör hans oberoende upptäckt av odefinierbarhet, beskrev han det i ett brev från 1931 till John von Neumann . Tarski hade fått nästan alla resultat av sin monografi " Pojęcie Prawdy w Językach Nauk Dedukcyjnych " från 1933 (" Sanningskonceptet i de deduktiva vetenskapens språk ") mellan 1929 och 1931 och talade om dem till den polska publiken. Men som han betonade i tidningen var satsen för odefinierbarhet det enda resultatet han inte fick tidigare. Enligt fotnot till odefinieringssatsen (Twierdzenie I) i monografin 1933 lades satsen och skissen på beviset till monografin först efter att manuskriptet skickades till skrivaren 1931. Tarski rapporterar där att när han presenterade innehållet i hans monografi till Warszawas vetenskapsakademi den 21 mars 1931, uttryckte han på denna plats endast några gissningar, dels baserade på hans egna undersökningar och dels på Gödels korta rapport om ofullständighetssatserna "Einige metamathematische Resultate über Entscheidungsdefinitheit und Widerspruchsfreiheit ", Akademie der Wissenschaften i Wien, 1930.

Påstående

Vi kommer först att ange en förenklad version av Tarski sats, då staten och bevisa i nästa avsnitt satsen Tarski visat 1933. Låt L vara språket i första ordningens aritmetik , och låt N vara standard strukturen för L . Således ( L , N ) är det "tolkade aritmetikens första ordens språk." Varje formel x i L har ett Gödel-tal g ( x ). Låt T beteckna uppsättningen av L -formulas sant i N , och T * uppsättningen av Gödels antal av formlerna i T . Följande sats svarar på frågan: Kan T * definieras med en formel av första ordningens aritmetik?

Tarskis odefinieringssats : Det finns ingen L- formel True ( n ) som definierar T *. Det vill säga det finns ingen L- formel Sann ( n ) sådan att för varje L- formel A , Sann ( g ( A )) ↔ A innehar.

Informellt säger satsen att med tanke på formell aritmetik kan begreppet sanning i den aritmetiken inte definieras med hjälp av de uttrycksfulla medel som aritmetiken ger. Detta innebär en stor begränsning av omfattningen av "självrepresentation". Det är möjligt att definiera en formel Sann ( n ), vars förlängning är T *, men endast genom att utnyttja ett metaspråk vars uttryckskraft går utöver den för L . Till exempel kan ett sanningspredikat för första ordningens aritmetik definieras i andra ordningens aritmetik . Detta skulle dock formel endast kunna definiera en sanning predikat för formler i originalspråket L . För att definiera ett sanningspredikat för metaspråket krävs en ännu högre metatalspråk, och så vidare.

Satsen som just nämnts är en följd av Postens sats om den aritmetiska hierarkin , bevisad några år efter Tarski (1933). Ett semantiskt bevis på Tarskis sats från Postens sats erhålls genom reductio ad absurdum enligt följande. Förutsatt att T * är aritmetiskt definierbart finns det ett naturligt tal n så att T * kan definieras med en formel på nivån i den aritmetiska hierarkin . Dock är T * -hårt för alla k . Således kollapsar den aritmetiska hierarkin på nivå n , vilket motsäger Posts sats.

Allmän form

Tarski visade sig vara en starkare sats än den som nämnts ovan, med en helt syntaktisk metod. Den resulterande satsen gäller alla formella språk med förnekande och med tillräcklig förmåga för självreferens som det diagonala lemmaet har. Första ordningens aritmetik uppfyller dessa förutsättningar, men satsen gäller mycket mer allmänna formella system.

Tarskis odefinieringssats (allmän form) : Låt ( L , N ) vara vilket som helst tolkat formellt språk som inkluderar negation och har en Gödel-numrering g ( x ) så att för varje L- formel A ( x ) finns en formel B så att B ↔ A ( g ( B )) innehar i N . Låt T * vara mängden av Gödels antal L -formula true i N . Sedan finns det ingen L- formel True ( n ) som definierar T *. Det vill säga, det finns ingen L -formula Sann ( n ) så att för varje L -formula A , Sann ( g ( A )) ↔ A i sig är sant i N .

Beviset för Tarskis odefinieringssats i denna form är återigen av reductio ad absurdum . Antag att en L- formel True ( n ) definierar T *. I synnerhet, om A är en formel av aritmetik, sedan Sann ( g ( A )) innehar i N om och endast om A har i N . Därmed för alla A , formeln Sann ( g ( A )) ↔ A innehar i N . Men fixpunktssatsen ger en motexempel till denna ekvivalens, genom att ge en "liar" formeln S så att S ↔ ¬ Sann ( g ( S )) innehar i N . Således kan ingen L- formel True ( n ) definiera T *. QED.

Det formella maskineriet för detta bevis är helt elementärt förutom den diagonalisering som det diagonala lemmaet kräver. Beviset på det diagonala lemmaet är också överraskande enkelt; det åberopar till exempel inte rekursiva funktioner på något sätt. Beviset antar att varje L- formel har ett Gödel-nummer , men detaljerna för en kodningsmetod krävs inte. Därför är Tarskis sats mycket lättare att motivera och bevisa än de mer berömda satserna i Gödel om de metematematiska egenskaperna hos första ordningens aritmetik .

Diskussion

Smullyan (1991, 2001) har med kraft argumenterat för att Tarskis odefinieringssats förtjänar mycket av den uppmärksamhet som Gödels ofullständiga satser fick . Att de senare satsningarna har mycket att säga om all matematik och mer kontroversiellt om en rad filosofiska frågor (t.ex. Lucas 1961) är mindre än uppenbart. Tarskis teorem, å andra sidan, handlar inte direkt om matematik utan om de inneboende begränsningarna i något formellt språk som är tillräckligt uttrycksfullt för att vara av verkligt intresse. Sådana språk kan nödvändigtvis ha tillräckligt med självreferens för att det diagonala lemmet ska kunna tillämpas på dem. Den bredare filosofiska importen av Tarskis teorem är tydligare.

Ett tolkat språk är starkt semantiskt självrepresentativt exakt när språket innehåller predikat och funktionssymboler som definierar alla semantiska begrepp som är specifika för språket. Följaktligen inkluderar de nödvändiga funktionerna den "semantiska värderingsfunktionen" som mappar en formel A till dess sanningsvärde || A || och den "semantiska denotationsfunktionen" som mappar en term t till det objekt som den betecknar. Tarskis sats generaliserar sedan följande: Inget tillräckligt kraftfullt språk är starkt semantiskt självrepresentativt .

Satsen för odefinierbarhet hindrar inte att sanningen i en teori definieras i en starkare teori. Till exempel är uppsättningen (koder för) formler av första ordningens Peano-aritmetik som är sanna i N definierbara med en formel i andra ordningens aritmetik . På samma sätt kan uppsättningen sanna formler för standardmodellen för andra ordningens aritmetik (eller n- ordningens aritmetik för vilken som helst n ) definieras av en formel i första ordningens ZFC .

Se även

Referenser

  • JL Bell och M. Machover, 1977. En kurs i matematisk logik . Nord-Holland.
  • G. Boolos , J. Burgess och R. Jeffrey , 2002. Computability and Logic , 4: e upplagan. Cambridge University Press.
  • JR Lucas , 1961. " Mind, Machines, and Gödel ". Filosofi 36: 112–27.
  • R. Murawski, 1998. Odefinierbarhet av sanningen. Problemet med prioriteringen: Tarski mot Gödel . Logikens historia och filosofi 19, 153–160
  • R. Smullyan , 1991. Godels ofullständighetssatser . Oxford Univ. Tryck.
  • R. Smullyan , 2001. "Gödel's Thecompleteness Theorems". I L. Goble, red., The Blackwell Guide to Philosophical Logic , Blackwell, 72–89.
  • A. Tarski , 1933. Pojęcie Prawdy w Językach Nauk Dedukcyjnych . Nakładem Towarzystwa Naukowego Warszawskiego.
  • A. Tarski (1936). "Der Wahrheitsbegriff in den formalisierten Sprachen" (PDF) . Studia Philosophica . 1 : 261–405. Arkiverad från originalet (PDF) den 9 januari 2014 . Hämtad 26 juni 2013 .