Mostre que o conjunto dos números de Mersenne,
, é enumerável.
Passo 1
Beleza, vamos lá! O enunciado pede para mostrar que o conjunto dos números de Mersenne, $ S = {2^{n} - 1 \mid n \in \mathbb{N}} $, é enumerável. Isso significa que queremos provar que podemos listar todos esses números de Mersenne de uma maneira que cada um deles possa ser associado a um número natural único. Para resolver isso, vamos precisar entender o que é um conjunto enumerável e como os números de Mersenne se encaixam nessa definição.
Passo 2
Primeiro, vamos entender o que significa um conjunto ser enumerável. Um conjunto é chamado de enumerável ou contável se existe uma correspondência um a um entre os elementos do conjunto e os números naturais (
). Em outras palavras, podemos listar todos os elementos do conjunto em uma sequência infinita sem deixar nenhum de fora.
Passo 3
Agora, vamos olhar para o conjunto dos números de Mersenne: $ S = {2^{n} - 1 \mid n \in \mathbb{N}} $. Cada número de Mersenne é gerado elevando 2 a uma potência natural
e subtraindo 1. Por exemplo, para
, temos
; para
,
, e assim por diante.
Passo 4
Para mostrar que
é enumerável, precisamos encontrar uma maneira de associar cada número de Mersenne a um número natural único. Felizmente, a própria definição do conjunto já nos dá uma maneira natural de fazer essa correspondência. Cada número de Mersenne é definido por um único
natural.
Passo 5
Vamos construir essa correspondência explicitamente. Podemos definir uma função
onde cada número natural
é mapeado para
. Ou seja,
.
Passo 6
Agora, precisamos verificar se essa função
é injetora e sobrejetora:
-
Injetora: Cada número natural
gera um número de Mersenne único . Não existem dois números naturais diferentes e que produzem o mesmo número de Mersenne, porque cresce de forma única para cada . -
Sobrejetora: Todo número de Mersenne no conjunto
é da forma para algum , então não deixamos nenhum elemento de fora.
Passo 7
Como a função
é injetora e sobrejetora, ela estabelece uma bijeção entre
e
. Isso significa que podemos listar todos os números de Mersenne associando cada um deles a um número natural único.
Resposta
Portanto, o conjunto dos números de Mersenne $ S = {2^{n} - 1 \mid n \in \mathbb{N}} $ é enumerável, já que podemos estabelecer uma correspondência bijetiva com os números naturais.