terça-feira, 8 de novembro de 2011

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

20 comentários:

  1. Olá, Diego!

    Mas, esses problemas aí, isso é o festival de "São João da Roça" em Caruaru ou vc está falando de ... Brasília?

    Olhe o carnaval #8... aí, geeeenteeeee!

    Um abraço!

    ResponderExcluir
  2. Olha Valdir, eu acho que esse problema teve sua "inspiração" em brasília mesmo!

    Não vou deixar de enviar mais um artigo para o Carnaval #8!!!

    Até mais !

    ResponderExcluir
  3. Olá Diego,

    Realmente a Matemática é bela! Contar, enumerar... para um leigo é algo tão simples; para um matemático, tão formal. E por isso que dá certo! Tão definido, tão logico!
    Ótimas postagens, meu amigo. Aproveito para agradecer o link citado.

    Um abraço e bom feriado!

    ResponderExcluir
  4. Como provar que um conjunto A finito e um conjunto B infinito enumerável. A união de A com B seja enumerável?

    ResponderExcluir
  5. Olá Anônimo,

    Temos a seguinte situação:

    A = finito
    B = Infinito enumerável

    Pela definição, A é enumerável (pois o mesmo é finito!).

    Assim existem f,g funções bijetivas tais que

    $f:\mathbb{N}\rightarrow A $

    e
    $g:\mathbb{N}\rightarrow B$

    Como A é finito podemos supor que o mesmo possui m elementos. Considere a função abaixo:

    $h:\mathbb{N}\rightarrow A\cup B$

    onde

    $h(n)= f(n)$ se $n\in\{1,2,\ldots,m\}$

    e

    $h(n)=g(n-m)$ se $n\in\{m+1,m+2,\ldots\}$

    Note que h é uma bijeção que enumera a união dos dois conjuntos, logo $A\cup B$ é enumerável.

    Até mais !

    ResponderExcluir
  6. Bom dia,

    Diego, poderia explica melhor porque colocaste g(n-m) na função h(n)= g(n−m) se n∈{m+1,m+2,…}.

    Obrigado.

    ResponderExcluir
    Respostas
    1. Bom dia Agner!
      Bem, queremos que o domínio de g seja {1,2,...}, mas em h os números naturais 1,2,...,m estão ligados à função f, para resolver este impasse é comum empregarmos estes artifícios para transmitir melhor a idéia, no nosso caso, realizamos o seguinte artifício:
      RESERVAMOS OS NÚMEROS 1,2,...,m PARA A FUNÇÃO f.
      O RESTANTE DOS NÚMEROS NATURAIS (m+1,m+2,...) SERÃO RESERVADOS PARA A FUNÇÃO g, ASSIM AO FAZERMOS g(n-m) TEMOS QUE

      EM m+1 A FUNÇÃO G SE TORNA g(m+1-m)=g(1);
      EM m+2 A FUNÇÃO G SE TORNA g(m+2-m)=g(2);
      .
      .
      .
      EM m+k A FUNÇÃO G SE TORNA g(m+k-m)=g(k);

      e assim sucessivamente.

      Excluir
  7. Olá Professor Diego! Sou Gabriel Ferreira do curso de matemática da UFC-UAB, fui seu aluno na disciplina EDO, gostei muito dessa sua explicação. Abraços! Poderia me ajudar nessa seguinte questão? 5. Seja card(X) o conjunto cujos elementos são os subconjuntos de X . Prove por indução que se é finito então card (X) = 2^card (X) .

    ResponderExcluir
  8. Este comentário foi removido pelo autor.

    ResponderExcluir
  9. defina cada um dos seguintes conjuntos abaixo enumerando seus elementos

    a) conjunto de letras da palavra 'granada'

    b) conjunto de todos os numero naturais que sao divisores de 20

    ResponderExcluir
  10. Este comentário foi removido pelo autor.

    ResponderExcluir
  11. Ola professor Diego Souza , poderia me tirar uma dúvida sobre a resolução de um exercício ?, a obviedade me leva achar que estou errado.

    Verifique se o conjunto $A$ a seguir é enumerável.
    $$A:=\left\{\sqrt3+n\sqrt2 \ ;\ n\in\Bbb{N} \right\}$$

    -----------

    Como $A:=\left\{\sqrt3+\sqrt2\ ;\sqrt3+2\sqrt2\ ;\cdots \right\}$ é possível estabelecer uma função bijetiva $$f:\Bbb{N}\longrightarrow A \\ \ \ \ \ \ \ \ \ \ \ \ n\longmapsto \sqrt3+n\sqrt2$$

    ResponderExcluir
  12. No dia a dia nos deparamos com situações diversas, onde temos que contar, enumerar objetos etc. No cotidiano você dispõe de um ambiente e objetos inseridos nele, na matemática temos conjuntos e elementos pertencentes a este conjunto. Desta forma, podemos definir um conjunto enumerável se:
    a) Existir uma função bijetora entre ele e o conjunto dos números naturais.
    b) Ser o conjunto de partida de uma função linear.
    c) Se ele for obrigatoriamente apenas finito.
    d) Ser um subconjunto dos números reais.

    ResponderExcluir
  13. Muito boa a explicação. Parabéns!!! Sou graduando e acabei vindo parar no seu blog para tentar entender bases enumeráveis de vizinhanças. Eu vi uma definição em que aparece o primeiro axioma da enumerabilidade, mas não consigo encontrar o enunciado claro dele na internet. Você chegou a ver ele na graduação? Poderia enunciar ele, rapidinho, por favor? Obrigado!!!

    ResponderExcluir
    Respostas
    1. De uma nada nesse link: https://www.ime.unicamp.br/~rigas/topolmujica/20.pdf

      Excluir

Você pode inserir suas fórmulas e equações no formato $\LaTeX$ nos comentários, basta escrevê-lo entre os símbolos $ \$ \ldots \$ $. Por exemplo, se você deseja escrever a seguinte fórmula:

$\lim_{x\to\infty}f(x)=0$

basta digitar a seguinte fórmula:

$ \$ $ \lim_{x\to\infty}f(x)=0 $ \$ $
(Um exemplo mais simples: $x^2=a$ é escrito como \$ x^2=a \$).

Agora é com você, comente à vontade, seu comentário é uma ferramenta fundamental para o crescimento do Giga Matemática!!!