Suponha que
é um conjunto não enumerável.
Prove que:
Se
, então ou
ou
é não enumerável.
Prove que:
Se
Passo 1
Beleza, vamos lá! O enunciado da questão diz que temos um conjunto
que é não enumerável, ou seja, ele é tão grande que não dá para listar todos os seus elementos um a um. Queremos provar que, se a união de dois subconjuntos
e
dá exatamente
(
), então pelo menos um desses subconjuntos (
ou
) também tem que ser não enumerável. Para resolver isso, vamos precisar entender o que significa um conjunto ser enumerável ou não, e usar algumas propriedades básicas de conjuntos.
Passo 2
Primeiro, vamos lembrar o que significa ser enumerável. Um conjunto é enumerável se seus elementos podem ser colocados em uma lista infinita, como os números naturais
. Se não conseguimos fazer essa listagem, o conjunto é não enumerável. Exemplos de conjuntos não enumeráveis incluem os números reais
.
Passo 3
Agora, vamos supor que
onde
é não enumerável. Queremos provar que pelo menos um entre
ou
é não enumerável. Vamos fazer isso por contradição, assumindo o oposto: que ambos
e
são enumeráveis, e ver onde isso nos leva.
Passo 4
Se assumirmos que
e
são ambos enumeráveis, então podemos listar os elementos de
como
e os de
como
. A união de dois conjuntos enumeráveis também é enumerável. Podemos criar uma lista para
intercalando os elementos de
e
, por exemplo:
.
Passo 5
Isso significaria que
seria enumerável, já que conseguimos listar todos os seus elementos. Mas isso contraria a nossa hipótese inicial de que
é não enumerável. Ou seja, nossa suposição de que ambos
e
são enumeráveis está errada.
Passo 6
Portanto, a única possibilidade restante é que pelo menos um dos conjuntos
ou
seja não enumerável. Não podemos ter ambos sendo enumeráveis sem entrar em contradição com o fato de
ser não enumerável.
Resposta
Assim, provamos que se
e
é não enumerável, então ou
ou
é não enumerável.