He buscado por todas partes y he mirado muchos ejemplos. No entiendo muy bien qué tiene de malo la trampa de la inducción. El ejemplo más común es el del árbol de la teoría de grafos (página 5 aquí: https://classes.soe.ucsc.edu/cmps102/Spring15/lect/1/ind-tantalo.pdf ). ¿Alguien puede explicarlo?
El problema está aquí "Añadir un nuevo vértice y unirlo a $T$ con una nueva arista. El gráfico resultante tiene $n + 1$ vértices y $n$ bordes". Todo lo que has mostrado aquí es que este nuevo gráfico satisface tu conclusión deseada. No has demostrado que esto sea cierto para cualquier gráfico arbitrario en $n+1$ vértices. El problema en este paso es que cuando se intenta afirmar su verdad para cualquier gráfico en $n+1$ vértices estás afirmando implícitamente que todo árbol se puede construir añadiendo vértices a un árbol más pequeño. Esto no es un hecho (aunque acaba siendo cierto). Normalmente, con la inducción se empieza realmente con $n+1$ desglosarlo en $n$ aplica tu hipótesis de inducción y vuelve a subir. Si en lugar de eso eliges ir directamente hacia arriba debes tener cuidado de que esto te lleve realmente a todos los casos posibles anteriores.
Nunca he escuchado el término "trampa de inducción" pero por lo que puedo deducir del enlace es cuando en lugar de realizar la inducción en un caso k = n se baja a un caso n-1 y luego se vuelve a subir al caso n y se muestra el caso n+1.
El problema es que el caso n-1 puede no ser válido.
El mejor ejemplo es la prueba de que en cualquier grupo de caballos, todos los caballos del grupo son del mismo color.
Si n=1 entonces todos los caballos de cualquier grupo de 1 son del mismo color. Verdadero.
Paso de inducción: Supongamos que hay un n para el que todos los n caballos de cualquier grupo de n son del mismo color. Quita un caballo para que tengas n-1 caballos. PROBLEMA Nunca verificamos para el caso n = 0. Todos los caballos n son del mismo color pero vacíos. No hay un solo color para que todos ellos sean. A partir de aquí nuestra prueba está condenada.
NUESTRO GRAN PASO INVÁLIDO. Todos los caballos n-1 restantes son del mismo color que el caballo eliminado. NO SE VERIFICA PARA n-1 = 0. Sólo es vacuamente cierto.
A partir de aquí nuestro razonamiento es sólido pero nuestra premisa es mala. Si añadimos un nuevo caballo, tenemos n caballos. Cualquier grupo de n caballos debe ser del mismo color. Así que el nuevo caballo debe ser del mismo color que los n-1 caballos. Añade el caballo original. Es del mismo color que los n-1 caballos y, por tanto, que el nuevo caballo. Así que todos los n+1 caballos son del mismo color. Así que cualquier grupo de n+1 caballos es del mismo color.
Si hubiéramos comenzó a n = 0 y se dijera inicialmente "Todos los caballos 0 son del mismo color" lo reconoceríamos como verdadero pero a partir del cual es imposible cualquier inducción (ya que son del mismo color vacuamente pero no es el caso que sean de un color específico).
Creo que has entendido mal el cuento de los caballos: La proposición es obviamente cierta para $n=0,1$ . Supongamos que se mantiene para todos los $k\leq n$ . Considere un grupo de $n+1$ caballos, al quitar el último caballo tenemos un grupo de $n$ caballos, todos del mismo color. Añade ese caballo de nuevo, y elimina el primer caballo, blablabla $\dots$ como los grupos tenían en un caballo en común, el $n+1$ los caballos son del mismo color. La afirmación en negrita es la parte errónea: Eso no es cierto para un grupo de $2$ caballos.
No tiene nada que ver con la $0$ caso de los caballos, ya que eso es cierto (que el caso base sea vacuo no hace que una prueba de inducción sea inválida).
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
0 votos
¿por qué esto ha sido votado negativamente?
0 votos
@m.badaoui no necesitas aceptar una respuesta hasta que encuentres una que te ayude a resolver tu problema.