Prove que todo subconjunto infinito de
é enumerável.
Passo 1
Beleza, vamos lá! O enunciado pede para provar que todo subconjunto infinito de
(os números naturais) é enumerável. Isso está dentro da matéria de Teoria dos Conjuntos, mais especificamente sobre conjuntos contáveis. Para resolver, vamos precisar entender o que significa um conjunto ser enumerável e como podemos listar seus elementos de forma que cada um tenha um lugar na lista.
Passo 2
Primeiro, vamos lembrar o que significa um conjunto ser enumerável (ou contável). Um conjunto é enumerável se conseguimos listar todos os seus elementos em uma sequência, tipo
, onde cada elemento aparece em algum lugar da lista. No caso dos números naturais
, já sabemos que eles são enumeráveis porque podemos listá-los:
.
Passo 3
Agora, vamos considerar que temos um subconjunto infinito
de
. Como
é infinito, não tem um último elemento, ou seja, para qualquer número que você pegar em
, sempre há outro número maior que ele também em
. Isso é importante porque nos dá uma maneira de organizar os elementos de
em uma sequência.
Passo 4
Vamos construir uma lista dos elementos de
passo a passo. Primeiro, selecionamos o menor elemento de
e chamamos de
. Como
é infinito, sabe que há elementos maiores que
em
. Então, escolhemos o próximo menor elemento e chamamos de
, e assim por diante.
Passo 5
Formalizando isso, definimos uma função injetora
onde
é o n-ésimo menor elemento de
. Como sempre podemos encontrar um próximo elemento maior, essa função cobre todos os elementos de
sem repetição, garantindo que cada elemento de
apareça exatamente uma vez na nossa lista.
Passo 6
Como conseguimos listar todos os elementos de
de forma que cada número natural
está associado a um único elemento
em
, isso mostra que
é enumerável. Assim, todo subconjunto infinito de
pode ser colocado em uma sequência como fizemos.
Resposta
Portanto, provamos que todo subconjunto infinito de
é enumerável.