Enumeração

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.

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:

• 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.

• 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.

 

O Wikcionário tem o verbete enumeração.