Enumeração

Foram assinalados vários problemas nesta página ou se(c)ção:

Não tem fontes.
Necessita ser reciclada de acordo com o livro de estilo.
Precisa ser formatada para o padrão wiki.

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 {\displaystyle S} $S$ pode ser definida como:

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

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

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

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

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

f : N → Z {\displaystyle f:\mathbb {N} \to \mathbb {Z} } $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 {\displaystyle S} $S$ um conjunto finito com n {\displaystyle n} $n$ elementos, e seja K = { 1 , 2 , ⋯ , n } {\displaystyle K=\{1,2,\cdots ,n\}} $K=\{1,2,\cdots ,n\}$ . Selecione qualquer elemento s {\displaystyle s} $s$ em S {\displaystyle S} $S$ e atribua f ( n ) = s {\displaystyle f(n)=s} $f(n)=s$ . Configure S ′ = S − { s } {\displaystyle S'=S-\{s\}} $S'=S-\{s\}$ . Selecione qualquer elemento s ′ {\displaystyle s'} $s'$ em S ′ {\displaystyle S'} $S'$ e atribua f ( n − 1 ) = s ′ {\displaystyle f(n-1)=s'} $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 , ⋯ , n } → S {\displaystyle f:\{1,2,\cdots ,n\}\to S} $f:\{1,2,\cdots ,n\}\to S$ é uma enumeração de S {\displaystyle S} $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.