Formalmente, uma enumeração de um conjunto
pode ser definida como:
- Um mapeamento bijetor de
para um segmento dos números naturais. Essa definição é adequada para questões de combinatória e conjuntos finitos. Assim, o início do segmento dos números naturais é
para algum
que é a cardinalidade de
.
Em ciência da computação, considera-se como um requisito adicional para enumerações que o mapeamento de
para o conjunto seja computável. O conjunto é então chamado recursivamente enumerável, referindo-se ao uso de teoria da recursividade na formalização do que significa ao mapeamento ser computável.
Exemplos
Seja:
- Os números naturais são enumeráveis pela função
. Nesse caso,
é simplesmente a função identidade.
, o conjunto de números inteiros, é enumerável por

é uma bijeção já que cada número natural corresponde a exatamente um número inteiro. A seguinte tabela fornece os primeiros valores da enumeração:
Mais informação x, f(x) ...
x |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
f(x) |
0 | −1 | 1 | −2 | 2 | −3 | 3 | −4 | 4 |
Fechar
- Todos os conjuntos finitos são enumeráveis. Seja
um conjunto finito com
elementos, e seja
. Selecione qualquer elemento
em
e atribua
. Configure
. Selecione qualquer elemento
em
e atribua
. Continue o processo até que todos os elementos do conjunto original sejam atribuídos a um números natural. Então
é uma enumeração de
.
Propriedades
- Existe uma enumeração para um conjunto somente se o conjunto for contável.
- Se um conjunto é enumerável ele terá uma número infinito de diferentes enumerações, exceto nos casos de conjunto vazio ou conjuntos com um elemento.