Razonamiento mecanizado en álgebra homológica

• Autores: Jesús María Aransay Azofra
• Directores de la Tesis: Clemens Ballarin (dir. tes.) , Julio Rubio García (dir. tes.)
• Lectura: En la Universidad de La Rioja ( España ) en 2006
• Idioma: español
• ISBN: 0-542-60141-9
• Número de páginas: 208
• Tribunal Calificador de la Tesis: Eladio Domínguez Murillo (presid.) , Laureano Lambán Pardo (secret.) , Renaud Rioboo (voc.) , Luis Español González (voc.) , Francis Sergeraert (voc.)
• MSC2000 :
  • Lógica matemática y fundamentos
    • Lógica general
      • Mecanización de pruebas y operaciones lógicas
      • Lógica en informática
  • Teoría de categorías Álgebra homológica
    • Cálculo por máquinas y programas (no la teoría de la computación o programación)
  • Ciencias de la computación
    • Inteligencia artificial
      • Prueba del teorema (deducción, resolución, etc.)
• Enlaces
  • Tesis en acceso abierto en: Dialnet
• Resumen
  • español

    En la tesis se aborda el problema de obtener una versión certificada de un resultado fundamental en Álgebra Homológica, conocido como "Lema de Perturbación Básico". Dicho resultado es una pieza central del sistema "Kenzo", software dedicado al cálculo simbólico en Álgebra Homológica. Para tal fin, se utiliza el asistente de demostración "Isabelle". Las principales motivaciones de nuestro trabajo consisten en aumentar nuestro conocimiento sobre la naturaleza algorítmica de dicho resultado matemático, así como evaluar las distintas posibilidades que ofrece Isabelle para demostrar teoremas en Álgebra Homológica.

    El contenido de la tesis está dividido en cinco capítulos. En el primero se realiza una breve introducción a las herramientas de trabajo utilizadas. En particular, se presentan definiciones de estructuras algebraicas y resultados previos necesarios para enunciar el Lema de Perturbación; también se aporta información relevante para nuestro trabajo sobre la codificación de estructuras algebraicas en Kenzo e Isabelle. En el segundo capítulo se enuncia el Lema de Perturbación Básico y se da una demostración formal del mismo, basada en una demostración de F. Sergeraert. El tercer capítulo contiene resultados que tratan de la modelización, especificación y verificación de enunciados matemáticos en el demostrador de teoremas Isabelle. Más concretamente, cuatro representaciones distintas de los objetos matemáticos necesarios en las demostraciones son presentadas y analizadas desde distintos puntos de vista, que abarcan desde la especificación formal hasta la automatización de resultados. Una de estas representaciones, basada en el sistema modular de Isabelle, es escogida por su expresividad, grado de automatización, legibilidad en los enunciados y facilidad de extensión a nuevos problemas. Además, la adecuación de esta representación es mostrada por medio de su aplicación a diversos ejemplos. En el cuarto capítulo se hace una propuesta de extracción de programas certificados usando Isabelle. El interés de esta propuesta es doble: en primer lugar, su originalidad, ya que evita restringir las demostraciones matemáticas a lógicas constructivas. En segundo lugar, la aplicabilidad al tipo de enunciados que hemos abordado, que la hace especialmente atractiva para los algoritmos y enunciados en los que se basa Kenzo. En el quinto capítulo se presentan las conclusiones y las líneas de trabajo futuro.

    Nota: la memoria está redactada en inglés. También contiene un resumen en castellano al final de la misma.

  • English

    We face the problem of obtaining a certified version of a crucial algorithm in the field of Homological Algebra, known as "Perturbation Lemma". This lemma is intensively used in the software system "Kenzo", devoted to symbolic computation in Homological Algebra. To this end, we use the proof assistant "Isabelle". Our main motivations are to increase the knowledge in the algorithmic nature of this mathematical result, as well as to evaluate different possibilities offered by Isabelle in order to prove theorems in Homological Algebra.

    The memoir is divided into five chapters. In the first one, an introduction to some tools in Homological Algebra, Symbolic Computation and Theorem Proving is given. More concretely, some definitions of algebraic structures and results needed to state the Perturbation Lemma are given; relevant information for our work about encoding algebraic structures in Kenzo and Isabelle is also presented. In the second chapter the Perturbation Lemma is stated, as well as a formal proof of it, based on a proof by F. Sergeraert. The third chapter contains results about modeling, formal specification and verification of mathematical results in the theorem prover Isabelle. Four different approaches to produce formal proofs of results in Homological Algebra are proposed and also analysed from different points of view, ranging from the formal specification of each of them, to the automation of proofs obtained. One of the approaches, based on the modular system of Isabelle, is chosen and shown to be appropriate due to its expresiveness, degree of automation, readability and extensibility to new problems, by means of illustrative examples. In the fourth chapter a technique for obtaining certified programs using Isabelle is introduced. The relevance of this technique is twofold: firstly, its originality, as far as it avoids restricting proofs to a constructive logic; secondly, the feasability of applying it to the kind of mathematical statements we deal with. The fifth chapter contains the conclusions and explores some possibilities for further work.

    Note: the dissertation has been written in English; it also includes a resume in Spanish at the end.