Conjuntos enumeráveis

A enumerabilidade de um conjunto é uma espécie de equivalente do tamanho de conjuntos, porque nos conjuntos infinitos não dá para trabalhar com o número de elementos, já que o número de elementos é, surpreendentemente… infinito. O tamanho de um conjunto também é chamado de cardinalidade.

Tamanho de um conjunto infinito

Determinar o tamanho de um conjunto finito é simples: contamos o número de elementos. Assim, o conjunto M = {a, b, c, d, e} tem tamanho 5, e escrevemos |M| = 5.

Nos conjuntos infinitos, a situação é bem mais complicada. Como poderíamos comparar o tamanho de conjuntos infinitos? Isso é possível, afinal, ou todos os conjuntos infinitos são “do mesmo tamanho”?

Como exemplo, tomemos o conjunto dos números naturais (sem o zero) e o conjunto dos números naturais pares. Temos, assim, os conjuntos ℕ^* = {1, 2, 3, 4, 5, 6, …} e S = {2, 4, 6, …}. Daria vontade de dizer que o conjunto dos números naturais é maior que o conjunto dos números pares, porque os números naturais contêm todos os números pares e ainda alguns elementos a mais — os números ímpares.

Poderíamos então escrever que vale S ⊂ ℕ^*, isto é, o conjunto S é subconjunto próprio do conjunto ℕ^*. E poderíamos dizer que, se S ⊂ ℕ^*, o conjunto ℕ^* é maior — afinal, contém mais elementos que o conjunto S.

Um dos motivos pelos quais não podemos medir conjuntos pela relação de subconjunto é que conjuntos podem ter tamanhos diferentes mesmo quando nenhum dos dois é subconjunto do outro. Isso pode ser mostrado até com conjuntos finitos: A = {1, 3, 4, 9} e B = {b, u, r, z, m}. Vale |A| = 4 e |B| = 5. O conjunto B é maior que o conjunto A, mas não vale A ⊂ B. No caso de conjuntos infinitos, podemos ver isso nos números pares e ímpares. Nenhum dos dois conjuntos é subconjunto do outro.

A relação de subconjunto não será, portanto, a candidata ideal para decidir se um conjunto é maior que outro.

Bijeção

Vamos tentar outra abordagem. Temos dois conjuntos, A e B. Podemos dizer que eles têm o mesmo tamanho se existe uma função bijetora entre eles. O que isso significa? Que tomamos um elemento do conjunto A, um elemento do conjunto B e formamos o par (a, b). Removemos esses elementos dos conjuntos e continuamos. Se conseguimos “esvaziar” os dois conjuntos, encontramos uma função bijetora.

Exemplo com conjuntos finitos: A = {a, b, c} e B = {1, 2, 3}. O primeiro par poderia ser (a, 1), o seguinte (b, 2) e, por fim, (c, 3). Esgotamos todos os elementos dos dois conjuntos, encontramos uma função bijetora. É importante notar que essa não é a única função bijetora. Esta também é uma solução válida: (a, 3), (b, 1), (c, 2).

Nos conjuntos infinitos, a coisa já fica um pouco mais interessante. Vamos tentar os números naturais ímpares e pares. Intuitivamente, sentimos que deveria haver a mesma quantidade deles. Vamos tentar. Tomamos o primeiro número ímpar e o associamos ao primeiro número par: (1, 2). Depois, o segundo ímpar e o segundo par: (3, 4). E assim por diante. Obtemos, assim, os pares: (1, 2), (3, 4), (5, 6), (7, 8), … Poderíamos escrever que cada número ímpar l é associado ao número par l + 1 e cada número par s é a imagem do número ímpar s − 1. Assim, para cada número ímpar e para cada número par temos algum par que contém esse número. Os conjuntos dos números ímpares e pares têm, portanto, o mesmo tamanho.

Números pares versus números naturais

Agora vamos tentar o mesmo procedimento e comparar o conjunto dos números naturais e o dos números pares. Temos os conjuntos ℕ^* = {1, 2, 3, 4, 5, 6, …} e S = {2, 4, 6, …}. Intuitivamente, esperamos que o conjunto dos números naturais seja maior.

Vamos, porém, tentar encontrar a bijeção em questão. Podemos dizer que cada número natural n é associado ao seu dobro, 2n. Com isso, obtemos os pares (1, 2), (2, 4), (3, 6), (4, 8), (5, 10), … Para cada número natural n temos, assim, o par (n, 2n) e, para cada número par s, temos o par (s/2, s). Encontramos uma função bijetora; o conjunto dos números pares e o conjunto dos números naturais têm, portanto, o mesmo tamanho, isto é, a mesma cardinalidade.

Isso pode parecer confuso, porque os números naturais contêm mais elementos que os números pares. Os números naturais contêm todos os números pares e ainda todos os números ímpares. No entanto, conseguimos encontrar uma bijeção, então os dois conjuntos têm o mesmo tamanho.

Comparação com os números naturais

Os números naturais determinam, na verdade, o menor tamanho de um conjunto infinito. Muitas vezes é bem fácil descobrir se algum outro conjunto tem o mesmo tamanho que o conjunto dos números naturais — basta encontrar uma bijeção com os números naturais, o que na prática significa que basta conseguirmos numerar, ordenar os elementos do nosso conjunto M.

Ou seja, se conseguimos ordenar os elementos do conjunto de modo a decidir qual elemento é o primeiro, qual é o segundo, o terceiro, o quarto, o décimo etc., então o conjunto tem o mesmo tamanho que ℕ^*. Dizemos, então, que esse conjunto é enumerável.

Vemos facilmente que os números naturais pares e ímpares são enumeráveis, porque sabemos determinar o primeiro, o segundo, o terceiro etc. número par/ímpar. E os números inteiros pares? Ou seja, o conjunto S = {…, −4, −2, 0, 2, 4, …}. Conseguimos ordená-los? Conseguimos, basta pegar a mesma ordem de antes e, logo depois de cada número par positivo, escrever também a sua versão negativa: S = {0, 2, −2, 4, −4, 6, −6, …}. Do mesmo modo, por exemplo, para os números inteiros.

Tamanho dos números racionais

Um exemplo mais interessante são os números racionais, as frações. Conseguimos ordená-los? Conseguimos, mas será um pouco mais complicado. Construímos uma tabela com infinitas linhas e colunas. Em cada célula haverá uma fração. Na n-ésima coluna e na m-ésima linha teremos a fração n/m. Ou seja, na 1ª coluna e na 2ª linha temos $\frac{1}{2}$ e na terceira coluna e na quarta linha temos 3/4.

$$\begin{array}{ccccc}1/1& 2/1& 3/1& 4/1& \dots \\ 1/2& 2/2& 3/2& 4/2& \dots \\ 1/3& 2/3& 3/3& 4/3& \dots \\ 1/4& 2/4& 3/4& 4/4& \dots \\ \dots & \dots & \dots & \dots & \dots \end{array}$$

Como ordenar e numerar agora esses números? Não podemos numerá-los por linhas ou por colunas, porque ficaríamos logo afogados na linha/coluna em questão. Em vez disso, tomamos os números pelas diagonais: (primeira diagonal:) 1/1, (segunda diagonal:) 2/1, 1/2, (terceira diagonal:) 3/1, 2/2, 1/3, (quarta diagonal:) 4/1, 3/2, 2/3, 1/4, … Ainda há muitas frações repetidas, mas isso não atrapalha. O que atrapalha mais é que não há números negativos. Isso se resolve facilmente: sempre que escrevemos uma fração, colocamos logo depois dela a sua versão negativa. E então só nos falta o zero, bem no começo. E é só isso, temos todos os números racionais em uma sequência.

No total, obtemos a sequência: 0, 1/1, −1/1, 2/1, −2/1, 1/2, −1/2, 3/1, −3/1, 2/2, −2/2, 1/3, −1/3, …

Tamanho dos números reais

Os números reais têm o mesmo tamanho que os números naturais? A decisão será ainda mais complicada que no caso dos números racionais. Faremos uma demonstração por absurdo. Suponhamos que os números reais são enumeráveis e que existe uma função bijetora com os números naturais. Ou seja, suponhamos que eles podem ser ordenados. E digamos que a tabela a seguir seja essa ordenação:

$$\begin{array}{ccccccccc}0,& 3& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& 9& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& 3& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& 7& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& 7& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& 6& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& 0& \dots \\ \dots \end{array}$$

Na tabela estão os sete primeiros números reais da nossa ordenação. Essa ordenação, é claro, pode ser qualquer uma; não precisa estar ordenada pelo tamanho dos números.

Pela suposição, estão ordenados nessa tabela infinita todos os números reais. (A tabela, novamente, é infinita; aqui estão apenas os sete primeiros registros.) Agora vamos tentar encontrar/construir um número que seja real, mas não apareça nessa tabela. Se encontrarmos um número assim, isso contradiz o fato de que na tabela estão todos os números reais, e então podemos concluir que o conjunto dos números reais não é enumerável.

Construímos esse número que não está na tabela assim:

$$\begin{array}{ccccccccc}0,& \boxed{\text{3}}& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& \boxed{\text{9}}& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& \boxed{\text{3}}& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& \boxed{\text{7}}& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& \boxed{\text{7}}& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& \boxed{\text{6}}& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& \boxed{\text{0}}& \dots \\ \dots \end{array}$$

Começamos escrevendo 0,… É assim que o nosso novo número real vai começar. Na primeira casa decimal ficará um algarismo que não seja o que está na primeira casa do primeiro número real da nossa ordenação (na tabela, ele está destacado com uma caixa). Ali está o algarismo 3, então escolhemos, por exemplo, 1 e obtemos o número 0,1…

Continuamos. Na segunda casa ficará um algarismo que não seja o que está na segunda casa do segundo número real. Ali está o 9, então, por exemplo, 2. Obtemos o número 0,12… Na terceira casa ficará um algarismo diferente do terceiro algarismo do terceiro número real. Ali está o 3, então escolhemos, digamos, 7. Obtemos 0, 127…

E assim por diante. Sempre na n-ésima posição do novo número ficará um algarismo diferente do algarismo que está na n-ésima posição do n-ésimo número da nossa ordenação.

O que ganhamos com isso? Ganhamos um número que difere de todos os números da nossa ordenação em pelo menos um algarismo. Tomemos o último resultado provisório: 0,127… Esse número com certeza difere do primeiro número da nossa ordenação pelo menos no primeiro algarismo — porque o construímos assim. Do segundo número, difere pelo menos no segundo algarismo. Do terceiro, no terceiro algarismo. Em geral, esse novo número difere do número da ordenação que está na n-ésima posição pelo menos no algarismo da n-ésima casa.

Esse número recém-construído não será, portanto, encontrado na tabela que deveria simbolizar a bijeção entre os números naturais e os números reais. Os números reais são, assim, mais numerosos que os números naturais. Os números reais não são enumeráveis, são não enumeráveis.

Outras fontes

• Are there more odd or even numbers? (em inglês)