Questão 3 Mostre que existe f: A \rightarrow B injetora se, e somente se, existe g: B \rightarrow A sobrejetora.

Passo 1

O que o enunciado pede e o que nos é dado.
  • Dados dois conjuntos A e B.
  • Pedido: provar que existe uma função injetora f\colon A\to B se, e somente se, existe uma função sobrejetora g\colon B\to A.
Vou dividir a prova nas duas direções (" \Rightarrow" e “ \Leftarrow”) 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 f\colon A\to B é injetora se, e somente se,
\forall x,y\in A,\qquad f(x)=f(y)\Rightarrow x=y.
Em palavras: imagens diferentes vêm de elementos diferentes; não há colisão de duas entradas distintas.
  • Uma função g\colon B\to A é sobrejetora se, e somente se,
\forall a\in A,\\ \exists b\in B\\ \text{tal que}\\ g(b)=a.
Em palavras: todo elemento de A tem pelo menos um precursor em B.
Essas serão as propriedades que vamos verificar nas construções que fizeremos.

Passo 3

Direção ("[\Rightarrow)"): se existe f\colon A\to B injetora, então existe g\colon B\to A sobrejetora.
Vamos construir g explicitamente a partir de uma injeção f. Primeiro, tratar o caso especial \,A=\varnothing.
  • Se A=\varnothing: existe a função injetora f\colon\varnothing\to B (a única função do conjunto vazio para qualquer conjunto é injetora). Existe uma sobrejeção g\colon B\to\varnothing somente se B=\varnothing (porque uma sobrejeção exige que para todo a\in\varnothing exista pré-imagem; essa condição é automaticamente verdadeira, mas uma função B\to\varnothing só existe se B=\varnothing). Portanto, quando A=\varnothing a implicação “existe injeção \Rightarrow existe sobrejeção” só é verdadeira em geral se B=\varnothing. Logo o caso vazio é uma observação necessária.
Agora suponha \,A\neq\varnothing e exista uma injeção f\colon A\to B.
  • A imagem f(A)\subseteq B é um subconjunto de B. Como f é injetora, para cada b\in f(A) existe um único a\in A tal que f(a)=b. Então podemos definir g assim:
    • escolha um elemento fixo a_0\in A (pode-se, pois A\neq\varnothing);
    • defina g\colon B\to A por g(b)= \begin{cases} \text{ o único }a\text{ com }f(a)=b, & \text{se }b\in f(A),\\[4pt] a_0, & \text{se }b\notin f(A). \end{cases}ú
    Essa definição é bem dada: no primeiro caso a unicidade vem da injetividade de f\]; no segundo caso usamos um elemento fixo \(a_0.
  • Verificação de que g é sobrejetora: tome qualquer a\in A. Então b=f(a)\in f(A)\subseteq B e, pela definição, g(f(a))=a. Assim todo a\in A tem um pré-imagem (pelo menos f(a)), logo g é sobrejetora.
Conclusão da direção: se A\neq\varnothing e existe injeção f\colon A\to B, então existe sobrejeção g\colon B\to A. (No caso A=\varnothing a implicação só vale quando também B=\varnothing.)]

Passo 4

Direção (" \Leftarrow"): se existe g\colon B\to A sobrejetora, então existe f\colon A\to B injetora — construção e papel do Axioma da Escolha.
Suponha que exista uma sobrejeção g\colon B\to A. Para cada a\in A o conjunto
S_a:=\{\,b\in B : g(b)=a\,\}
é não vazio (porque g é sobrejetora). Para construir uma injeção f\colon A\to B queremos escolher, para cada a\in A, um elemento distinto b_a\in S_a e definir f(a)=b_a. Precisamos garantir duas coisas:
  1. que existe uma escolha b_a\in S_a para cada a (isto é, escolher um elemento em cada conjunto da família \{S_a\}_{a\in A});
  2. que a aplicação a\mapsto b_a seja injetora (isto vem automaticamente se escolhermos b_a\in S_a e lembrarmos que se a_1\neq a_2 então S_{a_1} e S_{a_2} são disjuntos — porque se um mesmo b pertencesse aos dois isso implicaria g(b)=a_1 e g(b)=a_2 com a_1\neq a_2, impossível).
  • Observação sobre disjunção: para a_1\neq a_2 não pode existir b com g(b)=a_1 e g(b)=a_2 ao mesmo tempo, logo S_{a_1}\cap S_{a_2}=\varnothing. Assim diferentes escolhas b_{a} em conjuntos S_a garantem automaticamente que f será injetora.
  • Mas existe uma dificuldade: escolher simultaneamente um elemento b_a\in S_a para cada a\in A é exatamente a definição de uma função de escolha para a família não vazia \{S_a\}_{a\in A}. 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 c tal que c(a)\in S_a para todo a\in A. Definindo f(a):=c(a)obtemos f\colon A\to B.
    • Verificação da injetividade: se f(a_1)=f(a_2) então c(a_1)=c(a_2)\in S_{a_1}\cap S_{a_2}. Como os S_a são disjuntos, isso implica a_1=a_2. Logo f é injetora.
Conclusão da direção: a partir de uma sobrejeção g\colon B\to A obtemos uma injeção f\colon A\to B 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,B a existência de uma sobrejeção B\to A implica a existência de uma injeção A\to B é 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 \Rightarrow sobrejeção: é construtiva e não exige o Axioma da Escolha, desde que \,A\neq\varnothing. Se A=\varnothing então uma injeção \varnothing\to B sempre existe, mas uma sobrejeção B\to\varnothing só existe se B=\varnothing. Portanto, para a equivalência literal sem restrição sobre vazios convém supor A\neq\varnothing ou tratar o caso vazio separadamente.
  • Direção sobrejeção \Rightarrow injeção: exige escolher um representante de cada fibra S_a=g^{-1}(\{a\}). A existência de uma escolha simultânea para todos os a\in A é 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:
\bigl(\exists\\ \text{injeção }f\colon A\to B\bigr) \quad\Longleftrightarrow\quad \bigl(\exists\\ \text{sobrejeção }g\colon B\to A\bigr),çãçã
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 f) que permite construir uma sobrejeção; a sobrejeção dá fibras não vazias das quais é preciso escolher um elemento para cada a — e esse escolher simultâneo é exatamente o papel do Axioma da Escolha.

Resposta

Se A\neq\varnothing: existe f\colon A\to B injetora \Longrightarrow existe g\colon B\to A sobrejetora.
Sob o Axioma da Escolha: existe g\colon B\to A sobrejetora \Longrightarrow existe f\colon A\to B injetora.

Exercícios relacionados