teoria indecidibile

Enciclopedia della Matematica (2013)

teoria indecidibile


teoria indecidibile in logica, teoria formalizzata in un sistema formale S per la quale non per ogni formula ben formata a di S esiste un algoritmo di calcolo che riesce a stabilire se a è un teorema della teoria oppure no, vale a dire se a è o non è dimostrabile nel sistema formale dato. Esempi di teorie indecidibili sono l’aritmetica formalizzata dagli assiomi di → Peano e la teoria degli insiemi formalizzata secondo gli assiomi di → Zermelo-Fraenkel (→ decidibilità).

Tag
Vocabolario
indecidìbile
indecidibile indecidìbile agg. [der. di decidere, col pref. in-2]. – Propr., che non può essere deciso. In logica, è detto di ogni asserzione, proposizione, formula per la quale si dimostra che, in un dato sistema formalizzato, né essa...
teorìa
teoria teorìa s. f. [dal gr. ϑεωρία, der. di ϑεωρός (v. teoro), e quindi, in origine, «delegazione di teori»; nel sign. 1, attraverso il lat. tardo theorĭa]. – 1. Formulazione logicamente coerente (in termini di concetti ed enti più o meno...