Questão 6. Sejam
um conjunto finito e
um conjunto infinito. Prove que existe uma função injetiva
e uma função sobrejetiva
.
Passo 1
O enunciado pede duas coisas:
- Construir uma função injetiva
, onde é finito e é infinito. - Construir uma função sobrejetiva
.
Conteúdo principal: conceitos de injeção e sobrejeção entre conjuntos de cardinais distintos. Vamos usar o fato de que um conjunto infinito possui arbitrariamente muitos elementos distintos, o que nos permite extrair tantos quanto o tamanho de
.
Passo 2
Como
é finito, podemos enumerá-lo como
Por
ser infinito, existe uma sequência infinita de pontos distintos
. Em particular, podemos pegar os primeiros
termos dessa sequência, que são todos distintos em
. Definimos então
Essa função é injetiva porque, se
, então
e, por distinção dos
, segue
e logo
.
Passo 3
Escolha um elemento fixo de
Para ver que basta tomar
; então
mostrando que todo
tem um antecessor em
.
Resposta
A construção explícita das funções é:
onde
Aqui é sobrejetiva.