Asistente de prueba para escribir matemáticas

12

Me gustaría escribir pruebas matemáticas con algún asistente de prueba. Todo se escribirá utilizando la lógica de primer orden (con igualdad) y la deducción natural. El fondo es la teoría de conjuntos (ZF). Por ejemplo, ¿cómo podría escribir la siguiente prueba?

Axioma: $\forall x\forall y(x=y\leftrightarrow\forall z(z\in x\leftrightarrow z\in y))$

Teorema: $\forall x\forall y(\forall z(z\notin x)\land\forall z(z\notin y)\rightarrow x=y)$

Es decir, el conjunto vacío es único.

Es trivial para mí lograr eso usando papel y un bolígrafo, pero lo que realmente necesito es un software que me ayude a verificar la corrección de la prueba.

Gracias.

lo.logic software proof-assistants Kaveh
fuente

11

Primero debe seleccionar un asistente de prueba. Coq es lo que uso, pero hay muchos otros . Algunos de estos se basan en la lógica de primer orden, por lo que serán más adecuados para sus necesidades. Entonces debes comprometerte a aprender el asistente de pruebas. En unos pocos días, debería poder codificar teoremas simples, como el anterior, y probarlos. No esperes que haremos esto por ti. No aprenderás nada de esa manera.

Dave Clarke

55

Si le interesa la teoría de conjuntos, no la teoría de tipos, entonces Isabelle es probablemente el sistema más directo. Coq parecerá extraño y confuso.

Mark Reitblatt

2

Creo que el axioma que escribiste no es la lógica de primer orden, sino la lógica de segundo orden. Esto se debe a que en el primero, las variables solo varían sobre los individuos, mientras que en el segundo, las variables pueden variar sobre los individuos y los conjuntos. Aparentemente, en el axioma dado, e son conjuntos mientras que es un individuo.

x

$x$

y

$y$

z

$z$

MS Dousti

99

@Sadeq: ¿En ZF no se establecen los elementos básicos del universo de todos modos? Por lo tanto, debería poder decir cosas como "para todos los conjuntos" en la lógica de primer orden, que es lo que se está haciendo en ese axioma.

Robin Kothari

99

@Sadeq, lo que Robin dijo es correcto, es una teoría de primer orden y el axioma escrito en la pregunta también es de primer orden. En todo es solo un conjunto, no hay nada como individuos frente a conjuntos. (Como nota al margen, no es necesario moverse a objetos de segundo orden o superiores para hablar sobre diferentes tipos de variables, solo se necesitan diferentes tipos, la lógica de segundo y superior orden es bastante diferente de las lógicas de muchos tipos).

Z F

$\mathbf{ZF}$

Z F

$\mathbf{ZF}$

Kaveh

13

Tanto Coq como Isabelle pueden hacer esto.

[Coq] Aquí hay un artículo que discute cómo codificar ZFC en CIC, en el que se basa Coq.

Benjamin Werner: Conjuntos en tipos, Tipos en conjuntos (1997). http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.1709

[Isabelle] Hay una biblioteca para ZF.

http://www.cl.cam.ac.uk/research/hvg/Isabelle/dist/library/ZF/index.html

yhirai
fuente

3

Si bien este documento es bastante bueno, creo que sería más pragmático agregar especies (variables de tipo) y axiomas para codificar directamente la teoría axiomática de ZF, luego hacer las pruebas por apelación directa a estos axiomas. La codificación es más para mostrar que las teorías están relacionadas en fuerza expresiva.

cody

2

Sin embargo, debo agregar que hay una implementación de estas ideas, por Bruno Barras: lix.polytechnique.fr/~barras/proofs/sets/index.html

cody

9

Movido del comentario por sugerencia de Kaveh

Primero debe seleccionar un asistente de prueba. Coq es lo que uso, pero hay muchos otros . Coq se basa en la lógica de orden superior (el llamado cálculo de construcciones inductivas). Otros asistentes de prueba se basan en la lógica de primer orden, por lo que pueden ser más adecuados para sus necesidades (modulo de los comentarios anteriores).

Entonces debes comprometerte a aprender el asistente de pruebas. El documento vinculado es un tutorial para despegar con Coq. Convertirse en un experto en Coq requiere años de dedicación y práctica, pero los teoremas simples se pueden probar en una tarde. La clave para aprender Coq o cualquier otro asistente de pruebas es hacer pruebas, como las que se encuentran en el documento vinculado. Solo leer el documento ayudará muy poco, porque toda la experiencia de interactuar con el asistente de pruebas no se puede transmitir bien en papel.

En unos pocos días, debería poder codificar teoremas simples, como el anterior, y probarlos. No esperes que haremos esto por ti. No aprenderás nada de esa manera.

Cuando logre probar estos teoremas, no dude en publicar sus respuestas aquí y tal vez dejar algunos comentarios sobre sus experiencias.

¿Estás preparado para el reto?

Dave Clarke
fuente

44

Coq es una opción razonable; sin embargo, si xddz5 realmente quiere trabajar en la teoría de conjuntos ZF en lugar de la teoría de tipos, entonces quizás Mizar sea más adecuado.

Timothy Chow

8

Hay muchos artículos de matemáticas escritos con el asistente de pruebas Mizar: http://mizar.org/fm/

Radu GRIGore
fuente

3

¿Cómo es el soporte de herramientas para Mizar?

Dave Clarke

No lo usé.

Radu GRIGore

5

Dave Clarke sugiere Coq, pero en realidad Isabelle parece una idea mucho mejor, ya que tiene una biblioteca A para ZF . Isabelle también es muy madura e incluye una amplia variedad de tácticas y extensiones.

Personalmente no he usado Mizar, pero también puede ser bueno.

Liam O'Connor
fuente

2

¿Cómo podría escribir la siguiente prueba?

En Isabelle / ZF puedes escribir algo como esto

theory csthquestion imports Main

begin

theorem empty_unique:
shows "\<forall> x.\<forall>y.(\<forall>z. (z\<notin>x)) \<and> (\<forall>z.(z\<notin>y)) \<longrightarrow> x=y"
    by auto

end

Como puede ver, Isabelle lo prueba automáticamente. Por supuesto, puede escribir una prueba más detallada si realmente lo desea.

fuente

2

Este mismo teorema es un ejemplo trabajado (ver Ejemplo 11) en el tutorial incluido con mi software DC Proof 2.0. Descárguelo gratuitamente en mi sitio web http://www.dcproof.com

Dan Christensen
fuente

1

Esta es una pequeña venta para este sitio. ¿Podría presentar alguna información de manera imparcial para decir de qué manera su software se adapta bien al problema? ¿Quizás se está llevando a cabo un enlace a un video o una captura de pantalla de esta derivación?

Charles Stewart

1

Aquí está la prueba: dcproof.com/EmptySetUnique.htm Hay un video en mi sitio web que muestra cómo funciona el sistema.

Dan Christensen

Asistente de prueba para escribir matemáticas

Respuestas: