Hacer la prueba como asistentes Coq realmente necesario para realizar los cálculos para demostrar que n <= m, o es que hay un más óptimo algoritmo?

Question

Por ejemplo, tratando de demostrar que 100,000 <= 1,000,000. Pero Coq tiene un desbordamiento de la pila, lo que significa que es en realidad tratando de realizar el 100k cálculos.

Coq < Eval compute in le_lt_dec 100000 1000000.
Warning: Stack overflow or segmentation fault happens when working with large
numbers in nat (observed threshold may vary from 5000 to 70000 depending on
your system limits and on the command executed).
Stack overflow.

¿Significa esto que no es posible demostrar que en Coq? Parece extraño que usted realmente necesita para ejecutar a través de cada comparación para probar esto, porque los matemáticos en el pasado nunca hizo tales cosas, ya que habría tomado demasiado tiempo y esfuerzo.

Si lo intentas en números más pequeños, se ve que en realidad no intentar comparar cada uno:

Coq < Eval compute in le_lt_dec 42 42.
     = left
         (Gt.gt_le_S 41 42
            (Lt.le_lt_n_Sm 41 41
               (Gt.gt_le_S 40 41
                  (Lt.le_lt_n_Sm 40 40
                     (Gt.gt_le_S 39 40
                        (Lt.le_lt_n_Sm 39 39
                           (Gt.gt_le_S 38 39
                              (Lt.le_lt_n_Sm 38 38
                                 (Gt.gt_le_S 37 38
                                    (Lt.le_lt_n_Sm 37 37
                                       (Gt.gt_le_S 36 37
                                          (Lt.le_lt_n_Sm 36 36
                                             (Gt.gt_le_S 35 36
                                                (Lt.le_lt_n_Sm 35 35
                                                  (Gt.gt_le_S 34 35
                                                  (Lt.le_lt_n_Sm 34 34
                                                  (Gt.gt_le_S 33 34
                                                  (Lt.le_lt_n_Sm 33 33
                                                  (Gt.gt_le_S 32 33
                                                  (Lt.le_lt_n_Sm 32 32
                                                  (Gt.gt_le_S 31 32
                                                  (Lt.le_lt_n_Sm 31 31
                                                  (Gt.gt_le_S 30 31 (..))))))))))))))))))))))))
     : {42 <= 42} + {42 < 42}

Hacer la prueba asistentes realmente necesario para realizar estos cálculos, para poder ser comprobada la correcta? Parece que debe haber un acceso directo, y conocen sólo a partir de la estructura de la prueba de que 42 <= 42 o 100,000 <= 1,000,000. Hay un camino para que se vea que es cierto que sin llegar a la realización de los cálculos?

También, soy nuevo en Coq, por lo que podría estar haciendo algo mal. Tal vez hay una manera en Coq probar sin usar Eval compute?

En general, estoy tratando de conseguir una mejor comprensión de cómo la mecánica de probar este tipo de cosas en la práctica. Si crea una proposición en le Coq, que es sólo una "proposición de que hay un $n$ menos que o igual a $m$". Pero para obtener un valor booleano true/false que $100,000 <= 1,000,000$, se dijo que tengo que probar, primero, la decidability de le mirando le_lt_dec. Así que aquí es donde estoy en el proceso de tratar de aprender si que ayuda.

Answer 1

Tenga en cuenta que, en CoQ, 100000 es en realidad la abreviatura sintáctica $S S S S S \ldots 0$. No es razonable que las pruebas de reclamaciones que involucren grandes términos mismos deben ser bastante grandes. Cuando un matemático se ve en una reclamación como $1000 \leq 1000000$ y dice que "obviamente", que están aprovechando el hecho de que se escribió la reclamación en notación decimal. Si quieres hacer algo similar en CoQ, usted podría tratar de demostrar, por ejemplo, $10 * 10 * 10 \leq 10 * 10 * 10 * 10 * 10$. Usted puede probar tales afirmaciones usando lemas como forall n, n > 0 -> 10 * n >= n.

Usted todavía tiene que ser un poco cuidadoso, sin embargo, ya que la forma normal de, por ejemplo, $10 * 10 * 10 * 10$ es bastante grande, aunque el término en sí no lo es.

Si desea eficiente de los procedimientos de decisión para expresiones con números tan grandes, que podrían, entre otras cosas, hacer un nuevo tipo inductivo correspondiente a las expresiones aritméticas, código de procedimientos de toma de decisiones en la que, luego de demostrar su veracidad.