teoremi di indecidibilità
Silvio Bozzi
In logica matematica, risultati che affermano che una data teoria formalizzata T non è decidibile, vale a dire non ammette un algoritmo in grado di stabilire in [...] così esplicita l’analogia con i problemi di assiomatizzabilità e decidibilità per teorie. Su un altro versante si pone il teorema dimostrato da Yuri Matijasevic (1968), il quale prova che non esiste un algoritmo in grado di stabilire quando un ...
Leggi Tutto
Hauptsatz di Gentzen
Silvio Bozzi
Con questo nome (che significa teorema fondamentale) nella letteratura logica si indica una classe di teoremi il cui prototipo è dato dal risultato ottenuto da Gerhald [...] fornirebbe una dimostrazione finitista di coerenza. Come provato da Gentzen nel 1936 nel caso dell’aritmetica di Peano, il teorema vale ma richiede sul piano metateorico il ricorso all’induzione aperta sull’ordinale . Il discorso si può estendere a ...
Leggi Tutto
rimpiazzamento
rimpiazzaménto [Atto ed effetto del rimpiazzare, der. del fr. remplacer "mettere una cosa al posto di un'altra", comp. di re- sostitutivo e der. di place "posto"] [ALG] [FAF] Assioma, [...] o teoremi, di r.: nella logica matematica, assioma introdotto da A.A. Fraenkel, intorno al 1922, per eliminare alcuni inconvenienti della teoria assiomatica degli insiemi di Zermelo, che può essere così enunciato: se all'interno di una formula si ...
Leggi Tutto
Skolem Thoralf Albert
Skolem 〈skùulem〉 Thoralf Albert [STF] (Sandsvær 1887 - Oslo 1963) Prof. di matematica nell'univ. di Oslo (1938). ◆ [ALG] [FAF] Paradosso di S.: v. Gödel, teorema di: III 54 f. ◆ [...] [ALG] [FAF] Teoremi di Löwenheim-S.: v. logica: III 485 e. ...
Leggi Tutto
inferènza Nel linguaggio filosofico, ogni forma di ragionamento deduttivo, che dimostra come una proposizione derivi logicamente da un'altra. In logica matematica, si dicono 'regole d'i.' l'insieme delle [...] regole in base alle quali in un sistema deduttivo possono essere derivati enunciati e teoremi a partire da assiomi o da altri enunciati. ...
Leggi Tutto
dimostrazione
dimostrazióne [Der. del lat. demonstratio -onis, dal part. pass. demonstratus di demonstrare "rendere manifesto", comp. di de- e monstrare "mostrare"] [FAF] (a) Argomentazione attraverso [...] nozione o tesi è vera. (b) In una teoria matematica o fisica, procedimento consistente nel ricavare, come teoremi, proposizioni da altre proposizioni primitive. ◆ [FAF] D. a posteriori: in una teoria fisica, procedimento consistente nell'articolare ...
Leggi Tutto
Lowenheim Leopold
Löwenheim 〈lö´vënhàim〉 Leopold [STF] (Krefeld 1878 - Berlino 1940) Prof. di matematica nel liceo di Berlino-Lichtenberg. ◆ [ALG] [FAF] Teorema di L.: un'espressione in cui non occorrono [...] variabili predicative poliadiche, ma solo k monadiche, ammette un modello se e solo se ne ammette uno di cardinalità 2k. ◆ [ALG] [FAF] Teoremi di L.-Skolem: v. logica: III 485 e. ...
Leggi Tutto
logicismo
logicismo [Der. di logica] [STF] [FAF] (a) In senso lato, ogni dottrina che pone la logica a fondamento della filosofia. (b) In senso specifico, indirizzo di pensiero che, soprattutto per opera [...] tutti i concetti matematici a partire da un numero ristretto di concetti logici fondamentali e che tutti i teoremi matematici sono dimostrabili a partire da un numero ristretto di proposizioni logiche fondamentali; tale programma di riduzione della ...
Leggi Tutto
algoritmizzazione
algoritmizzazióne [Der. di algoritmizzare "tradurre in algoritmi"] [FAF] [INF] Processo di traduzione in algoritmi di un fenomeno naturale o artificiale, a scopo conoscitivo o normativo. [...] proposero addirittura un'a. della matematica, quale metodo più rigoroso di derivazione logica dei teoremi della matematica a partire dagli assiomi: ogni teorema dovrebbe, secondo questo programma di lavoro, essere visto come il risultato di un ...
Leggi Tutto
incompleto
incomplèto [agg. Comp. di in- neg. e completo] [CHF] Reazione i.: reazione che s'arresta prima della completa trasformazione delle sostanze reagenti. ◆ [ALG] [FAF] Teoria i.: nella logica [...] dice sintatticamente i. quando esiste una formula del suo linguaggio di cui non si può dimostrare né la verità né la falsità, e si dice semanticamente i. se esistono conseguenze dell'insieme dei suoi assiomi che non sono teoremi della teoria stessa. ...
Leggi Tutto
teorema
teorèma s. m. [dal lat. tardo theorēma, gr. ϑεώρημα (propr. «ricerca, meditazione», der. di ϑεω-ρέω «esaminare, osservare»)] (pl. -i). – 1. Nella cultura classica e medievale, la «visione» sensibile o intellettiva e il relativo oggetto,...
principio
princìpio s. m. [dal lat. principium, der. di princeps -cĭpis nel sign. di «primo»: v. principe]. – 1. a. L’atto e il fatto di cominciare, inizio: il p. di una azione, di un’impresa; il p. di una nuova vita; dare p., avviare, intraprendere...