Explicar por qué una función es definida

Question

¿Cómo puedo explicar que una función está bien definida, si se define recursivamente especificando $f(1)$ y una regla para encontrar el $f(n)$ $f(n-1)$?

Mi razonamiento: Si la función $f(n)$ puede derivarse de $f(n-1)$, entonces la función debe dar un valor único para cada entrada, que es parte de lo que significa ser bien definidos. Y puesto que tengo $f(1)$, entonces puedo probar cualquier otra función a partir de aquél, por lo que es bien definido.

Answer 1

"Bien definido" es un poco difusa plazo. Pero aquí parece que usted quiere asegurarse de que una función que está definida en $1$ y, a continuación, usted tiene una definición recursiva de explicar cómo obtener el $f(n)$ $f(n-1)$ no en el hecho de conducir a una función cuyo dominio es todos los números naturales.

La respuesta es que esto se deduce del Teorema de Recursión.

Teorema De Recursión. Deje $X$ ser un conjunto, vamos a $a\in X$, y deje $g\colon X\to X$ ser una función. Entonces existe una única función de $u\colon\mathbb{N}\to X$ tal que $u(1)=a$ $u(n+1) = g(u(n))$ todos los $n$.

Así que aquí, $X$ es el codominio de $f$; $a$ es el valor de $f(1)$; y $g$ es la función que corresponde a la regla para la búsqueda de $f(n)$$f(n-1)$. La Recursividad Teorema garantiza la existencia de una función cuyo dominio son todos los de $\mathbb{N}$ que tiene la propiedad que usted desea.

La prueba del teorema de recursión es por inducción. Lo que sigue es el argumento en el Halmos la Ingenua Teoría de conjuntos, páginas 48-49.

Recuerde que se puede considerar una función de $\mathbb{N}\to X$ como un conjunto $u$ de los pares ordenados $(n,x)$, donde para cada una de las $n\in \mathbb{N}$ hay un $x$$(n,x)\in u$; y si $(n,x)$ $(n,y)$ están en $u$,$x=y$.

Considerar la colección de todas las relaciones $A$ $\mathbb{N}$ $X$ que contengan $(1,a)$, y de tal manera que si $(n,x)\in A$,$(n+1,g(x))\in A$. La colección está vacía (el total de la relación satisface las propiedades), por lo que podemos considerar la intersección de todos los conjuntos de la colección. Llame a esta intersección $u$; debemos demostrar que $u$ es una función definida en todos los números naturales.

Deje $S$ ser el conjunto de todos los números naturales $n$ para el que no es exactamente un elemento $x$ $X$ tal que $(n,x)\in u$. Mostramos $S=\mathbb{N}$ por inducción.

Si $1\notin S$, entonces no existe $b\neq a$ tal que $(1,b)\in u$. Pero, a continuación, $u-\{(1,b)\}$ todavía contiene $(1,a)$, y si contiene $(n,x)$ a continuación, contiene $(n+1,g(x))$; por lo $u-\{(1,b)\}$ es una de las relaciones en nuestra colección, lo cual es imposible (ya que está correctamente contenida en la intersección de todas esas relaciones). Por lo $1\in S$.

Ahora supongamos que $n\in S$; Luego hay un único, $x\in X$ tal que $(n,x)\in u$. Por las propiedades de $u$, $(n+1,g(x))\in u$. Si $n+1\notin S$, entonces no existe $y\in X$, $y\neq g(x)$, tal que $(n+1,y)\in u$. A continuación, considere la posibilidad de $u-\{(n+1,y)\}$ y obtener una similar contradicción. Por lo $n+1\in S$.

Por inducción $S=\mathbb{N}$, lo $u$ es una función de$\mathbb{N}$$X$, como se desee.