Enumeraçã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{cases}-(x+1)/2,&{\mbox{se }}x{\mbox{ for impar}}\\x/2,&{\mbox{se }}x{\mbox{ for par}}.\end{cases}}

$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'=S-\{s\}$ . Selecione qualquer elemento $s'$ em $S'$ e atribua $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 $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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.