Definición por recursividad

Question

Acabo de empezar a estudiar lógica, no como un curso en una universidad, pero como pasatiempo. Pues yo no estudio de la lógica en una institución utilizo muchos diferentes libros de texto, entre Enderton del $A$ $Mathematical$ $Introduction$ $to$ $Logic$ y Van Dalen del $Logic$ $and$ $Structure$. Ahora, mi pregunta es esta: Es el siguiente teorema (Van Dalen p. 11) una reformulación de la habitual teorema de recursión? Si no, entonces ¿cómo se podría ir sobre demostrar este teorema.

Vamos a asignaciones $H_{\square}: A^{2} \to A$ $H_{\neg}:A \to A$ ser dado y deje $H_{at}$ ser un mapeo del conjunto de átomos en $A$, entonces existe exactamente una asignación de $F:PROP \to A$ $$F(\phi) = H_{at}(\phi) \quad \text{for $\phi$ atomic,}$$ $$ F((\phi \square \psi)) = H_{\square}(F(\phi),F(\psi)),$$ $$F((\neg \phi)) =H_{\neg}(F(\phi))$$

Gracias por tomarse el tiempo para leer esta pregunta.

Answer 1

Dependiendo de lo que entendemos por "el" teorema de recursión (hay demasiados resultados con el mismo nombre), esta afirmación puede o no puede ser visto como un caso particular, o incluso como equivalente. Me parece que es mejor argumentar directamente que tratar para que se ajuste de manera abstracta en alguna opción de configuración y, a continuación, deducir, como un corolario.

Una manera de proceder es fuerte por inducción sobre la longitud de las fórmulas proposicionales, primero verificar que para cada una de las $n$ hay un único, $F_n$ definido en las fórmulas de longitud en la mayoría de las $n$, y la satisfacción de las tres necesidades.

Esto es claro si $n=1$, puesto que las dos últimas cláusulas doe no se aplican, y el primero nos dice exactamente lo $F_1$: $$F_1=H_{at}\upharpoonright\{\mbox{Propositional formulas}\}.$$

Si $n>1$ y el resultado es cierto para las fórmulas de longitud estrictamente menor $n$, también tiene para las fórmulas de longitud $n$, que es: Si para todas las $m<n$ hay un único, $F_m$ definido en las fórmulas de longitud en la mayoría de las $m$ y la satisfacción de las tres necesidades, entonces, el mismo es válido para $n$.

Para ver esto, supongamos primero que $F_n$ $F_n'$ son dos funciones de la satisfacción de las tres necesidades, definidas en el conjunto de las fórmulas de longitud en $n$. Para cualquier $m<n$, la restricción de $F_n$ a las fórmulas de longitud en la mayoría de las $m$ debe $F_m$ (por la suposición inductiva) y de manera similar para $F_n'$. De ello se sigue que si $F_n$ $F_n'$ está en desacuerdo, el desacuerdo se produce en una fórmula de longitud, precisamente,$n$. Pero ninguna de esas fórmulas, no se atómica, es $(\lnot\phi)$ o $(\phi\mathrel{\square}\psi)$ para algunos más corto fórmulas de $\phi,\psi$, y algunos binario conectivo $\square$.

En el primer caso, tenemos $$ F_n((\lnot\phi))=H_{\lnot}(F_n(\phi))=H_{\lnot}(F_{n-3}(\phi))=H_{\lnot}(F_n'(\phi))=F_n'((\lnot\phi)), $$ desde $F_n$ $F_{n'}$ satisfacer el tercer requisito, y la perspectiva de la asunción en la uniquenesss de $F_{n-3}$.

El segundo caso es completamente análogo. Esto muestra que no hay ningún desacuerdo entre $F_n$$F_n'$, y la singularidad de la siguiente manera.

Para demostrar la existencia es similar, si sólo un poco más engorroso. Podemos definir a la $F_n$ el uso de los tres dados cláusulas, y la existencia de las anteriores funciones de $F_m$. Por ejemplo, $F_n(\phi)$ se define como $F_1(\phi)$ si $\phi$ es atómica, y como $H_\square(F_m(\psi),F_j(\tau))$ si $\phi$ $(\psi\mathrel{\square}\tau)$ donde $\psi$ es una fórmula de longitud de $m$ $\tau$ es una fórmula de longitud de $j$ (y lo mismo para el resto de casos).

Que esto está bien definido de la siguiente manera a partir de la (previamente establecido) a resultado que no es único en la legibilidad de las fórmulas, así: Dado cualquier $\phi$, es atómica, o tiene la forma $(\lnot\tau)$, e $\tau$ es una fórmula, o tiene la forma $(\psi\mathrel{\square}\tau)$, para algunas fórmulas $\psi,\tau$ y algunos binario conectivo $\square$. Por otra parte, estos casos son mutuamente excluyentes, y en el último caso, no hay una única dicha descomposición de $\phi$.

Una vez que tenemos ese $F_n$ está bien definido, se sigue trivialmente que cumple con los tres requisitos: en Primer lugar, la suposición inductiva nos da (de nuevo) que $F_n$ extiende la única $F_m$ siempre $m<n$. Esto asegura que los tres requisitos se mantienen cuando la evaluación de $F_n(\phi)$ para las fórmulas de $\phi$ de la longitud de menos de $n$. Para $\phi$ de longitud, precisamente,$n$, esto se deduce de la definición de $F_n$, dándose cuenta de que desde $F_n$ amplía las funciones $F_m$$m<n$, entonces, por ejemplo, $$ F_n((\psi\mathrel{\square}\tau))=H_\square(F_m(\psi),F_j(\tau))=H_\square(F_n(\psi),F_n(\tau)). $$

Ahora que hemos establecido la existencia y unicidad de la $F_n$, tenemos que las funciones son compatibles, en el sentido de que sus gráficos se extienden cada uno de los otros: $$F_1\subseteq F_2\subseteq F_3\subseteq \dots$$ This means that $F=\bigcup_n F_n$ is a function, and it satisfies the three requirements since each $F_n$ does. But $F$ has domain the set $\mathsf{PROPOSICIÓN}$ of all propositional formulas. Uniqueness of $F$ is as before, noticing that if $F$ is any function with domain $\mathsf{PROPOSICIÓN}$ and satisfying the three requirements, its restriction to formulas of length at most $n$ is precisely $F_n$, so in fact $F=\bigcup_n F_n$.