O Teorema de Cantor - Pt. 4

A CHAVE PARA A INFINITUDE DOS INFINITOS


No seu artigo de 1891, Über eine elementare Frage der Mannigfaltigkeitslehre, Cantor apresentou pela primeira vez o argumento que ficou conhecido como Diagonal de Cantor. Neste artigo, encontra-se também a famosa prova de que o conjunto potência P(A) tem cardinalidade estritamente maior que o conjunto A, usando a técnica matemática conhecida como redução ao absurdo (do latim reductio ad absurdum).


Demonstração:


Suponhamos, por absurdo, que existe uma correspondência um para um entre A e P(A), ou seja, que existe uma função f injetora que liga os dois conjuntos. Mostraremos que essa função não é nem sobrejetora. Foi este tipo de argumento que usamos para provar que R tem cardinalidade maior que N.


Podemos dividir os elementos de A em elementos bons ou maus:


Um elemento é dito bom se ele está no conjunto ao qual ele está ligado. 
Um elemento é dito mau se ele não está no conjunto ao qual ele está ligado.


Exemplificando com o conjunto dos números naturais:


{1} -> {1, 2}                              1 é bom
{2} -> {1, 3}                              2 é mau
{3} -> {2, 3, 4, 5, 6}                   3 é bom
{4} -> {1, 3, 5, 7, 9, ...}              4 é mau


Agora considere o subconjunto dos elementos maus. A qual elemento de A ele está ligado? Não sabemos, mas este elemento só pode ser bom ou mau.


* Ele é bom - impossível, porque ele estaria ligado a um subconjunto que não o contém e seria, portanto, mau.
* Ele é mau - impossível, porque ele estaria ligado a um subconjunto que o contém e seria, portanto, bom.


Genial, não? Uma prova tão simples e uma implicação tão forte. Já ouviu falar da frase "eu sou mentiroso", que necessariamente leva a uma contradição? Ocorre exatamente o mesmo paradoxo. Analise a frase supondo que quem a diz é uma pessoa mentirosa ou não e veja o que acontece.


Temos, portanto, que este subconjunto de A não pode estar ligado a um elemento de A e, desta forma, que há mais subconjuntos de A do que elementos de A.

Teorema de Cantor: 

cardinalidade de P(A) > cardinalidade de A.

Quanto dá infinito mais infinito? - Pt. 3

Como consequência da existência de vários infinitos, temos uma álgebra para eles.

Primeiro vamos definir o que é chamado conjunto potência de um conjunto. Conjunto potência de um conjunto A é o conjunto dos subconjuntos de A e denotamos P(A). Exemplo:

A={a, b, c}
P(A)={{vazio}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}

Quando o conjunto A é finito e tem cardinalidade n, o conjunto potência tem cardinalidade 2 elevado a n. No exemplo acima, A tem 3 elementos e P(A) tem 8 (= 2 elevado a 3) elementos.

Quando o conjunto é infinito, fica mais difícil fazer esta conta (quanto vale 2 elevando a infinito?). No entanto, Cantor demonstrou que P(A) tem cardinalidade estritamente maior que A, mesmo que A seja infinito. Este teorema é conhecido como Teorema de Cantor. Demonstrá-lo-ei em outro post.

Podemos então, chegar à uma nova formulação da Hipótese do Contínuo:
A cardinalidade dos reais é a mesma que a do conjunto potência dos naturais?


Demonstramos que o infinito dos reais é maior que o dos naturais no último post, mas o Teorema de Cantor afirma que o conjunto dos subconjuntos dos naturais também tem mais elementos que os naturais.

Depois veremos como fica esta discussão, por enquanto vejamos como trabalhar com números transfinitos.

Como decorrência do Teorema de Cantor, temos que existem infinitos infinitos. Dado um conjunto infinito, criamos outro maior que ele através do seu conjunto potência. Então, dado um conjunto cuja cardinalidade é aleph-n, definimos a álgebra dos números transfinitos da seguinte forma (a é um número real qualquer):

A álgebra não é intuitiva. No fundo ela diz que podemos fazer operações simples (adição e multiplicação) com um número transfinito que não vamos aumentá-lo se a operação não envolver um transfinito maior do que ele. No caso em que m > n, temos:

Como se vê, a álgebra é baseada na majoração dos infinitos e permite que trabalhemos com infinitos como se fossem números reais.

Por fim, digo qual é a Hipótese Generalizada do Contínuo:

O conjunto potência de um conjunto infinito sempre tem a cardinalidade do próximo infinito?

A parte realmente divertida disto tudo é que a Hipótese Generalizada do Contínuo não pode ser provada a partir da Hipótese do Contínuo, ou seja, após tanta discussão, subimos apenas o primeiro degrau de uma longa escada.

De fato, de uma escada infinita.

Quantos infinitos existem? - Pt. 2

QUANTOS INFINITOS EXISTEM?

Um conceito chave que deve ser fixado neste momento é o de enumerabilidade. 

Um conjunto é enumerável se e somente se é possível uma bijeção entre ele e o conjunto dos números naturais.

Bijeção entre dois conjuntos significa que há sempre uma correspondência um para um entre eles. Exemplos:

Vemos uma tabela com a correspondência entre os naturais e, você deve ter notado, os quadrados perfeitos, os inteiros, os pares e os ímpares. Isso, no fundo, significa que estes conjuntos podem ser ordenados de forma organizada, porque o conjuntos dos naturais nada mais é do que um conjunto de índices. Um pouco mais complicado (mas possível) é ordenar os racionais.

Esta é a prova que a cardinalidade dos inteiros é a mesma destes conjuntos e, de fato, de muitos outros (divirta-se criando infinitos conjuntos com esta cardinalidade).


Os infinitos dos inteiros, dos quadrados perfeitos, dos pares, dos ímpares, dos racionais, ... , são todos iguais.

 Cantor definiu que dois conjuntos tem a mesma cardinalidade quando é possível uma bijeção entre seus elementos, mesmo que os conjuntos tenham cardinalidade transfinita [ou seja, infinitos elementos].

Agora vamos adiante: provemos que o conjunto dos números reais é não-enumerável. Para isto, usaremos o famosíssimo argumento da Diagonal de Cantor.

3  1  4  1  5  9  2  6  ...
1  2  4  1  7  3  7  2  ...
1  5  6  7  8  3  6  3  ...

3  5  3  5  3  5  3  5  ...

7  8  7  6  8  6  7  5  ...

6  4  9  5  9  3  9  6  ...

2  3  4  5  6  1  2  3  ...

1  8  9  7  8  6  7  5  ...

.. .. .. .. .. .. .. .. ..

Vamos supor, por absurdo, que seja possível fazer uma lista, evidentemente infinita, com todos os números reais de forma ordenada. Neste caso, você poderia dizer: o 2542º real é o 23876283..., por exemplo. Vamos construir um novo real, da seguinte forma:

1) Pegue o 1º algarismo do 1º número. Escolha um algarismo diferente.

2) Pegue o 2º algarismo do 2º número. Escolha um algarismo diferente.

3) Pegue o 3º algarismo do 3º número. Escolha um algarismo diferente.

E daí em diante. O novo número, com os algarismos escolhidos, será diferente de todos os outros da lista, porque difere de cada um pelo menos por um algarismo.


LEIA QUANTAS VEZES FOR NECESSÁRIO PARA ENTENDER ISTO!

Se mesmo com uma lista infinita de reais que parecia ordenada podemos criar um novo real diferente dos demais, não é possível estabeler uma bijeção entre R e N. Temos portanto, que a cardinalidade de R é maior que a de N.


O infinito dos reais é maior que o dos naturais.