Complete as demonstrações abaixo justificando cada passagem.
Prove que se f: X \rightarrow Y é uma função sobrejetora e X é finito então o conjunto Y é finito.
Demonstração: Devemos mostrar que existe uma bijeção h: Y \rightarrow I_{n} para algum n \in \mathbb{N}. Para isso, considere uma restrição adequada da função f: X \rightarrow Y, que a torne uma bijeção. Use o fato de que X é finito para concluir que Y também o é.
Passo 1
Temos uma função sobrejetora f\colon X\to Y e sabemos que X é finito. Queremos mostrar que Y também é finito, ou seja, que existe bijeção h\colon Y\to I_m para algum m\in\mathbb{N}. A ideia é escolher em X exatamente um pré-imagem para cada y\in Y, obter uma bijeção intermediária f|_{A}\colon A\to Y e depois usar que A\subseteq X é finito.
Passo 2
Como f é sobrejetora, para cada y\in Y existe pelo menos um x\in X tal que f(x)=y. Escolhemos exatamente um desses pontos e definimos
A \;=\;\{\,x_y\in X \mid f(x_y)=y,\;y\in Y\}.
Pela definição de A, a restrição
f\bigl|_{A}\colon A \to Y
é sobrejetora por construção e, de fato, também é injetora: se f(x_{y_1})=f(x_{y_2}) então y_1=y_2, logo x_{y_1}=x_{y_2}. Portanto f|_{A} é bijeção.
Passo 3
Sendo X finito e A\subseteq X, segue que A é finito. Assim existe algum m\in\mathbb{N} e bijeção
p\colon A \to I_{m}, \quad I_{m}=\{1,2,\dots,m\}.
Passo 4
Como f|_{A}\colon A\to Y é bijeção, sua inversa
q=(f|_{A})^{-1}\colon Y\to A
existe. Definimos então
h \;=\; p \circ q \;:\; Y \;\longrightarrow\; I_{m}.
Sendo composição de bijeções, h é bijeção. Logo há bijeção de Y em I_m, provando que Y é finito.