Decidibilità: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m →Decidibilità in logica matematica: +consistente |
|||
Riga 11:
Nella logica matematica un enunciato rappresentato da una [[formula ben formata]] φ di una [[teoria del primo ordine]] '''T''' si dice '''decidibile in T''' se o φ o la sua [[negazione]] ¬φ sono [[Teoria del primo ordine#dimostrazioni formali|dimostrabili]] in '''T'''. In caso contrario (se cioè non sono dimostrabili nè φ nè ¬φ) l'enunciato di dice '''indecidibile in T'''.
Esempi classici di enunciati indecidibili sono dati dal [[teorema di Goodstein]] per l'[[aritmetica di Peano]] e dall'[[ipotesi del continuo]] per la [[teoria assiomatica degli insiemi]]. Tali enunciati sono stati dimostrati indecidibili sotto l'ipotesi che le teorie in questione siano [[consistenza (logica matematica)|consistenti]]. I [[teoremi di incompletezza di Gödel]] forniscono una procedura con cui data una qualunque teoria consistente '''T''' in grado di [[funzione rappresentabile|rappresentare]] le operazioni di addizione e moltiplicazione sui [[numeri naturali]] è possibile costruire enunciati indecidibili da '''T'''. Le [[formula ben formata|formule]] associate a tali enunciati tuttavia sono talmente lunghe e complesse che la loro scrittura esplicita nel [[linguaggio del primo ordine]] è di fatto impossibile da realizzare sia per un uomo sia per un computer.
[[categoria: logica matematica]]
| |||