Técnica Diagonalização de
Cantor
Para provar que um conjunto não
é enumerável
Exemplo
Números Reais entre 0 e 1 = [0,1]
r1
r2
r3
r4
r5
r6
r7
….
1
0
3
1
1
2
0
….
4
5
5
3
2
5
7
….
3
4
6
7
3
0
3
….
2
4
2
9
7
2
8
….
1
0
4
2
3
9
0
….
5
0
6
7
9
9
1
….
….
….
….
….
….
….
….
….
Exemplo
Números Reais entre 0 e 1 = [0,1]
0
0
3
1
1
2
0
….
rk ???
4
4
5
3
2
5
7
….
3
4
5
7
3
0
3
….
2
4
2
6
7
2
8
….
1
0
4
2
2
9
0
….
5
0
6
7
9
8
1
….
….
….
….
….
….
….
….
….
Exemplo
Números Reais entre 0 e 1 = [0,1]
r1
r2
r3
r4
r5
r6
r7
….
rk ???
1
0
3
1
1
2
0
….
0
4
5
5
3
2
5
7
….
4
3
4
6
7
3
0
3
….
2
4
2
9
7
2
8
….
5
6
1
0
4
2
3
9
0
….
2
5
0
6
7
9
9
1
….
8
….
….
….
….
….
….
….
….
Teorema
• Seja A um conjunto
• P(A) = conjunto das partes de A
• Então não existe bijeção
f: A -> P(A)
cardinalidade de P(A) > cardinalidade de A
Exercicio: Mostrar que existe uma função injetora
f : A  P(A)
Prova : suponhamos por absurdo
que exista bijeção de A em P(A)
O
a11
{a1,a2}
a1
A
a2
{a1, a3, a7, a8}
a3
{a1, a3, a5, a7,….}
a4
A
P(A)
a11 não pertence a f(a11) = O
a4 não pertence a f(a4) = {a1,a3,a5,a7,....}
Prova
O
a1
a2
a11
{a1, a2}
a3
α
a4
A
X = { x ϵ A | x  f(x) }
A
{a1, a3, a7, a8}
{a1, a3, a5, a7,….}
X
P(A)
f(α) = X
Prova
• Duas possibilidades : α ϵ X ou α X
– Se α ϵ X, como X = { x ϵ A | x  f(x) }
então α  f(α). Mas f(α) = X. Logo α  X
Absurdo !
– Se α  X, como X = { x ϵ A | x  f(x) }
então α ϵ f(α). Mas f(α) = X. Logo α ϵ X
Absurdo !
Hipótese do Contínuo
• Cardinalidade dos naturais = 0 (Aleph zero)
• Cardinalidade de P(N) = 1 (Aleph 1)
N … P(N) …. P(P(N)) …. P(P…(P(N)…)
aleph-0 aleph-1
0
1
aleph-2
aleph-n
2
Cardinalidade de R (conj. dos números reais) =
n
1
(???)
Hipótese do Contínuo
• Problema em aberto – (ainda sem solução)
• Um dos problemas mais intrigantes da matemática.
• Primeiro dos 23 problemas propostos por David Hilbert
no 2nd International Congress of Mathematicians em
Paris em 1900.
• A tentativa de se provar a Hipótese do Contínuo deu
origem a muitos resultados importantes de análise
matemática, topologia, teoria dos conjuntos e Lógica.
Cardinalidades finitas e infinitas
{1} {5}
{2}
{1,2}
{2,5,7}
{21,50}
1
2
N
R ??
3
P(N)
Z
P(P(N))
Q
P(P(P(N)))
Pares
Impares
0
Hipótese
do Contínuo:
Problema em aberto !!
1
2
3