Enumeração

Predefinição:Multitag Predefinição:Ver 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 $S$ pode ser definida como:

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

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

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

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

$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 $S$ um conjunto finito com $n$ elementos, e seja $K=\{1,2,\cdots ,n\}$. Selecione qualquer elemento $s$ em $S$ e atribua $f(n)=s$. Configure $S^{\prime }=S-\{s\}$. Selecione qualquer elemento $s^{\prime }$ em $S^{\prime }$ e atribua $f(n-1)=s^{\prime }$. Continue o processo até que todos os elementos do conjunto original sejam atribuídos a um números natural. Então $f:\{1,2,\cdots ,n\}\to S$ é uma enumeração de $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.