En ciencias de la computación y la semántica de la que me he encontrado estructurales de inducción muchas veces. En ese contexto, a menudo se presenta como algo diferente, pero similar a la inducción matemática, a veces se describe como una generalización de la misma, y, a menudo, las pruebas o las discusiones de las fundaciones se omite, sustituye con una apelación a la plausibilidad. Wikipedia Estructurales de la Inducción de estados de página que "así como el estándar de la inducción matemática es equivalente al principio de buena ordenación estructural, la inducción es también equivalente a un principio de orden." Mientras que no acaba de decir que es y no tengo una referencia que dice, creo que eso estructurales de la inducción es la inducción matemática sobre un bien fundado de la estructura que no puede ser que los números naturales, y que puede decir sobre el Lema de Zorn? También sospecho que puede ser reducido a la inducción matemática sobre los números naturales, si uno es lo suficientemente inteligente. Tengo ese derecho, y puede que me apunte a cualquier referencia que llegar a estos tipos de detalles de la matemática y los aspectos fundamentales de esta ciencia de la computación-y el tema?
Respuesta
¿Demasiados anuncios?
Estructural de la inducción es un caso especial de Noetherian de inducción, sin embargo no parece ser claro cuando algo es Estructural de la inducción. Vagamente la relación en la bien fundada conjunto de necesidades a ser definido por algún tipo de recursividad. También se observa que a medida Zhen Lin señala Noetherian inducción no siempre puede ser reducido a normal inducción sobre los números naturales. Su ejemplo es muy claro desde los ordinales son innumerables, mientras que los números naturales son contables.
El punto de estructural de la inducción para demostrar que una propiedad $P$ tiene para todos los elementos de una bien fundada conjunto $S$. Para hacer esto usted puede asumir que no es cierto, entonces no es un conjunto no vacío $Q$ consiste de los objetos que no cumplen las $P$. Desde $S$ está bien fundada $Q$ contiene un mínimo elemento $m$. Cuando nos referimos a estructural de la inducción de la relación en $S$ es generalmente definida recursivamente (Que es el si $m<n$ si y sólo si $n$ puede obtenerse mediante la recursividad en $m$ un número finito de veces. Desde $S$ se define recursivamente el truco es tomar un elemento $c$ menor que $m$ y demostrar que también satisface $P$. pero si $c$ está en $P$ $m$ no puede ser mínima, una contradicción.
Estructural de la inducción es útil cuando la recursividad se ramifica en muchos niveles, y no es muy claro. Por ejemplo, considere la prueba de ratas Sprague Grundy teorema, donde una posición $a$ es menor que la posición $b$ si la posición $b$ es una opción de posición $a$
