Inducción sin enteros (también conocido como inducción estructural)

Question

Mientras que la composición de la siguiente pregunta, que yo tenía un "ah-ha" momento. Todavía quiero post de la pregunta junto con mi respuesta a mostrar lo que he aprendido. Cualquier comentario o preguntas adicionales será muy apreciada.

Recientemente me encontré con un teorema en Un Introcution a la Lógica Matemática y la Teoría Tipo: A la Verdad a través de la Prueba de Peter B. Andrews, donde el autor afirma que puede ser utilizado en inductiva pruebas sin el uso de números enteros. El teorema se expresa como

1000 Principio de Inducción en la Construcción de un Wff. Deje $\mathscr{R}$ ser una propiedad de las fórmulas, y deje $\mathscr{R}(\mathbf{A})$ significa que $\mathbf{A}$ propiedad $\mathscr{R}$. Supongamos que

(1) $\mathscr{R}(\mathbf{q})$ para cada variable proposicional $\mathbf{q}$.

(2) Siempre que $\mathscr{R}(\mathbf{A})$,$\mathscr{R}(\mathord{\sim} \mathbf{A})$.

(3) Cuando $\mathscr{R}(\mathbf{A})$$\mathscr{R}(\mathbf{B})$,$\mathscr{R}([\mathbf{A} \lor \mathbf{B}])$.

A continuación, cada wff tiene la propiedad $\mathscr{R}$.

Estoy bastante familiarizado con la inducción matemática en enteros. Mina suelen tomar la forma siguiente:

Bla, bla, bla. Por lo tanto, la declaración tiene por $n=1$.

Ahora, supongamos que la afirmación es verdadera para algún entero $n$. Ahora considere la declaración de $n+1$. Yadda, yadda, yadda (transformar la declaración de $n+1$ en una declaración que implican $n$). Por lo tanto, la declaración tiene por $n+1$.

También estoy cómodo con el uso fuerte de inducción:

Bla, bla, bla. Por lo tanto, la declaración tiene por $n=1$.

Ahora, supongamos que la afirmación es verdadera para todos los enteros $k$ tal que $1 \le k \le n$ para algunos entero $n$. Ahora considere la declaración de $n+1$. Yadda, yadda, yadda (transformar la declaración de $n+1$ en una declaración de enteros $k$$1$$n$). Por lo tanto, la declaración tiene por $n+1$.

Un ejemplo de que la usaría esto es en la teoría de grafos para demostrar que un enunciado acerca de los árboles. De proceder por inducción sobre el número de vértices en un árbol. Esto se asigna el objeto de interés (un árbol) para los números enteros.

Cuando traté de aplicar el teorema acerca de wffs, me quedé atrapado cómo proceder. ¿Cómo puedo aplicar este teorema para una prueba?

Answer 1

$\def\p{{\mathscr R}}$Si usted se siente incómodo con la idea de hacer la inducción directamente sobre la estructura, o si desea reducir la cuestión a una de inducción sobre los números enteros, se puede proceder por inducción sobre el tamaño de la WFF, para algunos definición adecuada de "tamaño". Una típica definición es que el tamaño de la WFF es el número de operadores lógicos que contiene.

A continuación, para demostrar que $\p(W)$ es válido para cada WFF $W$, prosiga de la siguiente manera:

1. Mostrar que $\p(W)$ mantiene para cada una de las $W$ del tamaño más pequeño posible. (1, si usted está contando los átomos, o 0, si usted está contando los operadores.)
2. Mostrar que si $\p(W)$ tiene para todos los $W$ de tamaño inferior a $n$, entonces se debe mantener para todos los $W$ del tamaño de la $n$, como sigue: vaya a $W$ ser un WFF de tamaño $n$. A continuación, debe tener la forma $\sim A$ para algunos wff $A$ del tamaño de la $n-1$, o la forma $A\oplus B$ para algunos operador $\oplus$ y algunos wffs $A$ $B$ cada uno del tamaño en la mayoría de los $n-1$. Rellene el argumento inductivo por el que dos o más casos.

Formulado de esta manera, la inducción es un fuerte inducción en números enteros, donde en lugar de la prueba de la declaración "$\p(W)$ tiene para todos los wffs $W$", reformular como "Para todos los números $n$, $\p(W)$ tiene para cada wff de tamaño $n$".

Pero este tipo de transformación, realmente no debería ser necesario. El principio de la inducción puede ser dicho de forma más general. Supongamos $S$ es cualquier conjunto, y $\prec$ es un bien fundado orden en $S$; esto significa que cada subconjunto de $S$ está vacío o contiene un $\prec$-mínimo elemento, que es un elemento $m\in S$ de manera tal que no hay ningún otro elemento $m'\in S$$m'\prec m$.

Un ejemplo típico sería que wffs puede ser ordenada por un orden que dice que $a\prec b$ siempre $a$ es un subformula de $b$. Por ejemplo, $(x\land y)$ es un subformula de $\lnot(x\land y)\lor z$, lo $(x\land y)\prec \lnot(x\land y)\lor z$.

El pedido de $\prec$ no necesita ser total, lo que significa que es posible que ninguno de $a\prec b, a=b, $ $b\prec a$ necesita ser verdadero. Para el $\prec$ en el párrafo anterior, no tenemos ni $a\land b \prec a\lor b$ ni $a\lor b \prec a\land b$. Que está muy bien.

A continuación, puede utilizar bien fundado de la inducción de la siguiente manera:

1. Deje $F$ el conjunto de wffs para que $\p$ es falso. Supongamos $F$ es no vacío. A continuación, por el fundamento de $\prec$, tiene un $\prec$-mínimo elemento $m$.
2. Mostrar que $m$ no tiene ningún subformulas, de la siguiente manera. Mostrar que si $m$ tiene subformulas, entonces, usando algunas propiedades de $\p$, muestran que $\p$ debe mantener para uno de los subformulas. Pero luego esta el subformula es un elemento de $F$, contradiciendo la minimality de $m$, lo que descarta este caso.
3. Por lo $m$ no tiene subformulas. Descartar este caso con un poco de propiedad de $\p$.

Esto descarta la posibilidad de que $F$ contiene en realidad una $\prec$-mínimo elemento $m$, y la única posibilidad es que el $F$ está vacía, y por lo $\p$ es válido para cada wff.

Ordinario de la inducción es un caso especial de bien fundado de inducción que utiliza el bien fundado relación $\lt$ sobre los números naturales. El fundamento de $\lt$ es equivalente a los llamados principio de ordenación de los números naturales, que dice que todo subconjunto de a $\Bbb N$ o bien contiene un $\lt$-mínimo elemento, o está vacío.

Answer 2

Voy a dar una respuesta generalizada aquí. Tengo otra pregunta sobre el ejercicio en el que he estado usando este teorema, por lo que esperamos que sirva de ejemplo cuando voy a publicar más tarde.

La clave para aplicar el Principio de Inducción en la Construcción de un Wff es en la ruptura de su estructura lógica. Empezamos con una propiedad $\mathscr{R}$ de fórmulas y, a continuación, quieren demostrar que cada wff tiene la propiedad de $\mathscr{R}$. Para ello, sólo tenemos que verificar cada una de las tres condiciones:

(1) $\mathscr{R}(\mathbf{q})$ para cada variable proposicional $\mathbf{q}$.

Este es el caso base para la inducción. Sólo tenemos que verificar que cada variable proposicional tiene la propiedad de $\mathscr{R}$.

(2) Siempre que $\mathscr{R}(\mathbf{A})$,$\mathscr{R}(\mathord{\sim} \mathbf{A})$.

Aquí es donde me encontré a la primera. Sin embargo, después de pensarlo, me di cuenta de que esto es una implicación, similar a la que utilizamos para inducción típico en los enteros. Para aplicar esta condición, tenemos que asumir que algunas fórmula $\mathbf{A}$ propiedad $\mathscr{R}$ a continuación muestran que la $~ \mathbf{A}$ propiedad $\mathscr{R}$.

(3) Cuando $\mathscr{R}(\mathbf{A})$$\mathscr{R}(\mathbf{B})$,$\mathscr{R}([\mathbf{A} \lor \mathbf{B}])$.

Este es básicamente el mismo que el anterior. La implicación significa que tengo que asumir que $\mathscr{R}(\mathbf{A})$ $\mathscr{R}(\mathbf{B})$ y demostrar que $\mathscr{R}([\mathbf{A} \lor \mathbf{B}])$.

Voy a publicar otra cuestión sobre la que se aplica este theorm y hace los comentarios anteriores un poco más concreto, con un ejemplo.

Añadió:

Un ejemplo más concreto de una aplicación estructural de la inducción se puede encontrar en esta pregunta.