(Monnalysa) Prove que o conjunto das sequências crescentes ( n 1<n 2<n 3<ldots ) de números naturais não é enumerável.

Passo 1

O enunciado pede para provar que o conjunto X de todas as sequências estritamente crescentes de números naturais
(n1 < n2 < n3 < cdots)
não é enumerável. Vamos usar teoria de cardinalidade e o famoso argumento diagonal de Cantor para construir, por absurdo, um elemento de X que não pode estar em nenhuma enumeração.

Passo 2

Suponha, por absurdo, que X seja enumerável. Então existe uma enumeração
S1, S2, S3, dots
onde cada
Sk = l(nk,1,,nk,2,,nk,3,dotsr)
é uma sequência estritamente crescente de naturais, e toda sequência de X aparece em algum Sk.

Passo 3

Vamos construir uma nova sequência
B = (b1, b2, b3, dots)
de forma que ela difira de Sk na coordenada k. Definimos recursivamente:
b1 = n1,1 + 1,
e, para cada k>=2,
bk = max,nk,k + 1,;bk-1 + 1

Passo 4

Mostramos que B é estritamente crescente. Para k>=2 temos por construção
bk >= bk-1 + 1,
logo
b1 < b2 < b3 < cdots
Assim Bin X.

Passo 5

Para cada k, por definição,
bk >= nk,k + 1 > nk,k,
logo bk neq nk,k. Isso significa que B difere de Sk na posição k, de modo que B não pode coincidir com nenhum dos S1,S2,dots. Isso contradiz a hipótese de que listamos todas as sequências de X.

Resposta

O conjunto das sequências estritamente crescentes de números naturais não é enumerável.

Exercícios relacionados