(Monnalysa) Prove que o conjunto das sequências crescentes (
) de números naturais não é enumerável.
Passo 1
O enunciado pede para provar que o conjunto
de todas as sequências estritamente crescentes de números naturais
não é enumerável. Vamos usar teoria de cardinalidade e o famoso argumento diagonal de Cantor para construir, por absurdo, um elemento de
que não pode estar em nenhuma enumeração.
Passo 2
Suponha, por absurdo, que
seja enumerável. Então existe uma enumeração
onde cada
é uma sequência estritamente crescente de naturais, e toda sequência de
aparece em algum
.
Passo 3
Vamos construir uma nova sequência
de forma que ela difira de
na coordenada
. Definimos recursivamente:
e, para cada
,
Passo 4
Mostramos que
é estritamente crescente. Para
temos por construção
logo
Assim
.
Passo 5
Para cada
, por definição,
logo
. Isso significa que
difere de
na posição
, de modo que
não pode coincidir com nenhum dos
. Isso contradiz a hipótese de que listamos todas as sequências de
.
Resposta
O conjunto das sequências estritamente crescentes de números naturais não é enumerável.