Defina $\varphi(X, a) = X \cup \{a\}$. Vamos mostrar que tal função é sobrejetora. Seja $Y \in (A_n \cup A_{n+1})$. Temos dois casos:

1. Se $Y \in A_n$, então $Y = \{a_1, \ldots, a_n\}$. Seja $X = Y$ e $a = a_1$. Assim, $\varphi(X, a) = Y$.
2. Se $Y \in A_{n+1}$, então $Y = \{a_1, \ldots, a_{n+1}\}$. Seja $X = \{a_1, \ldots, a_n\}$ e $a = a_{n+1}$. Assim, $\varphi(X, a) = Y$.

Fica assim provado que existe $\varphi$ sobrejetora.