Infinito Contável

Infinito contável refere-se a teoria dos conjuntos. Um conjunto é dito infinito se contém um subconjunto próprio que possa ser posto em correspondência biunívoca consigo mesmo. Um conjunto é dito infinito contável se pode ser posto em correspondência biunívoca com os naturais, ou seja, ser numerado.

Por exemplo, os números pares são um subconjunto próprio dos naturais mas cada número par pode ser posto em correspondência com um número natural.

Alguns conjuntos não podem ser postos nesta correspondência, um exemplo é o conjunto dos reais (conforme o argumento de diagonalização de Cantor).

Quando existe uma função bijectiva entre os naturais e um conjunto, esta função se chama uma enumeração do conjunto, e representa-se por $a_i\,$ sendo i o índice. Normalmente não é importante se o índice começa no zero ou no um.

Exemplos

O conjunto dos números naturais é infinito contável, pela função identidade
O conjunto dos números inteiros é infinito contável. Uma enumeração dos inteiros é:

f(n) = n/2 se n é par

f(n) = -(n+1)/2 se n é ímpar

O produto cartesiano de dois conjuntos contáveis é um conjunto contável. Para isto, basta mostrar uma função bijectiva de $\mathbb{N}^\star \times \mathbb{N}^\star \to \mathbb{N}^\star\,$ , por exemplo:

f (n, m) = (2 n + 1)2 m - 1

O conjunto dos números racionais é infinito contável. Temos que existe uma função injectiva de $\mathbb{Q}\,$ no conjunto infinito contável $\mathbb{Z} \times \mathbb{N}^\star\,$ , definida por $f(r) = (p, q), r = \frac {p} {q}, q > 0 \mbox{ e mdc}(p, q) = 1\,$ . Temos também que existe uma função injectiva de $\mathbb{N}\,$ em $\mathbb{Q}\,$ , que é a função inclusão. Portanto, pelo teorema de Cantor-Bernstein-Schroeder, existe uma enumeração de $\mathbb{Q}\,$