El método de decisión de Tarski para el Álgebra y la Geometría elementales

Traballo Fin de Grao El método de decisión de Tarski para el Álgebra y la Geometría elementales Rosana Sobrido Codesido 2019/2020 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA GRAO DE MATEMÁTICAS Traballo Fin de Grao El método de decisión de Tarski para el Álgebra y la Geometría elementales Rosana Sobrido Codesido Julio, 2020 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA Trabajo propuesto Área de Coñecemento: Álgebra Título: El método de decisión de Tarski para el Álgebra y la Geometría elementales Breve descrición do contido El logista Alfred Tarski en los años 30 del siglo XX, y restringiéndose a lo que él llama la geometría elemental, probó la existencia de un procedimiento que, aplicado a cualquier fórmula de la teoría formal puede decir, en un número finito de pasos, si es o no un teorema. Además Tarski desenvuelve un sistema formal para la geometría euclidiana. Su algoritmo funciona también en la teoría formal del Álgebra elemental. Este admite eliminación de cuantificadores, resultando en un sistema completo, decidible y que admite una demostración constructiva de su consistencia. Recomendacións Es conveniente usar la bibliografía sugerida. Outras observacións iii Índice general Resumen vii Introducción ix 1. Contexto histórico 1 2. Álgebra elemental 5 3. El método de decisión 13 3.1. PrimeraParte................................... 13 3.2. SegundaParte .................................. 35 4. Extensión a otros ámbitos: Geometría Elemental 37 4.1. El sistema de Tarski para la Geometría Elemental . . . . . . . . . . . . . . . 37 4.2. Aplicación del Método de Decisión a la Geometría Elemental . . . . . . . . 41 4.3. Ampliación de las teorías . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Apéndice 43 Bibliografía 47 v Resumen El trabajo se enmarca en el campo de la Teoría de Modelos dentro de la lógica matemática. Con este contexto se estudiarán las propiedades de las teorías del álgebra y la geometría elementales. Particularmente se realiza un estudio sintáctico presentando el método de decisión proporcionado por el matemático y filósofo Alfred Tarski que permite conocer qué resultados son ciertos dentro de una de estas dos teorías y, en consecuencia, particularizar los teoremas de las mismas. Esta es una idea muy interesante ya que este algoritmo permite resolver cuestiones complicadas de forma mecánica sin que sean necesarios grandes conocimientos de la materia. En consecuencia, al poder ser aplicado, quedará probado que ambas teorías son decidibles. Se hará uso de conceptos metamatemáticos y de lógica de predicados junto con los puramente algebraicos y, además de la propia definición del método se hará un estudio de los fundamentos del álgebra y la geometría elementales en el sentido de Tarski. Abstract The work is framed in the field of the Model Theory inside the Mathematical logic. In this context we will study the properties of Elementary Algebra and Geometry. In particular a syntactic study is carried out presenting the decision method provided by the mathematician and philosopher Alfred Tarski that allows to know which results are true within one of these two theories and, consequently, to particularize the theorems of them. This is a very interesting idea since this algorithm allows to solve complicated questions in a mechanical way without being necessary to have a great knowledge of the matter. Consequently, if it can be applied, it will be proved that both theories are decidable. It will make use of metamathematical concepts and logic of predicates along with the purely algebraic ones and, in addition to the definition of the method we will make a study of the fundamentals of Elementary Algebra and Geometry in the sense of Tarski. vii 2CAPÍTULO 1. CONTEXTO HISTÓRICO aspectos de una teoría matemática, no son teoremas en la definición habitual del concepto. Después de Hilbert otros matemáticos se interesarían por el problema de decisión, uno de ellos es Tarski. El papel del matemático polaco resulta esencial puesto que transformó el concepto de la metamatemática al introducir métodos semánticos3. Sinaceur (1940) afirmó sobre la relación de Tarski con este ámbito: Desde la perspectiva de Tarski, la metamatemática es similar a cualquier disciplina matemática. No solo sus conceptos y resultados pueden ser matematizados, si no que pueden ser integrados dentro de las matemáticas (...) Tarski destruyó la línea entre la matemática y la metamatemática. Se opuso a restringir el papel de las metamatemáticas a los fundamentos de las matemáticas. [2] En las siguientes páginas presentaremos el método de decisión proporcionado por Alfred Tarski que nos permitirá dar respuesta al problema de decisión en el ámbito del álgebra y la geometría elementales. Este fue un trabajo no exento de dificultades teóricas e históricas. Una pista de la problemática histórica viene dado por el nombre original de Tarski: Alfred Teitelbaum, de origen judío, además de su nacimiento datado en 1901 en Varsobia, pocos años antes del estallido de las Guerras Mundiales. Podemos extraer un breve sumario de su vida siguiendo [13], en su juventud Alfred cambia su nombre a la versión que conocemos hoy en día (Tarski) y se convierte al catolicismo siguiendo ideales nacionalistas polacos y tratando de esquivar el antisemitismo de la época. La vida de Tarski se ve dificultada por las guerras, esta situación incluso le llevará a interrumpir sus estudios en varias ocasiones para luchar por sus ideales y es que, antes de comenzar la Universidad Tarski se unió durante un tiempo al ejército polaco y también en una segunda ocasión durante sus estudios universitarios. Este ambiente hostil de guerra y ocupación no impide que Alfred sea un brillante estudiante y lleve a cabo multitud de investigaciones. Siendo muy joven, en 1925 nuestro hombre consigue no uno, si no dos trabajos como profesor en matemáticas y comienza a ser conocido internacionalmente. En sus lecturas universitarias entre 1926 y 1928 afloran algunos resultados parciales que darán lugar al método de decisión. En sus inicios las condiciones fueron más restrictivas para la existencia del mismo, así en sus estudios iniciales la única operación considerada en el ámbito del álgebra era la suma y la geometría solo contemplaba la línea recta. confirmamos que existe un método para determinar si cualquier fórmula pertenece al conjunto de verdades de la misma. En el trabajo este método es el método de decisión. 3El método semántico, frente al sintáctico trata de analizar la concepción de verdad en lugar de limitarse a pruebas y derivaciones. 3 Según las palabras del propio Tarski en [5] los primeros resultados referidos a este trabajo de una forma casi similar a la actual se obtienen en los años treinta y su elaboración se alarga nueve años. La publicación estaba prevista para 1939 pero debido al comienzo de la Segunda Guerra Mundial tuvo que ser aplazada. El primer momento del que se tienen referencias del trabajo es en 1931 en la publicación Sur les ensembles définissables de nombres réels , Fundamenta Mathematicae 17.1, (1931), 210–239 pero parcialmente y sin demostrar sus hipótesis. Siguiendo el libro [11] podemos analizar la biografía de Tarski en esos años, tardó en aceptar el hecho de que era necesario emigrar de su país debido al presente conflicto y la persecución judía que estaba comenzando a surgir. La guerra afecta a todos pero, los orígenes judíos de Tarski podían llevarlo a los guetos impuestos por los alemanes en Varsobia o a una sentencia de muerte. El matemático había recibido una invitación oficial para asistir a un congreso en Cambridge, Massachusetts, pero acercándose la fecha aún no había dado una respuesta. El profesor de Harvard y logista Willard Van Orman Quine repitió la invitación y pidió a Tarski que considerara la emigración, idea que Tarski acepta en el último minuto. En un principio la estancia en Estados Unidos sería pasajera pero terminará por quedarse allí el resto de su vida, al igual que su mujer e hijas que tras sobrevivir a la guerra se unirán a él en América. Volviendo a la narración que realiza el propio Tarski sobre los hechos, una vez en Estados Unidos le comienzan a surgir dudas sobre la calidad de su trabajo y trata de reescribirlo, lo que alarga aún más su publicación. Los duros momentos de la guerra y la posguerra llevan a que el trabajo se posponga durante años hasta que a principios de 1948 la corporación RAND, Santa Mónica, California se interesa por el trabajo y se ofrece a publicarlo. Tras leves modificaciones, en las que el propio Alfred toma parte, se publica A decision Method for Elementary Algebra and Geometry. No todo el entorno de Tarski tuvo la misma suerte, sus padres, su hermano y la familia de este último fueron asesinados por los alemanes así como muchos matemáticos compañeros que no pudieron huir de la guerra. 4CAPÍTULO 1. CONTEXTO HISTÓRICO Capítulo 2 Álgebra elemental El marco donde es aplicable el método de decisión es el álgebra elemental, en las siguientes líneas se describirá su sistema formal, además de estudiar la forma de los elementos que la componen. Esto se llevará a cabo en el ámbito de la lógica de primer orden empleando conceptos básicos1. Todos los conceptos seguirán las ideas descritas en [5]. En rasgos generales se considera elemental a la teoría que no hace uso de conceptos de teoría de conjuntos. Nuestro trabajo conlleva el estudio de las teorías del álgebra y la geometría elementales en su origen por tanto debemos emplear algunos conceptos metamatemáticos además de los clásicos símbolos matemáticos2. A continuación se presenta un esquema de los elementos que componen el álgebra elemental. En primer lugar, los elementos más básicos son las variables, que nos permitirán tomar valores de forma arbitraria. La notación empleada será x1, x2, ..., y1, y2, ..., z1, z2, ... donde los subíndices nos indican que están ordenadas y en consecuencia podemos hablar de primera variable, segunda variable, hasta n-ésima variable. Las variables se interpretan como números reales arbitrarios sin que existan las distinciones entre los conceptos clásicos de entero, racional etc. pues en caso contrario pasaríamos al caso en el que no existe método de decisión probado por Gödel. Definición 2.1. Una operación n-aria en el conjunto A es una función t:An→A. Siendo nel número de aridad, este viene dado por la cantidad de elementos que se 1Para una caracterización más lógica ver Apéndice 1. 2Los símbolos y expresiones matemáticos se denotan de la forma habitual y podemos considerar que son constantes metamatemáticas. Por otro lado, en la parte metamatemática α, β, γ representarán términos arbitrarios, las letras ξ, η, λ, µ, ν variables arbitrarias y finalmente θ, φ, ψ fórmulas y sentencias arbitrarias. Para una discusión más amplia sobre estos conceptos ver [4](Sección 2, pp.279 ff., en particular p.289) y [3](p.100 en particular). 5 6CAPÍTULO 2. ÁLGEBRA ELEMENTAL necesitan para llevar a cabo la operación. [10] A continuación tenemos las constantes algebraicas que son los símbolos 1,0,−1y por otro lado los signos de operación suma y multiplicación +,·. Ambos son de aridad 2. Solamente mencionamos dos signos de operación porque queremos simplificar el modelo lo máximo posible, otros pueden surgir de diversas combinaciones, como es el caso de la resta pues decir α−βes lo mismo que [α+ (−1·β)] . Juntando variables y constantes mediante signos de operación obtenemos los términos algebraicos como serían por ejemplo x+yo−1·x. Sin olvidar que, en algunos casos, será importante el uso de signos de agrupación para indicar qué operación se realiza antes que otra, Tarski emplea paréntesis, corchetes y llaves con este fin, entendiendo este último como un superparéntesis y no con nociones de teoría de conjuntos. Los términos adquieren distinto orden. Un término algebraico de primer orden es simplemente una variable o una constante. A partir de aquí por cada interacción se aumentará el orden. Si tenemos los términos αyβsiendo kel máximo orden (de una o de ambas), entonces α·βyα+β son términos algebraicos de orden k+ 1. Por ejemplo, ¿cuál sería el orden de −1·x1+x2? 1 + 1 + 1 = 3. El siguiente elemento a definir son los signos algebraicos de relación:=,≥conocidos como signo de igualdad y signo mayor que3. Definición 2.2. Una fórmula atómica es una expresión formada por términos algebraicos arbitrarios junto con los símbolos de relación. Los dos tipos de fórmulas obtenidas son las igualdades α=βy las desigualdades α > β. Podemos unir las fórmulas atómicas mediante diversos conectores para formar otras más complejas. Los conectores son, en particular operaciones. Sean θyφfórmulas atómicas, presentamos así las conectivas ¬,∧y∨. La negación ¬: Leído como “no” ¬θ. Es un operador lógico unario. La conjunción ∧: Leído como “y” θ∧φ. Es un operador lógico binario La disyunción ∨: Leído como “o” θ∨φ. Es también un operador lógico binario. Existen otras dos conectivas lógicas que pueden expresarse en función de las tres anteriores y aunque reducimos nuestro sistema a la forma más sencilla por comodidad utilizaremos 3Tratamos de presentar el sistema de la forma más simple posible, omitiremos el signo <. De hecho también podemos reducirlo más puesto que x > y ≡(Ez)[¬(z= 0) ∧(x=y+z2)]. 7 su notación particular, estos son la implicación →y la equivalencia ↔. Las entendemos como abreviaturas para expresiones que emplean las anteriores conectivas lógicas.4 5 Otro elemento lógico que debemos nombrar es el cuantificador existencial ∃, que nos permite decir que existe al menos un elemento que cumplirá lo que viene a continuación. No obstante la notación que emplearemos será la de Tarski, esta resulta Eξ para decir que existe un ξtal que. Definición 2.3. Una fórmula es una expresión construida mediante la unión de fórmulas atómicas junto con conectores y cuantificadores. Al igual que los términos las fórmulas tienen un orden asociado. Una fórmula de orden 1 es simplemente una fórmula atómica. Por cada conector que empleamos la fórmula sube un orden, es decir si θes una fórmula de orden kentonces ¬θes una fórmula de orden k+ 1 al igual que si empleamos el cuantificador (Ex)θresultando también de orden k+ 1. Aquellos que involucran dos fórmulas θyφ, siendo kel orden máximo de ambas, θ∧φy θ∨φresultan de orden k+ 1. Ahora nos interesa hablar de un tipo de variables, las variables libres que definimos en particular para cada situación. Suponemos que θyφson dos fórmulas atómicas. ξes libre en φsi y solo si ξaparece en φ. ξes libre en (Eη)θsi y solo si ηno es la misma variable que ξyξes libre en θ. ξes libre en ¬θsi y solo si φes libre en θ. ξes libre en θ∨φy en θ∧φsi y solo si ξes libre en al menos una de las fórmulas θ yφ. Definición 2.4. Una sentencia es una fórmula que no contiene variables libres. Además debemos nombrar otro importante elemento: el cuantificador universal ∀, que Tarski escribe como (Aξ)θpara decir: para todo ξque existe en θ. No obstante no constituiría un elemento principal si no que puede derivarse del cuantificador existencial. (Aξ)θ≡ ¬(Eξ)¬θ 4No debemos confundir dos conceptos similares, la equivalencia material y la equivalencia lógica. La equivalencia material es la conectiva lógica binaria que aquí se explica, denotada con el símbolo ↔y al cual se le asocia su semántica particular. Por otro lado denotaremos la equivalencia lógica por ≡o también podría ser denotada por ⇔, esta acepción está dentro del ámbito de la semántica y nos indica que ambas partes, a un lado y al otro, poseen el mismo valor de verdad. 5Ambas provienen de las conectivas básicas de la siguiente manera, θ→φ≡ ¬θ∨φentendiendo θ como el antecedente o hipótesis y φla consecuencia o conclusión de la implicación. De la misma forma θ↔φ≡(θ→φ)∧(φ→θ). 8CAPÍTULO 2. ÁLGEBRA ELEMENTAL Se leería como no existe un ξque no está en θ, dicho de otra forma todo ξestá en θ. También para el método será muy importante el uso de disyunciones y conjunciones de muchas fórmulas simultáneamente, lo denotaremos de la siguiente forma. Si las fórmulas están ordenadas en una secuencia finita, θ1, ...θn _ 1≤i≤n θi ^ 1≤i≤n θi Si se involucran más casos, aumentarán los subíndices de las fórmulas y pasará a haber dos líneas bajo el conector. Hasta este punto hemos tratado la construcción de sentencias, elemento a partir del cual emplearemos el método de decisión. Toda esta parte compondría la sintaxis del lenguaje de primer orden. A continuación nos corresponde la parte de semántica que estudia el significado o interpretación de las fórmulas, aquí entra en juego el concepto de verdad.6 7 Existen sentencias básicas que sabemos directamente si son verdaderas o falsas, para las demás se usarán unas normas establecidas, estas vienen dadas por los conectores. Sean θyφdos sentencias. ¬θes verdad si y solo si θes falsa. θ∧φes verdad si y solo si ambas sentencias son verdad. θ∨φes verdad si y solo si al menos una de ellas es verdad. θ→φes verdad en todo caso excepto que θsea verdad y φfalsa. 6Para Tarski la noción de verdad fue una cuestión muy importante, la trata de forma extendida en obras como [4] donde se proporciona una definición formal. No obstante el concepto filosófico sobre qué es la verdad no es necesario para nuestro trabajo. Usaremos la definición de verdad de forma intuitiva. 7También podemos eliminar directamente la noción de verdad del trabajo si sometemos al álgebra elemental a un proceso de axiomatización. En este contexto podemos sustituir la idea de sentencia verdadera por la de sentencia probable. Una sentencia probable es aquella que puede ser derivada de los axiomas mediante la repetición de las reglas de inferencia. Los axiomas de la teoría son los de la lógica de primer orden(Apéndice 2) y los axiomas propios de la misma que son de tipo algebraico. Estos últimos involucran los que permiten la caracterización del conjunto de números reales como un campo ordenado junto con las operaciones +y·y la relación >sin olvidar los elementos especiales 1, -1 y 0; además se añade un último axioma (Aξ1)...(Aξn)(Aη)(Aζ){[(η > ζ)∧(Eξ)((ξ=η)∧(α > 0)) ∧(Eξ)((ξ=ζ)∧(0 > α))] →(Eξ)((η > ξ)∧(ξ > ζ)∧(α= 0))} que indica que si en un punto una función, en el sentido que empleamos, es positiva y en otro negativa existe un punto intermedio en el cual la función toma el valor cero. 9 θ↔φes verdad si y sólo si ambas sentencias son verdad o ambas sentencias son falsas. Las sentencias son verdaderas o falsas mientras que las fórmulas pueden tomar diversos valores y resultarán falsas o verdaderas dependiendo de ellos. Por ejemplo 0=1es una sentencia que resulta ser falsa mientras que la fórmula x > 0es válida para ciertos valores pero falsa para otros. Definición 2.5. Sean θyφfórmulas arbitrarias y ξ1, ξ2, ..., ξnlas variables libres que aparecen en ellas. Entonces si la sentencia (Aξ1)...(Aξn)(θ↔φ)es verdad diremos que ambas fórmulas son equivalentes. Teorema 2.6. La relación de equivalencia es simétrica, reflexiva y transitiva. Demostración. Reflexiva, lógicamente si θrelacionada con φ,φestá relacionada con θpues si ocurre lo primero al ser verdad (Aξ1)...(Aξn)(θ↔φ)significa que θyφson ambas verdad o ambas mentira, de cualquiera de las dos formas (Aξ1)...(Aξn)(φ↔θ). Simétrica, toda fórmula está relacionada consigo misma puesto que θ↔θsiempre es verdad. Transitiva θrelacionada con φluego (Aξ1)...(Aξn)(θ↔φ)es verdad, así ambas θyφson verdaderas o falsas. φrelacionada con ϕluego (Aξ1)...(Aξn)(φ↔ϕ)es verdad, así ambas φyϕson verdaderas o falsas. Suponemos que θ,φyϕson verdad para todas las variables libres que están en las fórmulas luego como ambas θyϕson verdad también lo es (θ⇔ϕ)para todas las variables libres. Por contra, si suponemos que θ,φyϕson mentira para todas las variables libres que están en las fórmulas luego como ambas θyϕson mentira, (θ↔ϕ)es verdad para todas las variables libres. Teorema 2.7. Sean θ1yθ2dos fórmulas equivalentes y supongamos que la fórmula ψ2 surge de la fórmula ψ1reemplazando θ1por θ2en uno o más lugares. Entonces ψ1es equivalente a ψ2. Análogamente, ya viendo que esta definición y teoremas se verifican para fórmulas, en consecuencia podrán aplicarse a términos. 10 CAPÍTULO 2. ÁLGEBRA ELEMENTAL Definición 2.8. Sean αyβtérminos arbitrarias y ξ1, ξ2, ..., ξnlas variables que aparecen en ellas. Entonces si la sentencia (Aξ1)...(Aξn)(α=β)es verdad diremos que ambos términos son equivalentes. Teorema 2.9. La relación de equivalencia de términos es simétrica, reflexiva y transitiva. Teorema 2.10. Sean α1yα2dos términos equivalentes y supongamos que el término β2surge del término β1reemplazando α1por α2en uno o más lugares. Entonces β1es equivalente a β2. Teorema 2.11. Sean α1yα2dos términos equivalentes y supongamos que la fórmulaψ2 surge la fórmula ψ1reemplazando α1por α2en uno o más lugares. Entonces ψ1es equivalente a ψ2. Finalmente presentamos las últimas nociones algebraicas básicas que necesitaremos para establecer el método de decisión.8 Definición 2.12. Sean α0, α1, ..., αntérminos que no dependen de x. Se dice que α0+α1·ξ+... +αn·ξn es un polinomio en ξde grado ncon coeficientes α0, ..., αnsiendo αnel coeficiente principal. El grado viene dado por el coeficiente principal, este no tiene que ser necesariamente distinto de cero, (1 −1) ·x2+xes un polinomio de grado dos. Definición 2.13. Sean αyβdos polinomios en ξde grados mynrespectivamente. α≡α0+α1·ξ+... +αm·ξm β≡β0+β1·ξ+... +βn·ξn Sean r=min{m, n}ys=max{m, n}yγi≡αi+βicon i≤r. Si m < n γi≡βicon r < i ≤s. Si m > n γi≡αicon r < i ≤s. Es decir, para los índices superiores al mínimo se toma como valor el correspondiente con el polinomio de mayor grado. Definimos la suma de polinomios +ξ: α+ξβ≡γ0+γ1·ξ+... +γs·ξs 8La definición común de polinomio incluye la teoría de conjuntos, p∈ P(x), por tanto debemos de dar una versión adaptada a nuestro contexto “elemental” incluyendo también el procedimiento para las operaciones entre polinomios. 11 En resumen, la suma de polinomios resulta en otro polinomio cuyos coeficientes son la suma de los otros dos. Definición 2.14. Sea αun polinomio en ξde grado m. Se dice que Rdξ(α)≡a0+a1·ξ+... +am−1·ξm−1 es el reductum de α. Si el polinomio es de grado nulo, es decir no depende de ξ, el reductum será el polinomio nulo Rdξ(α)≡0. Podemos decir que Rd0 ξ(α)≡α Rd1 ξ(α)≡a0+a1·ξ+... +am−1·ξm−1 Rd2 ξ(α)≡a0+a1·ξ+... +am−2·ξm−2 Por tanto Rdk+1 ξ(α)≡Rdξ[Rdk ξ(α)] Efectivamente observamos que el reductum de un polinomio es otro polinomio con los mismos coeficientes pero eliminando el principal, de forma que tendrá un grado menor. Definición 2.15. Sean αyβdos polinomios en ξde grados mynrespectivamente. α≡α0+α1·ξ+... +αm·ξm β≡β0+β1·ξ+... +βn·ξn Se define la operación poducto de polinomios ·ξ: Si m= 0 α·ξβ≡(α·β0)+(α·β1)·ξ+... + (α·βn)·ξn Así se obtiene el polinomio nulo, ojo no podríamos decir que α·ξβ≡0porque el resultado de la operación no daría lugar a un polinomio si no al valor cero. Si m > 0 α·ξβ≡[Rdξ(α)·ξβ] +ξ(γ0+γ1·ξ+... +γm+n·ξm+n) Siendo γi≡0parai<m γm≡αm·β0 γm+1 ≡αm·β1 . . . γm+n≡αm·βn 18 CAPÍTULO 3. EL MÉTODO DE DECISIÓN descartados por hipótesis). Luego nos encontramos en el punto 2 de la definición 3.5 viendo que efectivamente es una disyunción de conjunciones de fórmulas atómicas. La equivalencia se sigue de la ley distributiva del cálculo proposicional. Teorema 3.7. Sea φuna fórmula arbitraria sin cuantificadores y ξuna variable cualquiera. Entonces QPξ(φ)4es una disyunción de conjunciones de fórmulas atómicas donde cada una de ellas tiene un polinomio en ξen el lado izquierdo y 0 en el lado derecho. Además QPξ(φ) es equivalente a φ. Demostración. Efectivamente QPξ(φ)es equivalente a φsiguiendo los Teoremas 3.4 y 3.6. QPξ(φ)≡Q(φ)≡φ. Además su forma también es trivial siguiendo la definición de ambos operadores. Definición 3.8. Sea αun polinomio en ξ, definimos la derivada con respecto a ξ Dξ(α) como: 1. Si es de grado n > 0, es decir α≡α0+α1·ξ+... +αn·ξn: Dξ(α)≡α1+ (2 ·α2)·ξ+... + (n·αn)·ξn−1 2. Si es de grado 0: Dξ(α)≡0 Lógicamente la derivada de un polinomio es un polinomio pues sigue teniendo el esquema de la definición 2.12, solo que de un grado menor. Este concepto de derivada puede también extenderse a términos arbitrarios que no sean polinomios en ξutilizando la primera transformación, así Dξ(α)≡DξPξ(α) Definición 3.9. Si αes cualquier término y ξuna variable arbitraria. Definimos la derivada de orden k: D0 ξ(α)≡α Dk+1 ξ(α)≡Dξ[Dk ξ(α)] Como estas son la derivada de la derivada sucesivamente y ya vimos que la derivada de un polinomio es un polinomio todas las derivadas de orden superior serán polinomios. 4Abreviamos la notación en lugar de escribir Q[Pξ(φ)]. 3.1. PRIMERA PARTE 19 Definición 3.10. Sea αun polinomio en ξyn∈N. Definimos el operador M de la siguiente manera: Mn ξ(α)≡ {(^ 1≤i≤n [Di−1 ξ(α) = 0]) ∧ ¬[Dn ξ(α) = 0]} M0 ξ(α)≡ ¬(α= 0) Se leerá como “el número ξes de orden nen el polinomio α”. Este operador nos indica las raíces del polinomio, traducimos la parte formal de la derecha: dos condiciones que deben darse simultáneamente, la primera que el valor ξes una raíz para el propio polinomio y todas sus derivadas hasta el orden n−1y la segunda que el valor ξno es raíz para la derivada n-ésima. Luego el significado de Mn ξ(p)es que ξ es una raíz del polinomio de orden ny cuando el valor de nes nulo significará que ξno es raíz de α. Definición 3.11. Sea ξuna variable y φuna fórmula arbitraria, n un número entero positivo y η1, ..., ηnlas primeras n-variables que no aparecen en φy que son diferentes de ξ. Definimos el cuantificador existencial numérico: (E0ξ)φ≡(Aξ)¬φ (E nξ)φ≡ {(Eη1)...(Eηn)( ^ 1≤i<j≤n ¬(ηi=ηj)∧(Aξ)[φ↔_ 1≤i≤n (ηi=ξ)])} Lo que quiere decir este cuantificador es que existen η1hasta ηnvalores que verifican dos condiciones, la primera que todos ellos son distintos y la segunda que no hay ningún valor además de los ya citados que hace a φverdadera. Por tanto el cuantificador (E nξ)φ indica que existen exactamente n valores para ξque hacen que φsea cierta. Definición 3.12. Sean αyβdos polinomios, el primero de grado py el segundo de grado qen ξ. Además supongamos que η1yη2son las primeras dos variables distintas de ξque no aparecen ni en αni en β. Definimos el operador F,Fn ξ(α, β)5: Fn ξ(α, β)≡(E nξ){_ 0≤k≤q 0≤2m≤p−k−1 [Mk+2m+1 ξ(α)∧Mk ξ(β)] ∧(Eη1)(Eη2)[(η1=ξ)∧(ξ > η2) ∧(Aξ){[(ξ > η2)∧(η1> ξ)] →(α·β > 0)}]} Si analizamos la notación lo que nos dice el operador Fn ξ(α, β)es que existen exactamente nvalores para ξtales que: 5Nótese que la variable ξno es libre en Fn ξ(α, β) 20 CAPÍTULO 3. EL MÉTODO DE DECISIÓN 1. ξes raíz de orden k+ 2m+ 1 del polinomio αy es raíz de orden kdel polinomio β por tanto ξes raíz de ambos polinomios pero es de mayor orden en αy si calculamos la diferencia de ambos órdenes k+ 2m+ 1 −k= 2m+ 1 vemos que es un número entero impar. 2. Existen η1yη2tales que: a) O bien η1tiene el mismo valor que ξyη2es menor que ξ. b) O bien para todos los valores de ξsituados entre η2yη1los polinomios tienen el mismo signo. En conclusión, que existe un intervalo abierto cuyo punto final es ξdentro del cual αyβtienen el mismo signo. Definición 3.13. Sea nentero sin restricciones, αyβdos polinomios en ξy supongamos que kes el máximo de sus grados. Definimos el Operador G Gn ξ(α, β): Gn ξ(α, β)≡_ 0≤m≤k 0≤m+n≤k [Fn+m ξ(α, β)∧Fm ξ(α, (−1) ·ξβ)] Gn ξ(α, β)significa que n1es el entero para el cual se verifica Fn1 ξ(α, β)yn2el entero para el cual se verifica Fn2 ξ(α, (−1) ·ξβ)resultando n=n1−n2 Ahora nos interesa definir el resto obtenido por la división de polinomios, no obstante nos es más sencillo hacerlo cambiado de signo, es decir en su forma negativa a la que denotaremos como Rξ(α, β) Definición 3.14. Sean ξuna variable y αyβdos polinomios de grados mynrespectivamente. Además supongamos que el coeficiente principal de αes αmy el de β βn. Definimos el resto en negativo Rξ(α, β)6 1. Si m<n Rξ(α, β)≡(−1) ·ξα 2. Si m=n Rξ(α, β)≡RdξPξ(αm·βn·β−β2 n·α) 3. Si m>n Rξ(α, β)≡Rξ{RdξPξ(β2 n·α−αm·βn·ξm−n·β), β} 6Se requiere la hipótesis ¬(βn= 0) puesto que, en caso contrario todos los coeficientes de Rξ(α, β) serían equivalentes a 0 3.1. PRIMERA PARTE 21 Observación 3.15.Nótese que es importante recordar, para el cálculo del resto, que el coeficiente principal puede ser cero. De esta forma Rdξ(0ξ2−ξ+ 1) ≡ −ξ+ 1. Efectivamente Rξ(α, β)da como resultado otro polinomio de menor grado que β. Teorema 3.16. Sean αyβdos polinomios en ξde grados mynrespectivamente. Supongamos que βnes el coeficiente principal de β. Establecemos: 1. Si m<nse tiene q= 0. 2. Si m≥nse tiene q=m−n+ 1 Entonces existe un polinomio γen ξcuyos coeficientes no tienen otras variables que las que están en αyβpara el cual α·β2q nyβ·γ−Rξ(α, β)son equivalentes. Generalmente no se emplea este modo para hablar sobre la división de polinomios, no obstante tiene que ser así puesto que en nuestro sistema no disponemos de la operación división. Normalmente se define el resto como un polinomio δpara el cual, para cierto polinomio γ, se satisface la ecuación α=β·γ−δ. Sin embargo el teorema anterior nos proporciona una situación equivalente a esta ecuación utilizando los elementos que disponemos en nuestro sistema. A continuación veremos los operadores principales S T yUque nos permitirán obtener fórmulas sin cuantificadores equivalentes a cualquier tipo de fórmula original. Los siguientes tres teoremas asociados a estos operadores resultan interesantes a nivel matemático porque pueden ser relacionados fácilmente con el Teorema de Sturm(1803) (Ver Apéndice 3) y en su demostración se hace uso de los métodos de este matemático. Definición 3.17. Sean kentero, αyβpolinomios en ξde grados mynrespectivamente con coeficientes principales αmyβn. Denotamos φ≡Gk ξ(α, β). Entonces definimos el operador S de la siguiente forma: 1. Si alguno de los polinomios es nulo:    S(φ)≡(0 = 0) si k= 0 S(φ)≡(0 = 1) si k6= 0 2. Si ninguno de los polinomios es nulo y la suma de sus grados es par: S(φ)≡ {[(αm= 0) ∧SGk ξ(Rdξ(α), β)] ∨[βn= 0) ∧SGk ξ(α, Rdξ(β))] ∨[¬(αm·βn= 0) ∧SGk ξ(β, Rξ(α, β))]} 22 CAPÍTULO 3. EL MÉTODO DE DECISIÓN 3. Si ninguno de los polinomios es nulo y la suma de sus grados es impar: S(φ)≡ {[(αm= 0) ∧SGk ξ(Rdξ(α), β)] ∨[βn= 0) ∧SGk ξ(α, Rdξ(β))] ∨[(αm·βn>0) ∧SGk+1 ξ(β, Rξ(α, β))] ∨[0 >(αm·βn)∧SGk−1 ξ(β, Rξ(α, β))]} Este operador sólo sirve para casos bastante particulares, las fórmulas del tipo Gk ξ(α, β). No obstante nos será de gran importancia porque los demás operadores se definirán en función de él. Teorema 3.18. Sea φuna de las fórmulas para las cuales podemos definir el operador S según la definición anterior. Entonces S(φ)es una fórmula sin cuantificadores y sin variables excepto las libres en φ. Además φes equivalente a S(φ). Demostración. La primera parte resulta inmediata por la definición. Para la segunda parte, basta con demostrarlo para los tres casos de la definición empleando la misma notación. En primer lugar, atendiendo al primer caso, si αoβson el polinomio nulo entonces Gk ξ(α, β)es equivalente a (0 = 0) si k= 0 y a (0 = 1) si k6= 0. Sean ξ1, ...ξnlas variables que aparecen en los coeficientes de α, β o ambas. Entonces: G0 ξ(α, β)equivalente a (0 = 0) si la sentencia (Aξ1)...(Aξs)(G0 ξ(α, β)↔(0 = 0)) es verdad. Como (0 = 0) es verdad en consecuencia debe serlo G0 ξ(α, β)para todos los valores de ξ. Gk ξ(α, β)equivalente a (0 = 1) si la sentencia (Aξ1)...(Aξs)(Gk ξ(α, β)↔(0 = 1)) es verdad. Como (0 = 1) es falsa en consecuencia debe serlo Gk ξ(α, β)o lo que es lo mismo, ¬Gk ξ(α, β)debe de ser verdadera para todos los valores de ξ. Por la definición de derivada, para todo entero no negativo pse verifica Dp ξ(0) ≡0 luego por la definición del operador Msi α≡0oβ≡0Fk ξ(α, β)se satisface para todos los valores de ξ1, ...ξnsi k= 0 y no se satisface si k6= 0. Por la definición del operador G vemos que se aplica lo mismo para Gk ξ(α, β). Para el segundo y tercer caso Gk ξ(α, β)equivalente al punto uno y dos de la definición 3.19 según el valor de m+n. Para demostrar la equivalencia, mediante transformaciones, todo se reduce a probar que: 1. (Aξ1)...(Aξs){¬(αm·βn= 0) →[Gk ξ(α, β)↔Gk ξ(β, Rξ(α, β))]}para m+npar 2. (Aξ1)...(Aξs){(αm·βn>0) →[Gk ξ(α, β)↔Gk+1 ξ(β, Rξ(α, β))]}para m+nimpar 3.1. PRIMERA PARTE 23 3. (Aξ1)...(Aξs){0>(αm·βn)→[Gk ξ(α, β)↔Gk−1 ξ(β, Rξ(α, β))]}para m+nimpar A continuación convertiremos estas expresiones en otras más fuertes. Emplearemos la fórmula Hp ξ(α, β)7. Establecemos γyδpolinomios arbitrarios en ξcuyos coeficientes solo involucran las variables ξ1, ..., ξsypyqson enteros cualesquiera no negativos. Con esto tendremos que probar que las siguientes sentencias son verdaderas: 4. (Aξ1)...(Aξs){[Hp ξ(α, β)∧(Aξ)(α·β2q n=β·γ−δ)∧ ¬(αm·βn= 0)] →[Gk ξ(α, β)↔ Gk ξ(β, δ)]}para ppar. 5. (Aξ1)...(Aξs){[Hp ξ(α, β)∧(Aξ)(α·β2q n=β·γ−δ)∧(αm·βn>0)] →[Gk ξ(α, β)↔ Gk+1 ξ(β, δ)]}para pimpar 6. (Aξ1)...(Aξs){[Hp ξ(α, β)∧(Aξ)(α·β2q n=β·γ−δ)∧(0 > αm·βn)] →[Gk ξ(α, β)↔ Gk−1 ξ(β, δ)]}para pimpar. Efectivamente, la verdad de 4 implica la de 1, la de 5 la de 2 y la verdad de 6 la de 3.8 Antes de probar la verdad de estas sentencias se incluye cierta notación: Dado un polinomio αy un número λdenotaremos mediante f(λ, α)el orden de λen α, lo que coincide con el valor rpara el cual se verifica Mr λ(α). Dados dos polinomios αyβ, escribiremos g(α, β)para representar el entero kpara el cual se verifica Gk ξ(α, β). Consideraremos todos los números λpara los cuales f(λ, α)−f(λ, β)es positivo e impar y los dividiremos en dos grupos •P, al cual pertenece λsi existe un intervalo abierto cuyo punto final (a la derecha) es λdentro del cual los valores de αyβtienen siempre el mismo signo. •Nal cual pertenece λsi existe un intervalo abierto cuyo punto final (a la derecha) es λdentro del cual los valores de αyβtienen siempre distinto signo. Ambos grupos son finitos y la diferencia entre el número de elementos de ambos es g(α, β) Por último se empleará h(α, β)para denotar el entero ppara el cual se verifica Hp ξ(α, β). Lo que quiere decir que es el número de todos los valores λpara los cuales f(λ, α)−f(λ, β)es impar. 7Lo que expresa esta fórmula es que existen exactamente pvalores ξtales que la diferencia entre el orden de ξen αy el orden de ξen βes un entero impar tanto positivo como negativo. 8Para una prueba de estas implicaciones consultar [5] pág. 26. 24 CAPÍTULO 3. EL MÉTODO DE DECISIÓN También se hará uso de la siguiente propiedad: 7. Sean α, β, γ yδpolinomios en ξ, tales que α·β2q n=γ·β−δse verifica para todo valor de ξ, siendo βnel coeficiente principal, distinto de cero, del polinomio βyqun entero. Si para cierto número λ f(λ, β)> f(λ, α)(luego ni αni βpueden ser el valor cero) entonces f(λ, α) = f(λ, δ)y por tanto δtampoco es el polinomio nulo. Análogamente si f(λ, β)> f(λ, δ)se tiene f(λ, α) = f(λ, δ) Por tanto procederemos a probar la verdad de 4, 5 y 6. Estas tres afirmaciones se cumplen trivialmente si el polinomio δtoma el valor cero por tanto descartamos ese caso. Lo haremos por inducción sobre h(α, β). En primer lugar supongamos que h(α, β) = 0 por tanto no existen valores para λtales que f(λ, α)−f(λ, β)y, en consecuencia, g(α, β)=0. Tampoco existen valores para λ tales que f(λ, β)−f(λ, δ)es impar y positivo, lo vemos por reducción a lo absurdo. Si tal valor existiera, por la propiedad 7, se tendría que f(λ, α) = f(λ, δ), lo que llevaría a que f(λ, α)−f(λ, β)fuese impar lo que supone una contradicción. Concluimos que g(β, δ) = 0 y así g(α, β) = g(β, δ)=0. Lo que prueba las afirmaciones. Suponemos que las afirmaciones 4. 5 y 6 se verifican para polinomios arbitrarios αyβ tales que h(α, β) = p. Probemos que son ciertas para los polinomios arbitrarios αyβtales que h(α, β) = p+ 1, siendo αmyβncoeficientes principales distintos de cero. Consideramos también dos polinomios γyδtales que 8. α·β2q n=γ·β−δpara cierto entero no negativo q En esta situación existen dos casos según si la multiplicación de los coeficientes principales es positiva o negativa, solo se resolverá para el caso positivo ya que el restante es análogo. h(α, β) = p+1 implica que existen exactamente p+1 valores para λtales que f(λ, α)− f(λ, β)es impar, denotemos por λ0al mayor valor para λque verifica esa condición. Como αm·βn>0para los ξ > λ0ambos polinomios tienen el mismo signo, como se verifica para todo número sea o no raíz podemos afirmar que no existe ningún ξ > λ0para el cual f(ξ, α)−f(ξ, β)es impar. Por esto y porque f(λ0, α)−f(λ0, β)es impar se tiene que existe un intervalo abierto cuyo punto final es λ0donde los valores de αyβson de distinto signo. Se definen los polinomios α0,γ0yδ0que verifican las ecuaciones 9. α0=α·(λ0−ξ)γ0=γ·(λ0−ξ)δ0=δ·(λ0−ξ) 3.1. PRIMERA PARTE 25 Por 8, que αm·βn>0y 9 concluimos que 10. α0·β2q n=γ0·β−δ0se verifica para algún entero no negativo q. 11. α0 m+1 ·βn<0donde α0 m+1 es el coeficiente principal de α0. 12. f(λ0, α0) = f(λ0, α)+1yf(λ0, δ0) = f(λ0, δ)+1siempre que δyδ0sean distintos de cero. 13. f(ε, α0) = f(ε, α)para todo ε+δ0yf(ε, δ0) = f(ε, δ)para todo ε+δ0siempre que δyδ0sean distintos de cero. Debido a 12 y 13 el conjunto de los números λtales que f(λ, α0)−f(λ, β)es impar es distinto del conjunto análogo para αyβsolo por la ausencia de λ0luego h(α0, β) = h(α, β)−1 = p. En consecuencia la premisa para la inducción se aplica a los polinomios α0yβlo que quiere decir que las sentencias 4, 5 y 6 son verdad si cambiamos αpor α0. Concluimos, por 10 y 11:    g(α0, β) = g(β, δ0)si ppar g(α0, β) = g(β, δ0)+1si pimpar Queremos probar que g(α, β)−g(β, δ) = g(α0, β)−g(β, δ0)−1. Por 9 los valores de αyα0tienen el mismo signo para todo ξ < λ0de la misma forma que para los valores de δyδ0. 14. Por 9 los valores de αyα0tienen el mismo signo para todo ξ < λ0de la misma forma que para los valores de δyδ0. 15. Además no existe ξ > λ0para el cual f(ξ, β)−f(ξ, δ)es positivo e impar, de la misma forma que para βyδ0. Probemos este hecho, procedemos por reducción a lo absurdo. Si para cierto valor ξ > λ0,f(ξ, β)−f(ξ, δ)fuese positivo e impar, siguiendo 7 y 8 f(ξ, α)−f(ξ, β)sería impar para el mismo ξ > λ0y llegaríamos a una contradicción puesto que se había determinado que λ0era el mayor valor para λpara el cual f(λ, α)−f(λ, β)es impar. Por otro lado aplicado aβyδ0se procede de manera análoga pero por 7, 10 llegando a la misma contradicción pero combinada con la primera parte de 13. Nos encontramos ante dos casos según el signo de f(λ0, α)−f(λ0, β), antes de estudiarlos vemos que, siguiendo 13, 14 y 15 el único valor que puede provocar diferencias entre g(α, β)yg(α0, β)o entre g(β, δ)yg(β, δ0)es λ0. 26 CAPÍTULO 3. EL MÉTODO DE DECISIÓN f(λ0, α)−f(λ0, β)>0 Siguiendo la notación para λ0y la existencia del intervalo abierto con ese punto final donde αyβtienen distintos signos, este número provoca un decrecimiento de una unidad de g(α, β)mientras que, por 12 no afecta al valor de g(α0, β). Luego 16. g(α, β) = g(α0, β)−1. Además f(λ0, β)−f(λ0, δ)no puede ser positivo en consecuencia de 7 luego tampoco puede serlo f(λ0, β)−f(λ0, δ0)por 12. En este caso probamos que el número λ0no tiene efecto en los valores de g(β, δ)ni g(β, δ0). Por tanto 17. g(β, δ) = g(β, δ0). En consecuencia de 16 y 17 se verifica g(α, β)−g(β, δ) = g(α0, β)−g(β, δ0)−1. f(λ0, α)−f(λ0, β)<0 Se observa de forma directa que el valor λ0no afecta al valor de g(α, β). Además tampoco afecta al valor de g(α0, β)ya que por la definición de λ0y 12 f(δ0, α0)− f(δ0, β)es par. Luego 18. g(α, β) = g(α0, β). Por otro lado, en consecuencia de 7 f(λ0, α) = f(λ0, δ)que, sumado con la definición de λ0 19. f(λ0, β)−f(λ0, δ)es positivo e impar. Sea f(λ0, α) = f(λ0, δ) = r. Así λ0es de orden ren αy en δy de orden mayor en β. En consecuencia existen tres polinomios α00,β00 yδ00tales que se verifican las ecuaciones 20. α=α00 ·(λ0−ξ)rβ=β00 ·(λ0−ξ)rδ=δ00 ·(λ0−ξ)r λ0es raíz de β00 pero no de α00 oδ00. Seguido de 8 y 20 α00 ·β2q n=γ·β00 −δ00. En consecuencia los valores de α00 yδ00 para ξ=λ0tienen distintos signos, luego existe un intervalo abierto cuyo punto final es λ0en el cual los valores de α00 yδ00 tienen distintos signos y por 20 esto también se aplica a αyδ. Si comparamos este resultado con el intervalo que habíamos obtenido anteriormente podemos concluir que existe un intervalo abierto cuyo punto final es λ0en el cual los valores de βydelta tienen el mismo signo. Por lo tanto seguido de 19 λ0aumenta el valor de g(β, δ)en 1. Por otro lado determinamos, por 12 y 19, que f(λ0, β)−f(λ0, δ0)es par luego λ0no afecta al valor g(β, δ0). Concluimos así 3.1. PRIMERA PARTE 27 21. g(β, δ) = g(β, δ0)+1 En consecuencia de 18 y 21 se verifica g(α, β)−g(β, δ) = g(α0, β)−g(β, δ0)−1. Finalmente al haber probado          g(α0, β) = g(β, δ0)si ppar g(α0, β) = g(β, δ0)+1si pimpar g(α, β)−g(β, δ) = g(α0, β)−g(β, δ0)−1 se obtiene que    g(α, β) = g(β, δ)si p+ 1 par g(α, β) = g(β, δ)−1si p+ 1 impar Luego 4, 5 y 6 se verifican para polinomios αyβtales que h(α, β) = p+ 1 y así por inducción se verifica para todos los polinomios arbitrarios 9. Definición 3.19. Sean α, β, γ1, ..., γrpolinomios arbitrarios en ξ. α≡α0+α1ξ+... +αmξm β≡β0+β1ξ+... +βnξn γ1≡γ1,0+γ1,1ξ+... +γ1,n1ξn1 . . . γr≡γr,0+γr,1ξ+... +γr,nrξnr Definimos el Operador T, que da lugar a la fórmula T(φ): 1. Si φes una fórmula del tipo (E kξ)[α= 0], entonces: T(φ)≡[¬(α0= 0) ∨... ∨ ¬(αm= 0)] ∧SG−k ξ(α, Dξ(α)) 9Relacionándolo con el Teorema de Sturm, a partir de la demostración de este teorema podemos llegar a la siguiente generalización, sean αyβdos polinomios en ξyκyµdos números reales tales que κ<µ. Se construye una serie de polinomios γ1, ..., γnque pueden ser entendidos como la cadena de Sturm para αyβusando αpara γ1,βpara γ2y los siguientes γison el resto en negativo de γi−2yγi−1finalizando el proceso al encontrar un polinomio γndivisor de γn−1. Finalmente denotamos las secuencias de valores κ1, ..., κnyµ1, ..., µnde γ1, ..., γntales que ξ=kyξ=µykel número de cambios de signo en la primera secuencia y mel de la segunda. Así k−mes lo mismo que el número g(α, β)de esta demostración solo que en vez de que las raíces estén entre κyµestán en (−∞,∞). 34 CAPÍTULO 3. EL MÉTODO DE DECISIÓN Definición 3.21. Sean φ, ψ yθfórmulas arbitrarias y ξuna variable cualquiera. Entonces definimos el operador U de la siguiente forma: 1. Si φes una fórmula atómica, establecemos: U(φ)≡φ 2. Si φ≡(ψ∨θ), establecemos: U(φ)≡[U(ψ)∨U(θ)] 3. Si φ≡(ψ∧θ), establecemos: U(φ)≡[U(ψ)∧U(θ)] 4. Si φ≡ ¬ψ, establecemos: U(φ)≡ ¬U(ψ) 5. Si φ≡(Eξ)ψyQPξU(ψ)≡ψ1∨...∨ψn, donde ψipara i= 1, ..., n es una conjunción de fórmulas atómicas, establecemos: U(φ)≡ ¬T[(E 0ξ)ψ1]∨ ¬T[(E 0ξ)ψ2]∨... ∨ ¬T[(E 0ξ)ψn] Teorema 3.22. Si φes cualquier fórmula entonces U(φ)es una fórmula sin cuantificadores y sin variables libres exceptuando aquellas que ocurren en φ. Además φes equivalente a U(φ).12 para el Teorema de Sturm. Usamos la notación de la nota al pie 9. El primer caso es el básico ya conocido, a partir de un polinomio α(considerar que el polinomio βes el polinomio derivado de α) construir la cadena y obtener que k−mes el número de distintas raíces en el intervalo (κ, µ), es el que se considera en el Apéndice. No obstante existe un caso dos que formamos a partir del anterior teorema donde αyβ son dos polinomios cualesquiera y k−mpasa a ser la diferencia entre el número de raíces de αlas cuales tienen el mismo signo en βy en el polinomio derivado de αy el número de raíces de αcon distinto signo en βy en el polinomio derivado de α, todo dentro del intervalo κ, µ. 12Podemos ver este teorema como una extensión del Teorema de Sturm (Apéndice 3). Este último proporciona un criterio para que una ecuación algebraica de una incógnita tenga exactamente ksoluciones reales mediante la construcción de sistemas en función de sus coeficientes. Luego la ecuación tiene exactamente kraíces si y solo si sus coeficientes satisfacen todas las ecuaciones e inecuaciones de al menos uno de esos sistemas. El Teorema 3.22 da una extensión para poder aplicar esta idea a sistemas de ecuaciones e inecuaciones de varias incógnitas. 3.2. SEGUNDA PARTE 35 Demostración. Lo haremos por inducción en el orden de φ. Si φes de orden uno significa que es una fórmula atómica luego siguiendo la definición 3.21 U(φ)≡φy trivialmente se verifica el teorema. Suponemos cierto para orden k. Para probarlo para orden k+ 1 bastaría con emplear los teoremas 3.7 y 3.20. Corolario 3.23. Si φes cualquier sentencia, entonces U(φ)es una sentencia equivalente sin variables y sin cuantificadores. De esta forma quedan cubiertos todos los casos para convertir una fórmula o sentencia con cuantificadores en otra sin ellos. 3.2. Segunda Parte Lo que nos interesa ahora es darle un valor de verdad a cada sentencia. En primer lugar estableceremos una correlación entre una sentencia sin variables ni cuantificadores con 0=0o1=0. Primero nos centramos en los términos de esas sentencias, estos se obtienen combinando las constantes algebraicas mediante las operaciones +,·. Definición 3.24. Sean α,βyγtérminos, definimos el entero n(α)como: n(1) = 1 n(−1) = −1 n(0) = 0 Si α≡(β+γ):n(α) = n(β) + n(γ) Si α≡(β·γ):n(α) = n(β)·n(γ) Como estamos trabajando con números enteros y no comparando expresiones empleamos el signo igual en lugar de ≡, no estamos nombrando el número uno por ejemplo en el primer caso si no que estamos indicando el valor. Definición 3.25. Sean αyβtérminos y φ, ψ yθfórmulas sin variables. Definimos W(φ): 1. Si φ≡(α=β)    W(φ)≡(0 = 0) si n(α) = n(β)) W(φ)≡(0 = 1) en otro caso 36 CAPÍTULO 3. EL MÉTODO DE DECISIÓN 2. Si φ≡(α > β)    W(φ)≡(0 = 0) si n(α)> n(β)) W(φ)≡(0 = 1) en otro caso 3. Si φ≡(ψ∨θ)    W(φ)≡(0 = 0) si W(ψ)≡(0 = 0) oW(θ)≡(0 = 0) W(φ)≡(0 = 1) en otro caso 4. Si φ≡(ψ∧θ)    W(φ)≡(0 = 0) si W(ψ)≡(0 = 0) yW(θ)≡(0 = 0) W(φ)≡(0 = 1) en otro caso 5. Si φ≡(¬ψ)    W(φ)≡(0 = 0) si W(ψ)≡(0 = 1) W(φ)≡(0 = 1) en otro caso Teorema 3.26. Si φes cualquier sentencia sin variables ni cuantificadores, entonces W(φ) es una de las sentencias 0 = 0 o0=1. Además φes equivalente a W(φ). Demostración. Se ve de forma sencilla por inducción en el orden de φ. Teorema 3.27. Si φes cualquier sentencia, entonces W U(φ)es una de las sentencias 0=0o0=1. Además φes equivalente a W U(φ). Demostración. En consecuencia directa del teorema 3.26 y el corolario 3.23. Por tanto queda visto que hemos encontrado un método que nos permite conocer si una sentencia pertenece a la teoría del álgebra elemental. Además cualquier teoría lógica de primer orden que admite un algoritmo de eliminación de cuantificadores es completa, así el álgebra elemental entendida en el sentido del Capítulo 2 es decidible y completa. Capítulo 4 Extensión a otros ámbitos: Geometría Elemental Podemos extender el método a otros ámbitos como es el de la geometría Elemental. La primera pregunta es qué entendemos por una sentencia de geometría elemental. De nuevo, Tarski afirma en su simposio[6] que “consideramos elemental la parte de la geometría Euclidiana que puede formularse y establecerse sin la ayuda de cualquier mecanismo de la teoría de conjuntos.”(p.16) Por ello todo el sistema vendrá dado dentro de la lógica de primer orden. Estamos pues en la misma definición general que proporcionamos para el álgebra elemental, lo que corresponde ahora es presentar el sistema de la geometría elemental. Tarski lo proporciona alrededor del año 1926 y es de una innegable elegancia y simpleza puesto que su característica principal es que el único objecto primitivo son los puntos, a diferencia de otros famosos sistemas como el de Hilbert que añade a parte de ellos planos o líneas como objectos geométricos primitivos. Entender este sistema es otra forma de definir la geometría elemental. 4.1. El sistema de Tarski para la Geometría Elemental El primer ingrediente en la receta de la geometría elemental de Tarski ya lo hemos visto: el objecto matemático primitivo, es decir los puntos, que serán variables del tipo a, b, c, .... Lo siguiente que emplea son dos relaciones no lógicas, también símbolos primitivos: 1. La relación ternaria “estar entre” β(abc)que se leería como b está entre a y c y significa que bestá en el segmento que une los puntos ayc. 2.La relación cuaternaria de equidistancia denotada como δ(abcd)[6] o ab ≡cd [7] que quiere decir que la distancia del punto aabes la misma que la del punto cal d. 37 38 CAPÍTULO 4. EXTENSIÓN A OTROS ÁMBITOS: GEOMETRÍA ELEMENTAL El concepto de centralidad no aparece hasta el siglo XX, lo que parece increíble basándose en la simpleza del mismo. Tanto Hilbert con sus axiomas para la geometría Euclidiana como Tarski lo usan. Por otra parte en consecuencia de la relación de equidistancia podemos obtener el concepto de congruencia para la geometría, de hecho una de las notaciones es la misma que para la congruencia de números. De esta forma decir que ab ≡a0b0querrá decir que el segmento con puntos finales aybes congruente con el segmento con puntos finales a0yb0. El último ingrediente que precisamos son las constantes lógicas. Aquí entran los conectores y cuantificadores ya vistos en el capítulo de Álgebra Elemental junto con los símbolos de igualdad y diferencia 6={∧,∨,→,↔,∀,∃}. El siguiente paso es presentar los axiomas de la teoría. Este sistema de axiomas ha recibido cierto número de modificaciones a lo largo de los años, tanto por el propio Tarski como por otros matemáticos. Presentamos la forma final que Tarski decidió y formó con otros dos matemáticos: Schwabhäuser(1931) y Szmielew(1918)1. Ya resaltamos la sencillez del sistema, no precisamos definiciones previas como es el caso de los Elementos de Euclides, los axiomas se presentan directamente. Axioma 4.1. Reflexividad para la Equidistancia ab ≡ba Lógicamente a está a la misma distancia de b tanto como b lo está de a. Axioma 4.2. Transitividad para la Equidistancia ab ≡pq ∧ab ≡rs →pq ≡rs Si un segmento es congruente a otros dos estos últimos lo serán entre ellos. Axioma 4.3. Identidad para la Equidistancia ab ≡cc →a=b Axioma 4.4. Axioma de la identidad para “estar entre” β(aba)→a=b Axioma 4.5. Axioma de la Construcción de segmentos ∃(β(qax)∧ax ≡bc) 1Todas las modificaciones pueden verse en el documento [7], aquí nos limitamos a mostrar la versión más reducida hasta el momento. 4.1. EL SISTEMA DE TARSKI PARA LA GEOMETRÍA ELEMENTAL 39 Si tenemos un segmento bc podemos construir uno congruente qx b c a Axioma 4.6. Axioma de los cinco segmentos [a6=b∧β(abc)∧β(a0b0c0)∧ab ≡a0b0∧bc ≡b0c0∧ad ≡a0d0∧bd ≡b0d0]→cd ≡c0d0. a d c ba’ d’ c’ b’ En lenguaje más simple este axioma nos dice que si tenemos dos triángulos 4acd y 4a0c0d0y dos puntos byb0que estén en el segmento que une aycya0yc0respectivamente, existe una correspondencia entre ciertos pares de segmentos como se indica en el dibujo. Este axioma es el que precede la mayor parte de los resultados relacionados con congruencia de ángulos, segmentos y triángulos Axioma 4.7. Primer Axioma de Pasch β(apc)∧β(bqc)→ ∃[β(pxb)∧β(qxa)] a c b q p x Se leería como si pestá entre aycyqestá entre bycentonces existe un xque está entre pyby entre qya. Otra forma de expresarlo es que si una recta corta a uno de los lados de un triángulo tiene que cortar a otro y no al tercero, es decir si una recta penetra en el interior de un triángulo también sale de nuevo al exterior del mismo. 40 CAPÍTULO 4. EXTENSIÓN A OTROS ÁMBITOS: GEOMETRÍA ELEMENTAL Axioma 4.8. Axioma n-Dimensional inferior para n= 3,4, ... Este axioma nos dice que existen n−1puntos distintos p1, p2, ..., pn−1y tres puntos a, b, c tales que cada uno de estos tres últimos es equidistante de los puntos n−1no siendo coolineaes. Es decir el conjunto de todos los puntos equidistantes de cada n-1 puntos p1, p2, ..., pn−1no siempre es una línea. Axioma 4.9. Axioma n-Dimensional superior para n= 2,3... Axioma 4.10. Segunda forma del Axioma de Euclides β(abc)∨β(bca)∨β(cab)∨ ∃x[ax ≡bx ∧ax ≡cx] Dado un triángulo (compuesto por los segmentos dados) siempre existe un punto equidistante a los vértices, lo que nos lleva a que todo triángulo puede ser inscrito en un círculo. x a bc Nótese que no debemos echar de menos el axioma de las paralelas pues este es una formulación equivalente. Axioma 4.11. Axioma de continuidad ∃a∀x∀y[x∈X∧y∈Y→β(axy)] → ∃b∀x∀y[x∈X∧y∈Y−→ β(xby)] a b X Y Dados dos conjuntos XeYde forma que los elementos de X precedan a los de Y con respecto a un punto a, entonces están separados por un punto b Todo esto compone la Geometría elemental de Tarski, 2 2No obstante también ideó un sistema para toda la Geometría pero que no estudiaremos en este trabajo. 4.2. APLICACIÓN DEL MÉTODO DE DECISIÓN A LA GEOMETRÍA ELEMENTAL41 4.2. Aplicación del Método de Decisión a la Geometría Elemental Alrededor del año 1930 Tarski prueba que su sistema de geometría admite eliminación de cuantificadores, a partir de estos estudios se presenta como aplicar el método de decisión a este ámbito, probando que la geometría elemental entendida por Tarski es completa y decidible. Volviendo a la presentación de Tarski de la Corporación Rand [5] veremos cómo aplicar el Método de Decisión en este ámbito. Lo que debemos hacer es correlacionar cada sentencia φde geometría elemental con una sentencia φ∗del álgebra elemental. Es decir, a cada variable de φ, denotada por ξse le asignan dos variables algebraicas ¯ ξy¯ ¯ ξde forma que si tenemos dos variables distintas ξe ηtambién lo serán ¯ ξ,¯ ¯ ξ,¯ηy¯ ¯η. Lo siguiente es particularizar los cambios de cada expresión del ámbito de la geometría elemental, esto es: La expresión (Eξ)se reemplaza por (E¯ ξ)(E¯ ¯ ξ). La fórmula ξ=ηse reemplaza por (¯a= ¯η)∧(¯ ¯ ξ=¯ ¯η) La fórmula β(ξ, η, µ)se reemplaza por [(¯ ¯η−¯ ¯ ξ)·(¯µ−¯η)=(¯ ¯µ−¯ ¯η)·(¯η−¯ ξ)] ∧[((¯ ξ−¯η)·(¯η−¯µ)>0) ∨((¯ ξ−¯η)·(¯η−¯µ) = 0)] ∧[((¯ ¯ ξ−¯ ¯η)·(¯ ¯η−¯ ¯µ)>0) ∨((¯ ¯ ξ−¯ ¯η)·(¯ ¯η−¯ ¯µ) = 0)] La fórmula D(ξ, η, µ, ν)por (¯ ξ−¯η)2+ (¯ ¯ ξ−¯ ¯η)2= (¯µ−¯ν)2+ (¯ ¯µ−¯ ¯ν)2 De esta forma si la sentencia φes verdadera también lo será φ∗y viceversa. 4.3. Ampliación de las teorías A continuación podemos preguntarnos si sería posible aumentar las teorías definidas con algunas propiedades. Existen respuestas que ya conocemos como el hecho de añadir conceptos como “ser entero” o “ser racional”,en este caso sabemos que no existiría un método de decisión en el sentido que hemos dado y así no se podría construir la máquina. Esto se sigue de los resultados de Gödel-Church-Rosser mencionados anteriormente y Mrs. Robinson para el caso de racional. También tiene el mismo resultado añadir funciones periódicas como sin, esto es debido a que un número xes racional si y solo si verifica la fórmula (Ey)(Ez)[(x·y=z)∧ ¬(y= 0) ∧(siny = 0) ∧(sinz = 0)] 42 CAPÍTULO 4. EXTENSIÓN A OTROS ÁMBITOS: GEOMETRÍA ELEMENTAL En otros casos el problema sigue aún abierto, como es el caso de añadir la operación exponenciación(restringida a casos reales) denotada por Exp3o el símbolo Cn que denotase la propiedad de ser un número construible4. No existe todavía respuesta, tanto positiva o negativa para la pregunta de si existe un método de decisión. No obstante las dificultades parecen ser de tipo matemático y puede que en los próximos años se halle una solución para el problema. 3Precisaríamos de tres nuevos axiomas para incluirla (Ax)(Ay)[(x > y)→(Exp(x)> Exp(y))], (Ax)(Ay)[(Exp(x)·Ep(y)) = Exp(x+y)] yExp(1) = 1 + 1. 4Este es un tipo de número que indica que puede ser obtenido a partir del 1 mediante las operaciones sumas, restas, multiplicaciones, divisiones y raíz cuadrada. Añadir esta propiedad resultaría muy interesante porque nos permitiría no solo decidir la verdad de una sentencia de la geometría elemental si no también decidir cuándo la verdad de una sentencia puede establecerse usando solamente regla y compás. Apéndice 1. Todo el desarrollo del sistema formal para el álgebra elemental sigue un esquema lógico básico, es decir, que se corresponde con la lógica de primer orden de los números reales junto con la suma y la multiplicación. En estas líneas se proporciona un resumen de los conceptos de lógica que son necesarios para la comprensión del trabajo. La base de la lógica son los argumentos, formados por un conjunto de premisas y una conclusión luego son una serie de ideas que desencadenan lógicamente una última. Pueden ser válidos o inválidos en cuestión de si su forma es correcta. Un argumento es inválido si las premisas pueden ser todas verdaderas y la conclusión falsa, en caso contrario, es válido. El proceso de formalización del Álgebra que se vio en el Capítulo 2 precisa de un lenguaje que, al igual que sería el caso del entorno lingüístico, está compuesto por un alfabeto y una gramática. El alfabeto tiene como elementos las variables, constantes, funciones (y en consecuencia operaciones), los conectores{⊥,¬,∨,∧,→,↔}, los cuantificadores{∃,∀}, los elementos de agrupación y los predicados. Salvo estos últimos los anteriores están definidos en la parte principal del trabajo. Los predicados son frases que asignan propiedades y generalmente se denotan con letras mayúsculas P, Q, R etc., son tratados como funciones y también podemos hablar de aridad de un predicado según el número de elementos que tenga en cuenta. A partir de variables, constantes, operaciones y signos de agrupación podemos formar términos. Finalmente una fórmula atómica será un símbolo de predicado n-ario seguido, entre paréntesis, por n términos separados por comas. La parte de la gramática está dividida a su vez en dos ámbitos: la sintaxis y la semántica. La primera estudia las reglas de formación de los elementos del lenguaje cuyo fin es establecer fórmulas bien formadas (a su vez compuestas por términos y fórmulas atómicas dadas al juntar elementos del alfabeto) y sentencias en el caso 43