¿Entiendes la definición de \( \Gamma_n \)? Se trata del conjunto de todas las fórmulas en las que a lo sumo aparecen los átomos \( p_0,\ldots, p_n \) y que resultan de aplicar a lo sumo \( n \) reglas de construcción.
Por ejemplo, \( \Gamma_0 = \{p_0, \bot\} \),
\( \Gamma_1 = \{p_0, p_1, \bot, p_0\land p_0, p_1\land p_1, \)\( p_0\land p_1,p_1\land p_0,p_0\land \bot, p_1\land \bot, \bot\land p_0,\bot\land p_1,\bot\land \bot,\ldots\} \)
Se trata de probar que cada \( \Gamma_n \) es finito, que toda fórmula está en un \( \Gamma_n \) y que \( \Gamma_n\subset \Gamma_{n+1} \).
Entonces, puedes biyectar \( \Gamma_0 \) con \( \{0,1\} \), luego puedes biyectar \( \Gamma_1\setminus \Gamma_0 \) con los números naturales \( 2, 3, \ldots, k_1 \), hasta cierto \( k_1 \), luego puedes biyectar \( \Gamma_2\setminus \Gamma_1 \) con \( k_1+1,\ldots, k_2 \), y uniendo todas estas biyecciones tienes una biyección entre fórmulas y números naturales.
Puedes dar un criterio explícito para elegir cada fragmento de biyección, y entonces tienes definida explícitamente la biyección completa.
No obstante, yo creo que hay una forma más sencilla de hacerlo: asocia a cada signo de PROP un número natural. Por ejemplo
\( n(\land)=0 \), \( n(\lor)=1 \), \( n(\rightarrow)=2 \), \( n(\lnot)=3 \), \( n(\leftrightarrow)=4 \), \( n(\bot)=5 \), \( n(()=6 \), \( n())=7 \), \( n(p_0)=8 \), \( n(p_1)=9 \), etc.
Cada fórmula \( \phi \) de PROP es una sucesión finita de signos, digamos \( s_0,\ldots, s_n \). Asígnale el número natural \( g(\phi) = p_0^{n(s_0)}\cdots p_n^{n(s_n)} \), donde \( p_i \) es la sucesión de los primos.
De este modo tienes una aplicación inyectiva del conjunto de fórmulas de PROP en los números naturales. Para hacerla biyectiva asigna el \( 0 \) a la fórmula \( \phi_0 \) tal que \( g(\phi_0) \) es el menor posible, asigna el \( 1 \) a la fórmula \( \phi_1 \) tal que \( g(\phi_1) \) es el menor posible después de \( g(\phi_0) \), etc.