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

T aballo Fin de G ao
El mé odo de decisión de Ta ski pa a
el Álgeb a y la Geome ía
elemen ales
Rosana Sob ido Codesido
2019/2020
UNIVERSIDADE DE SANTIAGO DE COMPOSTELA
GRAO DE MATEMÁTICAS
T aballo Fin de G ao
El mé odo de decisión de Ta ski pa a
el Álgeb a y la Geome ía
elemen ales
Rosana Sob ido Codesido
Julio, 2020
UNIVERSIDADE DE SANTIAGO DE COMPOSTELA
T abajo p opues o
Á ea de Coñecemen o: Álgeb a
Tí ulo: El mé odo de decisión de Ta ski pa a el Álgeb a y la
Geome ía elemen ales
B e e desc ición do con ido
El logis a Al ed Ta ski en los años 30 del siglo XX, y es ingiéndose
a lo que él llama la geome ía elemen al, p obó la exis encia de un p o-
cedimien o que, aplicado a cualquie ó mula de la eo ía o mal puede
deci , en un núme o ini o de pasos, si es o no un eo ema. Además
Ta ski desen uel e un sis ema o mal pa a la geome ía euclidiana. Su
algo i mo unciona ambién en la eo ía o mal del Álgeb a elemen al.
Es e admi e eliminación de cuan i icado es, esul ando en un sis ema
comple o, decidible y que admi e una demos ación cons uc i a de
su consis encia.
Recomendacións
Es con enien e usa la bibliog a ía suge ida.
Ou as obse acións
iii

Índice gene al
Resumen ii
In oducción ix
1. Con ex o his ó ico 1
2. Álgeb a elemen al 5
3. El mé odo de decisión 13
3.1. P ime aPa e................................... 13
3.2. SegundaPa e .................................. 35
4. Ex ensión a o os ámbi os: Geome ía Elemen al 37
4.1. El sis ema de Ta ski pa a la Geome ía Elemen al . . . . . . . . . . . . . . . 37
4.2. Aplicación del Mé odo de Decisión a la Geome ía Elemen al . . . . . . . . 41
4.3. Ampliación de las eo ías . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
Apéndice 43
Bibliog a ía 47
Resumen
El abajo se enma ca en el campo de la Teo ía de Modelos den o de la lógica ma-
emá ica. Con es e con ex o se es udia án las p opiedades de las eo ías del álgeb a y la
geome ía elemen ales. Pa icula men e se ealiza un es udio sin ác ico p esen ando el mé-
odo de decisión p opo cionado po el ma emá ico y ilóso o Al ed Ta ski que pe mi e
conoce qué esul ados son cie os den o de una de es as dos eo ías y, en consecuencia,
pa icula iza los eo emas de las mismas. Es a es una idea muy in e esan e ya que es e
algo i mo pe mi e esol e cues iones complicadas de o ma mecánica sin que sean necesa-
ios g andes conocimien os de la ma e ia. En consecuencia, al pode se aplicado, queda á
p obado que ambas eo ías son decidibles. Se ha á uso de concep os me ama emá icos y de
lógica de p edicados jun o con los pu amen e algeb aicos y, además de la p opia de inición
del mé odo se ha á un es udio de los undamen os del álgeb a y la geome ía elemen ales
en el sen ido de Ta ski.
Abs ac
The wo k is amed in he ield o he Model Theo y inside he Ma hema ical logic.
In his con ex we will s udy he p ope ies o Elemen a y Algeb a and Geome y. In
pa icula a syn ac ic s udy is ca ied ou p esen ing he decision me hod p o ided by he
ma hema ician and philosophe Al ed Ta ski ha allows o know which esul s a e ue
wi hin one o hese wo heo ies and, consequen ly, o pa icula ize he heo ems o hem.
This is a e y in e es ing idea since his algo i hm allows o sol e complica ed ques ions
in a mechanical way wi hou being necessa y o ha e a g ea knowledge o he ma e .
Consequen ly, i i can be applied, i will be p o ed ha bo h heo ies a e decidable. I
will make use o me ama hema ical concep s and logic o p edica es along wi h he pu ely
algeb aic ones and, in addi ion o he de ini ion o he me hod we will make a s udy o he
undamen als o Elemen a y Algeb a and Geome y in he sense o Ta ski.
ii
2CAPÍTULO 1. CONTEXTO HISTÓRICO
aspec os de una eo ía ma emá ica, no son eo emas en la de inición habi ual del concep o.
Después de Hilbe o os ma emá icos se in e esa ían po el p oblema de decisión, uno
de ellos es Ta ski. El papel del ma emá ico polaco esul a esencial pues o que ans o mó el
concep o de la me ama emá ica al in oduci mé odos semán icos3. Sinaceu (1940) a i mó
sob e la elación de Ta ski con es e ámbi o:
Desde la pe spec i a de Ta ski, la me ama emá ica es simila a cualquie disciplina
ma emá ica. No solo sus concep os y esul ados pueden se ma ema izados, si no que
pueden se in eg ados den o de las ma emá icas (...) Ta ski des uyó la línea en e la
ma emá ica y la me ama emá ica. Se opuso a es ingi el papel de las me ama emá icas
a los undamen os de las ma emá icas. [2]
En las siguien es páginas p esen a emos el mé odo de decisión p opo cionado po Al ed
Ta ski que nos pe mi i á da espues a al p oblema de decisión en el ámbi o del álgeb a y la
geome ía elemen ales. Es e ue un abajo no exen o de di icul ades eó icas e his ó icas.
Una pis a de la p oblemá ica his ó ica iene dado po el nomb e o iginal de Ta ski:
Al ed Tei elbaum, de o igen judío, además de su nacimien o da ado en 1901 en Va sobia,
pocos años an es del es allido de las Gue as Mundiales. Podemos ex ae un b e e suma-
io de su ida siguiendo [13], en su ju en ud Al ed cambia su nomb e a la e sión que
conocemos hoy en día (Ta ski) y se con ie e al ca olicismo siguiendo ideales nacionalis as
polacos y a ando de esqui a el an isemi ismo de la época.
La ida de Ta ski se e di icul ada po las gue as, es a si uación incluso le lle a á a
in e umpi sus es udios en a ias ocasiones pa a lucha po sus ideales y es que, an es de
comenza la Uni e sidad Ta ski se unió du an e un iempo al ejé ci o polaco y ambién en
una segunda ocasión du an e sus es udios uni e si a ios. Es e ambien e hos il de gue a
y ocupación no impide que Al ed sea un b illan e es udian e y lle e a cabo mul i ud de
in es igaciones.
Siendo muy jo en, en 1925 nues o homb e consigue no uno, si no dos abajos como
p o eso en ma emá icas y comienza a se conocido in e nacionalmen e. En sus lec u as
uni e si a ias en e 1926 y 1928 a lo an algunos esul ados pa ciales que da án luga al
mé odo de decisión. En sus inicios las condiciones ue on más es ic i as pa a la exis encia
del mismo, así en sus es udios iniciales la única ope ación conside ada en el ámbi o del
álgeb a e a la suma y la geome ía solo con emplaba la línea ec a.
con i mamos que exis e un mé odo pa a de e mina si cualquie ó mula pe enece al conjun o de e dades
de la misma. En el abajo es e mé odo es el mé odo de decisión.
3El mé odo semán ico, en e al sin ác ico a a de analiza la concepción de e dad en luga de limi a se
a p uebas y de i aciones.

3
Según las palab as del p opio Ta ski en [5] los p ime os esul ados e e idos a es e
abajo de una o ma casi simila a la ac ual se ob ienen en los años ein a y su elabo ación
se ala ga nue e años. La publicación es aba p e is a pa a 1939 pe o debido al comienzo
de la Segunda Gue a Mundial u o que se aplazada. El p ime momen o del que se
ienen e e encias del abajo es en 1931 en la publicación Su les ensembles dé inissables
de nomb es éels , Fundamen a Ma hema icae 17.1, (1931), 210–239 pe o pa cialmen e y
sin demos a sus hipó esis.
Siguiendo el lib o [11] podemos analiza la biog a ía de Ta ski en esos años, a dó
en acep a el hecho de que e a necesa io emig a de su país debido al p esen e con lic o
y la pe secución judía que es aba comenzando a su gi . La gue a a ec a a odos pe o,
los o ígenes judíos de Ta ski podían lle a lo a los gue os impues os po los alemanes en
Va sobia o a una sen encia de mue e.
El ma emá ico había ecibido una in i ación o icial pa a asis i a un cong eso en Cam-
b idge, Massachuse s, pe o ace cándose la echa aún no había dado una espues a. El
p o eso de Ha a d y logis a Willa d Van O man Quine epi ió la in i ación y pidió a
Ta ski que conside a a la emig ación, idea que Ta ski acep a en el úl imo minu o.
En un p incipio la es ancia en Es ados Unidos se ía pasaje a pe o e mina á po que-
da se allí el es o de su ida, al igual que su muje e hijas que as sob e i i a la gue a
se uni án a él en Amé ica. Vol iendo a la na ación que ealiza el p opio Ta ski sob e los
hechos, una ez en Es ados Unidos le comienzan a su gi dudas sob e la calidad de su
abajo y a a de eesc ibi lo, lo que ala ga aún más su publicación. Los du os momen os
de la gue a y la posgue a lle an a que el abajo se posponga du an e años has a que
a p incipios de 1948 la co po ación RAND, San a Mónica, Cali o nia se in e esa po el
abajo y se o ece a publica lo. T as le es modi icaciones, en las que el p opio Al ed oma
pa e, se publica A decision Me hod o Elemen a y Algeb a and Geome y.
No odo el en o no de Ta ski u o la misma sue e, sus pad es, su he mano y la a-
milia de es e úl imo ue on asesinados po los alemanes así como muchos ma emá icos
compañe os que no pudie on hui de la gue a.
4CAPÍTULO 1. CONTEXTO HISTÓRICO
Capí ulo 2
Álgeb a elemen al
El ma co donde es aplicable el mé odo de decisión es el álgeb a elemen al, en las siguien-
es líneas se desc ibi á su sis ema o mal, además de es udia la o ma de los elemen os que
la componen. Es o se lle a á a cabo en el ámbi o de la lógica de p ime o den emplean-
do concep os básicos1. Todos los concep os segui án las ideas desc i as en [5]. En asgos
gene ales se conside a elemen al a la eo ía que no hace uso de concep os de eo ía de
conjun os.
Nues o abajo conlle a el es udio de las eo ías del álgeb a y la geome ía elemen ales
en su o igen po an o debemos emplea algunos concep os me ama emá icos además de los
clásicos símbolos ma emá icos2. A con inuación se p esen a un esquema de los elemen os
que componen el álgeb a elemen al.
En p ime luga , los elemen os más básicos son las a iables, que nos pe mi i án
oma alo es de o ma a bi a ia. La no ación empleada se á x1, x2, ..., y1, y2, ..., z1, z2, ...
donde los subíndices nos indican que es án o denadas y en consecuencia podemos habla
de p ime a a iable, segunda a iable, has a n-ésima a iable. Las a iables se in e p e an
como núme os eales a bi a ios sin que exis an las dis inciones en e los concep os clásicos
de en e o, acional e c. pues en caso con a io pasa íamos al caso en el que no exis e mé odo
de decisión p obado po Gödel.
De inición 2.1. Una ope ación n-a ia en el conjun o A es una unción :An→A.
Siendo nel núme o de a idad, es e iene dado po la can idad de elemen os que se
1Pa a una ca ac e ización más lógica e Apéndice 1.
2Los símbolos y exp esiones ma emá icos se deno an de la o ma habi ual y podemos conside a que son
cons an es me ama emá icas. Po o o lado, en la pa e me ama emá ica α, β, γ ep esen a án é minos
a bi a ios, las le as ξ, η, λ, µ, ν a iables a bi a ias y inalmen e θ, φ, ψ ó mulas y sen encias a bi a ias.
Pa a una discusión más amplia sob e es os concep os e [4](Sección 2, pp.279 ., en pa icula p.289) y
[3](p.100 en pa icula ).
5
6CAPÍTULO 2. ÁLGEBRA ELEMENTAL
necesi an pa a lle a a cabo la ope ación. [10]
A con inuación enemos las cons an es algeb aicas que son los símbolos 1,0,−1y
po o o lado los signos de ope ación suma y mul iplicación +,·. Ambos son de a idad
2. Solamen e mencionamos dos signos de ope ación po que que emos simpli ica el modelo
lo máximo posible, o os pueden su gi de di e sas combinaciones, como es el caso de la
es a pues deci α−βes lo mismo que [α+ (−1·β)] .
Jun ando a iables y cons an es median e signos de ope ación ob enemos los é minos
algeb aicos como se ían po ejemplo x+yo−1·x. Sin ol ida que, en algunos casos, se á
impo an e el uso de signos de ag upación pa a indica qué ope ación se ealiza an es
que o a, Ta ski emplea pa én esis, co che es y lla es con es e in, en endiendo es e úl imo
como un supe pa én esis y no con nociones de eo ía de conjun os. Los é minos adquie en
dis in o o den. Un é mino algeb aico de p ime o den es simplemen e una a iable o una
cons an e. A pa i de aquí po cada in e acción se aumen a á el o den. Si enemos los
é minos αyβsiendo kel máximo o den (de una o de ambas), en onces α·βyα+β
son é minos algeb aicos de o den k+ 1. Po ejemplo, ¿cuál se ía el o den de −1·x1+x2?
1 + 1 + 1 = 3.
El siguien e elemen o a de ini son los signos algeb aicos de elación:=,≥conocidos
como signo de igualdad y signo mayo que3.
De inición 2.2. Una ó mula a ómica es una exp esión o mada po é minos algeb ai-
cos a bi a ios jun o con los símbolos de elación. Los dos ipos de ó mulas ob enidas son
las igualdades α=βy las desigualdades α > β.
Podemos uni las ó mulas a ómicas median e di e sos conec o es pa a o ma o as más
complejas. Los conec o es son, en pa icula ope aciones. Sean θyφ ó mulas a ómicas,
p esen amos así las conec i as ¬,∧y∨.
La negación ¬: Leído como “no” ¬θ. Es un ope ado lógico una io.
La conjunción ∧: Leído como “y” θ∧φ. Es un ope ado lógico bina io
La disyunción ∨: Leído como “o” θ∨φ. Es ambién un ope ado lógico bina io.
Exis en o as dos conec i as lógicas que pueden exp esa se en unción de las es an e io-
es y aunque educimos nues o sis ema a la o ma más sencilla po comodidad u iliza emos
3T a amos de p esen a el sis ema de la o ma más simple posible, omi i emos el signo <. De hecho
ambién podemos educi lo más pues o que x > y ≡(Ez)[¬(z= 0) ∧(x=y+z2)].
7
su no ación pa icula , es os son la implicación →y la equi alencia ↔. Las en endemos
como ab e ia u as pa a exp esiones que emplean las an e io es conec i as lógicas.4 5
O o elemen o lógico que debemos nomb a es el cuan i icado exis encial ∃, que nos
pe mi e deci que exis e al menos un elemen o que cumpli á lo que iene a con inuación.
No obs an e la no ación que emplea emos se á la de Ta ski, es a esul a Eξ pa a deci que
exis e un ξ al que.
De inición 2.3. Una ó mula es una exp esión cons uida median e la unión de ó mulas
a ómicas jun o con conec o es y cuan i icado es.
Al igual que los é minos las ó mulas ienen un o den asociado. Una ó mula de o den
1 es simplemen e una ó mula a ómica. Po cada conec o que empleamos la ó mula sube
un o den, es deci si θes una ó mula de o den ken onces ¬θes una ó mula de o den
k+ 1 al igual que si empleamos el cuan i icado (Ex)θ esul ando ambién de o den k+ 1.
Aquellos que in oluc an dos ó mulas θyφ, siendo kel o den máximo de ambas, θ∧φy
θ∨φ esul an de o den k+ 1.
Aho a nos in e esa habla de un ipo de a iables, las a iables lib es que de inimos
en pa icula pa a cada si uación. Suponemos que θyφson dos ó mulas a ómicas.
ξes lib e en φsi y solo si ξapa ece en φ.
ξes lib e en (Eη)θsi y solo si ηno es la misma a iable que ξyξes lib e en θ.
ξes lib e en ¬θsi y solo si φes lib e en θ.
ξes lib e en θ∨φy en θ∧φsi y solo si ξes lib e en al menos una de las ó mulas θ
yφ.
De inición 2.4. Una sen encia es una ó mula que no con iene a iables lib es.
Además debemos nomb a o o impo an e elemen o: el cuan i icado uni e sal ∀,
que Ta ski esc ibe como (Aξ)θpa a deci : pa a odo ξque exis e en θ. No obs an e no
cons i ui ía un elemen o p incipal si no que puede de i a se del cuan i icado exis encial.
(Aξ)θ≡ ¬(Eξ)¬θ
4No debemos con undi dos concep os simila es, la equi alencia ma e ial y la equi alencia lógica. La
equi alencia ma e ial es la conec i a lógica bina ia que aquí se explica, deno ada con el símbolo ↔y al
cual se le asocia su semán ica pa icula . Po o o lado deno a emos la equi alencia lógica po ≡o ambién
pod ía se deno ada po ⇔, es a acepción es á den o del ámbi o de la semán ica y nos indica que ambas
pa es, a un lado y al o o, poseen el mismo alo de e dad.
5Ambas p o ienen de las conec i as básicas de la siguien e mane a, θ→φ≡ ¬θ∨φen endiendo θ
como el an eceden e o hipó esis y φla consecuencia o conclusión de la implicación. De la misma o ma
θ↔φ≡(θ→φ)∧(φ→θ).

8CAPÍTULO 2. ÁLGEBRA ELEMENTAL
Se lee ía como no exis e un ξque no es á en θ, dicho de o a o ma odo ξes á en θ.
También pa a el mé odo se á muy impo an e el uso de disyunciones y conjunciones de
muchas ó mulas simul áneamen e, lo deno a emos de la siguien e o ma. Si las ó mulas
es án o denadas en una secuencia ini a, θ1, ...θn
_
1≤i≤n
θi
^
1≤i≤n
θi
Si se in oluc an más casos, aumen a án los subíndices de las ó mulas y pasa á a habe dos
líneas bajo el conec o .
Has a es e pun o hemos a ado la cons ucción de sen encias, elemen o a pa i del cual
emplea emos el mé odo de decisión. Toda es a pa e compond ía la sin axis del lenguaje
de p ime o den. A con inuación nos co esponde la pa e de semán ica que es udia el
signi icado o in e p e ación de las ó mulas, aquí en a en juego el concep o de e dad.6 7
Exis en sen encias básicas que sabemos di ec amen e si son e dade as o alsas, pa a
las demás se usa án unas no mas es ablecidas, es as ienen dadas po los conec o es. Sean
θyφdos sen encias.
¬θes e dad si y solo si θes alsa.
θ∧φes e dad si y solo si ambas sen encias son e dad.
θ∨φes e dad si y solo si al menos una de ellas es e dad.
θ→φes e dad en odo caso excep o que θsea e dad y φ alsa.
6Pa a Ta ski la noción de e dad ue una cues ión muy impo an e, la a a de o ma ex endida en
ob as como [4] donde se p opo ciona una de inición o mal. No obs an e el concep o ilosó ico sob e qué es
la e dad no es necesa io pa a nues o abajo. Usa emos la de inición de e dad de o ma in ui i a.
7También podemos elimina di ec amen e la noción de e dad del abajo si some emos al álgeb a
elemen al a un p oceso de axioma ización. En es e con ex o podemos sus i ui la idea de sen encia e dade a
po la de sen encia p obable. Una sen encia p obable es aquella que puede se de i ada de los axiomas
median e la epe ición de las eglas de in e encia. Los axiomas de la eo ía son los de la lógica de p ime
o den(Apéndice 2) y los axiomas p opios de la misma que son de ipo algeb aico. Es os úl imos in oluc an
los que pe mi en la ca ac e ización del conjun o de núme os eales como un campo o denado jun o con las
ope aciones +y·y la elación >sin ol ida los elemen os especiales 1, -1 y 0; además se añade un úl imo
axioma
(Aξ1)...(Aξn)(Aη)(Aζ){[(η > ζ)∧(Eξ)((ξ=η)∧(α > 0)) ∧(Eξ)((ξ=ζ)∧(0 > α))]
→(Eξ)((η > ξ)∧(ξ > ζ)∧(α= 0))}
que indica que si en un pun o una unción, en el sen ido que empleamos, es posi i a y en o o nega i a
exis e un pun o in e medio en el cual la unción oma el alo ce o.
9
θ↔φes e dad si y sólo si ambas sen encias son e dad o ambas sen encias son
alsas.
Las sen encias son e dade as o alsas mien as que las ó mulas pueden oma di e sos
alo es y esul a án alsas o e dade as dependiendo de ellos. Po ejemplo 0=1es una
sen encia que esul a se alsa mien as que la ó mula x > 0es álida pa a cie os alo es
pe o alsa pa a o os.
De inición 2.5. Sean θyφ ó mulas a bi a ias y ξ1, ξ2, ..., ξnlas a iables lib es que
apa ecen en ellas. En onces si la sen encia (Aξ1)...(Aξn)(θ↔φ)es e dad di emos que
ambas ó mulas son equi alen es.
Teo ema 2.6. La elación de equi alencia es simé ica, e lexi a y ansi i a.
Demos ación. Re lexi a, lógicamen e si θ elacionada con φ,φes á elacionada con
θpues si ocu e lo p ime o al se e dad (Aξ1)...(Aξn)(θ↔φ)signi ica que θyφson
ambas e dad o ambas men i a, de cualquie a de las dos o mas (Aξ1)...(Aξn)(φ↔θ).
Simé ica, oda ó mula es á elacionada consigo misma pues o que θ↔θsiemp e
es e dad.
T ansi i a
θ elacionada con φluego (Aξ1)...(Aξn)(θ↔φ)es e dad, así ambas θyφson
e dade as o alsas.
φ elacionada con ϕluego (Aξ1)...(Aξn)(φ↔ϕ)es e dad, así ambas φyϕson
e dade as o alsas.
Suponemos que θ,φyϕson e dad pa a odas las a iables lib es que es án en las
ó mulas luego como ambas θyϕson e dad ambién lo es (θ⇔ϕ)pa a odas las
a iables lib es.
Po con a, si suponemos que θ,φyϕson men i a pa a odas las a iables lib es que
es án en las ó mulas luego como ambas θyϕson men i a, (θ↔ϕ)es e dad pa a
odas las a iables lib es.
Teo ema 2.7. Sean θ1yθ2dos ó mulas equi alen es y supongamos que la ó mula ψ2
su ge de la ó mula ψ1 eemplazando θ1po θ2en uno o más luga es. En onces ψ1es
equi alen e a ψ2.
Análogamen e, ya iendo que es a de inición y eo emas se e i ican pa a ó mulas, en
consecuencia pod án aplica se a é minos.
10 CAPÍTULO 2. ÁLGEBRA ELEMENTAL
De inición 2.8. Sean αyβ é minos a bi a ias y ξ1, ξ2, ..., ξnlas a iables que apa ecen en
ellas. En onces si la sen encia (Aξ1)...(Aξn)(α=β)es e dad di emos que ambos é minos
son equi alen es.
Teo ema 2.9. La elación de equi alencia de é minos es simé ica, e lexi a y ansi i a.
Teo ema 2.10. Sean α1yα2dos é minos equi alen es y supongamos que el é mino
β2su ge del é mino β1 eemplazando α1po α2en uno o más luga es. En onces β1es
equi alen e a β2.
Teo ema 2.11. Sean α1yα2dos é minos equi alen es y supongamos que la ó mulaψ2
su ge la ó mula ψ1 eemplazando α1po α2en uno o más luga es. En onces ψ1es equi-
alen e a ψ2.
Finalmen e p esen amos las úl imas nociones algeb aicas básicas que necesi a emos
pa a es ablece el mé odo de decisión.8
De inición 2.12. Sean α0, α1, ..., αn é minos que no dependen de x. Se dice que
α0+α1·ξ+... +αn·ξn
es un polinomio en ξde g ado ncon coe icien es α0, ..., αnsiendo αnel coe icien e p in-
cipal.
El g ado iene dado po el coe icien e p incipal, es e no iene que se necesa iamen e
dis in o de ce o, (1 −1) ·x2+xes un polinomio de g ado dos.
De inición 2.13. Sean αyβdos polinomios en ξde g ados myn espec i amen e.
α≡α0+α1·ξ+... +αm·ξm
β≡β0+β1·ξ+... +βn·ξn
Sean =min{m, n}ys=max{m, n}yγi≡αi+βicon i≤ .
Si m < n γi≡βicon < i ≤s.
Si m > n γi≡αicon < i ≤s.
Es deci , pa a los índices supe io es al mínimo se oma como alo el co espondien e con
el polinomio de mayo g ado. De inimos la suma de polinomios +ξ:
α+ξβ≡γ0+γ1·ξ+... +γs·ξs
8La de inición común de polinomio incluye la eo ía de conjun os, p∈ P(x), po an o debemos de
da una e sión adap ada a nues o con ex o “elemen al” incluyendo ambién el p ocedimien o pa a las
ope aciones en e polinomios.
11
En esumen, la suma de polinomios esul a en o o polinomio cuyos coe icien es son la
suma de los o os dos.
De inición 2.14. Sea αun polinomio en ξde g ado m. Se dice que
Rdξ(α)≡a0+a1·ξ+... +am−1·ξm−1
es el educ um de α. Si el polinomio es de g ado nulo, es deci no depende de ξ, el
educ um se á el polinomio nulo Rdξ(α)≡0. Podemos deci que
Rd0
ξ(α)≡α
Rd1
ξ(α)≡a0+a1·ξ+... +am−1·ξm−1
Rd2
ξ(α)≡a0+a1·ξ+... +am−2·ξm−2
Po an o
Rdk+1
ξ(α)≡Rdξ[Rdk
ξ(α)]
E ec i amen e obse amos que el educ um de un polinomio es o o polinomio con los
mismos coe icien es pe o eliminando el p incipal, de o ma que end á un g ado meno .
De inición 2.15. Sean αyβdos polinomios en ξde g ados myn espec i amen e.
α≡α0+α1·ξ+... +αm·ξm
β≡β0+β1·ξ+... +βn·ξn
Se de ine la ope ación poduc o de polinomios ·ξ:
Si m= 0
α·ξβ≡(α·β0)+(α·β1)·ξ+... + (α·βn)·ξn
Así se ob iene el polinomio nulo, ojo no pod íamos deci que α·ξβ≡0po que el
esul ado de la ope ación no da ía luga a un polinomio si no al alo ce o.
Si m > 0
α·ξβ≡[Rdξ(α)·ξβ] +ξ(γ0+γ1·ξ+... +γm+n·ξm+n)
Siendo
γi≡0pa ai<m
γm≡αm·β0
γm+1 ≡αm·β1
.
.
.
γm+n≡αm·βn
18 CAPÍTULO 3. EL MÉTODO DE DECISIÓN
desca ados po hipó esis). Luego nos encon amos en el pun o 2 de la de inición 3.5 iendo
que e ec i amen e es una disyunción de conjunciones de ó mulas a ómicas. La equi alencia
se sigue de la ley dis ibu i a del cálculo p oposicional.
Teo ema 3.7. Sea φuna ó mula a bi a ia sin cuan i icado es y ξuna a iable cualquie a.
En onces QPξ(φ)4es una disyunción de conjunciones de ó mulas a ómicas donde cada una
de ellas iene un polinomio en ξen el lado izquie do y 0 en el lado de echo. Además QPξ(φ)
es equi alen e a φ.
Demos ación. E ec i amen e QPξ(φ)es equi alen e a φsiguiendo los Teo emas 3.4 y 3.6.
QPξ(φ)≡Q(φ)≡φ. Además su o ma ambién es i ial siguiendo la de inición de ambos
ope ado es.
De inición 3.8. Sea αun polinomio en ξ, de inimos la de i ada con espec o a ξ Dξ(α)
como:
1. Si es de g ado n > 0, es deci α≡α0+α1·ξ+... +αn·ξn:
Dξ(α)≡α1+ (2 ·α2)·ξ+... + (n·αn)·ξn−1
2. Si es de g ado 0:
Dξ(α)≡0
Lógicamen e la de i ada de un polinomio es un polinomio pues sigue eniendo el es-
quema de la de inición 2.12, solo que de un g ado meno . Es e concep o de de i ada puede
ambién ex ende se a é minos a bi a ios que no sean polinomios en ξu ilizando la p ime a
ans o mación, así
Dξ(α)≡DξPξ(α)
De inición 3.9. Si αes cualquie é mino y ξuna a iable a bi a ia. De inimos la de i-
ada de o den k:
D0
ξ(α)≡α
Dk+1
ξ(α)≡Dξ[Dk
ξ(α)]
Como es as son la de i ada de la de i ada sucesi amen e y ya imos que la de i ada
de un polinomio es un polinomio odas las de i adas de o den supe io se án polinomios.
4Ab e iamos la no ación en luga de esc ibi Q[Pξ(φ)].

3.1. PRIMERA PARTE 19
De inición 3.10. Sea αun polinomio en ξyn∈N. De inimos el ope ado M de la
siguien e mane a:
Mn
ξ(α)≡ {(^
1≤i≤n
[Di−1
ξ(α) = 0]) ∧ ¬[Dn
ξ(α) = 0]}
M0
ξ(α)≡ ¬(α= 0)
Se lee á como “el núme o ξes de o den nen el polinomio α”.
Es e ope ado nos indica las aíces del polinomio, aducimos la pa e o mal de la
de echa: dos condiciones que deben da se simul áneamen e, la p ime a que el alo ξes
una aíz pa a el p opio polinomio y odas sus de i adas has a el o den n−1y la segunda
que el alo ξno es aíz pa a la de i ada n-ésima. Luego el signi icado de Mn
ξ(p)es que ξ
es una aíz del polinomio de o den ny cuando el alo de nes nulo signi ica á que ξno es
aíz de α.
De inición 3.11. Sea ξuna a iable y φuna ó mula a bi a ia, n un núme o en e o
posi i o y η1, ..., ηnlas p ime as n- a iables que no apa ecen en φy que son di e en es de
ξ. De inimos el cuan i icado exis encial numé ico:
(E0ξ)φ≡(Aξ)¬φ
(E
nξ)φ≡ {(Eη1)...(Eηn)( ^
1≤i<j≤n
¬(ηi=ηj)∧(Aξ)[φ↔_
1≤i≤n
(ηi=ξ)])}
Lo que quie e deci es e cuan i icado es que exis en η1has a ηn alo es que e i ican
dos condiciones, la p ime a que odos ellos son dis in os y la segunda que no hay ningún
alo además de los ya ci ados que hace a φ e dade a. Po an o el cuan i icado (E
nξ)φ
indica que exis en exac amen e n alo es pa a ξque hacen que φsea cie a.
De inición 3.12. Sean αyβdos polinomios, el p ime o de g ado py el segundo de g ado
qen ξ. Además supongamos que η1yη2son las p ime as dos a iables dis in as de ξque
no apa ecen ni en αni en β. De inimos el ope ado 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 no ación lo que nos dice el ope ado Fn
ξ(α, β)es que exis en exac a-
men e n alo es pa a ξ ales que:
5Nó ese que la a iable ξno es lib e en Fn
ξ(α, β)
20 CAPÍTULO 3. EL MÉTODO DE DECISIÓN
1. ξes aíz de o den k+ 2m+ 1 del polinomio αy es aíz de o den kdel polinomio β
po an o ξes aíz de ambos polinomios pe o es de mayo o den en αy si calculamos
la di e encia de ambos ó denes k+ 2m+ 1 −k= 2m+ 1 emos que es un núme o
en e o impa .
2. Exis en η1yη2 ales que:
a) O bien η1 iene el mismo alo que ξyη2es meno que ξ.
b) O bien pa a odos los alo es de ξsi uados en e η2yη1los polinomios ienen
el mismo signo.
En conclusión, que exis e un in e alo abie o cuyo pun o inal es ξden o del cual
αyβ ienen el mismo signo.
De inición 3.13. Sea nen e o sin es icciones, αyβdos polinomios en ξy supongamos
que kes el máximo de sus g ados. De inimos el Ope ado G Gn
ξ(α, β):
Gn
ξ(α, β)≡_
0≤m≤k
0≤m+n≤k
[Fn+m
ξ(α, β)∧Fm
ξ(α, (−1) ·ξβ)]
Gn
ξ(α, β)signi ica que n1es el en e o pa a el cual se e i ica Fn1
ξ(α, β)yn2el en e o
pa a el cual se e i ica Fn2
ξ(α, (−1) ·ξβ) esul ando n=n1−n2
Aho a nos in e esa de ini el es o ob enido po la di isión de polinomios, no obs an e
nos es más sencillo hace lo cambiado de signo, es deci en su o ma nega i a a la que
deno a emos como Rξ(α, β)
De inición 3.14. Sean ξuna a iable y αyβdos polinomios de g ados myn espec i a-
men e. Además supongamos que el coe icien e p incipal de αes αmy el de β βn. De inimos
el es o en nega i o 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 equie e la hipó esis ¬(βn= 0) pues o que, en caso con a io odos los coe icien es de Rξ(α, β)
se ían equi alen es a 0
3.1. PRIMERA PARTE 21
Obse ación 3.15.Nó ese que es impo an e eco da , pa a el cálculo del es o, que el
coe icien e p incipal puede se ce o. De es a o ma Rdξ(0ξ2−ξ+ 1) ≡ −ξ+ 1.
E ec i amen e Rξ(α, β)da como esul ado o o polinomio de meno g ado que β.
Teo ema 3.16. Sean αyβdos polinomios en ξde g ados myn espec i amen e. Supon-
gamos que βnes el coe icien e p incipal de β. Es ablecemos:
1. Si m<nse iene q= 0.
2. Si m≥nse iene q=m−n+ 1
En onces exis e un polinomio γen ξcuyos coe icien es no ienen o as a iables que las
que es án en αyβpa a el cual α·β2q
nyβ·γ−Rξ(α, β)son equi alen es.
Gene almen e no se emplea es e modo pa a habla sob e la di isión de polinomios, no
obs an e iene que se así pues o que en nues o sis ema no disponemos de la ope ación
di isión. No malmen e se de ine el es o como un polinomio δpa a el cual, pa a cie o
polinomio γ, se sa is ace la ecuación α=β·γ−δ. Sin emba go el eo ema an e io
nos p opo ciona una si uación equi alen e a es a ecuación u ilizando los elemen os que
disponemos en nues o sis ema.
A con inuación e emos los ope ado es p incipales S T yUque nos pe mi i án ob ene
ó mulas sin cuan i icado es equi alen es a cualquie ipo de ó mula o iginal. Los siguien es
es eo emas asociados a es os ope ado es esul an in e esan es a ni el ma emá ico po que
pueden se elacionados ácilmen e con el Teo ema de S u m(1803) (Ve Apéndice 3) y
en su demos ación se hace uso de los mé odos de es e ma emá ico.
De inición 3.17. Sean ken e o, αyβpolinomios en ξde g ados myn espec i amen e
con coe icien es p incipales αmyβn. Deno amos φ≡Gk
ξ(α, β). En onces de inimos el
ope ado S de la siguien e o ma:
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 g ados es pa :
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 g ados es impa :
S(φ)≡ {[(αm= 0) ∧SGk
ξ(Rdξ(α), β)] ∨[βn= 0) ∧SGk
ξ(α, Rdξ(β))]
∨[(αm·βn>0) ∧SGk+1
ξ(β, Rξ(α, β))] ∨[0 >(αm·βn)∧SGk−1
ξ(β, Rξ(α, β))]}
Es e ope ado sólo si e pa a casos bas an e pa icula es, las ó mulas del ipo Gk
ξ(α, β).
No obs an e nos se á de g an impo ancia po que los demás ope ado es se de ini án en
unción de él.
Teo ema 3.18. Sea φuna de las ó mulas pa a las cuales podemos de ini el ope ado
S según la de inición an e io . En onces S(φ)es una ó mula sin cuan i icado es y sin
a iables excep o las lib es en φ. Además φes equi alen e a S(φ).
Demos ación. La p ime a pa e esul a inmedia a po la de inición. Pa a la segunda pa e,
bas a con demos a lo pa a los es casos de la de inición empleando la misma no ación.
En p ime luga , a endiendo al p ime caso, si αoβson el polinomio nulo en onces
Gk
ξ(α, β)es equi alen e a (0 = 0) si k= 0 y a (0 = 1) si k6= 0. Sean ξ1, ...ξnlas a iables
que apa ecen en los coe icien es de α, β o ambas. En onces:
G0
ξ(α, β)equi alen e a (0 = 0) si la sen encia
(Aξ1)...(Aξs)(G0
ξ(α, β)↔(0 = 0))
es e dad. Como (0 = 0) es e dad en consecuencia debe se lo G0
ξ(α, β)pa a odos los
alo es de ξ.
Gk
ξ(α, β)equi alen e a (0 = 1) si la sen encia
(Aξ1)...(Aξs)(Gk
ξ(α, β)↔(0 = 1))
es e dad. Como (0 = 1) es alsa en consecuencia debe se lo Gk
ξ(α, β)o lo que es lo mismo,
¬Gk
ξ(α, β)debe de se e dade a pa a odos los alo es de ξ.
Po la de inición de de i ada, pa a odo en e o no nega i o pse e i ica Dp
ξ(0) ≡0
luego po la de inición del ope ado Msi α≡0oβ≡0Fk
ξ(α, β)se sa is ace pa a odos
los alo es de ξ1, ...ξnsi k= 0 y no se sa is ace si k6= 0. Po la de inición del ope ado G
emos que se aplica lo mismo pa a Gk
ξ(α, β).
Pa a el segundo y e ce caso Gk
ξ(α, β)equi alen e al pun o uno y dos de la de inición
3.19 según el alo de m+n. Pa a demos a la equi alencia, median e ans o maciones,
odo se educe a p oba que:
1. (Aξ1)...(Aξs){¬(αm·βn= 0) →[Gk
ξ(α, β)↔Gk
ξ(β, Rξ(α, β))]}pa a m+npa
2. (Aξ1)...(Aξs){(αm·βn>0) →[Gk
ξ(α, β)↔Gk+1
ξ(β, Rξ(α, β))]}pa a m+nimpa
3.1. PRIMERA PARTE 23
3. (Aξ1)...(Aξs){0>(αm·βn)→[Gk
ξ(α, β)↔Gk−1
ξ(β, Rξ(α, β))]}pa a m+nimpa
A con inuación con e i emos es as exp esiones en o as más ue es. Emplea emos la ó -
mula Hp
ξ(α, β)7. Es ablecemos γyδpolinomios a bi a ios en ξcuyos coe icien es solo
in oluc an las a iables ξ1, ..., ξsypyqson en e os cualesquie a no nega i os. Con es o
end emos que p oba que las siguien es sen encias son e dade as:
4. (Aξ1)...(Aξs){[Hp
ξ(α, β)∧(Aξ)(α·β2q
n=β·γ−δ)∧ ¬(αm·βn= 0)] →[Gk
ξ(α, β)↔
Gk
ξ(β, δ)]}pa a ppa .
5. (Aξ1)...(Aξs){[Hp
ξ(α, β)∧(Aξ)(α·β2q
n=β·γ−δ)∧(αm·βn>0)] →[Gk
ξ(α, β)↔
Gk+1
ξ(β, δ)]}pa a pimpa
6. (Aξ1)...(Aξs){[Hp
ξ(α, β)∧(Aξ)(α·β2q
n=β·γ−δ)∧(0 > αm·βn)] →[Gk
ξ(α, β)↔
Gk−1
ξ(β, δ)]}pa a pimpa .
E ec i amen e, la e dad de 4 implica la de 1, la de 5 la de 2 y la e dad de 6 la de 3.8
An es de p oba la e dad de es as sen encias se incluye cie a no ación:
Dado un polinomio αy un núme o λdeno a emos median e (λ, α)el o den de λen
α, lo que coincide con el alo pa a el cual se e i ica M
λ(α).
Dados dos polinomios αyβ, esc ibi emos g(α, β)pa a ep esen a el en e o kpa a
el cual se e i ica Gk
ξ(α, β).
Conside a emos odos los núme os λpa a los cuales (λ, α)− (λ, β)es posi i o e
impa y los di idi emos en dos g upos
•P, al cual pe enece λsi exis e un in e alo abie o cuyo pun o inal (a la
de echa) es λden o del cual los alo es de αyβ ienen siemp e el mismo signo.
•Nal cual pe enece λsi exis e un in e alo abie o cuyo pun o inal (a la de echa)
es λden o del cual los alo es de αyβ ienen siemp e dis in o signo.
Ambos g upos son ini os y la di e encia en e el núme o de elemen os de ambos es
g(α, β)
Po úl imo se emplea á h(α, β)pa a deno a el en e o ppa a el cual se e i ica
Hp
ξ(α, β). Lo que quie e deci que es el núme o de odos los alo es λpa a los cuales
(λ, α)− (λ, β)es impa .
7Lo que exp esa es a ó mula es que exis en exac amen e p alo es ξ ales que la di e encia en e el
o den de ξen αy el o den de ξen βes un en e o impa an o posi i o como nega i o.
8Pa a una p ueba de es as implicaciones consul a [5] pág. 26.

24 CAPÍTULO 3. EL MÉTODO DE DECISIÓN
También se ha á uso de la siguien e p opiedad:
7. Sean α, β, γ yδpolinomios en ξ, ales que α·β2q
n=γ·β−δse e i ica pa a odo
alo de ξ, siendo βnel coe icien e p incipal, dis in o de ce o, del polinomio βyqun
en e o.
Si pa a cie o núme o λ (λ, β)> (λ, α)(luego ni αni βpueden se el alo ce o)
en onces (λ, α) = (λ, δ)y po an o δ ampoco es el polinomio nulo. Análogamen e
si (λ, β)> (λ, δ)se iene (λ, α) = (λ, δ)
Po an o p ocede emos a p oba la e dad de 4, 5 y 6. Es as es a i maciones se
cumplen i ialmen e si el polinomio δ oma el alo ce o po an o desca amos ese caso.
Lo ha emos po inducción sob e h(α, β).
En p ime luga supongamos que h(α, β) = 0 po an o no exis en alo es pa a λ ales
que (λ, α)− (λ, β)y, en consecuencia, g(α, β)=0. Tampoco exis en alo es pa a λ
ales que (λ, β)− (λ, δ)es impa y posi i o, lo emos po educción a lo absu do. Si al
alo exis ie a, po la p opiedad 7, se end ía que (λ, α) = (λ, δ), lo que lle a ía a que
(λ, α)− (λ, β) uese impa lo que supone una con adicción. Concluimos que g(β, δ) = 0
y así g(α, β) = g(β, δ)=0. Lo que p ueba las a i maciones.
Suponemos que las a i maciones 4. 5 y 6 se e i ican pa a polinomios a bi a ios αyβ
ales que h(α, β) = p.
P obemos que son cie as pa a los polinomios a bi a ios αyβ ales que h(α, β) =
p+ 1, siendo αmyβncoe icien es p incipales dis in os de ce o. Conside amos ambién dos
polinomios γyδ ales que
8. α·β2q
n=γ·β−δpa a cie o en e o no nega i o q
En es a si uación exis en dos casos según si la mul iplicación de los coe icien es p incipales
es posi i a o nega i a, solo se esol e á pa a el caso posi i o ya que el es an e es análogo.
h(α, β) = p+1 implica que exis en exac amen e p+1 alo es pa a λ ales que (λ, α)−
(λ, β)es impa , deno emos po λ0al mayo alo pa a λque e i ica esa condición.
Como αm·βn>0pa a los ξ > λ0ambos polinomios ienen el mismo signo, como se
e i ica pa a odo núme o sea o no aíz podemos a i ma que no exis e ningún ξ > λ0pa a
el cual (ξ, α)− (ξ, β)es impa . Po es o y po que (λ0, α)− (λ0, β)es impa se iene
que exis e un in e alo abie o cuyo pun o inal es λ0donde los alo es de αyβson de
dis in o signo.
Se de inen los polinomios α0,γ0yδ0que e i ican las ecuaciones
9. α0=α·(λ0−ξ)γ0=γ·(λ0−ξ)δ0=δ·(λ0−ξ)
3.1. PRIMERA PARTE 25
Po 8, que αm·βn>0y 9 concluimos que
10. α0·β2q
n=γ0·β−δ0se e i ica pa a algún en e o no nega i o q.
11. α0
m+1 ·βn<0donde α0
m+1 es el coe icien e p incipal de α0.
12. (λ0, α0) = (λ0, α)+1y (λ0, δ0) = (λ0, δ)+1siemp e que δyδ0sean dis in os
de ce o.
13. (ε, α0) = (ε, α)pa a odo ε+δ0y (ε, δ0) = (ε, δ)pa a odo ε+δ0siemp e que
δyδ0sean dis in os de ce o.
Debido a 12 y 13 el conjun o de los núme os λ ales que (λ, α0)− (λ, β)es impa es dis in o
del conjun o análogo pa a αyβsolo po la ausencia de λ0luego h(α0, β) = h(α, β)−1 = p.
En consecuencia la p emisa pa a la inducción se aplica a los polinomios α0yβlo que
quie e deci que las sen encias 4, 5 y 6 son e dad si cambiamos αpo α0. Concluimos, po
10 y 11:



g(α0, β) = g(β, δ0)si ppa
g(α0, β) = g(β, δ0)+1si pimpa
Que emos p oba que g(α, β)−g(β, δ) = g(α0, β)−g(β, δ0)−1.
Po 9 los alo es de αyα0 ienen el mismo signo pa a odo ξ < λ0de la misma o ma
que pa a los alo es de δyδ0.
14. Po 9 los alo es de αyα0 ienen el mismo signo pa a odo ξ < λ0de la misma o ma
que pa a los alo es de δyδ0.
15. Además no exis e ξ > λ0pa a el cual (ξ, β)− (ξ, δ)es posi i o e impa , de la
misma o ma que pa a βyδ0.
P obemos es e hecho, p ocedemos po educción a lo absu do. Si pa a cie o alo ξ >
λ0, (ξ, β)− (ξ, δ) uese posi i o e impa , siguiendo 7 y 8 (ξ, α)− (ξ, β)se ía impa pa a
el mismo ξ > λ0y llega íamos a una con adicción pues o que se había de e minado que
λ0e a el mayo alo pa a λpa a el cual (λ, α)− (λ, β)es impa . Po o o lado aplicado
aβyδ0se p ocede de mane a análoga pe o po 7, 10 llegando a la misma con adicción
pe o combinada con la p ime a pa e de 13.
Nos encon amos an e dos casos según el signo de (λ0, α)− (λ0, β), an es de es u-
dia los emos que, siguiendo 13, 14 y 15 el único alo que puede p o oca di e encias en e
g(α, β)yg(α0, β)o en e g(β, δ)yg(β, δ0)es λ0.
26 CAPÍTULO 3. EL MÉTODO DE DECISIÓN
(λ0, α)− (λ0, β)>0
Siguiendo la no ación pa a λ0y la exis encia del in e alo abie o con ese pun o inal
donde αyβ ienen dis in os signos, es e núme o p o oca un dec ecimien o de una
unidad de g(α, β)mien as que, po 12 no a ec a al alo de g(α0, β). Luego
16. g(α, β) = g(α0, β)−1.
Además (λ0, β)− (λ0, δ)no puede se posi i o en consecuencia de 7 luego ampoco
puede se lo (λ0, β)− (λ0, δ0)po 12. En es e caso p obamos que el núme o λ0no
iene e ec o en los alo es de g(β, δ)ni g(β, δ0). Po an o
17. g(β, δ) = g(β, δ0).
En consecuencia de 16 y 17 se e i ica g(α, β)−g(β, δ) = g(α0, β)−g(β, δ0)−1.
(λ0, α)− (λ0, β)<0
Se obse a de o ma di ec a que el alo λ0no a ec a al alo de g(α, β). Además
ampoco a ec a al alo de g(α0, β)ya que po la de inición de λ0y 12 (δ0, α0)−
(δ0, β)es pa . Luego
18. g(α, β) = g(α0, β).
Po o o lado, en consecuencia de 7 (λ0, α) = (λ0, δ)que, sumado con la de inición
de λ0
19. (λ0, β)− (λ0, δ)es posi i o e impa .
Sea (λ0, α) = (λ0, δ) = . Así λ0es de o den en αy en δy de o den mayo
en β. En consecuencia exis en es polinomios α00,β00 yδ00 ales que se e i ican las
ecuaciones
20. α=α00 ·(λ0−ξ) β=β00 ·(λ0−ξ) δ=δ00 ·(λ0−ξ)
λ0es aíz de β00 pe o no de α00 oδ00. Seguido de 8 y 20 α00 ·β2q
n=γ·β00 −δ00. En
consecuencia los alo es de α00 yδ00 pa a ξ=λ0 ienen dis in os signos, luego exis e
un in e alo abie o cuyo pun o inal es λ0en el cual los alo es de α00 yδ00 ienen
dis in os signos y po 20 es o ambién se aplica a αyδ. Si compa amos es e esul ado
con el in e alo que habíamos ob enido an e io men e podemos conclui que exis e
un in e alo abie o cuyo pun o inal es λ0en el cual los alo es de βydel a ienen el
mismo signo. Po lo an o seguido de 19 λ0aumen a el alo de g(β, δ)en 1. Po o o
lado de e minamos, po 12 y 19, que (λ0, β)− (λ0, δ0)es pa luego λ0no a ec a al
alo g(β, δ0). Concluimos así
3.1. PRIMERA PARTE 27
21. g(β, δ) = g(β, δ0)+1
En consecuencia de 18 y 21 se e i ica g(α, β)−g(β, δ) = g(α0, β)−g(β, δ0)−1.
Finalmen e al habe p obado









g(α0, β) = g(β, δ0)si ppa
g(α0, β) = g(β, δ0)+1si pimpa
g(α, β)−g(β, δ) = g(α0, β)−g(β, δ0)−1
se ob iene que



g(α, β) = g(β, δ)si p+ 1 pa
g(α, β) = g(β, δ)−1si p+ 1 impa
Luego 4, 5 y 6 se e i ican pa a polinomios αyβ ales que h(α, β) = p+ 1 y así po
inducción se e i ica pa a odos los polinomios a bi a ios 9.
De inición 3.19. Sean α, β, γ1, ..., γ polinomios a bi a ios en ξ.
α≡α0+α1ξ+... +αmξm
β≡β0+β1ξ+... +βnξn
γ1≡γ1,0+γ1,1ξ+... +γ1,n1ξn1
.
.
.
γ ≡γ ,0+γ ,1ξ+... +γ ,n ξn
De inimos el Ope ado T, que da luga a la ó mula T(φ):
1. Si φes una ó mula del ipo (E
kξ)[α= 0], en onces:
T(φ)≡[¬(α0= 0) ∨... ∨ ¬(αm= 0)] ∧SG−k
ξ(α, Dξ(α))
9Relacionándolo con el Teo ema de S u m, a pa i de la demos ación de es e eo ema podemos llega
a la siguien e gene alización, sean αyβdos polinomios en ξyκyµdos núme os eales ales que κ<µ.
Se cons uye una se ie de polinomios γ1, ..., γnque pueden se en endidos como la cadena de S u m pa a
αyβusando αpa a γ1,βpa a γ2y los siguien es γison el es o en nega i o de γi−2yγi−1 inalizando
el p oceso al encon a un polinomio γndi iso de γn−1. Finalmen e deno amos las secuencias de alo es
κ1, ..., κnyµ1, ..., µnde γ1, ..., γn ales que ξ=kyξ=µykel núme o de cambios de signo en la p ime a
secuencia y mel de la segunda. Así k−mes lo mismo que el núme o g(α, β)de es a demos ación solo
que en ez de que las aíces es én en e κyµes án en (−∞,∞).
34 CAPÍTULO 3. EL MÉTODO DE DECISIÓN
De inición 3.21. Sean φ, ψ yθ ó mulas a bi a ias y ξuna a iable cualquie a. En onces
de inimos el ope ado U de la siguien e o ma:
1. Si φes una ó mula a ómica, es ablecemos:
U(φ)≡φ
2. Si φ≡(ψ∨θ), es ablecemos:
U(φ)≡[U(ψ)∨U(θ)]
3. Si φ≡(ψ∧θ), es ablecemos:
U(φ)≡[U(ψ)∧U(θ)]
4. Si φ≡ ¬ψ, es ablecemos:
U(φ)≡ ¬U(ψ)
5. Si φ≡(Eξ)ψyQPξU(ψ)≡ψ1∨...∨ψn, donde ψipa a i= 1, ..., n es una conjunción
de ó mulas a ómicas, es ablecemos:
U(φ)≡ ¬T[(E
0ξ)ψ1]∨ ¬T[(E
0ξ)ψ2]∨... ∨ ¬T[(E
0ξ)ψn]
Teo ema 3.22. Si φes cualquie ó mula en onces U(φ)es una ó mula sin cuan i icado es
y sin a iables lib es excep uando aquellas que ocu en en φ. Además φes equi alen e a
U(φ).12
pa a el Teo ema de S u m. Usamos la no ación de la no a al pie 9. El p ime caso es el básico ya conocido,
a pa i de un polinomio α(conside a que el polinomio βes el polinomio de i ado de α) cons ui la
cadena y ob ene que k−mes el núme o de dis in as aíces en el in e alo (κ, µ), es el que se conside a
en el Apéndice. No obs an e exis e un caso dos que o mamos a pa i del an e io eo ema donde αyβ
son dos polinomios cualesquie a y k−mpasa a se la di e encia en e el núme o de aíces de αlas cuales
ienen el mismo signo en βy en el polinomio de i ado de αy el núme o de aíces de αcon dis in o signo
en βy en el polinomio de i ado de α, odo den o del in e alo κ, µ.
12Podemos e es e eo ema como una ex ensión del Teo ema de S u m (Apéndice 3). Es e úl imo
p opo ciona un c i e io pa a que una ecuación algeb aica de una incógni a enga exac amen e ksoluciones
eales median e la cons ucción de sis emas en unción de sus coe icien es. Luego la ecuación iene exac a-
men e k aíces si y solo si sus coe icien es sa is acen odas las ecuaciones e inecuaciones de al menos uno
de esos sis emas. El Teo ema 3.22 da una ex ensión pa a pode aplica es a idea a sis emas de ecuaciones
e inecuaciones de a ias incógni as.

3.2. SEGUNDA PARTE 35
Demos ación. Lo ha emos po inducción en el o den de φ.
Si φes de o den uno signi ica que es una ó mula a ómica luego siguiendo la de inición
3.21 U(φ)≡φy i ialmen e se e i ica el eo ema.
Suponemos cie o pa a o den k.
Pa a p oba lo pa a o den k+ 1 bas a ía con emplea los eo emas 3.7 y 3.20.
Co ola io 3.23. Si φes cualquie sen encia, en onces U(φ)es una sen encia equi alen e
sin a iables y sin cuan i icado es.
De es a o ma quedan cubie os odos los casos pa a con e i una ó mula o sen encia
con cuan i icado es en o a sin ellos.
3.2. Segunda Pa e
Lo que nos in e esa aho a es da le un alo de e dad a cada sen encia. En p ime
luga es ablece emos una co elación en e una sen encia sin a iables ni cuan i icado es
con 0=0o1=0.
P ime o nos cen amos en los é minos de esas sen encias, es os se ob ienen combinando
las cons an es algeb aicas median e las ope aciones +,·.
De inición 3.24. Sean α,βyγ é minos, de inimos el en e o n(α)como:
n(1) = 1
n(−1) = −1
n(0) = 0
Si α≡(β+γ):n(α) = n(β) + n(γ)
Si α≡(β·γ):n(α) = n(β)·n(γ)
Como es amos abajando con núme os en e os y no compa ando exp esiones emplea-
mos el signo igual en luga de ≡, no es amos nomb ando el núme o uno po ejemplo en el
p ime caso si no que es amos indicando el alo .
De inición 3.25. Sean αyβ é minos y φ, ψ yθ ó mulas sin a iables. De inimos W(φ):
1. Si φ≡(α=β)



W(φ)≡(0 = 0) si n(α) = n(β))
W(φ)≡(0 = 1) en o o caso
36 CAPÍTULO 3. EL MÉTODO DE DECISIÓN
2. Si φ≡(α > β)



W(φ)≡(0 = 0) si n(α)> n(β))
W(φ)≡(0 = 1) en o o caso
3. Si φ≡(ψ∨θ)



W(φ)≡(0 = 0) si W(ψ)≡(0 = 0) oW(θ)≡(0 = 0)
W(φ)≡(0 = 1) en o o caso
4. Si φ≡(ψ∧θ)



W(φ)≡(0 = 0) si W(ψ)≡(0 = 0) yW(θ)≡(0 = 0)
W(φ)≡(0 = 1) en o o caso
5. Si φ≡(¬ψ)



W(φ)≡(0 = 0) si W(ψ)≡(0 = 1)
W(φ)≡(0 = 1) en o o caso
Teo ema 3.26. Si φes cualquie sen encia sin a iables ni cuan i icado es, en onces W(φ)
es una de las sen encias 0 = 0 o0=1. Además φes equi alen e a W(φ).
Demos ación. Se e de o ma sencilla po inducción en el o den de φ.
Teo ema 3.27. Si φes cualquie sen encia, en onces W U(φ)es una de las sen encias
0=0o0=1. Además φes equi alen e a W U(φ).
Demos ación. En consecuencia di ec a del eo ema 3.26 y el co ola io 3.23.
Po an o queda is o que hemos encon ado un mé odo que nos pe mi e conoce si
una sen encia pe enece a la eo ía del álgeb a elemen al. Además cualquie eo ía lógica
de p ime o den que admi e un algo i mo de eliminación de cuan i icado es es comple a,
así el álgeb a elemen al en endida en el sen ido del Capí ulo 2 es decidible y comple a.
Capí ulo 4
Ex ensión a o os ámbi os:
Geome ía Elemen al
Podemos ex ende el mé odo a o os ámbi os como es el de la geome ía Elemen al.
La p ime a p egun a es qué en endemos po una sen encia de geome ía elemen al. De
nue o, Ta ski a i ma en su simposio[6] que “conside amos elemen al la pa e de la geome ía
Euclidiana que puede o mula se y es ablece se sin la ayuda de cualquie mecanismo de
la eo ía de conjun os.”(p.16) Po ello odo el sis ema end á dado den o de la lógica de
p ime o den.
Es amos pues en la misma de inición gene al que p opo cionamos pa a el álgeb a ele-
men al, lo que co esponde aho a es p esen a el sis ema de la geome ía elemen al. Ta ski
lo p opo ciona al ededo del año 1926 y es de una innegable elegancia y simpleza pues o
que su ca ac e ís ica p incipal es que el único objec o p imi i o son los pun os, a di e encia
de o os amosos sis emas como el de Hilbe que añade a pa e de ellos planos o líneas
como objec os geomé icos p imi i os. En ende es e sis ema es o a o ma de de ini la
geome ía elemen al.
4.1. El sis ema de Ta ski pa a la Geome ía Elemen al
El p ime ing edien e en la ece a de la geome ía elemen al de Ta ski ya lo hemos is o:
el objec o ma emá ico p imi i o, es deci los pun os, que se án a iables del ipo a, b, c, ....
Lo siguien e que emplea son dos elaciones no lógicas, ambién símbolos p imi i os:
1. La elación e na ia “es a en e” β(abc)que se lee ía como b es á en e a y c y
signi ica que bes á en el segmen o que une los pun os ayc.
2.La elación cua e na ia de equidis ancia deno ada como δ(abcd)[6] o ab ≡cd [7] que
quie e deci que la dis ancia del pun o aabes la misma que la del pun o cal d.
37
38 CAPÍTULO 4. EXTENSIÓN A OTROS ÁMBITOS: GEOMETRÍA ELEMENTAL
El concep o de cen alidad no apa ece has a el siglo XX, lo que pa ece inc eíble basán-
dose en la simpleza del mismo. Tan o Hilbe con sus axiomas pa a la geome ía Euclidiana
como Ta ski lo usan. Po o a pa e en consecuencia de la elación de equidis ancia pode-
mos ob ene el concep o de cong uencia pa a la geome ía, de hecho una de las no aciones
es la misma que pa a la cong uencia de núme os. De es a o ma deci que ab ≡a0b0que á
deci que el segmen o con pun os inales aybes cong uen e con el segmen o con pun os
inales a0yb0.
El úl imo ing edien e que p ecisamos son las cons an es lógicas. Aquí en an los conec-
o es y cuan i icado es ya is os en el capí ulo de Álgeb a Elemen al jun o con los símbolos
de igualdad y di e encia 6={∧,∨,→,↔,∀,∃}.
El siguien e paso es p esen a los axiomas de la eo ía. Es e sis ema de axiomas ha
ecibido cie o núme o de modi icaciones a lo la go de los años, an o po el p opio Ta ski
como po o os ma emá icos. P esen amos la o ma inal que Ta ski decidió y o mó con
o os dos ma emá icos: Schwabhäuse (1931) y Szmielew(1918)1. Ya esal amos la sencillez
del sis ema, no p ecisamos de iniciones p e ias como es el caso de los Elemen os de Euclides,
los axiomas se p esen an di ec amen e.
Axioma 4.1. Re lexi idad pa a la Equidis ancia
ab ≡ba
Lógicamen e a es á a la misma dis ancia de b an o como b lo es á de a.
Axioma 4.2. T ansi i idad pa a la Equidis ancia
ab ≡pq ∧ab ≡ s →pq ≡ s
Si un segmen o es cong uen e a o os dos es os úl imos lo se án en e ellos.
Axioma 4.3. Iden idad pa a la Equidis ancia
ab ≡cc →a=b
Axioma 4.4. Axioma de la iden idad pa a “es a en e”
β(aba)→a=b
Axioma 4.5. Axioma de la Cons ucción de segmen os
∃(β(qax)∧ax ≡bc)
1Todas las modi icaciones pueden e se en el documen o [7], aquí nos limi amos a mos a la e sión
más educida has a el momen o.
4.1. EL SISTEMA DE TARSKI PARA LA GEOMETRÍA ELEMENTAL 39
Si enemos un segmen o bc podemos cons ui uno cong uen e
qx
b
c
a
Axioma 4.6. Axioma de los cinco segmen os
[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 es e axioma nos dice que si enemos dos iángulos 4acd y
4a0c0d0y dos pun os byb0que es én en el segmen o que une aycya0yc0 espec i amen e,
exis e una co espondencia en e cie os pa es de segmen os como se indica en el dibujo.
Es e axioma es el que p ecede la mayo pa e de los esul ados elacionados con con-
g uencia de ángulos, segmen os y iángulos
Axioma 4.7. P ime Axioma de Pasch
β(apc)∧β(bqc)→ ∃[β(pxb)∧β(qxa)]
a
c
b
q
p
x
Se lee ía como si pes á en e aycyqes á en e bycen onces exis e un xque es á
en e pyby en e qya. O a o ma de exp esa lo es que si una ec a co a a uno de los
lados de un iángulo iene que co a a o o y no al e ce o, es deci si una ec a pene a
en el in e io de un iángulo ambién sale de nue o al ex e io del mismo.

40 CAPÍTULO 4. EXTENSIÓN A OTROS ÁMBITOS: GEOMETRÍA ELEMENTAL
Axioma 4.8. Axioma n-Dimensional in e io pa a n= 3,4, ...
Es e axioma nos dice que exis en n−1pun os dis in os p1, p2, ..., pn−1y es pun os
a, b, c ales que cada uno de es os es úl imos es equidis an e de los pun os n−1no siendo
coolineaes. Es deci el conjun o de odos los pun os equidis an es de cada n-1 pun os
p1, p2, ..., pn−1no siemp e es una línea.
Axioma 4.9. Axioma n-Dimensional supe io pa a n= 2,3...
Axioma 4.10. Segunda o ma del Axioma de Euclides
β(abc)∨β(bca)∨β(cab)∨ ∃x[ax ≡bx ∧ax ≡cx]
Dado un iángulo (compues o po los segmen os dados) siemp e exis e un pun o equi-
dis an e a los é ices, lo que nos lle a a que odo iángulo puede se insc i o en un cí culo.
x
a
bc
Nó ese que no debemos echa de menos el axioma de las pa alelas pues es e es una
o mulación equi alen e.
Axioma 4.11. Axioma de con inuidad
∃a∀x∀y[x∈X∧y∈Y→β(axy)] → ∃b∀x∀y[x∈X∧y∈Y−→ β(xby)]
a b
X Y
Dados dos conjun os XeYde o ma que los elemen os de X p ecedan a los de Y con
espec o a un pun o a, en onces es án sepa ados po un pun o b
Todo es o compone la Geome ía elemen al de Ta ski, 2
2No obs an e ambién ideó un sis ema pa a oda la Geome ía pe o que no es udia emos en es e abajo.
4.2. APLICACIÓN DEL MÉTODO DE DECISIÓN A LA GEOMETRÍA ELEMENTAL41
4.2. Aplicación del Mé odo de Decisión a la Geome ía Ele-
men al
Al ededo del año 1930 Ta ski p ueba que su sis ema de geome ía admi e eliminación
de cuan i icado es, a pa i de es os es udios se p esen a como aplica el mé odo de decisión
a es e ámbi o, p obando que la geome ía elemen al en endida po Ta ski es comple a y
decidible.
Vol iendo a la p esen ación de Ta ski de la Co po ación Rand [5] e emos cómo aplica
el Mé odo de Decisión en es e ámbi o.
Lo que debemos hace es co elaciona cada sen encia φde geome ía elemen al con
una sen encia φ∗del álgeb a elemen al. Es deci , a cada a iable de φ, deno ada po ξse le
asignan dos a iables algeb aicas ¯
ξy¯
¯
ξde o ma que si enemos dos a iables dis in as ξe
η ambién lo se án ¯
ξ,¯
¯
ξ,¯ηy¯
¯η. Lo siguien e es pa icula iza los cambios de cada exp esión
del ámbi o de la geome ía elemen al, es o es:
La exp esión (Eξ)se eemplaza po (E¯
ξ)(E¯
¯
ξ).
La ó mula ξ=ηse eemplaza po (¯a= ¯η)∧(¯
¯
ξ=¯
¯η)
La ó mula β(ξ, η, µ)se eemplaza po
[(¯
¯η−¯
¯
ξ)·(¯µ−¯η)=(¯
¯µ−¯
¯η)·(¯η−¯
ξ)] ∧[((¯
ξ−¯η)·(¯η−¯µ)>0) ∨((¯
ξ−¯η)·(¯η−¯µ) = 0)]
∧[((¯
¯
ξ−¯
¯η)·(¯
¯η−¯
¯µ)>0) ∨((¯
¯
ξ−¯
¯η)·(¯
¯η−¯
¯µ) = 0)]
La ó mula D(ξ, η, µ, ν)po (¯
ξ−¯η)2+ (¯
¯
ξ−¯
¯η)2= (¯µ−¯ν)2+ (¯
¯µ−¯
¯ν)2
De es a o ma si la sen encia φes e dade a ambién lo se á φ∗y ice e sa.
4.3. Ampliación de las eo ías
A con inuación podemos p egun a nos si se ía posible aumen a las eo ías de inidas
con algunas p opiedades. Exis en espues as que ya conocemos como el hecho de añadi
concep os como “se en e o” o “se acional”,en es e caso sabemos que no exis i ía un mé-
odo de decisión en el sen ido que hemos dado y así no se pod ía cons ui la máquina.
Es o se sigue de los esul ados de Gödel-Chu ch-Rosse mencionados an e io men e y M s.
Robinson pa a el caso de acional. También iene el mismo esul ado añadi unciones pe-
iódicas como sin, es o es debido a que un núme o xes acional si y solo si e i ica la
ó mula
(Ey)(Ez)[(x·y=z)∧ ¬(y= 0) ∧(siny = 0) ∧(sinz = 0)]
42 CAPÍTULO 4. EXTENSIÓN A OTROS ÁMBITOS: GEOMETRÍA ELEMENTAL
En o os casos el p oblema sigue aún abie o, como es el caso de añadi la ope ación
exponenciación( es ingida a casos eales) deno ada po Exp3o el símbolo Cn que deno ase
la p opiedad de se un núme o cons uible4. No exis e oda ía espues a, an o posi i a o
nega i a pa a la p egun a de si exis e un mé odo de decisión. No obs an e las di icul ades
pa ecen se de ipo ma emá ico y puede que en los p óximos años se halle una solución
pa a el p oblema.
3P ecisa íamos de es nue os axiomas pa a inclui la (Ax)(Ay)[(x > y)→(Exp(x)> Exp(y))],
(Ax)(Ay)[(Exp(x)·Ep(y)) = Exp(x+y)] yExp(1) = 1 + 1.
4Es e es un ipo de núme o que indica que puede se ob enido a pa i del 1 median e las ope aciones
sumas, es as, mul iplicaciones, di isiones y aíz cuad ada. Añadi es a p opiedad esul a ía muy in e esan e
po que nos pe mi i ía no solo decidi la e dad de una sen encia de la geome ía elemen al si no ambién
decidi cuándo la e dad de una sen encia puede es ablece se usando solamen e egla y compás.
Apéndice
1. Todo el desa ollo del sis ema o mal pa a el álgeb a elemen al sigue un esquema
lógico básico, es deci , que se co esponde con la lógica de p ime o den de los nú-
me os eales jun o con la suma y la mul iplicación. En es as líneas se p opo ciona
un esumen de los concep os de lógica que son necesa ios pa a la comp ensión del
abajo.
La base de la lógica son los a gumen os, o mados po un conjun o de p emisas y una
conclusión luego son una se ie de ideas que desencadenan lógicamen e una úl ima.
Pueden se álidos o in álidos en cues ión de si su o ma es co ec a. Un a gumen o
es in álido si las p emisas pueden se odas e dade as y la conclusión alsa, en caso
con a io, es álido.
El p oceso de o malización del Álgeb a que se io en el Capí ulo 2 p ecisa de un
lenguaje que, al igual que se ía el caso del en o no lingüís ico, es á compues o po
un al abe o y una g amá ica.
El al abe o iene como elemen os las a iables, cons an es, unciones (y en conse-
cuencia ope aciones), los conec o es{⊥,¬,∨,∧,→,↔}, los cuan i icado es{∃,∀}, los
elemen os de ag upación y los p edicados. Sal o es os úl imos los an e io es es án
de inidos en la pa e p incipal del abajo. Los p edicados son ases que asignan
p opiedades y gene almen e se deno an con le as mayúsculas P, Q, R e c., son a-
ados como unciones y ambién podemos habla de a idad de un p edicado según
el núme o de elemen os que enga en cuen a. A pa i de a iables, cons an es, ope-
aciones y signos de ag upación podemos o ma é minos. Finalmen e una ó mula
a ómica se á un símbolo de p edicado n-a io seguido, en e pa én esis, po n é minos
sepa ados po comas.
La pa e de la g amá ica es á di idida a su ez en dos ámbi os: la sin axis y la
semán ica. La p ime a es udia las eglas de o mación de los elemen os del lenguaje
cuyo in es es ablece ó mulas bien o madas (a su ez compues as po é minos y
ó mulas a ómicas dadas al jun a elemen os del al abe o) y sen encias en el caso
43