Ante todo, recordemos que una
función es una
colección de pares ordenados \( (x,y) \)
con la
propiedad de unicidad de la imagen, esto es:
- Si \( (x,y), (x,y') \) son dos pares correspondientes a la función,
entonces \( y = y' \).
Notacionalmente, se conviene en escribir que \( y= f(x) \) es lo mismo que afirmar
que el par ordenado \( (x,y) \) pertenece al conjunto \( f \).
Por lo tanto, la función \( f \) que estamos buscando,
cuyo dominio es \( N \) y cuya imagen está en \( X \),
será cierto conjunto de pares ordenados \( (n,y) \), con \( n\in N, y\in X \),
y de tal suerte que se cumpla la
propiedad de unicidad de la imagen.
Lo que se hace en esta situación es
- construir un conjunto de pares ordenados \( f \),
- posteriormente demostrar que \( f \) es, en efecto, una función, y
- que además cumple las relaciones de recurrencia.
- Finalmente, se debe probar que sólo hay una función \( f \) posible que satisface dicha recurrencia.
Este hecho es más sencillo de demostrar.
Así que vayamos a los detalles.
Vamos a dar algunas definiciones para limpiar un poco el lenguaje.
Sea \( D \) un subconjunto de \( N \).
Diremos que
\( h \) es una función \( G \)-recursiva
con dominio \( D \) y valor inicial \( \alpha\in X \),
si \( h \) es una función de \( D \) en \( X \), tal que:
- \( 1\in D \),
- \( h(1)=\alpha \), y además,
- para todo \( n\in N \), si \( S(n)\in D \), entonces también \( n\in D \) y \( h(S(n))=G(n,h(n)) \).
Tomemos \( \alpha\in X \) fijo,
y definamos un gran conjunto \( K_\alpha \) que contenga a todos los subconjuntos \( h \) de \( N\times X \)
(o sea, cada \( h \) es un conjunto formado por pares ordenados \( (n,y) \), con \( n\in N, y\in X \)),
con la propiedad de que existe un conjunto \( D\subset N \)
tal que \( h \) es una función \( G \)-recursiva con dominio \( D \)
y valor inicial \( \alpha \).
Formalmente, esto sería así:
\( K_\alpha=\{h: D\to X| D\subset N, h(1)=\alpha, \forall{n\in N}:(S(n)\in D \Rightarrow{n\in D \wedge h(S(n))=G(n,h(n))})\}. \)
Ahora definimos \( f \) como la unión de todos los elementos \( h \) del conjunto \( K_\alpha \):
\( \displaystyle f=\bigcup_{h\in K_\alpha} h. \)
¿Esta
unión de apariencia enorme y caótica va a comportarse como la función \( f \) que esperamos obtener?
Asombrosamente, sí.
O sea, la enormidad y el caos de esa
unión así tomada son sólo aparentes.
Veamos.
En primer lugar,
notemos que \( f \) es un conjunto de pares ordenados \( (n,y) \),
con \( n\in N \), \( y\in Y \).
Lo primero que deseamos probar es que,
para cada \( n\in N \), hay al menos un par \( (n,y) \) en \( f \).
Esto es necesario demostrarlo,
porque si pretendemos que \( f \) sea una función con dominio \( N \),
para cada \( n \) debe corresponder algún valor \( y \) por la aplicación \( f \).
Así que sea \( A \) el conjunto de las "
primeras componentes" de los pares que están en \( f \), esto es:
\( A=\{n\in N| \exists{y\in X:(n,y)\in f}\}. \)
Deseamos demostrar que \( A = N \),
y eso lo haremos usando el
Principio de Inducción.
Ciertamente, el elemento \( 1 \) está en \( A \), porque \( (1,\alpha)\in f \).
Para un \( n\in N \) arbitrario, supongamos que \( n\in A \).
Por definición de \( A \), existe \( y\in X \) tal que el par ordenado \( (n,y) \in f \).
Como \( f \) es la unión de los elementos de \( K_\alpha \),
ha de existir un elemento \( h\in K_\alpha \) tal que \( (n,y)\in h. \)
Denotemos \( D \) al dominio de una tal \( h \).
Ocurren dos casos posibles: o bien \( S(n) \) está en \( D \), o bien no está.
Si \( S(n)\in D \),
entonces existe\( z\in X \) tal que \( (S(n),z)\in h \),
pero como \( h\subset f \), tenemos que \( (S(n),z)\in f \)
Supongamos ahora el caso en que \( S(n) \) no pertenece a \( D \).
En tal situación, construiremos una función \( h_1 \) de la siguiente manera:
Definimos \( D_1 = D\cup\{S(n)\} \),
y hacemos que \( h_1 \) sea una función con dominio \( D_1 \), dada por:
\( h_1(k)=\begin{Bmatrix} h(k) & \mbox{ si }& k\in D\\G(n,h(n)) & \mbox{si}& k=S(n)\end{matrix} \).
Mostremos que \( h_1 \in K_\alpha. \)
En efecto, sea \( k\in N \) tal que \( S(k)\in D_1 \).
Si \( k\neq n \), entonces necesariamente \( S(k)\in D \), el dominio de \( h \),
y esto significa que \( k\in D \),
y además \( h(S(k))=G(k,h(k)) \).
Pero también, como \( k,S(k)\in D \), la definición de \( h_1 \) nos da
que \( h_1(S(k))=h(S(k))=G(k,h(k))=G(k,h_1(k)) \).
Por otra parte, si \( k=n \), recordemos que
teníamos al principio de todo que \( n \) es un elemento de \( D \) (pues \( (n,y)\in h\subset f \)),
luego \( h_1(n)=h(n) \), y por definición: \( h_1(S(n))=G(n,h(n))=G(n,h_1(n)). \)
Esto prueba que \( h_1 \in K_\alpha. \)
Por lo tanto, \( h_1 \subset f \), y esto quiere decir que existe \( z\in X \) tal que \( (S(n),z)\in f. \)
En cualquier caso, hemos probado que existe \( z\in X \) tal que \( (S(n),z)\in f. \)
Esto indica que \( S(n)\in A \).
En resumen, tenemos que \( 1\in A \) y \( n\in A\Rightarrow{S(n)\in A} \).
Aplicando
Principio de Inducción, obtenemos que \( A=N \).
Por lo tanto, para todo \( n\in N \),
existe algún \( z\in X \) tal que \( (n,z)\in f. \)
Ahora nos falta probar que \( f \) es una función,
o sea, que tiene la propiedad de unicidad de la imagen. Veamos.
Consideremos el conjunto \( B \) formado por todos los \( n\in N \)
para los que se cumple la
propiedad de unicidad de la imagen para \( f \),
o sea, tales que si \( (n,y),(n,z)\in f \), entonces \( y=z \). Formalmente:
\( B=\{n\in N: (n,y),(n,z)\in f \Rightarrow{ y=z}\}. \)
Sea \( n= 1 \). Para todo \( h\in K_\alpha \),
tenemos que \( (1,\alpha)\in h \subset f \),
por lo tanto \( (1,\alpha)\in f \).
Supongamos que para cierto \( z\in X \) se cumple que \( (1,z)\in f \).
Esto quiere decir que existe \( h\in K_\alpha \) tal que \( (1,z)\in h \).
Como \( h \) es una función, debemos tener que \( z=\alpha \).
Así que hemos probado que \( 1\in B \).
Supongamos que para cierto \( n\in N \) vale \( n\in B \).
Deseamos probar que esto implica que \( S(n)\in B \).
Sean \( y, z \in X \) tales que \( (S(n),y),(S(n),z)\in f \).
Existe alguna función \( h\in K_\alpha \) tal que \( (S(n),y)\in h \).
Esto quiere decir que existe \( v\in X \) tal que \( (n,v)\in h\subset f \),
y además \( y=h(S(n))=G(n,h(n))=G(n,v) \).
De modo similar, se puede encontrar una función \( \tilde h\in K_\alpha \) y un \( w\in X \)
tal que \( (n,w)\in \tilde h\subset f \),
y además \( z=\tilde h(S(n))=G(n,\tilde h(n))=G(n,w) \).
Como \( (n,v),(n,w)\in f \),
la hipótesis de inducción en \( n \) nos dice que \( v=w \).
Por lo tanto \( y=G(n,v)=G(n,w)=z \), como se deseaba probar.
Aplicando el
Principio de Inducción, hallamos que \( B= N \),
y entonces \( f \) tiene la
propiedad de unicidad de la imagen.
En resumen, \( f \) es una función, con dominio \( N \) e imagen en \( X \).
A su vez, vale que \( f(1)=\alpha \), y dado \( n\in N \),
existen \( h\in K_\alpha, y\in X, \) tal que \( (S(n),y)\in h\subset f \), \( (n,h(n))\in h\subset f \),
con lo cual \( f(S(n))=h(S(n))=G(n,h(n))=G(n,f(n)) \).
Hemos demostrado que
existe una función \( f \) que cumple con las condiciones de
recurrencia.
Resta demostrar que hay sólo una tal \( f \).
Sea \( \tilde f \) otra posible función de \( N \) en \( X \)
que cumple con las relaciones de recurrencia\( \tilde f(1)=\alpha, \tilde f(S(n))=G(n,\tilde f(n)) \).
Sea \( C \) el conjunto donde las imágenes de ambas funciones \( f, \tilde f \) coinciden, o sea:
\( C=\{n\in N: f(n)=\tilde f(n)\}. \)
Claramente \( 1\in C \), porque \( f(1)=\alpha=\tilde f(1). \)
Supongamos que \( n\in C \).
En ese caso, tenemos que \( f(n)=\tilde f(n) \),
luego \( f(S(n)) = G(n,f(n))=G(n,\tilde f(n))= \tilde f(S(n)). \)
Por lo tanto también \( S(n)\in C. \)
Por el
Principio de Inducción, resulta que \( C=N \).
Así que \( f=\tilde f \), como se deseaba demostrar.