Teoria dos conjuntos/Conjuntos Infinitos

Conjuntos infinitos

Definição: Um conjunto $A$ é infinito se, e somente se, existir um conjunto $B$ tal que $B\subsetneq A$ e $A\sim B$ . 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: $x\mapsto 2x$

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

bijeção entre Naturais e Naturais ímpares: $x\mapsto 2x+1$

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

bijeção entre Naturais e Naturais quadrados: $x\mapsto x^{2}$

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

Abaixo segue uma bijeção entre Naturais e Inteiros

bijeção entre Naturais e Inteiros: $x\mapsto {\begin{cases}{\frac {x}{2}},&{\text{se }}x{\text{ for par}}\\{\frac {x+1}{-2}},&{\text{se }}x{\text{ for impar}}\\\end{cases}}$

0,	1,	2,	3,	4,	5,	6,	...
$\downarrow$	$\downarrow$	$\downarrow$	$\downarrow$	$\downarrow$	$\downarrow$	$\downarrow$
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 $x$ e todo $x$ Racionais tais que $x<y$ , existe um $z\in \mathbb {Q}$ tal que $x<z<y$ . 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,	...
$\downarrow$	$\downarrow$	$\downarrow$	$\downarrow$	$\downarrow$	$\downarrow$
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 a_n,m.

0, a_1,1 a_2,1 a_3,1 a_4,1 a_5,1 a_6,1 a_7,1 a_8,1 ...

0, a_1,2 a_2,2 a_3,2 a_4,2 a_5,2 a_6,2 a_7,2 a_8,2 ...

0, a_1,3 a_2,3 a_3,3 a_4,3 a_5,3 a_6,3 a_7,3 a_8,3 ...

0, a_1,4 a_2,4 a_3,4 a_4,4 a_5,4 a_6,4 a_7,4 a_8,4 ...

0, a_1,5 a_2,5 a_3,5 a_4,5 a_5,5 a_6,5 a_7,5 a_8,5 ...

0, a_1,6 a_2,6 a_3,6 a_4,6 a_5,6 a_6,6 a_7,6 a_8,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, a_1,1 a_2,1 a_3,1 a_4,1 a_5,1 a_6,1 a_7,1 a_8,1 ...

0, a_1,2 a_2,2 a_3,2 a_4,2 a_5,2 a_6,2 a_7,2 a_8,2 ...

0, a_1,3 a_2,3 a_3,3 a_4,3 a_5,3 a_6,3 a_7,3 a_8,3 ...

0, a_1,4 a_2,4 a_3,4 a_4,4 a_5,4 a_6,4 a_7,4 a_8,4 ...

0, a_1,5 a_2,5 a_3,5 a_4,5 a_5,5 a_6,5 a_7,5 a_8,5 ...

0, a_1,6 a_2,6 a_3,6 a_4,6 a_5,6 a_6,6 a_7,6 a_8,6 ...

...

Agora vamos produzir o número b = 0, b₁ b₂ b₃ b₄ b₅ ... tal que

$b_{n}={\begin{cases}a_{n,n}+1,&{\text{se }}a_{n,n}<8\\a_{n,n}-1,&{\text{se }}a_{n,n}\geq 8\\\end{cases}}$

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 $a$ , não existe bijeção entre $a$ e $\wp (a)$ .

Demonstração: Suponha, por absurdo, que exista uma bijeção $f:a\to \wp (a)$ . Definimos o conjunto $b=\{x\in a\,\,|\,\,x\notin f(x)\}$ , ou seja, $b$ é o conjunto de todos os elementos de $a$ que correspondem a um conjunto ao qual eles não pertencem. Evidentemente, $b\subseteq a$ . Portanto, $b\in \wp (a)$ Logo, deve existir um elemento $c\in a$ tal que $f(c)=b$ . Agora cabe a questão, $c\in b$ ? Se $c\in b$ , então, pela definição de $b$ , $c\notin b$ . Se $c\notin b$ , então, pela definição de $b$ , $c\in b$ .