Prueba de inducción de lema básica recursividad

Question

Principio de inducción: Supongamos $A$ ser un conjunto tal que $0 \in A$$n \in A \implies n + 1 \in A$. A continuación, para todos $n \in \mathbb{N}$, $n \in A$.

Básicos de la Recursividad Lema: Para todos los conjuntos de $X, W$ y dadas las funciones $g : X \to W$, $h : W \times \mathbb{N} \times X \to W$, existe una única función de $f : \mathbb{N} \times X \to W$ tal que $$f(0, x) = g(x)$$ $$f(n + 1, x) = h(f(n, x), n, x).$$

Mi libro me dice que estos dos estados son equivalentes. Sé cómo demostrar a la básica recursividad lema de la inducción de los principios, pero no puedo entender cómo no a la inversa. Todo lo que he tratado impone el uso de la inducción. Puede alguien me apunte en la dirección correcta?

Gracias.

Answer 1

Suponga $0\in A$$n\in A\Rightarrow n+1\in A$.

Vamos $X=\{\bullet\}$, $W=A$. Entonces podemos definir el $g\colon X\to W$ $g(\bullet)=0$ porque $0\in A$. Y podemos definir $h\colon W\times \mathbb N\times X\to W$ por $$h(x,y,z)=\begin{cases}y+1&\text{if }y+1\in A\\x&\text{otherwise}\end{cases}$$ Entonces existe una única función de $f\colon \mathbb N\times X\to W$ tal que $$f(0,x)=g(x)$$ $$f(n+1,x)=h(f(n,x),n,x)$$ Tenga en cuenta que para cualquier elemento $a\in A$, la función $f_a\colon \mathbb N\times X\to W$, $f_a(n,x)=\begin{cases}n&\text{if }n\in A\\a&\text{otherwise}\end{cases}$ obedece esta recursividad:

• $f_a(0,\bullet)=0=g(\bullet)$ porque $0\in A$.
• Si $n+1\in A$ $f_a(n+1,\bullet)=n+1=h(f_a(n,\bullet),n,\bullet)$
• Si $n+1\notin A$ también $n\notin A$, por lo tanto $f(n+1,\bullet)=a =h(a,n,\bullet)=h(f_a(n,\bullet),n,\bullet)$

Por la singularidad, cualquiera de las dos funciones son iguales. Como $0\in A$ inmediatamente y $1=0+1\in A$,$f_0=f_1$. Debido a $0\ne 1$, esto sólo es posible si el "de otra manera" en la definición de $f_a$ nunca se produce, que es: para todos los $n\in \mathbb N$, también tenemos $n\in A$.

Answer 2

Bueno, yo fijo mi respuesta. Es similar a la de Hagen ahora, pero creo que es un poco más sencillo.

Podemos suponer sin pérdida de generalidad que $A$ es un segmento inicial de $\mathbb{N}$.

Deje $h:A \cup \{\infty_0,\infty_1\} \to A \cup \{\infty_0,\infty_1\}$ dado por $h(n) = n+1$$n \in A$$h(\infty_i) = \infty_i$$i<2$.

Para $i<2$, definir la función de $f_i: \mathbb{N} \to A \cup \{\infty_0,\infty_1\}$ por $$f_i(n) = \begin{cases} n & \text{if %#%#%}\\ \infty_i & \text{otherwise} \end{casos}$$ Estas funciones tanto de satisfacer $n \in A$$f_i(0) = 0$, por lo que por la singularidad de la asunción de definiciones recursivas, que son de la misma (no necesitamos de la existencia de la asunción.) Asumiendo $f_i(n+1) = h(f_i(n))$ esto significa que el segundo caso en el que la definición no puede ocurrir, por lo $\infty_0 \ne \infty_1$ es de $A$.