Es posible resolver cualquier geometría Euclidiana problema con un ordenador?

Question

Por "problema", me refiero a una escuela de tipo de geometría del problema.

Si no, hay otro conjunto de axiomas que permite eso? Si sí, ¿hay algún software que haga eso?

Hice una búsqueda, pero no era capaz de encontrar un programa único que permite que. Es extraño, porque incluso si es imposible resolver cualquier problema, la mayoría de los naturales problemas deben ser resueltos.

Answer 1

Hay un método para decidir (cierto o no) en algún teorema de Euclides y sus Elementos, mediante la traducción en geometría analítica, o multivariante de polinomios sobre los reales.

De las controversias filosóficas discutido por los Griegos que inspiró a Euclides para establecer su axiomas, conceptos comunes y definiciones (como lo que es un ángulo, lo que realmente es la acción de una 'brújula'), la mayoría de ellos son de facto resuelto por cómo las operaciones y de las variables de trabajo real en 2D geometría analítica con el teorema de Pitágoras (que ha demostrado ser a prueba de potencia equivalente al quinto postulado de Euclides).

La conversión funciona de la siguiente manera:

• Un punto indefinido se administra de dos variables, una $x$ $y$ coordinar $(x_1,y_1)$. Cualquier posible distintas punto debería ser nombrado por algún otro par $(x_2,y_2)$ (una prueba de que estos dos puntos coinciden mostraría que $x_1=x_2$$y_1=y_2$).
• un círculo se define por el centro de la $(x_3,y_3)$ y la distancia $d_1$ tal que $(x-x_3)^2 + (y-y_3)^2 = d_1^2$. Si quieres un punto en ese círculo, que crear una instancia de esta ecuación con la adecuada $x$$y$.
• una línea se define por, bien, dos puntos. Sólo por señalar dos puntos, tiene una línea.
• Francamente, no estoy seguro de cómo hacer ángulos, pero mi memoria me dice que es posible "jugar" con ellos.

Así que ahora usted tiene un conjunto de ecuaciones polinómicas en muchas variables. Y todo lo que usted necesita es un procedimiento para encontrar si hay una solución (algunas conjunto de la satisfacción de los números o realmente un trivial conjunto de ecuaciones) para ellos.

Supongamos que sólo tenía puntos y líneas. Entonces todo lo que usted necesita es la eliminación Gaussiana. Pero con círculos, usted puede tener arbitrario de grado. Base de Groebner de finalización (a través del algoritmo de Buchberger a partir de mediados de los 70) es lo que usted puede utilizar. Eseentially, que es justo lo que cabría esperar (pero no se dio cuenta de que podía) en mayor grado multivariante de polinomios. En analogía con la eliminación de las columnas de una matriz, intenta eliminar a los 'máxima' términos, uno por uno. Se hace más fácil si se multiplica todo para las ecuaciones son de la forma 'a suma de los términos' = 0, donde un término es un coeficiente con un número de variables posible, ninguno) multiplicado, por ejemplo,$17x_1^3y_{41}^2d_1^{1729}$. El algoritmo supone un pedido en estos términos, y luego sigue un análogo numérica de la DPC algoritmo (casualmente o no en la de Euclides).

De manera que el algoritmo intenta " reducir tanto como sea posible (la eliminación de líderes de términos donde se puede). Si se elimina tanto hasta el punto donde se tiene una ecuación de $0=1$, entonces usted sabe que usted tiene una contradicción y, a continuación, las ecuaciones no tienen forma de ser satisfechos, por lo que los polinomios que describen el teorema son inconsistentes, por lo que el teorema de la misma no se sostiene. De lo contrario (y esta es la belleza de ella), el teorema- ¿espera.

En algún sentido se podría hacer esto a mano, para algunos muy pequeño trivial problemas (Que le permite encontrar la intersección de un círculo y la línea, por ejemplo). De todos modos, los detalles del algoritmo de hacer un procedimiento de decisión (se detiene con una respuesta de " sí " o "no").

Como un asunto práctico, usted probablemente no quiere hacer esto a mano. Base de Groebner de finalización (dependiendo de lo que considere el problema exacto) PSPACE-completo, lo más probable es exponencial (en el número de variables).

En cuanto a Tarski el resultado de que los elementales de la geometría plana es decidable, sí, que es un clásico de resultado (a partir de los años 50). El teorema es el de la teoría de los reales es decidable, que incluye el '$\lt$' relación. Esto incluye la geometría Euclidiana, y es un poco más general. Tarski del algoritmo es ingeniosa, en la que se resolvió un largo problema pendiente, pero no es particularmente eficiente. Collins' 'cilíndrica algebraica de descomposición' algoritmo también a partir de mediados de los 70) es mucho más eficiente (si usted se considera un aumento en la eficiencia de ir de una pila de exponenciales, simplemente tal vez sólo doblemente exponencial; el segundo es meramente astronómicas, la primera terriblemente). Por supuesto, es todavía menos eficiente que el algoritmo de Buchberger. Debido a los diferentes campos de estos salió de eso, no estoy seguro de que cualquier investigación que analiza cualquier comparación explícita de los dos.

Lo que la eficiencia es, sí, hay un número de teoremas demostrado mecánicamente en este estilo. Un ejemplo muy trivial es el teorema de Morley (el trisectors de los ángulos de un triángulo se reúnen en un triángulo equilátero) que Zeilberger ha dado un fichero automatizado de prueba de uso de Arce. Y Wu (Wu método mencionado, que es similar a la del algoritmo de Buchberger) y sus acólitos tienen más ampliamente demostrado conjuntos completos de los teoremas de Euclides.

Un problema interesante sería saber cómo demostrar Euclidiana utilizando los teoremas de Euclides los axiomas de como es (en lugar de traducir). Ha habido algunas investigaciones recientes, por Avigad en que. Y he oído que uno puede hacer una traducción de Euclides en álgebras de Clifford que es un poco más 'me gusta' a la original de Euclides de la metodología analítica.

(por algo inexplicable, usted puede tratar de buscar en google o wikipedia con diversos grados de éxito)

---

Así que tal vez no nos satisface por el motivo que sea. Tal vez hay otro axioma de sistemas para la que uno puede de forma nativa (que es, sintéticamente, no interpretada) tener un procedimiento de decisión (lo que significa escribir un programa de ordenador para hacerlo. Los axiomas de Hilbert son realmente una 'revisión' de Euclides; es decir, se añade intermediación y algunos otros axiomas de Euclides, incluso en su ardua escepticismo, a la izquierda. Así que considero que es esencialmente el mismo. Luego hay Tarski los axiomas. Estos son sólo ligeramente diferentes, pero todavía se traducen a la analítica de la versión. (Yo soy de la opinión de que no era una deliberada de conexión, y tal vez un intelectual coincidencia, entre estos axiomas y Tarski del procedimiento de la decisión real de campos cerrados.

---

En cuanto a los programas de ordenador, así que hay Maple o Mathematica (o casi cualquier equipo de álgebra paquete que implementa la base de Groebner de cálculo); usted todavía tiene que hacer la traducción a ti mismo en polinomios.

En el otro lado hay una serie de geometría 'editores', que permiten a 'drwa' un teorema, lo que permite arrastrar y soltar los parámetros libres como objetos, es decir, mostrando que las bisectrices de un triángulo se unen en un punto, que permite mover todos los vértices, mostrando la intersección de la apirs de bisectrices todos se encuentran en el mismo punto. Algunos de estos le permitirá a usted para "probar" su construcción (que algunos puntos siempre coinciden, por ejemplo (Aparejador s Sketchpad?). Que yo sepa, estas "pruebas" no son simbólicos (como GB de cálculo), sino más bien numéricos (observe que la diferencia entre los valores calculados siempre es menos de lo que algunos muy pequeños epsilon).

Answer 2

Creo que es un teorema de Tarski que los elementales de la geometría plana es decidable.

Answer 3

Usted puede expresar el problema en el uso de coordenadas. Usted puede entonces utilizar la base de Gröbner técnicas para tratar de demostrar que la expresión que representa la conclusión es en el ideal generado por las expresiones que representan las hipótesis. Véase también el de Wu método.

Answer 4

Solo quiero comentar un aspecto de Mitch excelente respuesta (arriba).

Él escribió: "base de Groebner de finalización (a través del algoritmo de Buchberger a partir de mediados de los 70) es lo que usted puede utilizar. "

Como un asunto práctico, bases de Groebner no suelen trabajar en problemas geométricos. El Dixon resultante es mucho más eficaz. (Estoy hablando de la solución simbólica.)

Muchos ejemplos se pueden encontrar en mi sitio web. Por ejemplo, el documento sobre los problemas de Apolonio en

http://fordham.academia.edu/RobertLewis/Papers/82784/Apollonius_Problems_in_Biochemistry

Answer 5

Que yo sepa no hay ninguna herramienta práctica que proporcionan automáticamente un legibles pruebas de la misma clase de la escuela secundaria de pruebas para muchos de los teoremas de la geometría.

Como el Mitch señaló que hay métodos algebraicos tales como bases de Grobner y Wu método, pero no proporcionan legible de las pruebas. Se han implementado y están disponibles en el software, tales como: opengeoprover (una implementación de código abierto en java), Predrag Janicic del gclc, geother por Dong Ming Wang (arce implementación de Wu del método)... Algunos provers también están disponibles en GeoGebra 5.

También hay un método que produce pruebas que a veces puede ser considerado legible: El área de método por Chou, Gao y Zhang. Este método está implementado en abierto-geo-armario y lo he implementado en Coq.

También hay un viejo papel por Gelertner que describe un enfoque que intenta imitar a los humanos de las pruebas (pero que yo sepa este método no es muy eficiente): http://aitopics.org/sites/default/files/classic/Feigenbaum_Feldman/Computers_And_Thought-Part_1_Geometry.pdf