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.

CATEGORIE