(Outra demonstração da enumerabilidade de
.)
Explique por que
.
Explique por que
Passo 1
O enunciado quer mostrar que o conjunto
pode ser escrito como
onde cada
é um subconjunto de
.
O tema é a enumerabilidade de e, em particular, a decomposição de um conjunto de racionais num “gradeado” indexado por dois naturais.
O tema é a enumerabilidade de
Passo 2
Definimos cada bloco
como
adotando a convenção de que, se
, então
.
Assim, contém exatamente o racional
(se
) e nada mais.
Assim,
Passo 3
Mostramos primeiro que
Seja
. Então
é racional e
, logo podemos escrevê-lo como
com
e
, e ainda
.
Tomando e
temos
, ou seja,
.
Logo está em alguma das células da dupla união.
Tomando
Logo
Passo 4
Agora mostramos que
Se
então, por definição de
,
com
.
Como e
são naturais,
é racional; além disso,
.
E como só indexamos com e
, temos
(caso contrário
ainda daria um racional, mas fora do intervalo
, nesse caso concreto
ficaria vazio ou seria descartado).
Logo todo elemento de cada pertence a
.
Como
E como só indexamos com
Logo todo elemento de cada
Passo 5
Das inclusões dos Passos 3 e 4 segue imediatamente
Resposta
Mostramos que qualquer racional
cai em algum
escrevendo-o como
, e também que todo elemento de cada
está em
. Portanto