Dimostrazione, teoria della
Jean-Yves Girard
La teoria della dimostrazione nasce negli anni Venti del Novecento come strumento di realizzazione del programma di David Hilbert per la fondazione della [...] in vista di risultati negativi come il teoremadi indecidibilità di Kurt Gödel, che dicompletezza, risultati sull'eliminazione del taglio, corollari analoghi al principio della sottoformula e ‒ ammesse formule infinite ‒ anche un teoremadi ...
Leggi Tutto
Storia della civiltà europea a cura di Umberto Eco (2014)
Andrea Bernardoni
Il contributo è tratto da Storia della civiltà europea a cura di Umberto Eco, edizione in 75 ebook
All’inizio del Novecento la logica si sviluppa sotto l’egida della problematica circa [...] combinatori, ovvero le dimostrazioni.
Gli anni Trenta si aprono con l’elaborazione del teoremadicompletezzadiGödel che sembra confermare l’ipotesi possibilista di von Neumann. Tuttavia, negli stessi anni, si va profilando un altro filone logico ...
Leggi Tutto
Storia della civiltà europea a cura di Umberto Eco (2014)
Giorgio Strano
Il contributo è tratto da Storia della civiltà europea a cura di Umberto Eco, edizione in 75 ebook
Negli anni Trenta del Novecento i logici riescono a dare uno statuto matematico alla [...] teorema. Il motivo è che al suo interno unicamente la nozione di ricorsività rimanda a una definizione precisa, laddove la nozione di essere fatta risalire a una lettera diGödel del 20 marzo 1956 a John della nozione di NP-completezza, dimostrando che ...
Leggi Tutto
assiomatizzazione
Processo che riconduce un insieme di conoscenze a principi dai quali l’insieme può essere derivato o dedotto. È possibile distinguere nella riflessione matematica (e in quella filosofica [...] proprietà più note ricordiamo: la coerenza, l’indipendenza, la completezza e la decidibilità. Una teoria T è coerente se e solo se non vi è alcuna formula A di T tale che sia A che non-A siano teoremidi T; è completa se e solo se, per ogni enunciato ...
Leggi Tutto
completezzacompletézza [Der. di completo] [FAF] Proprietà di una teoria fisica per cui ogni suo elemento ha un corrispettivo nella realtà: v. completezza. ◆ [MCQ] C. asintotica: locuz. con cui s'indica [...] coincidente con f (nel senso che per gli stessi argomenti assume gli stessi valori di f). ◆ [FAF] Teoremadi c. semantica: nella logica, teorema, dimostrato da H. Gödel nel 1930, secondo il quale ogni teoria elementare, cioè del primo ordine, non ...
Leggi Tutto
conseguenza
conseguenza si dice che l’enunciato P è conseguenza logica di un insieme A di enunciati (tipicamente un sistema di assiomi) quando P è dedotta da uno o più enunciati di A. Se la deduzione [...] invece il fatto che P risulta vero in tutti modelli in cui sono veri gli enunciati di A. Per il teoremadicompletezzadiGödel, le due nozioni di conseguenza coincidono nella teoria del primo ordine relativa ai predicati. In essa, quindi, tutto ciò ...
Leggi Tutto
coerenza
coerenza in logica, termine (sinonimo di non contraddittorietà e di consistenza), che indica la proprietà di un sistema assiomatico in cui non è possibile derivare contraddizioni: un sistema [...] completezza semantica di questi due sistemi assiomatici; un esempio di teoria non coerente è la teoria degli insiemi nella formulazione di Cantor. Secondo la teoria di cioè ammette un modello. Il secondo teoremadiGödel asserisce che, se una teoria è ...
Leggi Tutto
Matematico tedesco (Königsberg 1862 - Gottinga 1943). Figura eminente della matematica e della filosofia della matematica a cavallo tra il 19° e il 20° sec., H. ha apportato, negli anni di insegnamento [...] a coerenza, completezza e indipendenza. di tale metateoria combinatoria. Il programma di completa formalizzazione delle teorie matematiche fu messo in crisi dalla formulazione, a opera diGödel, del teoremadi incompletezza (1930-31), ma sui lavori di ...
Leggi Tutto
Storia della civiltà europea a cura di Umberto Eco (2014)
Maria Conforti
Il contributo è tratto da Storia della civiltà europea a cura di Umberto Eco, edizione in 75 ebook
I teoremi d’incompletezza diGödel del 1931 sono i risultati più profondi e spettacolari [...] teoremadicompletezza semantica, dall’indimostrabilità di G in PA segue che G non è conseguenza logica di PA, ossia che non tutti i modelli di PA sono anche modelli di immunità. E tuttavia se i risultati diGödel ci conducono a una drastica e ...
Leggi Tutto
fondamenti, crisi dei
fondamenti, crisi dei locuzione con la quale si intende l’insieme di problemi, discussioni e ricerche in campo matematico e logico che si verificò agli inizi del secolo xx in seguito [...] naturali, che sta alla base di ogni altra teoria. Il programma di Hilbert, volto a dimostrare la coerenza e la completezza almeno dell’aritmetica, si rivelò ben presto impossibile, come fu dimostrato nel 1931 dal teoremadi incompletezza di → Gödel. ...
Leggi Tutto