Enumeração

 Nota: Para outros significados, veja Enumeração (desambiguação).

Em matemática e ciência da computação teórica, a enumeração é a repetiçao de diversas palavras seguidas de virgula.

Enumeração como listagem

Formalmente, uma enumeração de um conjunto ${\displaystyle S}$ pode ser definida como:

• Um mapeamento sobrejetivo de ${\displaystyle \mathbb {N} }$ (os números naturais) a ${\displaystyle S}$. Essa definição é adequada por questões de computabilidade e teoria dos conjuntos.

• Um mapeamento bijetor de ${\displaystyle S}$ 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 é ${\displaystyle \{1,2,\cdots ,n\}}$ para algum ${\displaystyle n}$ que é a cardinalidade de ${\displaystyle S}$.

Em ciência da computação, considera-se como um requisito adicional para enumerações que o mapeamento de ${\displaystyle \mathbb {N} }$ 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 ${\displaystyle f(x)=x}$. Nesse caso, ${\displaystyle f:\mathbb {N} \to \mathbb {N} }$ é simplesmente a função identidade.
• ${\displaystyle \mathbb {Z} }$, o conjunto de números inteiros, é enumerável por

${\displaystyle f(x):={\begin{cases}-(x+1)/2,&{\mbox{se }}x{\mbox{ for impar}}\\x/2,&{\mbox{se }}x{\mbox{ for par}}.\end{cases}}}$

${\displaystyle f:\mathbb {N} \to \mathbb {Z} }$ é 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:

x	0	1	2	3	4	5	6	7	8
f(x)	0	−1	1	−2	2	−3	3	−4	4

• Todos os conjuntos finitos são enumeráveis. Seja ${\displaystyle S}$ um conjunto finito com ${\displaystyle n}$ elementos, e seja ${\displaystyle K=\{1,2,\cdots ,n\}}$. Selecione qualquer elemento ${\displaystyle s}$ em ${\displaystyle S}$ e atribua ${\displaystyle f(n)=s}$. Configure ${\displaystyle S'=S-\{s\}}$. Selecione qualquer elemento ${\displaystyle s'}$ em ${\displaystyle S'}$ e atribua ${\displaystyle f(n-1)=s'}$. Continue o processo até que todos os elementos do conjunto original sejam atribuídos a um números natural. Então ${\displaystyle f:\{1,2,\cdots ,n\}\to S}$ é uma enumeração de ${\displaystyle S}$.

• Os números reais não possuem enumeração, como provado pelo argumento de diagonalização de Cantor.

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.