Seja f: A B uma função. Defina Pf: P(A) P(B) por
Pf(C)=beta in B mid existe alpha in C tal que f(alpha)=beta
para C subseteq A. Prove que:
f: A B é sobrejetora se, e somente se, Pf: P(A) P(B) é sobrejetora.

Passo 1

Vamos entender o problema: temos uma função e definimos uma nova função que mapeia subconjuntos de para subconjuntos de através de . O objetivo é provar que é sobrejetora (ou seja, cobre todo o conjunto ) se, e somente se, também for sobrejetora. Para isso, vamos precisar entender o que significa uma função ser sobrejetora e como está relacionada com .

Passo 2

Primeiro, vamos lembrar o que é uma função sobrejetora. Uma função é sobrejetora se, para todo elemento em , existe pelo menos um elemento em tal que . Em outras palavras, nenhum elemento de fica “sem imagem” em .

Passo 3

Agora, vamos analisar a função Pf(C) = beta in B mid existe alpha in C tal que f(alpha) = beta . Ela mapeia subconjuntos de para subconjuntos de da seguinte forma:
Isso significa que, dado um subconjunto de , é o conjunto de todas as imagens de elementos de através de .

Passo 4

Vamos primeiro provar que se é sobrejetora, então também é sobrejetora.
  • Suponha que é sobrejetora.
  • Queremos mostrar que, para qualquer subconjunto de , existe um subconjunto de tal que .
  • Como é sobrejetora, para cada em , existe pelo menos um em com .
  • Basta escolher como o conjunto de todos esses . Assim, vai exatamente cobrir todo .
Portanto, é sobrejetora se for sobrejetora.

Passo 5

Agora, vamos provar a direção inversa: se é sobrejetora, então também é sobrejetora.
  • Suponha que é sobrejetora.
  • Queremos mostrar que, para qualquer em , existe um em tal que .
  • Considere o subconjunto de .
  • Como é sobrejetora, existe um subconjunto de tal que .
  • Isso significa que existe pelo menos um em com .
  • Portanto, para todo em , existe um em com , mostrando que é sobrejetora.

Resposta

Assim, é sobrejetora se, e somente se, é sobrejetora.

Exercícios relacionados