b"\n_START_ARTICLE_\nInsieme ricorsivamente enumerabile\n_START_SECTION_\nDefinizioni formali\n_START_PARAGRAPH_\nLe due seguenti definizioni degli insiemi r.e. sono date riferendosi solo all'insieme dei naturali e a funzioni dai naturali ai naturali; tuttavia tramite opportune funzioni di decodifica \xc3\xa8 possibile ricondurre a questi casi tutti gli altri insiemi numerabili.\n_START_SECTION_\nLa cardinalit\xc3\xa0 della classe degli insiemi r.e.\n_START_PARAGRAPH_\n\xc3\x88 piuttosto banale dimostrare che la cardinalit\xc3\xa0 della classe degli insiemi r.e. \xc3\xa8 numerabile, dato che si pu\xc3\xb2 stabilire una corrispondenza biunivoca dalla suddetta classe all'insieme delle macchine di Turing, nonostante possano esistere diverse MdT che accettano il medesimo insieme. Ci\xc3\xb2 \xc3\xa8 possibile perch\xc3\xa9, per definizione, ogni insieme r.e. \xc3\xa8 accettato da almeno una macchina di Turing, e inoltre l'insieme delle MdT \xc3\xa8 ricorsivo, dato che esiste una MdT in grado di stabilire sempre se un numero binario rappresenta una macchina di Turing valida. Dunque, a fortiori, l'insieme delle MdT \xc3\xa8 numerabile, e di conseguenza lo \xc3\xa8 anche la classe degli insiemi r.e.\n_START_SECTION_\nUnione e intersezione\n_START_PARAGRAPH_\nSe gli insiemi  e  sono r.e., allora anche  e  sono ricorsivamente enumerabili.\n_START_SECTION_\nComplemento di K\n_START_PARAGRAPH_\nL'insieme  non \xc3\xa8 r.e. _NEWLINE_Dimostrazione: si vede facilmente dal fatto che  \xc3\xa8 r.e. ma non ricorsivo, e applicando il corollario della propriet\xc3\xa0 sull'insieme complemento."