Logica - Teorema del Tarski
Salve a tutti, è il mio primo post e quindi chiedo venia in anticipo.
Sto preparando un esame di logica e ho dubbi su una cosa.
L'argomento è la "deduzione naturale".
Su i miei appunti ho questa formulazione del
Teorema di Tarski
L'insieme T dei godeliani degli enunciati veri in N (cioè g[Th(N)]) ) non è esprimibile in N e non è neanche decidibile.
Dove N=($NN$;$<=$,<;+,*;0,1,2,... ...,n,...) e Th(N) è la teoria di N o ARITMETICA ELEMENTARE ovvero l'insieme degli enunciati veri nella struttura N. Infine $ g:E->NN $ (g dovrebbe essere la rappresentazione di Godel???)dove E è l'insieme degli enunciati ed è computabile ed effettivamente invertibile.
Come opera questa funzione di GODEL? Qual'è il significato di questo teorema? (Secondo me vuol dire che T non è esprimibile in N).
Spero di essere riuscito a spiegarmi.
Grazie.
Sto preparando un esame di logica e ho dubbi su una cosa.
L'argomento è la "deduzione naturale".
Su i miei appunti ho questa formulazione del
Teorema di Tarski
L'insieme T dei godeliani degli enunciati veri in N (cioè g[Th(N)]) ) non è esprimibile in N e non è neanche decidibile.
Dove N=($NN$;$<=$,<;+,*;0,1,2,... ...,n,...) e Th(N) è la teoria di N o ARITMETICA ELEMENTARE ovvero l'insieme degli enunciati veri nella struttura N. Infine $ g:E->NN $ (g dovrebbe essere la rappresentazione di Godel???)dove E è l'insieme degli enunciati ed è computabile ed effettivamente invertibile.
Come opera questa funzione di GODEL? Qual'è il significato di questo teorema? (Secondo me vuol dire che T non è esprimibile in N).
Spero di essere riuscito a spiegarmi.
Grazie.
Risposte
Ciao, purtroppo si legge malissimo tutto il tuo post, ti chiedo cortesemente di provare a modificarlo guardando qui
benvenuto nel forum.
non so quale sia il livello delle tue conoscenze precedenti, anche di carattere storico-filosofico, e non so esattamente che cosa ti occorra.
ti posso dire molto sinteticamente che Godel ha dimostrato che il "sogno" di Hilbert di dimostrare qualsiasi cosa all'interno della matematica è assurdo:
è impossibile dimostrare la fondatezza di una teoria mediante teoremi appartenenti alla stessa teoria ... da qui si parla di linguaggio "metamatematico".
se queste cose ti sono note, fai finta di nulla e prova a vedere questo file (non lo conosco, ma mi pare che possa esserti d'aiuto: l'ho trovato tramite un motore di ricerca).
http://math.sfsu.edu/smith/Math800/Unit ... Tarski.pdf
ciao.
non so quale sia il livello delle tue conoscenze precedenti, anche di carattere storico-filosofico, e non so esattamente che cosa ti occorra.
ti posso dire molto sinteticamente che Godel ha dimostrato che il "sogno" di Hilbert di dimostrare qualsiasi cosa all'interno della matematica è assurdo:
è impossibile dimostrare la fondatezza di una teoria mediante teoremi appartenenti alla stessa teoria ... da qui si parla di linguaggio "metamatematico".
se queste cose ti sono note, fai finta di nulla e prova a vedere questo file (non lo conosco, ma mi pare che possa esserti d'aiuto: l'ho trovato tramite un motore di ricerca).
http://math.sfsu.edu/smith/Math800/Unit ... Tarski.pdf
ciao.
Innanzitutto grazie per la risposta.
Questo esame è il penultimo della laurea specialistica in matematica e in questo caso il carattere storico-filosofico non c'entra.
Questo teorema è la conclusione di un "percorso" che (detto grossolanamente) vuole dimostrare le proprietà dell'aritmetica elementare. Tale aritmetica elementare è una teoria in un linguaggio del primo ordine che descrive, col linguaggio della logica formale, quanto già sappiamo.
Probabilmente, essendo la fine del corso, non ne potevo più e i miei appunti mancano di "qualcosa" e essendo uno studente lavoratore mi scocciava andare in facoltà per un chiarimento.
Quasi sicuramente, se riuscissi a capire come opera questa funzione di Godel, riuscirei a ricostruire il tutto.
Se qualcuno avesse un'idea ...
Ciao
Questo esame è il penultimo della laurea specialistica in matematica e in questo caso il carattere storico-filosofico non c'entra.
Questo teorema è la conclusione di un "percorso" che (detto grossolanamente) vuole dimostrare le proprietà dell'aritmetica elementare. Tale aritmetica elementare è una teoria in un linguaggio del primo ordine che descrive, col linguaggio della logica formale, quanto già sappiamo.
Probabilmente, essendo la fine del corso, non ne potevo più e i miei appunti mancano di "qualcosa" e essendo uno studente lavoratore mi scocciava andare in facoltà per un chiarimento.
Quasi sicuramente, se riuscissi a capire come opera questa funzione di Godel, riuscirei a ricostruire il tutto.
Se qualcuno avesse un'idea ...
Ciao
premetto che non ho capito esattamente che cosa tu voglia sapere: pare che tu voglia un chiarimento riguardo al teorema di tarski, però chiedi anche 'come opera' la funzione di goedel; io personalmente non ho idea di quali siano i programmi di logica matematica per i corsi di laurea in matematica, ma penso che dovresti aver studiato la dimostrazione del I teorema di incompletezza di goedel: la funzione di goedel associa ad ogni formula del linguaggio dell'aritmetica un numero naturale. detto in modo intuitivo, assegnamo ad ogni simbolo del linguaggio (connettivi vero-funzionali, quantificatori, variabili, funtori di successione, somma e prodotto...etc....) un numero, quindi con un algoritmo associamo un numero ad ogni sequenza di simboli (formula) a seconda dei simboli che la costituiscono. questo per rendere la cosa intuitivamente; in modo formale:
g(()=3, g())=5, g(,)=7, g(-)=9, g( $ -> $ )=11, g( $ AA $ )=13, g(=)=15, g(0)=17, g(f)=19, g(+)=21, g(*)=23, g(xi)=23+2i
dove '-' è il connettivo monadico di negazione, ed 'f' è il funtore di successione, che ad ogni numero naturale associa il successivo
quindi per ogni sequenza di simboli s1,..., sn:
g(s1,..., sn)=2^g(s1)*3^g(s2)*...*pn^g(sn)
dove 'pn' sta per n-esimo numero primo
in questo modo goedel per così dire esprime ogni proposizione dell'aritmetica con un oggetto dell'aritmetica; questo procedimento gioca un ruolo importante nella sua dimostrazione del teorema;
ora, tornando alla parte che più ti interessa, ovvero il teorema di tarski: l'insieme degli enunciati veri in N non è esprimibile in N.... cosa significa? significa che data una qualsiasi teoria formale (in questo caso particolare, l'aritmetica) non è possibile formulare la definizione di verità per tale teoria all'interno della teoria stessa; Tarski mostra che g(Th(N)) non è esprimibile in N, perchè se esistesse un predicato Th(x) siffatto, sarebbe possibile derivare all'interno dell'aritmetica una contraddizione; ma cos'è il nostro predicato Th(x)? è il predicato avente per argomenti enunciati, tale che Th(x) se e solo se x è verè, in altre parole, Th è l'espressione che stabilisce le condizioni per cui un qualsiasi enunciato x del nostro linguaggio è vero, ovvero: è una definizione di verità per un linguaggio formulata all'interno del linguaggio stesso; ma se esistesse Th(x), sarebbe possibile derivare all'interno della nostra teoria un analogo della (secolare) antinomia del mentitore, in altre parole, sarebbe possibile costruire una formula che dice di sè stessa di essere falsa; pertanto è condizione necessaria per la consistenza di una teoria (in particolare, nel nostro caso, dell'aritmetica) che la sua definizione di verità non venga formulata all'interno della teoria stessa, ma a livello metateorico.
ho scritto un po' di fretta ma spero di essere stato sufficientemente chiaro; se ci sono dei punti oscuri vedrò di chiarire.
g(()=3, g())=5, g(,)=7, g(-)=9, g( $ -> $ )=11, g( $ AA $ )=13, g(=)=15, g(0)=17, g(f)=19, g(+)=21, g(*)=23, g(xi)=23+2i
dove '-' è il connettivo monadico di negazione, ed 'f' è il funtore di successione, che ad ogni numero naturale associa il successivo
quindi per ogni sequenza di simboli s1,..., sn:
g(s1,..., sn)=2^g(s1)*3^g(s2)*...*pn^g(sn)
dove 'pn' sta per n-esimo numero primo
in questo modo goedel per così dire esprime ogni proposizione dell'aritmetica con un oggetto dell'aritmetica; questo procedimento gioca un ruolo importante nella sua dimostrazione del teorema;
ora, tornando alla parte che più ti interessa, ovvero il teorema di tarski: l'insieme degli enunciati veri in N non è esprimibile in N.... cosa significa? significa che data una qualsiasi teoria formale (in questo caso particolare, l'aritmetica) non è possibile formulare la definizione di verità per tale teoria all'interno della teoria stessa; Tarski mostra che g(Th(N)) non è esprimibile in N, perchè se esistesse un predicato Th(x) siffatto, sarebbe possibile derivare all'interno dell'aritmetica una contraddizione; ma cos'è il nostro predicato Th(x)? è il predicato avente per argomenti enunciati, tale che Th(x) se e solo se x è verè, in altre parole, Th è l'espressione che stabilisce le condizioni per cui un qualsiasi enunciato x del nostro linguaggio è vero, ovvero: è una definizione di verità per un linguaggio formulata all'interno del linguaggio stesso; ma se esistesse Th(x), sarebbe possibile derivare all'interno della nostra teoria un analogo della (secolare) antinomia del mentitore, in altre parole, sarebbe possibile costruire una formula che dice di sè stessa di essere falsa; pertanto è condizione necessaria per la consistenza di una teoria (in particolare, nel nostro caso, dell'aritmetica) che la sua definizione di verità non venga formulata all'interno della teoria stessa, ma a livello metateorico.
ho scritto un po' di fretta ma spero di essere stato sufficientemente chiaro; se ci sono dei punti oscuri vedrò di chiarire.
Sei un grande!
Hai colto nel segno, è quello che cercavo.
Questa sera mi riguardo tutto per bene e con calma, ma già ad una prima lettura sembra essersi chiarito tutto quello che volevo sapere.
Ti ringrazio tantissimo e se occorrerà ti disturberò ancora. Grazie comunque anche a chi ha cercato di aiutarmi in precedenza.
Hai colto nel segno, è quello che cercavo.
Questa sera mi riguardo tutto per bene e con calma, ma già ad una prima lettura sembra essersi chiarito tutto quello che volevo sapere.
Ti ringrazio tantissimo e se occorrerà ti disturberò ancora. Grazie comunque anche a chi ha cercato di aiutarmi in precedenza.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo