Questão 6. Sejam X um conjunto finito e Y um conjunto infinito. Prove que existe uma função injetiva f: X Y e uma função sobrejetiva g: Y X.

Passo 1

O enunciado pede duas coisas:
  1. Construir uma função injetiva fcolon Xto Y, onde X é finito e Y é infinito.
  2. Construir uma função sobrejetiva gcolon Yto X.
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 X.

Passo 2

Como X é finito, podemos enumerá-lo como
X=x1,x2,dots,xn
Por Y ser infinito, existe uma sequência infinita de pontos distintos (yk)k=1^inftysubseteq Y. Em particular, podemos pegar os primeiros n termos dessa sequência, que são todos distintos em Y. Definimos então
fcolon Xto Y, f(xi)=yi, i=1,dots,n
Essa função é injetiva porque, se f(xi)=f(xj), então yi=yj e, por distinção dos yk, segue i=j e logo xi=xj.

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.

Exercícios relacionados