Inducción sobre listas
Al terminar esta sección, habrás demostrado que tu función de inversión cumple "invertir dos veces es como no invertir". Más importante aún, vivirás un atasco en una demostración y aprenderás a detectar qué falta a partir del punto donde te quedaste.
Qué podrás hacer al terminar
- Escribir demostraciones por inducción sobre listas: la lista vacía, y "añadir un elemento al frente"
- Leer en un objetivo sin demostrar el lema auxiliar que necesitas
- Demostrar primero el lema y luego usarlo para terminar el teorema principal
Paso 1: escribir una función de inversión
def rev : List α → List α
| [] => []
| x :: xs => rev xs ++ [x][]es la lista vacía; invertirla sigue siendo vacía.x :: xses "el primer elemento x, seguido de la lista xs". Para invertirlo, primero se invierte el resto y luego se añade x al final.++es la concatenación de dos listas.
Pruébalo:
#eval rev [1, 2, 3][3, 2, 1]- Mi
revpuede invertir[1, 2, 3]
Paso 2: demostrar directamente, y atascarse
Lo que hay que demostrar es: para cualquier lista, rev (rev xs) = xs.
La inducción sobre listas, igual que sobre los números naturales, tiene dos ramas: nil es la lista vacía, cons x xs ih es "x seguido de xs", y ih dice que la proposición vale para xs. Escríbelo siguiendo el patrón de la sección anterior:
theorem rev_rev_try (xs : List α) : rev (rev xs) = xs := by
induction xs with
| nil => rfl
| cons x xs ih => simp [rev, ih]Deberías ver: Lean dice que queda un objetivo sin demostrar:
unsolved goals
case cons
α : Type u_1
x : α
xs : List α
ih : rev (rev xs) = xs
⊢ rev (rev xs ++ [x]) = x :: xsNo cambies de estrategia tan rápido; lee este objetivo. A la izquierda está rev (rev xs ++ [x]), una inversión sobre una "lista concatenada". ih dice rev (rev xs), con un ++ [x] de más en medio, así que no se puede usar.
Falta un conocimiento: ¿cuál es el resultado de invertir una concatenación?
- Veo
unsolved goalsy puedo señalar en qué se diferencia el objetivo deih
Paso 3: demostrar primero un ayudante
Piensa en un ejemplo concreto: concatenar [1, 2] y [3, 4] y luego invertir da [4, 3, 2, 1], es decir, "la inversión de la segunda mitad" seguida de "la inversión de la primera mitad". Escríbelo como teorema, de nuevo por inducción:
theorem rev_append (xs ys : List α) : rev (xs ++ ys) = rev ys ++ rev xs := by
induction xs with
| nil =>
simp [rev]
| cons x xs ih =>
simp [rev, ih]A estos teoremas pequeños que se demuestran antes para probar el teorema principal se les llama lemas.
rev_appendpasa
Paso 4: terminar el teorema principal
Entrega el lema a simp:
theorem rev_rev (xs : List α) : rev (rev xs) = xs := by
induction xs with
| nil =>
rfl
| cons x xs ih =>
simp [rev, rev_append, ih]Deberías ver: no hay errores.
Con rev_append, el objetivo atascado rev (rev xs ++ [x]) se reescribe como rev [x] ++ rev (rev xs); en ese momento ih ya se puede usar, y el simp restante lo calcula solo.
rev_revpasa
Pon a prueba tus conocimientosLa demostración se atasca, Lean muestra unsolved goals. ¿Cuál es el mejor siguiente paso?
Punto de control
- Puedo escribir las dos ramas de la inducción sobre listas:
nilycons x xs ih - Puedo explicar por qué el primer intento se atasca
- Sé qué es un lema y cómo se ocurrió el lema de esta sección
- Tanto
rev_appendcomorev_revpasan
¿No funcionó?
**rev_rev da un error de que no reconoce rev_append. ** El lema debe escribirse antes del teorema que lo usa. Lean lee el archivo de arriba abajo.
**Después de simp sigue quedando un objetivo. ** Compara con el código de arriba y mira si en los corchetes falta rev_append o ih.
Siguiente sección
Ya sabes verificar una función. La última sección usa los mismos tres pasos —definir, atascarse y buscar un lema, inducción— para demostrar que un mini compilador es correcto.