Dada a função f: X \rightarrow Y, prove que:
Se Y é finito e f é sobrejetiva, então X é finito.

Passo 1

O enunciado pede para provar que, dada uma função f\colon X\to Y, se Y é finito e f é sobrejetiva então X é finito. Aqui usamos a definição de conjunto finito (não vazio e equipotente a \{1,2,\dots,n\} para algum n) e a noção de sobrejeção (todo y\in Y tem pelo menos um x\in X com f(x)=y).

Passo 2

Para provar uma afirmação do tipo “se A então B” podemos tentar mostrar que A é falsa ou exibir um contraexemplo em que A é verdadeira e B é falsa.

Passo 3

Considere o conjunto
X = \mathbb{N} = \{0,1,2,\dots\}
e
Y = \{0,1\}.
Defina f\colon X\to Y por
f(n) = n \bmod 2,
ou seja, f(n)=0 se n é par e f(n)=1 se n é ímpar.

Passo 4

Verificações:
  1. Y é finito, pois tem exatamente dois elementos.
  2. f é sobrejetiva, já que existe n par para cobrir 0 e existe n ímpar para cobrir 1.
  3. X=\mathbb{N} é infinito.
Portanto temos um caso em que Y é finito e f é sobrejetiva, mas X não é finito.

Resposta

A afirmação é falsa; o contraexemplo acima mostra que uma função sobrejetiva em um conjunto finito de chegada pode ter domínio infinito.

Exercícios relacionados