Sé que para probar algunos $P(m,n)$ podemos aplicar la inducción de la siguiente manera: demostrar algún caso base $P(m_0, n_0)$ , un paso inductivo dado $P(m-1,n)$ para mostrar $P(m,n)$ y un paso inductivo dado $P(m,n-1)$ para mostrar $P(m,n)$ . Sin embargo, en una prueba en la que estoy trabajando necesito una hipótesis más fuerte. En particular, para demostrar $P(m,n)$ dado $P(m-1,n)$ También tengo que asumir que $P(m-1,n-k)$ se mantiene para $1\leq k\leq n$ también, una especie de fuerte inducción. ¿Es esto lógicamente sólido, y si no es así, cuál es el problema? Si es sólida, ¿cuánto más fuerte puede ser?
Respuestas
¿Demasiados anuncios?
Una forma de hacerlo es demostrar $P(1,n)$ para todos los valores de $n\geq1$ . A continuación, haz la hipótesis de inducción de que para algún $m>1$ , $P(m,n)$ es verdadera para todos los valores de $n\geq1$ y demostrar que $P(m+1,n)$ es verdadera para todos los valores de $n\geq1$ . Esto demuestra que $P(m,n)$ es cierto para $m\geq1$ y todos los valores de $m$ . Al demostrar que $P(m+1,n)$ es cierto para todos los $m,n\geq1$ Por supuesto, usted es libre de utilizar cualquier tipo de inducción que elija.
Gregory Nisbet
Puntos
143
Dado $P(m, n)$ puede tratar $P(m-1, 0), P(m-1, 1), \cdots P(m-1, n)$ como accesible a su paso de inducción, pero también puede ir más allá y tomar todos los pares de números naturales que sean menores lexicográficamente, lo que incluye afirmaciones de la forma $P(m-1, \cdot)$ .
Creo que ayudaría elegir explícitamente un conjunto, elegir explícitamente un orden parcial en ese conjunto, demostrar que ese orden parcial es un buen orden, y luego proceder a partir de ahí.
Puede realizar la inducción en cualquier conjunto equipado con una orden de pozo.
Definamos $\le$ en pares de números como sigue. Este es el orden lexicográfico en $\mathbb{N} \times \mathbb{N}$ .
$$ (a, b) \le (c, d) \;\;\text{iff}\;\; a \le c \lor (a = c \land b \le d) $$
Este orden es bastante interesante. No hay cadenas descendentes infinitas, pero si empezamos con $(1, 0)$ en nuestra cadena, podemos hacer una cadena descendente arbitrariamente larga eligiendo el siguiente elemento para que sea $(0, n)$ para algunos $n$ en $\mathbb{N}$ . El siguiente elemento a ser $(0, n-1)$ y así sucesivamente.
Para convencernos de que no hay cadenas descendentes infinitas, observamos que si empezamos en la fila $(n, \cdot)$ entonces debemos llegar a la fila $(n-1, \cdot)$ en un número finito de pasos. Y si estamos en la fila $(0, \cdot)$ debemos alcanzar $(0, 0)$ en un número finito de pasos. La suma de números finitos es finita.
El esquema de inducción fuerte es el siguiente Aquí, $\implies$ es una versión de baja precedencia de $\to$ . $\vec{0}$ es el elemento mínimo de $\le$ . Aquí, $a < b$ es la abreviatura de $a \ne b \land a \le b$ .
$$ \bigg((\forall u < x \mathop. \varphi(u)) \to \varphi(x)\bigg) \land \varphi\!\left( \vec{0} \right) \implies (\forall u \mathop. \varphi(u)) $$
