(Outra demonstração da enumerabilidade de
.)
Seja
definida por
Prove que
é injetora e conclua daqui que
é enumerável.
Seja
Passo 1
Beleza, vamos lá! O enunciado pede para a gente provar que a função
, definida por
, é injetora. Depois disso, precisamos concluir que os números racionais
são enumeráveis. Para resolver isso, vamos precisar entender o que significa uma função ser injetora e o que é enumerabilidade em conjuntos matemáticos.
Passo 2
Primeiro, vamos lembrar o que é uma função injetora. Uma função
é injetora se, sempre que
, então
. Em outras palavras, nenhum duas entradas diferentes mapeiam para a mesma saída.
No nosso caso,
mapeia números racionais
para pares de inteiros
. Geralmente,
e
representam o numerador e o denominador da fração que representa o número racional
.
Passo 3
Vamos supor que
. Isso significa que:
O que implica que:
Se
e
, então as frações que representam
e
são iguais. Portanto, temos:
Isso mostra que se
, então
, o que prova que a função
é injetora.
Passo 4
Agora que sabemos que
é injetora, podemos concluir que
é enumerável. A razão é a seguinte: sabemos que
(o conjunto dos pares de inteiros) é enumerável, ou seja, seus elementos podem ser listados de forma que cada par apareça em uma posição finita na lista.
Como
é uma injeção de
em
, cada número racional corresponde a um par único de inteiros. Isso significa que podemos enumerar
listando os pares de
e, consequentemente, listando todos os números racionais.
Resposta
A função
é injetora e, por isso, os números racionais
são enumeráveis.