• Istituto
    • Chi Siamo
    • La nostra storia
  • Magazine
    • Agenda
    • Atlante
    • Il Faro
    • Il Chiasmo
    • Diritto
    • Il Tascabile
    • Le Parole Valgono
    • Lingua italiana
    • WebTv
  • Catalogo
    • Le Opere
    • Bottega Treccani
    • Gli Ebook
    • Le Nostre Sedi
  • Scuola e Formazione
    • Portale Treccani Scuola
    • Formazione Digitale
    • Formazione Master
    • Scuola del Tascabile
  • Libri
    • Vai al portale
  • Arte
    • Vai al portale
  • Treccani Cultura
    • Chi Siamo
    • Come Aderire
    • Progetti
    • Iniziative Cultura
    • Eventi Sala Igea
  • ACQUISTA SU EMPORIUM
    • Arte
    • Cartoleria
    • Design & Alto Artigianato
    • Editoria
    • Idee
    • Marchi e Selezioni
  • Accedi
    • Modifica Profilo
    • Treccani X

indecidibilita

Enciclopedia della Matematica (2013)
  • Condividi

indecidibilita


indecidibilità in logica, termine utilizzato per indicare la non → decidibilità di una data proprietà. In particolare, un insieme è indecidibile se non esiste un algoritmo in grado di stabilire se un dato elemento appartiene o meno a esso. In questo senso il concetto di insieme indecidibile è strettamente collegato alla teoria della → calcolabilità. Una teoria formalizzata in un sistema formale S è indecidibile se lo è l’insieme dei suoi teoremi, se cioè non per ogni formula ben formata a di S esiste un algoritmo di calcolo che riesce a stabilire se a è un teorema 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. È importante distinguere il concetto di teoria indecidibile dalla nozione di formula indecidibile (→ decidibilità). Un esempio di enunciato indecidibile è quello espresso nel decimo problema di Hilbert, relativo alle equazioni diofantee (→ Hilbert, problemi di).

Tag
  • ASSIOMI DI → ZERMELO-FRAENKEL
  • TEORIA DELLA → CALCOLABILITÀ
  • ENUNCIATO INDECIDIBILE
  • TEORIA DEGLI INSIEMI
  • EQUAZIONI DIOFANTEE
Vocabolario
indecidibilità
indecidibilita indecidibilità s. f. [der. di indecidibile]. – L’essere indecidibile. In logica, condizione nella quale è impossibile decidere se una proposizione è vera o falsa.
paradòsso¹
paradosso1 paradòsso1 agg. e s. m. [dal gr. παράδοξος, comp. di παρα- nel sign. di «contro» e δόξα «opinione»; come sost., dal gr. παράδοξον (neutro sostantivato), lat. paradoxum]. – 1. agg. Che va contro l’opinione o contro il modo di...
  • Istituto
    • Chi Siamo
    • La nostra storia
  • Magazine
    • Agenda
    • Atlante
    • Il Faro
    • Il Chiasmo
    • Diritto
    • Il Tascabile
    • Le Parole Valgono
    • Lingua italiana
    • WebTv
  • Catalogo
    • Le Opere
    • Bottega Treccani
    • Gli Ebook
    • Le Nostre Sedi
  • Scuola e Formazione
    • Portale Treccani Scuola
    • Formazione Digitale
    • Formazione Master
    • Scuola del Tascabile
  • Libri
    • Vai al portale
  • Arte
    • Vai al portale
  • Treccani Cultura
    • Chi Siamo
    • Come Aderire
    • Progetti
    • Iniziative Cultura
    • Eventi Sala Igea
  • ACQUISTA SU EMPORIUM
    • Arte
    • Cartoleria
    • Design & Alto Artigianato
    • Editoria
    • Idee
    • Marchi e Selezioni
  • Accedi
    • Modifica Profilo
    • Treccani X
  • Ricerca
    • Enciclopedia
    • Vocabolario
    • Sinonimi
    • Biografico
    • Indice Alfabetico

Istituto della Enciclopedia Italiana fondata da Giovanni Treccani S.p.A. © Tutti i diritti riservati

Partita Iva 00892411000

  • facebook
  • twitter
  • youtube
  • instagram
  • Contatti
  • Redazione
  • Termini e Condizioni generali
  • Condizioni di utilizzo dei Servizi
  • Informazioni sui Cookie
  • Trattamento dei dati personali