ExistenciaDefinamos el conjunto \( F^*\subset \text{PROP}\times B \) de pares ordenados como el
menor conjunto que satisface con las reglas:
\( \begin{array}{ll} \mbox{ I } & \mbox{Si $\varphi=p_i$ o $\varphi=\bot$, entonces $(\varphi,H_{at}(\varphi))\in F^*$} \\ \mbox{ II }& \mbox{Si $(\varphi,b)\in F^*$ y $(\psi,b')\in F^*$, entonces $((\varphi\square \psi),H_{\square}(b,b'))\in F^*$}\\ \mbox{ III }& \mbox{Si $(\varphi,b) \in F^*$, entonces $((\lnot \varphi),H_{\lnot}(b))\in F^*$} \end{array} \)
Veamos ahora que este subconjunto del producto cartesiano \( \text{PROP}\times B \) es una función \( F=F^*:\text{PROP}\rightarrow B \). Para ello debemos mostrar que toda fórmula \( \varphi\in \text{PROP} \) aparece una y sólo una vez como primer componente de un par ordenado de \( F^* \). O dicho de otra manera, si \( \varphi\in \text{PROP} \) y \( b,b'\in B \) cumplen que \( (\varphi,b)\in F^* \) y \( (\varphi,b')\in F^* \) entonces \( b=b' \). La prueba la haré directamente por inducción sobre \( \varphi \) como sugeriste al principio porque me parece más fácil. Entonces la propiedad a probar estaría referida a los elementos de \( \text{PROP} \) y sería la siguiente \( A(\varphi):=\mbox{`` dados $b,b'\in B$, si $(\varphi,b)\in F^*$ y $(\varphi,b')\in F^*$ entonces $b=b'$ ''} \).
PASO BASE
Hay que probar que se cumple \( A(\varphi) \) para toda \( \varphi \) atómica. Supongamos que \( (\varphi,b)\in F^* \) y que \( (\varphi,b')\in F^* \). Como \( \varphi=p_i \) para algún \( i\in \mathbb{N} \), o \( \varphi=\bot \), por la regla \( \text{I} \) de construcción de \( F^* \) se tiene que \( b=H_{at}(\varphi) \) y que \( b'=H_{at}(\varphi) \). Como \( H_{at} \) es función, la imagen de \( \varphi \) por \( H_{at} \) es única y por lo tanto, \( b=b' \).
PASO INDUCTIVO 1
Supongamos que son ciertas \( A(\varphi) \) y \( A(\psi) \). Hay que probar \( A((\varphi\square \psi)) \), o sea, que si \( ((\varphi\square \psi),r)\in F^* \) y \( ((\varphi\square \psi),r')\in F^* \) entonces \( r=r' \). Por un lado sabemos que \( (\varphi,b_1)\in F^*\wedge (\varphi,b_2)\in F^* \) implica \( b_1=b_2=b \). Es decir, \( (\varphi,b) \) es el único par ordenado en \( F^* \) que tiene a \( \varphi \) como primer componente. Por otra parte, sabemos que \( (\psi,b_1')\in F^*\wedge (\psi,b_2')\in F^* \) implica \( b_1'=b_2'=b' \). Es decir, \( (\psi,b') \) es el único par ordenado en \( F^* \) que tiene a \( \psi \) como primer componente. Por la regla \( \text{II} \) de construcción de \( F^* \), como \( (\varphi,b)\in F^* \) y \( (\psi,b')\in F^* \) sabemos que \( ((\varphi\square \psi),H_{\square}(b,b'))\in F^* \). Como \( (\varphi,b) \) es el único par ordenado en \( F^* \) que tiene a \( \varphi \) como primer componente, y \( (\psi,b') \) es el único par ordenado en \( F^* \) que tiene a \( \psi \) como primer componente, todo par en \( F^* \) que tenga a \( (\varphi\square \psi) \) como primer componente, deberá tener a \( H_{\square}(b,b') \) como segunda componente. Por lo tanto, si \( ((\varphi\square \psi),r)\in F^* \) entonces \( r=H_{\square}(b,b') \). Análogamente, \( r'=H_{\square}(b,b') \). Finalmente, como \( H_{\square} \) es función, la imagen de \( (b,b') \) por \( H_{\square} \) es única y por lo tanto, \( r=r' \).
PASO INDUCTIVO 2
Supongamos que es cierta \( A(\varphi) \). Hay que probar \( A((\lnot \varphi)) \), o sea, que si \( ((\lnot \varphi),s)\in F^* \) y \( ((\lnot \varphi),s')\in F^* \) entonces \( s=s' \). Por hipótesis de inducción sabemos que \( (\varphi,b_1)\in F^*\wedge (\varphi,b_2)\in F^* \) implica \( b_1=b_2=b' \). Es decir, \( (\varphi,b) \) es el único par ordenado en \( F^* \) que tiene a \( \varphi \) como primer componente. Por la regla \( \text{III} \) de construcción de \( F^* \), como \( (\varphi,b)\in F^* \) sabemos que \( ((\lnot \varphi),H_{\lnot}(b))\in F^* \). De nuevo, como \( (\varphi,b) \) es el único par ordenado en \( F^* \) que tiene a \( \varphi \) como primer componente, todo par en \( F^* \) que tenga a \( (\lnot \varphi) \) como primer componente, deberá tener a \( H_{\lnot}(b) \) como segunda componente. Por lo tanto, si \( ((\lnot \varphi),s)\in F^* \) entonces \( s=H_{\lnot}(b) \). Análogamente, \( s'=H_{\lnot}(b) \). Finalmente, como \( H_{\lnot} \) es función, la imagen de \( b \) por \( H_{\lnot} \) es única y por lo tanto, \( s=s' \).
UnicidadEs inmediato a partir de ésto:
Pues supones otra función G que cumpla las mismas condiciones de la definición recursiva de F y tienes que probar la fórmula \( A(\phi) \) dada por \( F(\phi)=G(\phi) \) para toda fórmula \( \phi \).
Se trata de otra inducción en \( \text{PROP} \), mucho más directa que la anterior.