Elementos do conjunto

Mostre que o conjunto de todas as sucessões cujos termos são os algarismos 0 e 1 é não enumerável.

A ideia a ser usada neste exercício que é na prática um Teorema é por meio das concepções de Cantor (diagonal de Cantor) usadas na demonstração da Proposição 8.

Vamos chamar da A o conjunto de todas as sucessões cujos termos são os algarismos 0 e 1. Por exemplo, os elementos de E são do tipo 1,0,0,0,1,0,1,1,1, ....

Seja E um subconjunto enumerável de A, constituído das sucessões

s1, s2, s3, ...

Vamos a seguir definir uma sucessão, denotada por s, de tal forma que esta seja diferente de todos os elementos de E. Para tal basta sempre trocar o n-ésimo de zero para um ou de um para zero. Com esse critério . Mas certamente , pela sua característica de formação que confere com os elementos de A. Temos assim que E é um subconjunto próprio de A.

Como estamos trabalhando genericamente, podemos dizer que todo subconjunto enumerável de A é subconjunto próprio de A. Portanto, A não é enumerável, pois caso contrário A seria subconjunto próprio de A o que é um absurdo. (Lembrar da definição de subconjunto próprio!)

...