Ancora logica: la categoricità e la completezza
Materia affascinante, la logica! Ma... ecco un altro dubbio
"A sentimento", direi che l'affermazione di Zanardo è quella corretta, e quella di Odifreddi (un po') imprecisa. Giusto?
Grazie, mille
"Odifreddi":
Una teoria è categorica quando descrive sostanzialmente un'unica realtà: tutti i modelli sono isomorfi tra loro. Una teoria categorica è completa. Il viceversa non vale (p.268).
"Alberto Zanardo":
Ogni teoria semanticamente completa e categorica è sintatticamente completa.
"A sentimento", direi che l'affermazione di Zanardo è quella corretta, e quella di Odifreddi (un po') imprecisa. Giusto?
Grazie, mille
Risposte
Vi dirò quello che più o meno ho capito sulla relazione tra categoricità e completezza sintattica di una teoria formale del primo ordine. Si dimostra che se tale teoria ammette un modello numerabile allora ne ammette anche uno non numerabile; si dimostra anche che qualsiasi teoria che abbia un modello ammette modelli numerabili, se ne conclude che la nozione di categoricità in senso assoluto è troppo forte e praticamente inapplicabile. Se ci restringiamo ai modelli normali (sono quelli che danno un'interpretazione adeguata della relazione di uguaglianza), le cose non migliorano molto, esistono teorie che ammettono un modello normale e sono categoriche ma il modello è finito, quindi non molto interessanti, almeno non quanto PA (teoria formale dell'aritmetica) ad esempio. Si previene così ad una definizione più ristretta: " $T$ è $ k $-categorica sse $T$ ha qualche modello di cardinalità $ k $ e tutti i modelli di cardinalità $ k $ sono isomorfi". La relazione tra categoricità e completezza sintattica allora è espressa nel seguente teorema: "Se $T$ è coerente e $ k $-categorica per qualche $ k \ge | \mathbb{N} |$ allora $T$ è sintatticamente completo".
"fields":
Perché Zanardo con il concetto di completezza semantica di un sistema S intende che S dimostra tutte le formule che sono vere in tutti i modelli di S. Odifreddi nell'implicazione (1) con il concetto di completezza semantica intende che S dimostra tutte le formule vere in un particolare modello di S (ovvero la completezza e' relativa a un modello, nel caso dell'aritmetica il modello fissato e' quello dei naturali).
Perfetto! Infatti, nel mio post precedente ho usato le virgolette per distinguere la completezza-semantica-nel-senso-che-dimostra-tutte-le formule-valide (per questa ho usate le virgolette) dalla completezza-semantica-nel-senso-che-dimostra-tutte-le-formule-vere (per questa niente virgolette).
La mia modesta esperienza è: usare una buona notazione è il primo passo per capire le cose. Usare lo stesso nome per indicare due cose diverse è una pessima idea. Il caso in questione (due sensi per la completezza semantica) non fa eccezione!
"fields":
Odifreddi inoltre parla sempre di teorie del prim'ordine e quello che hai scritto e ottimamente riassunto e' valido relativamente alla terminologia di Odifreddi e alla teorie del prim'ordine.
Alè!
Mi viene la voglia di approfondire la materia con un dottorato, ma sono troppo vecchio per queste cose... 
"fields":
ps: ho tentato di mandarti il libro ma la tua mail non lo accetta, dice che è troppo grosso (sono 10 MB)
Scusami!. L'indirizzo
lory chiocciola lorenzopantieri.net
dovrebbe funzionare!
Grazie grazie mille!
L.
La frase di Zanardo mi ha ovviamente messo in crisi: secondo quanto dice Odifreddi, infatti, non è necessaria la categoricità per avere l'implicazione (1).
Perché Zanardo con il concetto di completezza semantica di un sistema S intende che S dimostra tutte le formule che sono vere in tutti i modelli di S. Odifreddi nell'implicazione (1) con il concetto di completezza semantica intende che S dimostra tutte le formule vere in un particolare modello di S (ovvero la completezza e' relativa a un modello, nel caso dell'aritmetica il modello fissato e' quello dei naturali).
Odifreddi inoltre parla sempre di teorie del prim'ordine e quello che hai scritto e ottimamente riassunto e' valido relativamente alla terminologia di Odifreddi e alla teorie del prim'ordine. Zanardo invece ogni tanto parla anche di teorie del secondo ordine.
Edit: ps: ho tentato di mandarti il libro ma la tua mail non lo accetta, dice che è troppo grosso (sono 10 MB)
"fields":
In effetti la frase che hai citato
Ogni teoria semanticamente completa e categorica è sintatticamente completa.
si riferiva alle teorie assiomatiche in generale, e non alle teorie della logica dei predicati, alle quali ci si riferisce di solito e che sono oggetto della trattazione di Odifreddi. Zanardi considera infatti anche la logica del secondo ordine, quella in cui si quantificano non solo gli individui, ma anche i sottinsiemi di individui.
Fammi capire... Odifreddi tratta la logica proposizionale, la logica predicativa, l'aritmetica e la teoria dei numeri reali. Provo a riassumere.
Un sistema si dice:
semanticamente corretto (o semplicemente, corretto), se dimostra solo verità;
semanticamente completo, se dimostra tutte le verità;
sintatticamente corretto (o consistente), se non dimostra una formula e la sua negazione;
sintatticamente completo, se dimostra una formula o la sua negazione.
decidibile, se esiste un algoritmo in grado di determinare se una formula è un teorema oppure no;
categorico, quando descrive sostanzialmente un'unica realtà: tutti i modelli sono isomorfi tra loro.
La logica proposizionale è "semanticamente completa" (nel senso che dimostra tutte le proposizioni valide), corretta, consistente, sintatticamente incompleta, decidibile.
La logica predicativa è "sematicamente completa" (nel senso che dimostra tutte le proposizioni valide), corretta, consistente, sintatticamente incompleta, indecidibile.
L'aritmetica, se è consistente, è sintatticamente (e dunque anche sematicamente) incompleta (primo teorema di Goedel). Inoltre è indecidibile. (Qui semanticamente completo vuol dire che dimostra tutte le proposizioni vere). L’aritmetica, se è consistente, non può provare la propria consistenza (secondo teorema di Goedel).
La teoria dei numeri reali è sematicamente (e dunque anche sintatticamente) completa, decidibile, non categorica. (Anche qui semanticamente completo vuol dire che dimostra tutte le proposizioni vere).
Valgono le relazioni:
(1) completezza semantica implica completezza sintattica;
(2) correttezza imnplica consistenza;
(3) categorico implica sintatticamente completo;
(4) sintatticamente completo implica decidibile.
Tutto quello che ho appena scritto vale per le teorie del prim'ordine. Al second'ordine la teoria dei numeri reali è categorica, mentre al primo non lo è.
Comunque, il fatto che Odifreddi usi il termine "completezza semantica" in due sensi diversi, è una fonte di confusione che depreco con tutto il cuore.
Ciao,
L.
Sì, sono delle note carine. Sono informali, ma quando si sa già la logica si apprezzano in pieno: ti consiglio di tenerle. Certo se non si sa bene la logica anche queste possono originare dubbi...
In effetti la frase che hai citato
si riferiva alle teorie assiomatiche in generale, e non alle teorie della logica dei predicati, alle quali ci si riferisce di solito e che sono oggetto della trattazione di Odifreddi. Zanardi considera infatti anche la logica del secondo ordine, quella in cui si quantificano non solo gli individui, ma anche i sottinsiemi di individui.
In effetti la frase che hai citato
Ogni teoria semanticamente completa e categorica è sintatticamente completa.
si riferiva alle teorie assiomatiche in generale, e non alle teorie della logica dei predicati, alle quali ci si riferisce di solito e che sono oggetto della trattazione di Odifreddi. Zanardi considera infatti anche la logica del secondo ordine, quella in cui si quantificano non solo gli individui, ma anche i sottinsiemi di individui.
"fields":
C'e' un libro ottimo: Mendelson, "Introduzione alla logica matematica". E' perfetto, completo, con solo due pecche: la notazione e la teoria dei modelli. Ad esempio il quantificatore universale, e la negazione hanno simboli non piu' in uso. Inoltre il concetto di verita' e modello e' trattato in modo antico e non va bene. Infatti il libro e' perfetto per gli aspetti sintattici, in pieno stile hilbertiano, per questo te lo consiglio. Con e-mule puoi recuperarlo facilmente, o in italiano o in inglese.
Poi puoi attingere da dove ho studiato io per la prima volta, qui (in fondo alla pagina) http://www.scienze.univr.it/fol/main?en ... =&discrCd= Il materiale e' perfetto, ha pochi eguali. Alcuni studenti ne escono sconvolti, ma e' solo perche' la trattazione e' di alto livello dal punto di vista matematico. Tuttavia mancano alcune cose, che puoi trovare pero' sul primo libro.
Terzo: Enderton, "A mathematical introduction to logic". Ottimo e moderno. Se mi mandi il tuo indirizzo mail, te lo invio. Io leggerei per primo questo, e poi recupererei ciò che manca dagli altri.
Beh, che dire, grazie per questi riferimenti! La frase di Zanardo l'ho trovata qui: sembrano dispense davvero ben fatte, chiare e ricche di esempi, proprio come le sto cercando. Tuttavia ci sono delle differenze rispetto al testo di Odifreddi e ad altri...
Ah, il mio indirizzo e-mail è sit6113 chiocciola iperbole.bologna.it
Ciao e grazie ancora!
L.
"Lorenzo Pantieri":
Che cosa farei senza di te? Saresti così gentile da indicarmi una dispensa/un testo dove queste cose (completezza sintattica, semantica, correttezza, consisenza, decidibilità, categoricità e loro legami) sono fatte "come dio comanda" (parafrasando Odifreddi)?
Eh, eh, Lorenzo, te la cavi bene anche senza di me, a quanto sembra, e' che non hai fonti dirette da cui attingere. Ma sei fortunato: negli ultimi vent'anni c'e' stata un esplosione di testi di logica, di buoni testi di logica, se ne contano ora a centinaia...
C'e' un libro ottimo: Mendelson, "Introduzione alla logica matematica". E' perfetto, completo, con solo due pecche: la notazione e la teoria dei modelli. Ad esempio il quantificatore universale, e la negazione hanno simboli non piu' in uso. Inoltre il concetto di verita' e modello e' trattato in modo antico e non va bene. Infatti il libro e' perfetto per gli aspetti sintattici, in pieno stile hilbertiano, per questo te lo consiglio. Con e-mule puoi recuperarlo facilmente, o in italiano o in inglese.
Poi puoi attingere da dove ho studiato io per la prima volta, qui (in fondo alla pagina) http://www.scienze.univr.it/fol/main?en ... =&discrCd= Il materiale e' perfetto, ha pochi eguali. Alcuni studenti ne escono sconvolti, ma e' solo perche' la trattazione e' di alto livello dal punto di vista matematico. Tuttavia mancano alcune cose, che puoi trovare pero' sul primo libro.
Terzo: Enderton, "A mathematical introduction to logic". Ottimo e moderno. Se mi mandi il tuo indirizzo mail, te lo invio. Io leggerei per primo questo, e poi recupererei ciò che manca dagli altri.
Per quanto riguarda il consiglio di vl4d, e' ottimo, ma in effetti e' piu' per informatici e mancano parecchi concetti teorici.
Io sto studiando qui: http://www.cis.upenn.edu/~jean/gbooks/logic.html
E' un testo "classico" pensato per Computer Scientists, e forse ad un Matematico potra' non bastare, ma
per me e' veramente fatto molto molto bene.
E' un testo "classico" pensato per Computer Scientists, e forse ad un Matematico potra' non bastare, ma
per me e' veramente fatto molto molto bene.
"fields":
L'affermazione di Zanardo è ridondante, mentre l'affermazione di Odifreddi è imprecisa (naturalmente se svincolata dal contesto in cui si trova).
L'affermazione giusta sarebbe: Se una teoria è categorica allora è sintatticamente completa.
L'ipotesi che la teoria sia anche semanticamente completa è inutile.
Che cosa farei senza di te? Saresti così gentile da indicarmi una dispensa/un testo dove queste cose (completezza sintattica, semantica, correttezza, consisenza, decidibilità, categoricità e loro legami) sono fatte "come dio comanda" (parafrasando Odifreddi)?
Grazie mille... avanzi un a birra!
Ciao,
L.
L'affermazione di Zanardo è ridondante, mentre l'affermazione di Odifreddi è imprecisa (naturalmente se svincolata dal contesto in cui si trova).
L'affermazione giusta sarebbe: Se una teoria è categorica allora è sintatticamente completa.
L'ipotesi che la teoria sia anche semanticamente completa è inutile.
L'affermazione giusta sarebbe: Se una teoria è categorica allora è sintatticamente completa.
L'ipotesi che la teoria sia anche semanticamente completa è inutile.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo