Prove que todo subconjunto infinito de N é enumerável.

Passo 1

Beleza, vamos lá! O enunciado pede para provar que todo subconjunto infinito de N (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 a1, a2, a3, dots, onde cada elemento aparece em algum lugar da lista. No caso dos números naturais N, já sabemos que eles são enumeráveis porque podemos listá-los: 1, 2, 3, dots.

Passo 3

Agora, vamos considerar que temos um subconjunto infinito A de N. Como A é infinito, não tem um último elemento, ou seja, para qualquer número que você pegar em A, sempre há outro número maior que ele também em A. Isso é importante porque nos dá uma maneira de organizar os elementos de A em uma sequência.

Passo 4

Vamos construir uma lista dos elementos de A passo a passo. Primeiro, selecionamos o menor elemento de A e chamamos de a1. Como A é infinito, sabe que há elementos maiores que a1 em A. Então, escolhemos o próximo menor elemento e chamamos de a2, e assim por diante.

Passo 5

Formalizando isso, definimos uma função injetora f: N to A onde f(n) = an é o n-ésimo menor elemento de A. Como sempre podemos encontrar um próximo elemento maior, essa função cobre todos os elementos de A sem repetição, garantindo que cada elemento de A apareça exatamente uma vez na nossa lista.

Passo 6

Como conseguimos listar todos os elementos de A de forma que cada número natural n está associado a um único elemento an em A, isso mostra que A é enumerável. Assim, todo subconjunto infinito de N pode ser colocado em uma sequência como fizemos.

Resposta

Portanto, provamos que todo subconjunto infinito de N é enumerável.

Exercícios relacionados