Mostre que o conjunto dos números de Mersenne, S=2^n-1 mid n in N, é 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 ( N). 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 S = 2^n - 1 mid n in N e subtraindo 1. Por exemplo, para n, temos n = 1; para 2^1 - 1 = 1, n = 2, e assim por diante.

Passo 4

Para mostrar que S é 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 n natural.

Passo 5

Vamos construir essa correspondência explicitamente. Podemos definir uma função f: N to S onde cada número natural n é mapeado para 2^n - 1. Ou seja, f(n) = 2^n - 1.

Passo 6

Agora, precisamos verificar se essa função f é injetora e sobrejetora:
  • Injetora: Cada número natural n gera um número de Mersenne único 2^n - 1. Não existem dois números naturais diferentes n1 e n2 que produzem o mesmo número de Mersenne, porque 2^n cresce de forma única para cada n.
  • Sobrejetora: Todo número de Mersenne no conjunto S é da forma 2^n - 1 para algum n in N, então não deixamos nenhum elemento de fora.

Passo 7

Como a função f é injetora e sobrejetora, ela estabelece uma bijeção entre N e S. 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.

Exercícios relacionados