I matematisk logik , Tarski sætning , eller Tarski 's manglende definability sætning, der uformelt angivet på følgende måde:
Man kan ikke på aritmetikens sprog definere sandheden af udsagnene fra dette sprog.Vi er her interesserede i de første ordres formler på sproget "0, s, +, ×, ≤" sandt på heltal. Dette er sand aritmetik (eller sandheden i N : positive heltal). Vi antager, at sproget er rekursivt : hvilket er tilfældet, når de primitive symboler, "0, s, +, ×, ≤" for Peano-aritmetik , er endelige i antal. Uden at gå i detaljer er teoriens sprog, der normalt bruges i matematik, rekursive.
Teoremet er baseret på Gödel 's arbejde , der til bevis for hans ufuldstændighedssætninger viser, at formler kan kodes med hele tal. Kodningen af formlerne kan udføres på samme måde som for Gödel's ufuldstændighedssætning . Vi betegner ved ⌈ F ⌉ koden for en formel F for sproget; ⌈ F ⌉ er derfor et heltal. Sættet med heltal, der er formelkoder, ligesom det sæt heltal, der er sætningskoder (lukkede formler uden frie variabler) er defineret i aritmetik. Vi er så interesseret i sættet C kode sande formler i N .
At definere et sæt heltal på aritmetisk sprog er at finde en formel for dette sprog med en fri variabel, som kun verificeres af heltalene i dette sæt. For eksempel findes der en y- formel , således at x = y + y , som kun har gratis variabel x , definerer sættet med lige heltal.
Vi kan bemærke, at vi på et tælleligt sprog aldrig kan definere mere end et tællbart sæt af undergrupper af N , dette er det væsentlige argument for Löwenheim-Skolem-sætningen . Ifølge et velkendt resultat af Cantor er sættet med delmængder af N imidlertid ikke tælles. Vi ved derfor, at alle delmængder af N ikke kan defineres.
Her er vi interesseret i at definere det sæt af C-kode sande formler i N . Med andre ord, at definere sandheden af udsagnene er at have en formel V sådan, at
A ⇔ V (⌈ A ⌉)er sandt i N for ethvert udsagn A .
Således siger Tarskis sætning nøjagtigt, at uanset den valgte kodning,
det sæt af koder for en meddelelse af et bestemt sprog til aritmetik, som er sande i N er ikke definerbart i dette samme sprog ,eller mere formelt, at der ikke er nogen formel V sådan, at
A ⇔ V (⌈ A ⌉)er sandt i N for ethvert udsagn A .
Alfred Tarski erklærede og demonstrerede denne sætning i en artikel, der blev offentliggjort på polsk i 1933, derefter oversat til tysk i 1936, som er kendt for at være den første artikel, der foreslår formaliseringer af sandhedens opfattelse i matematik. Imidlertid ser det ud til, at Gödel under sin forskning om ufuldstændighedssætninger beviste denne sætning, hvis bevis svarer meget til hans første ufuldstændighedssætning, samtidig med at den er teknisk enklere. Han nævnte det i et brev til John von Neumann i 1931 ifølge et senere brev fra Gödel selv. Han tilføjede, at han betragtede denne sætning som "den virkelige årsag til eksistensen af ubeslutsomme udsagn i formelle systemer, der indeholder aritmetik". Gödel ville have nægtet at tale om sandhed i sin artikel fra 1931, idet forestillingen på det tidspunkt var kontroversiel.
Teoremet generaliserer til ethvert rekursivt sprog, der gør det muligt at definere sproget i Peano-aritmetik.
Her ser vi på udtalelserne fra den sande sprog i N . Vi kan derfor definere dette sæt matematisk, men til det har vi brug for en teori på et sprog rigere end det originale. For eksempel kan vi definere sandheden i N i sætteori , eller mere simpelt i anden ordens aritmetik . Tarski taler om et metasprog , som nødvendigvis skal være rigere end objektsproget .
Ligesom beviset på Gödel's første ufuldstændighedssætning bruger beviset på Tarskis sætning et diagonalt argument, der afslører en erklæring svarende til løgnerparadoxet .
Tarskis demonstration er en demonstration fra det absurde. Således antog han eksistensen af en formel for den aritmetiske V ( x ) med en fri variabel x, der definerer sandheden, det vil sige, at følgende ækvivalens:
A ⇔ V (⌈ A ⌉)er sandt i N for ethvert udsagn A .
Ved en diagonalisering identisk med den, der blev brugt til Gödel's første ufuldstændighedssætning (ved hjælp af substitutionspredikatet), opnår vi en sætning D (som afhænger af V ) og sådan, at følgende ækvivalens er sand i N :
D ⇔ ¬ V (⌈ D ⌉) (tegnet ¬ betyder negation).Påstand D hævder sig selv, at den er falsk, så det er virkelig en formalisering af løgnerens paradoks. Vi ender med en modsigelse, da vi, som V skal definere sandheden, også skal have:
D ⇔ V (⌈ A ⌉) sand i N .Vi opnåede udsagnet D ved diagonalisering fra en vilkårlig formel V, hvor Gödel for hans sætning bruger en formel, som han konstruerede tidligere for at repræsentere bevisbarhed i den betragtede teori.
Raymond Smullyan , sætningerne om ufuldstændigheden af Gödel , Dunod, 2000 ( ISBN 210005287X )