Teoria dos conjuntos/Conjuntos Infinitos

Conjuntos infinitos

editar

Definição: Um conjunto   é infinito se, e somente se, existir um conjunto   tal que   e  . Ou seja, um conjunto infinito tem uma bijeção com um subconjunto próprio.

Segue abaixo três exemplos de bijeção entre Naturais e subconjuntos dos Naturais.

bijeção entre Naturais e Naturais pares:  

0, 1, 2, 3, 4, 5, 6, ...
             
0, 2, 4, 6, 8, 10, 12, ...


bijeção entre Naturais e Naturais ímpares:  

0, 1, 2, 3, 4, 5, 6, ...
             
1, 3, 5, 7, 9, 11, 13, ...


bijeção entre Naturais e Naturais quadrados:  

0, 1, 2, 3, 4, 5, 6, ...
             
0, 1, 4, 9, 16, 25, 36, ...


Abaixo segue uma bijeção entre Naturais e Inteiros

bijeção entre Naturais e Inteiros:  

0, 1, 2, 3, 4, 5, 6, ...
             
0, -1, 1, 2, -2, 3, -3, ...


bijeção entre Inteiros positivos e Racionais positivos:

O caso dos Racionais é mais complicado, pois a relação < é densa neste conjunto. Isto é, para todo   e todo   Racionais tais que  , existe um   tal que  . Portanto, entre dois números Racionais, por menor que seja a diferença entre eles, sempre existe infinitos outros Racionais.

George Cantor, o criador da teoria de conjuntos, encontrou uma forma de ordenar os Racionais positivos sem o uso de <, de forma que se possa estabelecer uma correspondência um-a-um entre estes e os Inteiros positivos. Chamamos seu método de ‘passeio de Cantor’.

Em primeiro lugar, os Racionais são dispostos em forma de fração em uma tabela de forma tal que os elementos da n–ésima coluna tem denominador n, enquanto os elementos da m–ésima linha tem numerador m.


 


Agora, ordenamos as frações da seguinte forma:


 


Assim, podemos estabelecer a seguinte correspondência um-a-um entre os Inteiros positivos e Racionais positivos: n corresponde ao n–ésimo termo não repetido na ordenação estabelecida pelo passeio de Cantor.


1, 2, 3, 4, 5, 6, ...
           
1, 1/2, 2, 3, 1/3, 1/4, ...

bijeção entre Inteiros positivos e Racionais

O princípio é o mesmo que no caso anterior, mas o passeio é feito da seguinte forma.

 


Contudo, nem todos conjuntos infinitos têm a mesma cardinalidade, como veremos nos resultados a seguir.


Proposição: Não é possível estabelecer uma bijeção entre os números Naturais e os números Reais do intervalo ]0, 1[.

Demonstração: Por absurdo, vamos supor que existe uma ordenação enumerável dos Reais no intervalo em questão. Mostraremos que sempre podemos produzir um número que não consta nesta ordenação.

Para fins de generalidade, representaremos o n–ésimo algarismo depois da vírgula do m–ésimo número por an,m.

0, a1,1 a2,1 a3,1 a4,1 a5,1 a6,1 a7,1 a8,1 ...

0, a1,2 a2,2 a3,2 a4,2 a5,2 a6,2 a7,2 a8,2 ...

0, a1,3 a2,3 a3,3 a4,3 a5,3 a6,3 a7,3 a8,3 ...

0, a1,4 a2,4 a3,4 a4,4 a5,4 a6,4 a7,4 a8,4 ...

0, a1,5 a2,5 a3,5 a4,5 a5,5 a6,5 a7,5 a8,5 ...

0, a1,6 a2,6 a3,6 a4,6 a5,6 a6,6 a7,6 a8,6 ...

...

Agora vamos tomar um algarismo de cada número, cada número na posição n da lista terá seu n–ésimo algarismo considerado:

0, a1,1 a2,1 a3,1 a4,1 a5,1 a6,1 a7,1 a8,1 ...

0, a1,2 a2,2 a3,2 a4,2 a5,2 a6,2 a7,2 a8,2 ...

0, a1,3 a2,3 a3,3 a4,3 a5,3 a6,3 a7,3 a8,3 ...

0, a1,4 a2,4 a3,4 a4,4 a5,4 a6,4 a7,4 a8,4 ...

0, a1,5 a2,5 a3,5 a4,5 a5,5 a6,5 a7,5 a8,5 ...

0, a1,6 a2,6 a3,6 a4,6 a5,6 a6,6 a7,6 a8,6 ...

...

Agora vamos produzir o número b = 0, b1 b2 b3 b4 b5 ... tal que

 

O número b não está na lista, pois difere do primeiro membro da lista no primeiro algarismo depois da vírgula, difere do segundo membro no segundo algarismo... ou seja difere de qualquer membro na posição n no n–ésimo algarismo após a vírgula. Assim, não é possível estabelecer uma bijeção entre os Naturais e qualquer intervalo entre os Reais. Logo, o infinito dos Reais é de cardinalidade superior ao infinito dos Naturais.


Proposição: Dado um conjunto  , não existe bijeção entre   e  .

Demonstração: Suponha, por absurdo, que exista uma bijeção  . Definimos o conjunto  , ou seja,   é o conjunto de todos os elementos de   que correspondem a um conjunto ao qual eles não pertencem. Evidentemente,  . Portanto,   Logo, deve existir um elemento   tal que  . Agora cabe a questão,  ? Se  , então, pela definição de  ,  . Se  , então, pela definição de  ,  .

A nossa suposição inicial acarretou contradição, portanto ela é falsa. Ou seja, não existe bijeção entre um conjunto e seu conjunto potência.


  Esta página é somente um esboço.
Ampliando-a você ajudará a melhorar o Wikilivros.