Topologia e conjuntos em exercícios

Vamos provar por indução sobre $n$ que o conjunto das funções com domínio de tamanho exatamente $n$ é enumerável. Dessa maneira a união dessas funções forma $P$ e como a união enumerável de conjuntos enumeráveis é enumerável estaremos provando que $P$ é enumerável.

• $n=1$

O conjunto das funções de domínio de tamanho 1 é, nesse caso, o conjunto $F=\{\{(a,b)\}: (a,b) \in \omega\times\omega\}$, que é enumerável, pois $\omega\times\omega$ é enumerável.

• Passo da indução

Agora suponha que existe $n \in \omega$ tal que o conjunto $F$ das funções com o domínio de tamanho $n$ seja enumerável. Queremos provar que o conjunto $G$ das funções de domínio com o tamanho $n+1$ é também enumerável. Note que dada $f \in F$ podemos acrescentar um novo elemento ao domínio, assim teremos uma função com domínio de tamanho $n+1$. Forme o conjunto $A_f = \{ f \cup \{(a,b)\} : a,b \in \omega, a \notin dom(f)\}$ que é enumerável. já que possui o mesmo número de elementos das funções de domínio de tamanho 1. Assim cada $g \in A_f$ tem domínio de tamanho $n+1$. Note agora que $\bigcup_{f\in F}A_f = G$ e isso nada mais é que uma união enumerável de conjuntos enumeráveis, que é enumerável.