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:


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

Fica assim provado que existe $\varphi$ sobrejetora.