Conjuntos Enumeráveis

Desde o surgimento da matemática a humanidade utiliza os números para representar quantidades, medir distâncias, calcular, etc.

Quando você escuta a expressão "contar", o que lhe vem à mente? Você pode dizer contar, classificar, ENUMERAR, note que a última palavra chama bastante atenção, pois a mesma designa a possibilidade de "contar" os elementos de um conjunto. No dia-a-dia nos deparamos com situações diversas, onde temos que contar, enumerar objetos, no cotidiano você dispõe de um ambiente e objetos inseridos nele, na matemática temos conjuntos e elementos pertencentes à este conjunto, por isso vamos definir o que é um conjunto enumerável.

Definição: Um conjunto $K$ é dito enumerável se um dos critérios abaixo for válido:

(a) $K$ é finito;

(b) Existe uma bijeção $f:\mathbb{N}\rightarrow K$.

No segundo caso, dizemos que $K$ é um conjunto infinito enumerável.

Observe que o caso (a) é óbvio, pois podemos "contar" os elementos de um conjunto finito, o segundo caso deverá ser discutido um pouco mais.

Um conjunto infinito enumerável é aquele que possui infinitos termos, porém somos capazes de nomear cada um deles, considere o conjunto $X=\{x_1,x_2,x_3,\ldots\}$ um conjunto finito, encontramos facilmente uma bijeção deste conjunto com os naturais, será dada por $f(n)=x_n$, assim, $x_1=f(1),x_2=f(2),\ldots,x_n=f(n),\ldots$.

Um conjunto infinito não-enumerável é aquele que possui uma infinidade tão imensa de termos que não somos capazes de "registrar" todos eles, o maior exemplo de conjunto não enumerável é o conjunto dos números reais $\mathbb{R}$, não somos capazes de exibir pelo menos uma bijeção entre os reais e os naturais, ou seja, os reais possuem mais elementos que possamos imaginar!

Aqui entra o paradoxo do Hotel de Hilbert (conheça esta história melhor em O Paradoxo do Hotel de Hilbert e Hotel de Hilbert: mesmo lotado ainda há vagas!) O hotel pode ser considerado o conjunto dos números naturais e o primeiro ônibus um conjunto infinito enumerável, e portanto pode receber uma quantidade infinita de hóspedes, porém ao tentar hospedar um ônibus com a quantidade de números reais existentes (conjunto não-enumerável), Hilbert solicita que o último ônibus procure o HOTEL REAL, lá eles poderão encontrar vagas.

Enunciaremos e provaremos um teorema que será bastante importante para nós:

Teorema: Todo conjunto infinito $X$ contém um subconjunto infinito enumerável.

Prova: Note que em uma função injetiva qualquer $f:A\rightarrow B$ podemos afirmar que existe uma bijeção entre $A$ e $f(A)\subset B$, haja vista que em $\phi:A\rightarrow f(A)$ todo elemento em $f(A)$ é imagem de somente um elemento em $A$. Portanto, basta definir uma função injetiva $f:\mathbb{N}\rightarrow X$.

Primeiramente, escolha em cada subconjunto não-vazio $A\subset X$, um elemento $x_A\in A$. Definimos então $f$ por indução.

Fazemos $f(1)=x_X$.

Agora suponha que $f(1),\ldots,f(n)$ já estão definidos. Escrevemos 

$$A_n=X-\{f(1),\ldots,f(n)\}$$

Como $X$ não é finito, $A_n$ não é vazio.

Poremos então $f(n+1)=x_{A_n}$. Completamos assim a definição indutiva da função $f:\mathbb{N}\rightarrow X$.

AFIRMAÇÃO: f é injetiva

De fato, dados $m\neq n$ em $\mathbb{N}$, suponha $m<n$, deste modo, $f(m)\in\{f(1),\ldots,f(n-1)\}$ enquanto que $f(n)\in C\{f(1),\ldots,f(n-1)\}$

Logo $f(m)\neq f(n)$. 

A imagem $f(\mathbb{N})$ é um subconjunto infinito enumerável de $X$


Um problema bastante interessante que envolve o conceito de enumerabilidade vem da XIV Olimpíada Cearense de Matemática (1994):


Problema 7
a) Uma "gang" tem infinitos bandidos, e cada um desses meliantes tem um único inimigo no interior da "gang", que ele quer matar. Prove que é possível reunir uma quantidade infinita de bandidos desta "gang" sem que haja risco de que um bandido mate o outro durante a reunião.


b) Se cada bandido tiver um número finito, mas indefinido, de inimigos (um bandido pode ter 2 inimigos, um outro somente 1, um terceiro pode ter 20 e assim por diante), será possível promover uma reunião com infinitos "gangsters" sem o risco de derramamento de sangue?


Solução:
a) Seja $G=\{B_1,B_2,B_3,\ldots\}$ um subconjunto enumerável infinito do conjunto dos bandidos da "gang"(a existência deste conjunto é garantida pelo teorema anterior). Provaremos que é possível escolher $X\subset G$ sem que haja derramamento de sangue em $X$.


Inicialmente vamos definir para cada $i\in\mathbb{N}$ os seguintes conjuntos:

$$H_i=\{B_j\in G; j\neq\ \textrm{quer matar}\ B_i\}$$ 

ou seja, $H_i$ é o conjunto de todos os marginais em $G$ que querem matar $B_i$.

Dividiremos o problema em dois casos:

1º Caso: Existe $i$ tal que $H_i$ é infinito. Neste caso podemos fazer $X=H_i$, e não há risco de mortes em $X$ pois todos nesse grupo odeiam apenas o bandido $B_i$.

2º Caso: Não existe $H_i$ infinito. Nesse caso, escolha $B_1$ para pertencer a $X$. Exclua de $G$ os seguintes bandidos: $B_1$, o inimigo de $B_1$ e o conjunto $H_1$. O conjunto que resta de $G$ a partir dessas exclusões, que chamaremos de $G_1$, é infinito. Agora é só repetir o processo com $G_1$ no lugar de $G$.

b) A resposta é não. Mostraremos um exemplo de uma "gang" onde não é possível promover uma reunião com infinitos bandidos sem derramamento de sangue. Nossa "gang" será o conjunto:

$$G=\{B_1,B_2,B_3,\ldots\}$$

Para cada $i\in\mathbb{N},i>1$, suponha que o bandido $B_i$ queira matar $B_1,B_2,B_3,\ldots,B_{1-i}$. ($B_1$ é bonzinho e não quer matar ninguém.)

É fácil ver que nessa situação cada bandido tem um número finito de inimigos, e que em qualquer reunião com dois bandidos um deles vai querer assassinar o outro.

Não percam a próxima postagem seguindo este assunto, mostraremos que existem mais números irracionais que racionais, ou seja, existem mais números do tipo $\sqrt{2},\pi,e,\phi\in\mathbb{R-Q}$ do que $\frac{a}{b},b\neq0\in\mathbb{Q}$.

Até a próxima!

Bibliografia:

- Curso de Análise vol.1 - Elon Lages Lima;

- Olimpíadas Cearenses de Matemática ENSINO MÉDIO (1981-2005) - Emanuel Carneiro, Francisco Antônio M, de Paiva, Onofre Campos