Sejam A, B \subset \mathbb{N} com B não-enumerável. Demonstre que se existir uma função sobrejetiva de A em B, então A é não-enumerável.

Passo 1

O enunciado (como dado) é: sejam A, B \subset \mathbb{N} com B não-enumerável e exista uma função sobrejetiva de A em B. O que se pede: demonstrar que A é não-enumerável.
Observação importante (para evitar confusão): se realmente B\subset\mathbb{N} então B seria enumerável (subconjunto de conjunto enumerável é enumerável), o que contradiz a hipótese de B não-enumerável. Vou então interpretar o enunciado da forma habitualmente usada neste tipo de exercício: A e B são conjuntos quaisquer (não repetir a hipótese impossível), com B não-enumerável, e existe uma função sobrejetiva f:A\to B. Essas são as informações que vou usar.

Passo 2

Definições e resultados que usarei (explicados de forma clara).
  • Definição de sobrejetiva: uma função f:X\to Y é sobrejetiva se, para todo y\in Y, existe pelo menos um x\in X tal que f(x)=y. Em símbolos:
f\text{ é sobrejetiva } \iff \forall y\in Y\\ \exists x\in X:\\ f(x)=y.é
  • Definição de enumerável (aqui uso a definição prática e comum): um conjunto S é enumerável (ou contável, no sentido “pelo menos enumerável”) se existe uma função sobrejetiva g:\mathbb{N}\to S. Essa definição inclui conjuntos finitos e conjuntos equiparáveis a \mathbb{N}.
  • Composição preserva sobrejetividade: se g:\mathbb{N}\to A é sobrejetiva e f:A\to B é sobrejetiva então a composição f\circ g:\mathbb{N}\to B é sobrejetiva. Vou provar isso explicitamente no próximo passo.

Passo 3

Prova por contradição (estrutura padrão e simples de aplicar em provas de conjunto).
Suponha, para chegar a uma contradição, que A seja enumerável. Pela definição anterior, existe uma função sobrejetiva
g:\mathbb{N}\to A.
Também, pelo enunciado, existe uma função sobrejetiva
f:A\to B.

Passo 4

Construção da composição e verificação de que ela é sobrejetiva (a peça chave).
Defina a composição h=f\circ g:\mathbb{N}\to B por h(n)=f(g(n)) para todo n\in\mathbb{N}.
Mostro que h é sobrejetiva: tome qualquer elemento b\in B. Como f é sobrejetiva, existe a\in A tal que f(a)=b. Como g é sobrejetiva, existe n\in\mathbb{N} tal que g(n)=a. Então
h(n)=f(g(n))=f(a)=b.
Como o b escolhido era arbitrário em B, concluímos que para todo b\in B existe n\in\mathbb{N} com h(n)=b. Logo h é sobrejetiva.

Passo 5

Contradição e conclusão.
Ter h:\mathbb{N}\to B sobrejetiva significa que B é enumerável (pela definição usada). Mas isso contradiz a hipótese de que B é não-enumerável. A única hipótese que assumimos e que pode ser falsa é a suposição de que A é enumerável. Portanto essa suposição é falsa, e concluímos que A é não-enumerável.
Comentário final rápido e amigável: a ideia prática é simples e muito usada em provas — se uma função surjetiva leva de A para B, então B não pode ser “maior” em cardinalidade do que A. Se B é não-enumerável, A também tem de ser não-enumerável; caso contrário, comporíamos uma enumeração de A com a sobrejeção e enumeraríamos B, o que dá contradição.

Resposta

A é não-enumerável.

Exercícios relacionados