projeto 2 Mat discreta Prof Moura

Prévia do material em texto

IME/UERJ
Matema´tica Discreta – Turma 1
Entre Cantor e Hilbert
Projeto 2 (Entrega: 18-X-2011)
Em vez de considerarmos a turma 1 de Matema´tica Discreta no semestre
2011/2, como no Projeto 1, vamos tomar agora todos os ho´spedes que lotam
o Hotel de Hilbert, isto e´, cada ho´spede (sozinho) ocupa um quarto sem dei-
xar apartamento algum vago.
Todos os grupos de ho´spedes que for poss´ıvel criar sera˜o fotografados – uma
u´nica vez. Para contabilizar os grupos – ou as fotos – criaremos tabelas, uma
para cada grupo: na primeira coluna, o nome de cada um dos ho´spedes, um
por linha. Ao lado, na segunda coluna, o d´ıgito 1 ou o d´ıgito 0, conforme o
correspondente ho´spede pertenc¸a ou na˜o a esse grupo.
Observe qualquer uma dessas tabelas. Ela esta´ associada a um u´nico grupo
e grupos diferentes esta˜o associados a diferentes tabelas. Mais ainda, dada
uma tabela desse tipo, criada arbitrariamente, existe um (u´nico) grupo que
a ela esta´ associado.
O que diz o Teorema de Cantor a respeito do conjunto de ho´spedes do hotel
e da colec¸a˜o de todos os grupos de ho´spedes?
Observe que se cada apartamento for identificado por um nu´mero natural,
cada ho´spede pode ser associado a esse nu´mero, e vice-versa.
Por outro lado, vendo uma dessas tabelas, podemos associa´-la tambe´m a um
nu´mero real entre 0 e 1, pensando em seus sucessivos d´ıgitos como sendo a
representac¸a˜o bina´ria (na base 2) de um nu´mero real x , com 0 < x < 1 .
Conclua que na˜o pode ser definida uma func¸a˜o com domı´nio nos naturais
e com valores no intervalo real (0, 1) que seja sobrejetora. Em outras pala-
vras, na˜o e´ poss´ıvel enumerar os reais do intervalo (0, 1) . E muito menos
os elementos da reta real toda. . .