enumerabile, insieme

Enciclopedia on line

Un insieme I si dice e. quando esiste un procedimento effettivo (➔ decisione) per stabilire una corrispondenza biunivoca tra I e l’insieme dei numeri naturali (nell’insieme numerabile invece non viene posta una condizione di effettiva costruibilità della corrispondenza).

Valgono tra i concetti di decidibilità, computabilità ed enumerabilità le relazioni: a) un insieme I è decidibile se e solo se sia I che il suo complemento sono e.; b) un insieme I è e. se e solo se esso è l’insieme dei valori di una funzione computabile.

Vedi anche
bicondizionale In logica matematica, la connessione p ↔ q di due enunciati p e q, che è vera se e solo se essi sono entrambi veri o entrambi falsi. computabilità computabilità In logica matematica, nozione che di solito s’identifica con quella di ricorsività generale, introdotta intorno al 1936 da A.M. Turing e da E.L. Post. Una funzione numerica di n variabili si dice computabile se esiste un algoritmo per cui si possa, con un numero finito di passi, calcolare ... applicazione matematica Il concetto di applicazione è una generalizzazione del concetto classico di funzione (➔ corrispondenza). Si parla di applicazione di un insieme P in un insieme Q, quando tra i due si stabilisce una corrispondenza del tipo seguente: a ogni elemento di P corrisponde un ben determinato elemento ... relazione Rapporto che collega, in maniera essenziale o accidentale, due o più cose, fatti, concetti. ● Esposizione, orale o scritta, con cui si danno informazioni intorno allo stato di una questione, ai risultati di una perizia, ai lavori compiuti da una commissione, da un organo collegiale. botanica Si parla ...
Categorie
Vocabolario
enumeràbile
enumerabile enumeràbile agg. [der. di enumerare]. – Che può essere enumerato, cioè enunciato ordinatamente (non com.): i suoi meriti sono tanti, che sono difficilmente enumerabili. Con sign. specifico, nella logica matematica, si dice di...
enumerazióne
enumerazione enumerazióne s. f. [dal lat. enumeratio -onis]. – 1. L’atto, il fatto di enumerare; enunciazione ordinata e puntuale di una serie di cose: mi fece una lunga e. dei mali che lo affliggevano; le parole con cui si enumera: una...