Skip to content

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 ih y dónde se puede usar
  • Escribir con induction n with una 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:

  1. Vale cuando n es 0.
  2. 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:

text
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 ih

ih 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:

lean
example (n : Nat) : 0 + n = n := by
  rfl
text
is not definitionally equal to the right-hand side

Así que hay que usar inducción. Hazlo tú mismo una vez y fíjate en cómo se ve ih en la segunda rama:

Demostrar en la prácticaPrimera prueba por inducción: 0 + n = nEl estado y los errores provienen de Lean 4.35.0 Generar
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:

lean
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:

lean
#check @Nat.add_succ
text
Nat.add_succ : ∀ (n m : Nat), n + m.succ = (n + m).succ

m.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 ih en 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:

lean
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]
    omega

Ahora 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: ih es 2 * sumTo k = k * (k + 1).
    • simp [sumTo]: por definición, expandir sumTo (k + 1) en sumTo k + (k + 1).
    • rw [Nat.mul_add, ih]: distribuir 2 en el paréntesis, aparece 2 * sumTo k, sustituirlo con ih.
    • Ú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_formula usa 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 ih es 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».

gaodong.aiAboutPrivacyContact

Independent tutorials, not affiliated with any product mentioned. Product names and trademarks belong to their owners. Check official pages for prices and policies.