Inducción sobre los números naturales
Al terminar esta sección, podrás demostrar proposiciones del tipo «vale para todos los números naturales n». Ese sumTo_formula que no entendías en la primera sección, al final de esta sección sabrás leerlo por ti mismo.
Qué podrás hacer al terminar
- Explicar las dos partes de una demostración por inducción
- Entender qué es la hipótesis de inducción
ihy dónde se puede usar - Escribir con
induction n withuna demostración por inducción completa
Por qué se necesita la inducción
El decide de la sección anterior solo puede calcular números concretos. «Para todo n» tiene infinitos casos y no se pueden calcular todos.
El método de la inducción consiste en demostrar solo dos cosas:
- Vale cuando n es 0.
- Si vale para k, entonces también vale para k + 1.
Con estas dos condiciones, vale para 0, por lo tanto vale para 1, por lo tanto vale para 2, y así sucesivamente: cada número natural llega su turno. Es como derribar una fila de fichas de dominó: la primera cae, y cada ficha puede derribar a la siguiente.
En Lean, estas dos cosas corresponden a dos ramas:
induction n with
| zero => demostrar el caso en que n es 0
| succ k ih => demostrar el caso en que n es k + 1, se puede usar ihih es justamente el «si vale para k» de la condición 2. Es una hipótesis cuyo contenido es la proposición con n sustituido por k.
Manos a la obra: 0 + n = n
Esta proposición parece no necesitar demostración. Pero la suma de Lean está definida capa por capa sobre el segundo número: n + 0 puede calcular n directamente, 0 + n no. Pruébalo y lo verás:
example (n : Nat) : 0 + n = n := by
rflis not definitionally equal to the right-hand sideAsí que hay que usar inducción. Hazlo tú mismo una vez y fíjate en cómo se ve ih en la segunda rama:
theorem zero_add' (n : Nat) : 0 + n = n := by
induction n with
| zero =>
rfl
| succ k ih =>
rw [Nat.add_succ]
rw [ih]
Escrito en código:
theorem zero_add' (n : Nat) : 0 + n = n := by
induction n with
| zero =>
rfl
| succ k ih =>
rw [Nat.add_succ]
rw [ih]Se usa un teorema ya existente; busca qué dice:
#check @Nat.add_succNat.add_succ : ∀ (n m : Nat), n + m.succ = (n + m).succm.succ es m + 1. Este teorema dice: n + (m + 1) es igual a (n + m) + 1. Después de reescribir con él, en el objetivo aparece 0 + k, que es justamente el lado izquierdo de ih, así que se puede usar ih para reescribir una vez más.
El patrón de las demostraciones por inducción es este: reorganizar el caso k + 1 hasta que se vea la forma del caso k, y luego usar la hipótesis de inducción.
- He terminado la demostración de
zero_add'en los ejercicios - Puedo decir cuál es el contenido de
ihen esta demostración:0 + k = k
Volvamos a la fórmula de la suma
La función y el teorema de la primera sección:
def sumTo : Nat → Nat
| 0 => 0
| n + 1 => sumTo n + (n + 1)
theorem sumTo_formula (n : Nat) : 2 * sumTo n = n * (n + 1) := by
induction n with
| zero =>
rfl
| succ k ih =>
simp [sumTo]
rw [Nat.mul_add, ih]
simp [Nat.mul_add, Nat.add_mul]
omegaAhora ya puedes leerlos:
induction n with: inducción sobre n.- Rama
zero: n es 0, ambos lados se calculan como 0,rfl. - Rama
succ k ih:ihes2 * sumTo k = k * (k + 1).simp [sumTo]: por definición, expandirsumTo (k + 1)ensumTo k + (k + 1).rw [Nat.mul_add, ih]: distribuir 2 en el paréntesis, aparece2 * sumTo k, sustituirlo conih.- Últimas dos líneas: lo que queda es aritmética pura, expandir la multiplicación y entregarlo a
omega.
El patrón no cambia: expandir la definición, dejar visible el caso k, usar ih, y entregar el resto a las tácticas automáticas.
- Puedo señalar qué paso de
sumTo_formulausa la hipótesis de inducción
Pon a prueba tus conocimientosEn la rama succ k ih, ¿qué dice la hipótesis de inducción ih?
Punto de control
- Puedo decir las dos partes de una demostración por inducción: el caso 0, de k a k + 1
- Puedo escribir la estructura de
induction n with | zero => … | succ k ih => … - Sé que
ihes una hipótesis, no un objetivo - He entendido qué hace cada línea de
sumTo_formula
¿No funcionó?
No sé qué hacer en el siguiente paso de la rama succ. Mira si en el objetivo aparece el lado izquierdo de ih. Si no, expande primero la definición o reescribe hasta que aparezca.
Nombres de las ramas mal escritos. Las dos ramas de los números naturales se llaman fijamente zero y succ. k y ih son nombres que les pones tú.
Siguiente sección
La inducción no solo sirve para números. La siguiente sección hace inducción sobre listas y, por primera vez, te encuentras con la situación de «no puedo seguir con la demostración, necesito demostrar primero un auxiliar».