Questão 3 Mostre que existe
injetora se, e somente se, existe
sobrejetora.
Passo 1
O que o enunciado pede e o que nos é dado.
- Dados dois conjuntos
e . - Pedido: provar que existe uma função injetora
se, e somente se, existe uma função sobrejetora .
Vou dividir a prova nas duas direções ("
" e “
”) e tratar os casos-especiais que aparecem (como conjuntos vazios) e a questão do Axioma da Escolha quando for necessário.
Passo 2
Definições básicas (bem mastigadas).
- Uma função
é injetora se, e somente se,
Em palavras: imagens diferentes vêm de elementos diferentes; não há colisão de duas entradas distintas.
- Uma função
é sobrejetora se, e somente se,
Em palavras: todo elemento de
tem pelo menos um precursor em
.
Essas serão as propriedades que vamos verificar nas construções que fizeremos.
Passo 3
Direção ("[\Rightarrow)"): se existe
injetora, então existe
sobrejetora.
Vamos construir
explicitamente a partir de uma injeção
. Primeiro, tratar o caso especial
.
- Se
: existe a função injetora (a única função do conjunto vazio para qualquer conjunto é injetora). Existe uma sobrejeção somente se (porque uma sobrejeção exige que para todo exista pré-imagem; essa condição é automaticamente verdadeira, mas uma função só existe se ). Portanto, quando a implicação “existe injeção existe sobrejeção” só é verdadeira em geral se . Logo o caso vazio é uma observação necessária.
Agora suponha
e exista uma injeção
.
-
A imagem
é um subconjunto de . Como é injetora, para cada existe um único tal que . Então podemos definir assim: - escolha um elemento fixo
(pode-se, pois ); - defina
por
Essa definição é bem dada: no primeiro caso a unicidade vem da injetividade de . - escolha um elemento fixo
-
Verificação de que
é sobrejetora: tome qualquer . Então e, pela definição, . Assim todo tem um pré-imagem (pelo menos ), logo é sobrejetora.
Conclusão da direção: se
e existe injeção
, então existe sobrejeção
. (No caso
a implicação só vale quando também
.)]
Passo 4
Direção ("
"): se existe
sobrejetora, então existe
injetora — construção e papel do Axioma da Escolha.
Suponha que exista uma sobrejeção
. Para cada
o conjunto
é não vazio (porque
é sobrejetora). Para construir uma injeção
queremos escolher, para cada
, um elemento distinto
e definir
. Precisamos garantir duas coisas:
- que existe uma escolha
para cada (isto é, escolher um elemento em cada conjunto da família ); - que a aplicação
seja injetora (isto vem automaticamente se escolhermos e lembrarmos que se então e são disjuntos — porque se um mesmo pertencesse aos dois isso implicaria e com , impossível).
-
Observação sobre disjunção: para
não pode existir com e ao mesmo tempo, logo . Assim diferentes escolhas em conjuntos garantem automaticamente que será injetora. -
Mas existe uma dificuldade: escolher simultaneamente um elemento
para cada é exatamente a definição de uma função de escolha para a família não vazia . A existência de tal função de escolha, em geral, é garantida pelo Axioma da Escolha. Portanto: - Usando o Axioma da Escolha (AC) existe uma função de escolha
tal que para todo . Definindo obtemos . - Verificação da injetividade: se
então . Como os são disjuntos, isso implica . Logo é injetora.
- Usando o Axioma da Escolha (AC) existe uma função de escolha
Conclusão da direção: a partir de uma sobrejeção
obtemos uma injeção
sempre que se aceite o Axioma da Escolha. Sem o Axioma da Escolha, a construção pode falhar em famílias infinitas arbitrárias e, de fato, a afirmação que para quaisquer conjuntos
a existência de uma sobrejeção
implica a existência de uma injeção
é equivalente ao Axioma da Escolha (isto é, não pode ser provada em ZF pura).
Passo 5
Resumo, comentários finais e casos especiais — conclusão didática e motivadora.
-
Direção injeção
sobrejeção: é construtiva e não exige o Axioma da Escolha, desde que . Se então uma injeção sempre existe, mas uma sobrejeção só existe se . Portanto, para a equivalência literal sem restrição sobre vazios convém supor ou tratar o caso vazio separadamente. -
Direção sobrejeção
injeção: exige escolher um representante de cada fibra . A existência de uma escolha simultânea para todos os é garantida pelo Axioma da Escolha. Assim, sob o Axioma da Escolha a implicação é válida e, portanto, sob AC temos a equivalência desejada:
com as observações sobre o caso vazio feitas acima.
Você sobreviveu! A ideia central é: a injeção dá uma inversa à esquerda (na imagem de
) que permite construir uma sobrejeção; a sobrejeção dá fibras não vazias das quais é preciso escolher um elemento para cada
— e esse escolher simultâneo é exatamente o papel do Axioma da Escolha.
Resposta
Se
: existe
injetora
existe
sobrejetora.
Sob o Axioma da Escolha: existe sobrejetora
existe
injetora.
Sob o Axioma da Escolha: existe