$X$ é enumerável, logo $X = \{ x_n \in X : n \in \omega\}$, e existe $g: \omega \rightarrow X$, sobrejetora. Definimos $Y \subset X$, como $ Y =\{ y_i \in Y: i = min\{n : g(n) = x_n\}, \forall x \in X \}$.

$Afirmação: X = Y$.

Seja $x_n \in X$, tal que $g(n) = x_n$, então $ x = x_n = y_i$, para algum i, ou seja $x_n \in Y$. Suponha agora $y_i \in Y$, note que da definição $y_i = x_n$, para algum $n$. Então $X = Y$

Sejam $A, B \subset Y$, definidos por, $A = \{ y_{2i} \in Y: i \in \omega\}$, e $B = \{ y_{2i+1} \in Y: i \in \omega\}$. Note que $A \cap B = \emptyset$, entçao definido $f : Y \rightarrow \omega$, como $f(y_i)= 2n$, se $y_i \in A$, e $f(y_i) = 2n+1$, se $y_i \in B$. $f$ é bijetora.