Il teorema di indefinibilità di Tarski

Il teorema di indefinibilità di Tarski (Reindirizzato dal teorema di indefinibilità di Tarski) Vai alla navigazione Vai alla ricerca del teorema di indefinibilità di Tarski, dichiarato e dimostrato da Alfred Tarski in 1933, è un importante risultato limitativo nella logica matematica, i fondamenti della matematica, e nella semantica formale. In modo informale, il teorema afferma che la verità aritmetica non può essere definita in aritmetica.

Il teorema si applica più in generale a qualsiasi sistema formale sufficientemente forte, mostrando che la verità nel modello standard del sistema non può essere definita all'interno del sistema.

Contenuti 1 Storia 2 Dichiarazione 3 Forma generale 4 Discussione 5 Guarda anche 6 Riferimenti Storia In 1931, Kurt Gödel ha pubblicato i teoremi di incompletezza, cosa che ha dimostrato in parte mostrando come rappresentare la sintassi della logica formale all'interno dell'aritmetica del primo ordine. Ad ogni espressione del linguaggio formale dell'aritmetica viene assegnato un numero distinto. Questa procedura è nota in vari modi come numerazione di Gödel, codifica e, più generalmente, come aritmetizzazione. In particolare, vari insiemi di espressioni sono codificati come insiemi di numeri. Per varie proprietà sintattiche (come essere una formula, essere una frase, eccetera.), questi insiemi sono calcolabili. Inoltre, qualsiasi insieme calcolabile di numeri può essere definito da una formula aritmetica. Per esempio, ci sono formule nel linguaggio dell'aritmetica che definiscono l'insieme dei codici per le frasi aritmetiche, e per le frasi aritmetiche dimostrabili.

Il teorema di indefinibilità mostra che questa codifica non può essere eseguita per concetti semantici come la verità. Mostra che nessun linguaggio interpretato sufficientemente ricco può rappresentare la propria semantica. Un corollario è che ogni metalinguaggio in grado di esprimere la semantica di qualche linguaggio oggetto deve avere una potenza espressiva superiore a quella del linguaggio oggetto. Il metalinguaggio include nozioni primitive, assiomi, e regole assenti dal linguaggio oggetto, in modo che ci siano teoremi dimostrabili nel metalinguaggio non dimostrabili nel linguaggio oggetto.

Il teorema di indefinibilità è convenzionalmente attribuito ad Alfred Tarski. Gödel ha anche scoperto il teorema di indefinibilità in 1930, pur dimostrando i suoi teoremi di incompletezza pubblicati in 1931, e ben prima del 1933 pubblicazione dell'opera di Tarski (Murawski 1998). Mentre Gödel non ha mai pubblicato nulla attinente alla sua scoperta indipendente dell'indefinibilità, lo ha descritto in a 1931 lettera a John von Neumann. Tarski aveva ottenuto quasi tutti i suoi risultati 1933 monografia "Il concetto di verità nei linguaggi delle scienze deduttive" fra 1929 e 1931, e ne ha parlato al pubblico polacco. Tuttavia, come ha sottolineato nel giornale, il teorema di indefinibilità è stato l'unico risultato che non ha ottenuto prima. Secondo la nota a piè di pagina al teorema di indefinibilità (Teorema I.) del 1933 monografia, il teorema e lo schizzo della dimostrazione furono aggiunti alla monografia solo dopo che il manoscritto era stato inviato alla tipografia in 1931. Tarski lo riferisce lì, quando ha presentato il contenuto della sua monografia all'Accademia delle scienze di Varsavia lo scorso marzo 21, 1931, ha espresso a questo punto solo alcune congetture, basato in parte sulle sue stesse indagini e in parte sulla breve relazione di Gödel sui teoremi di incompletezza "Alcuni risultati metamatematici sulla determinazione e la coerenza delle decisioni" [Alcuni risultati metamatematici sulla determinatezza della decisione e sulla coerenza], Accademia austriaca delle scienze, vienna, 1930.

Enunciato Dichiareremo prima una versione semplificata del teorema di Tarski, quindi enunciare e dimostrare nella sezione successiva il teorema dimostrato da Tarski 1933.

Sia L il linguaggio dell'aritmetica del primo ordine. Questa è la teoria dei numeri naturali, compresa la loro addizione e moltiplicazione, assiomatizzato dagli assiomi di Peano del primo ordine. Questo è un "primo ordine" teoria: i quantificatori si estendono sui numeri naturali, ma non su insiemi o funzioni di numeri naturali. La teoria è abbastanza forte da descrivere funzioni intere definite ricorsivamente come l'esponenziazione, fattoriali o la sequenza di Fibonacci.

Sia N la struttura standard per L, cioè. N è costituito dall'insieme ordinario dei numeri naturali e dalla loro addizione e moltiplicazione. Ogni frase in L può essere interpretata in N e quindi diventa vera o falsa. così (l, N) è il "linguaggio aritmetico del primo ordine interpretato".

Ogni formula φ in L ha un numero di Gödel g(Phi). Questo è un numero naturale che "codifica" Phi. In quel modo, la lingua L può parlare di formule in L, non solo di numeri. Sia T l'insieme delle L-frasi vere in N, e T* l'insieme dei numeri di Gödel degli enunciati in T. Il seguente teorema risponde alla domanda: Può T* essere definito da una formula di aritmetica del primo ordine?

Il teorema di indefinibilità di Tarski: Non esiste una formula L True(n) che definisce T*. Questo è, non esiste una formula L True(n) tale che per ogni L-frase A, Vero(g(UN)) ↔ A vale in N.

In modo informale, il teorema dice che il concetto di verità delle affermazioni aritmetiche del primo ordine non può essere definito da una formula nell'aritmetica del primo ordine. Ciò implica una notevole limitazione dell'ambito di applicazione "autorappresentazione". È possibile definire una formula True(n) la cui estensione è T*, ma solo attingendo a un metalinguaggio la cui forza espressiva va oltre quella di L. Per esempio, un predicato di verità per l'aritmetica del primo ordine può essere definito nell'aritmetica del secondo ordine. Tuttavia, questa formula potrebbe solo definire un predicato di verità per formule in lingua originale L. Definire un predicato di verità per il metalinguaggio richiederebbe un metametalinguaggio ancora più elevato, e così via.

Per dimostrare il teorema, procediamo per contraddizione e assumiamo che una formula L True(n) esiste che è vero per il numero naturale n in N se e solo se n è il numero di Gödel di un enunciato in L che è vero in N. Potremmo quindi usare True(n) per definire una nuova formula L S(m) che è vero per il numero naturale m se e solo se m è il numero di Gödel di una formula φ(X) (con una variabile libera x) tale che φ(m) è falsa se interpretata in N (cioè. la formula φ(X), quando applicato al proprio numero Gödel, restituisce una dichiarazione falsa). Se ora consideriamo il numero di Gödel g della formula S(m), e chiedi se la sentenza S(g) è vero in N, otteniamo una contraddizione. (Questo è noto come un argomento diagonale.) Il teorema è un corollario del teorema di Post sulla gerarchia aritmetica, dimostrato alcuni anni dopo Tarski (1933). Una dimostrazione semantica del teorema di Tarski dal teorema di Post è ottenuta per reductio ad absurdum come segue. Assumendo che T* sia definibile aritmeticamente, esiste un numero naturale n tale che T* sia definibile da una formula a livello {displaystyle Sigma _{n}^{0}} della gerarchia aritmetica. Tuttavia, T* è {displaystyle Sigma _{K}^{0}} -difficile per tutti k. Così la gerarchia aritmetica crolla al livello n, contraddice il teorema di Post.

Forma generale Tarski ha dimostrato un teorema più forte di quello sopra esposto, utilizzando un metodo interamente sintattico. Il teorema risultante si applica a qualsiasi linguaggio formale con negazione, e con sufficiente capacità di autoreferenzialità che vale il lemma diagonale. L'aritmetica del primo ordine soddisfa queste precondizioni, ma il teorema si applica a sistemi formali molto più generali, come ZFC.

Il teorema di indefinibilità di Tarski (forma generale): Permettere (l,N) essere qualsiasi linguaggio formale interpretato che includa la negazione e abbia una numerazione di Gödel g(Phi) soddisfacendo il lemma diagonale, cioè. per ogni formula L B(X) (con una variabile libera x) esiste una frase A tale che A ↔ B(g(UN)) tiene in N. Allora non c'è la formula L True(n) con la seguente proprietà: per ogni L-frase A, Vero(g(UN)) ↔ A è vero in N.

La dimostrazione del teorema di indefinibilità di Tarski in questa forma è ancora una volta per reductio ad absurdum. Supponiamo che una formula L True(n) come sopra esisteva, cioè., se A è una frase di aritmetica, poi Vero(g(UN)) vale per N se e solo se A vale per N. Quindi per tutti A, la formula Vero(g(UN)) ↔ A vale in N. Ma il lemma diagonale fornisce un controesempio a questa equivalenza, dando un "bugiardo" formula S tale che S ↔ ¬Vero(g(S)) tiene in N. Questa è una contraddizione. È.

Discussione Il meccanismo formale della dimostrazione data sopra è del tutto elementare eccetto per la diagonalizzazione che il lemma diagonale richiede. Anche la dimostrazione del lemma diagonale è sorprendentemente semplice; Per esempio, non invoca in alcun modo funzioni ricorsive. La dimostrazione presuppone che ogni formula L abbia un numero di Gödel, ma non sono richieste le specifiche di un metodo di codifica. Quindi il teorema di Tarski è molto più facile da motivare e dimostrare rispetto ai più celebri teoremi di Gödel sulle proprietà metamatematiche dell'aritmetica del primo ordine.

Smullian (1991, 2001) ha sostenuto con forza che il teorema di indefinibilità di Tarski merita gran parte dell'attenzione raccolta dai teoremi di incompletezza di Gödel. Che questi ultimi teoremi hanno molto da dire su tutta la matematica e in modo più controverso, su una serie di questioni filosofiche (per esempio., Luca 1961) è meno che evidente. Il teorema di Tarski, d'altro canto, non riguarda direttamente la matematica, ma i limiti intrinseci di qualsiasi linguaggio formale sufficientemente espressivo da essere di reale interesse. Tali linguaggi sono necessariamente in grado di autoriferirsi a sufficienza perché il lemma diagonale possa applicarsi ad essi. Il significato filosofico più ampio del teorema di Tarski è più evidente.

Un linguaggio interpretato è fortemente semanticamente autorappresentativo esattamente quando il linguaggio contiene predicati e simboli di funzione che definiscono tutti i concetti semantici specifici del linguaggio. Quindi le funzioni richieste includono il "funzione di valutazione semantica" mappare una formula A al suo valore di verità ||UN||, e il "funzione di denotazione semantica" mappare un termine t all'oggetto che denota. Il teorema di Tarski si generalizza quindi come segue: Nessun linguaggio sufficientemente potente è fortemente semanticamente autorappresentativo.

Il teorema di indefinibilità non impedisce che la verità in una teoria sia definita in una teoria più forte. Per esempio, l'insieme di (codici per) le formule dell'aritmetica di Peano del primo ordine che sono vere in N sono definibili da una formula dell'aritmetica del secondo ordine. Allo stesso modo, l'insieme delle formule vere del modello standard dell'aritmetica del secondo ordine (o aritmetica dell'n-esimo ordine per ogni n) può essere definito da una formula in ZFC del primo ordine.

Vedi anche Teoremi di incompletezza di Gödel – Risultati limitativi nella logica matematica Riferimenti J. l. Campana, e M. Machover, 1977. Un corso di logica matematica. Olanda Settentrionale. G. Boolo, J. Burgess, e R. Jeffrey, 2002. Calcolabilità e logica, 4th ed. Cambridge University Press. J. R. Luca, 1961. "Mente, Macchine, e Godel". Filosofia 36: 112–27. R. Murawski, 1998. Indefinibilità della verità. Il problema della priorità: Tarski vs. Godel. Storia e filosofia della logica 19, 153–160 R. Smullian, 1991. Teoremi di incompletezza di Godel. Università di Oxford. Premere. R. Smullian, 2001. "Teoremi di incompletezza di Gödel". In l. Goble, ed., La guida di Blackwell alla logica filosofica, Blackwell, 72–89. UN. Tarski, 1933. Il concetto di verità nei linguaggi delle scienze dell'educazione. Pubblicato dalla Società Scientifica di Varsavia. UN. Tarski (1936). "Il concetto di verità nei linguaggi formalizzati" (PDF). Studi filosofici. 1: 261–405. Archiviato dall'originale (PDF) Su 9 Gennaio 2014. Recuperato 26 Giugno 2013. UN. Tarski, tr. J. H. Woodger, 1983. "Il concetto di verità nei linguaggi formalizzati". Traduzione inglese di Tarski 1936 articolo. In un. Tarski, ed. J. Corcoran, 1983, Logica, Semantica, Metamatematica, Hackett. mostra vte Metalogica e metamatematica mostra vte Truth mostra vte Logica matematica Categorie: Logica matematicaMetateoremiFilosofia della logicaTeoremi nei fondamenti della matematicaTeorie della verità