=
CR´
ITICA,Re is a Hispanoame icana de Filoso ´
ıa
Vol. XXXI, No. 93 (diciemb e 1999): 21–47
TABLAS SEMÁNTICAS Y METALÓGICA (EL CASO
DE LA LÓGICA DE SEGUNDO ORDEN)∗
ÁNGEL NEPOMUCENO FERNÁNDEZ
Depa amen o de Filoso ía y Lógica y Filoso ía de la Ciencia
Uni e sidad de Se illa
1. In oducción
El mé odo de Be h, conocido como el mé odo de las a-
blas semán icas,1pe mi e la demos ación del eo ema de
sa is acción cuya o mulación puede se la siguien e:
Si Γes un conjun o consis en e de sen encias de p ime
o den, en onces Γes sa is acible en un uni e so ini o o
in ini o nume able.
A pa i de es e esul ado, Henkin2demues a la com-
ple i ud de la lógica de p edicados de p ime o den y señala
que el mé odo iene aplicación en el es udio de lógica de
o den supe io . Es deci , es e esul ado puede se ex endido
a lógicas supe io es, en pa icula a la de segundo o den,
de modo que de és as, aunque con cie as es icciones, se
puede p oba alguna o ma de comple i ud.
∗Sub encionado pa cialmen e po el P oyec o de In es igación
PB96-1301-C05-03 del Minis e io Español de Educación y Cul u a.
1También llamado de los á boles semán icos, po la p esen ación
a b´
o ea in e ida que se puede hace al cons ui las. Usa emos ambos
apela i os indis in amen e.
2V´
ease Henkin (1949) y Henkin (1950).
21
Esquemá icamen e, el mé odo de la p ueba de es e eo-
ema, pa a p ime o den, consis e en la ex ensión de Γaun
conjun o Γω al que sea máximamen e consis en e —inclui
una nue a ó mula lo ha ía inconsis en e— y ejempli icado
—si una ó mula del ipo ∃xϕ∈Γ, en onces ϕ(b/x)3∈Γ;
con iene alguna ins ancia de la ma iz pa a un pa áme o
(cons an e indi idual) del lenguaje. Se de ine además una
es uc u a in e p e a i a pa a dicho conjun o ex endido,
cuyo uni e so de discu so es el de cie as clases de equi-
alencia de pa áme os, po lo que es ini o o, a lo sumo,
nume able; se p ueba que dicha es uc u a sa is ace odas
las sen encias de Γωy, en consecuencia, ambién sa is ace
las del conjun o inicial Γ.
La comple i ud esul a en onces se un co ola io del eo-
ema de sa is acción: si Γ|=ϕ, en onces Γ∪{¬ϕ}es no
sa is acible, y po con aposición, Γ∪{¬ϕ}es no consis-
en e y, en consecuencia, Γϕ.
Aunque el mé odo de á boles semán icos iene algunos
an eceden es, como, po ejemplo en He b and, ue elabo-
ado po Be h, quien en 19554ideó una p ueba del mismo
eo ema de sa is acción y, po lo an o, de la comple i ud
de la lógica de p edicados de p ime o den, que iene sob e
el mé odo de Henkin la en aja de se más económica.
Pa a la nue a demos ación se de inen los á boles de
Be h y se p ueba que si Γes sa is acible, en onces el á bol
de Be h de Γes abie o; en segundo luga , se p ueba que
si el á bol de Be h de Γes ce ado, en onces Γes no
consis en e. De es o úl imo se sigue, po con aposición,
que si Γes consis en e, en onces el á bol semán ico de
Be h de Γno es ce ado (es abie o). En e ce luga , se
3Sus i ución de xpo ben ϕ, según se de ine más adelan e.
4Be h (1955); hay una e sión en español en Cuade nos Teo ema,
no. 18.
22
p ueba que si el á bol de Be h de Γno es ce ado, en onces
Γes sa is acible en un uni e so ini o o in ini o nume able.
El úl imo esul ado jun o con el an e io cons i uyen
una e sión del eo ema de sa is acción, y su p ueba es
muy simila a la de Henkin: a pa i de las sen encias
de cualquie a de las amas del á bol que haya quedado
abie a se de ine una es uc u a in e p e a i a y se p ueba
que la misma sa is ace odas las sen encias de las amas en
cues ión.
Se ad ie e, pues, una indudable u ilidad del mé odo en
lógica de p edicados de p ime o den. ¿Es asimismo aplica-
ble en lógica de p edicados de o den supe io , en pa icula ,
en la de segundo o den? Si pa a comp ende mejo la na u-
aleza de la cuan i icación hemos de a on a los p oblemas
que és a susci a cuando se ex iende a a iables de p edi-
cado, a ándose de un asun o nada i ial, la espues a a
dicha cues ión no puede se una espon ánea a i mación de
que al mé odo se ía aplicable, mu a is mu andi, a o den
supe io ; como ampoco una ap esu ada nega i a dada la
incomple i ud esencial de la lógica de segundo o den.
En es e abajo p esen amos el p ocedimien o de ablas
semán icas de Be h (y alguna modi icación del mismo) en
p ime o den. A con inuación se desc ibe b e emen e un
lenguaje o mal de segundo o den, des acando cie as cla-
ses de ó mulas. En el apa ado subsiguien e se abaja con
ablas aplicadas a (ma ices de) sen encias de es as clases,
de iniendo eglas adicionales pa a a a una de las clases en
cues ión. Po úl imo, se p esen a una se ie de obse acio-
nes sob e es as aplicaciones. A lo la go del ex o apa ecen
los eo emas (y un lema) que hemos conside ado ele an-
es; sus demos aciones se incluyen esquemá icamen e, o se
indica dónde pueden halla se, sal o en el caso del eo ema
9 y el lema necesa io pa a p oba lo, las cuales (y las de i-
niciones necesa ias), po su ex ensión, se han desa ollado
en un apéndice.
23
2. Reglas de o mación de á boles de p ime o den
Se han de especi ica las nociones necesa ias pa a las ablas
semán icas de p ime o den. A es os e ec os, hacemos uso
de L1, un lenguaje o mal de p ime o den sin iden idad ni
unc o es y con cons an es indi iduales y p edica i as (de-
nominados pa áme os y ela o es, espec i amen e). Un
á bol de Be h de sen encias es un conjun o de sucesiones
de sen encias de L1; es as sucesiones se denominan amas,
gene adas a pa i de un conjun o no acío de sen encias de
L1po aplicación a és as de las eglas de alladas más adelan-
e así como a las sen encias no elemen ales esul an es. Dis-
pues as sucesi amen e las sen encias gene ado as (que son
las asunciones iniciales), di emos que no es án con enien-
emen e ma cadas si no son elemen ales, cons i uyendo el
comienzo de una ama; a cada sen encia no elemen al no
con enien emen e ma cada se aplica á la egla co espon-
dien e, esc ibiendo a con inuación las sen encias esul an es
y se ma ca á con de e minado signo lógico como subíndice
(excep o cuando se a e de un cuan i icado , en cuyo caso
se ano a án los pa áme os u ilizados); el p oceso se con i-
núa has a que odas las sen encias no elemen ales queden
ma cadas o apa ezca un pa de con adicción, en endiendo
po al las sen encias elemen ales δyδde mane a que una
es negación de la o a.
Sea ϕuna sen encia no elemen al no con enien emen e
ma cada; las eglas se de inen en unción del g ado de
complejidad de ϕ:
1. si ϕes ¬ψ, en onces
(a) si ψes ¬β, en onces se añade β;
(b) si ψes β∧γ, en onces se añade ¬β∨¬γ;
(c) si ψes β∨γ, en onces se añade ¬β∧¬γ;
(d) si ψes β→γ, en onces se añade β∧¬γ;
24
(e) si ψes ∃xβ, en onces se añade ∀x¬β;
( ) si ψes ∀xβ, en onces se añade ∃x¬β;
además se ma ca ϕcon ¬como subíndice.
2. Si ϕes ψ∧β, en onces se añaden consecu i amen e
ψyβ, y se ma ca ϕcon ∧.
3. Si ϕes ψ∨β, en onces se ab en dos sub amas, una
con ψy o a con β, se ma ca ϕcon ∨, y decimos que
ϕes un pun o de bi u cación.
4. Si ϕes ψ→β, en onces se ab en dos sub amas, una
con ¬ϕy o a con β, se ma ca ϕcon →, y, asimismo,
decimos que ϕes un pun o de bi u cación.
5. Si ϕes ∃xψ, en onces se añade ψ(bk+1/x), siendo
bk+1 el pa áme o de meno subíndice que no ocu ía
an es en la ama (es deci , únicamen e ocu ían bi,
pa a i≤k), y se ma ca ϕcon dicho pa áme o.
6. Si ϕes ∀xψ, en onces se añaden ψ(b1/x), ψ(b2/x),...,
ψ(bn/x), siendo b1,...,bn odos los pa áme os que
ocu en en ó mulas de la ama.
Cuando en una ama apa ece un pa de con adicción
—en cuyo caso se de iene el p oceso, como se ha indica-
do— se dice que al ama es ce ada. Una ama es á aca-
bada si es ce ada o, en o o caso, si odas sus ó mulas
no elemen ales es án con enien emen e ma cadas. Un á -
bol es ce ado cuando odas sus amas son ce adas. Un
á bol es á acabado cuando odas sus amas es án acabadas.
La p opiedad undamen al de los á boles semán icos se ex-
p esa en el siguien e eo ema cuya demos ación omi imos
pa a ab e ia .5
5En Be h (1955) apa ece la p ueba del “ eo ema de á boles”; una
demos ación del eo ema al como se o mula a con inuación, apa ece
25

Teo ema 1: Dados un conjun o Γde sen encias y una
sen encia ϕ∈L1,Γ|=ϕsi y sólo si el á bol de Γ∪{¬ϕ}
es ce ado.
También se puede enuncia diciendo que ϕes sa is aci-
ble si y sólo si el á bol de {ϕ}es abie o. A pa i de una
ama abie a se de ine una L1-es uc u a que sa is ace odas
las sen encias de la ama en cues ión. Es a L1-es uc u a
ep esen a una clase de L1-es uc u as que sa is acen ϕ.
Además de los á boles de BETH, omamos los á boles ∃-
modi icados6ob enidos median e una lige a modi icación
de la de inición del á bol espec o de las sen encias a que
dan luga las ó mulas de la o ma ∃xϕ. Veamos la de ini-
ción de la cláusula co espondien e en un caso y o o:
1. BETH. Se a a de la egla 5 ci ada: Si en una ama apa-
ece una ó mula de la o ma ∃xψy es á con enien e-
men e ma cada, en onces apa ece ambién ψ(bk+1/x),
siendo bk,k≥1, el úl imo pa áme o que ocu ía en
la ama (an es de aplica la egla 5).
2. ∃-MODIFICADOS. La an e io egla 5 se e o mula de
la siguien e mane a: Si ϕes ∃xψ, en onces se ab en
sub amas cada una de ellas con ψ(bi/x), pa a cada
i≤k+ 1, siendo bk,k≥0, el úl imo pa áme o
en Nepomuceno (1995), pp. 45–49 y 58–60 —pa a lógica p oposicional
y pa a lógica de p edicados de p ime o den, espec i amen e.
6Díaz (1993) y Boolos (1984) idea on un a amien o especial pa a
ó mulas que gene an á boles in ini os pe o que son sa is acibles en
dominios ini os. En Díaz (1993, p. 43) apa ece una b e e no a ace ca
del momen o en que apa ece al a amien o.
En es e pun o, como en o os a lo la go del abajo, hemos de
econoce la deuda con a´
ıda con las ideas expues as en Díaz (1987) y
Díaz (1993) (así como las incluidas en documen os inédi os del mismo
au o ), especialmen e las nociones de ∆- ó mulas y las eglas especiales
pa a de e minados lenguajes.
26
que ocu ía en la ama (an es de la aplicación de es a
egla) y se ma ca ϕcon |b1|,...,|bk|,bk+1.7
Los á boles ob enidos aplicando es a nue a egla poseen
cie as en ajas sob e los de Be h. Veámoslo en un senci-
llo ejemplo: Sea la sen encia ∀x∃yRxy; el á bol de Be h
end ía una única ama in ini a, pe o es a ó mula es sa is-
acible en un uni e so de un único indi iduo. En el á bol
∃-modi icado, hab ía una ama con exac amen e las siguien-
es sen encias:
<∀x∃yRxy,∃yRa1y,Ra1a1>,
la cual pe mi e de ini una L1-es uc u a que sa is ace odas
las ó mulas de dicha ama, con al de que se in e p e en
el p ime pa áme o y el ela o de la mane a adecuada,
aunque ambién con enga amas in ini as, como
<∀x∃yRxy,∃yRa1y,Ra1a2,∃yRa2y,Ra2a3,...>.
3. Un lenguaje o mal de segundo o den
L2es un lenguaje o mal de segundo o den ob enido a pa -
i de L1, incluyendo a iables p edica i as y no es in-
giendo la cuan i icación a las a iables indi iduales. Así
pues, si ϕes una ó mula de L2yses una a iable de
cualquie ipo (indi idual o p edica i a de cie a a idad),
en onces ∃sϕ, ∀sϕson ó mulas, y se dice que ses el su ijo
del cuan i icado co espondien e. Las ó mulas de L2que
7De es e modo, las ma cas |bi|,i≤kexp esan que se a a de
amas ob enidas po la nue a egla, mien as que la ma ca bk+1 indica
que se a a de una ama co espondien e a un á bol de Be h.
27
ca ezcan de a iables lib es se án denominadas sen encias,
como es usual.
Sea ϕ∈L2, de inimos ϕ( /s), donde ses una a iable y
una a iable indi idual o pa áme o, si ses indi idual, o
bien una a iable p edica i a o ela o de la misma a idad
que s, si és a es p edica i a, según las cláusulas:
1. Si sno ocu e, o no ocu e lib e, en ϕ, en onces ϕ( /s)
es ϕ.
2. Si es su ijo de un cuan i icado bajo cuyo alcance
cae s, en onces ϕ( /s)esϕ.
3. En o o caso, ϕ( /s) es la ó mula esul an e de sus-
i ui cada ocu encia lib e de sen ϕpo .
Pa a ep esen a la sus i ución en ϕde s1ys2po 1y
2—siemp e que sean del ipo co espondien e— se
ano a á ϕ( 1, 2/s1,s2); en gene al, pa a sus i ución de
n≥1 é minos, o sus i ución simul ánea, la no ación
es
ϕ( 1,..., n/s1,...,sn).
La semán ica de L2queda es ablecida de la siguien e
mane a: Una L2-es uc u a iene dada po un dominio o
uni e so de discu so y una unción in e p e ación:
M=<D,>,
en donde  ep esen a la denominada unción in e p e a-
ción, de inida con dominio en los pa áme os y ela o es y
ango en D(y en los p edicados y elaciones de inidos en
D) de mane a que
1. Pa a cada pa áme o b,(b)∈D.
28
2. Pa a cada ela o n-ádico R,(R)∈P(Dn), pa a odo
n≥1.
La noción de sa is acción y las es an es nociones semán-
icas ( alidez en un dominio, alidez uni e sal, e c.) son las
usuales. Si ϕ∈L2es una sen encia M|=ϕindica que M
sa is ace dicha sen encia; si Γes un conjun o de sen encias,
Γ|=ϕindica que ϕes consecuencia lógica de Γ.
Podemos conside a que los ela o es de L1son ambién
ela o es de L2. Asimismo, cada ó mula de L1como una
ó mula de L2. En gene al, si ϕ∈L2,X1,...,Xk, son sus
a iables p edica i as, R1,...,Rkson ela o es ales que
la a idad de Ries la misma que la de Xi, pa a odo i≤k,
y se e i ica que
ϕ(R1,...,Rk/X1,...,Xk)∈L1,
en onces di emos que ϕes esencialmen e de p ime o den.
Respec o de ó mulas de L2en o ma p enexa, el eo ema
de Zyko es ablece:
Pa a oda sen encia ϕ∈L2se puede ob ene una sen encia
ψen o ma p enexa en la que los cuan i icado es p edica-
i os p eceden a los cuan i icado es indi iduales, ales que
|=ϕ↔ψ.8
La demos ación equie e la adopción de la semán ica
con axioma de elección. Po aho a, p obadas una se ie de
equi alencias p e ias, lo que omi imos en a as de la b e e-
dad, se ob iene:
8ϕ↔ψse puede conside a ab e ia u a de (ϕ→ψ)∧(ψ→ϕ)
(de o o modo, ácilmen e se ede ini ía Lcon eniendo es e signo). La
demos ación o iginal de Zyko (1956), es ela i a a o den supe io ;
en Hilbe -Acke mann (1962) apa ece un esumen de su adap ación a
segundo o den.
29
Lema:12 Dadas una sen encia Qγsiendo QyQp e-
ijos cuan i icacionales p edica i os, y una L2-es uc u a
M
1. Si Qes ∃X,M|=Qγsi y sólo si pa a odo i≤k,
δi∈∆(γ,X),|∆(γ,X)|=k,
M|=Qγ(δ1/X)∨Qγ(δ2/X)∨...∨Qγ(δk/X);
2. Si Qes ∀X,M|=QQγsi y sólo si pa a odo i≤k,
δi∈∆(γ,X), |∆(γ,X)|=k,
M|=Qγ(δ1/X)∧Qγ(δ2/X)∧...∧Qγ(δk/X).
La demos ación del Teo ema 9 es análoga a la del Teo-
ema 4, eniendo en cuen a es e lema. .
5. Obse aciones sob e es as aplicaciones
De acue do con la me odología expues a, hemos ex endido
el p ocedimien o de á boles de p ime o den, eniendo en
cuen a la modi icación incluida pa a el a amien o de la
clase de las IZ, de mane a que podemos eseña algunas
consecuencias, pa a lo cual end emos en cuen a los esul-
ados an e io es y los siguien es.
Teo ema 10: Pa a oda sen encia β∈Π1
1(1
1)exis e
o a sen encia β∗∈1
1(Π1
1), ales que |=βsi y sólo si β∗
es no sa is acible.
En e ec o, sea βde la o ma ∀X1,...,Xmϕ,m≥1.
Ob iamen e, |=βsi y sólo si ¬βes no sa is acible, pe o
¬∀X1,...,Xmϕ←→ ∃ X1,...,Xm¬ϕ,
12 Como en el caso de las nociones necesa ias pa a la demos ación,
hemos incluido és a en el apéndice.
36

y∃X1,...,Xm¬ϕ∈1
1. De mane a análoga, si βes de la
o ma ∃X1,...,Xmϕ, en onces β∗se ía ∀X1,...,Xm¬ϕ.
.
Teo ema 11: Pa a cada β∈Π1
1 al que ∀Z1,...,Zkβ∈
Π1
1y ca ezca a iables lib es,13 son equi alen es:
1. |=β(R1,...,Rk/Z1,...,Zk), siendo Ri ela o de la
misma a idad que Zi, pa a odo i≤k;
2. |=∀Z1,...,Zkβ;
3. si βes ∀X1,...,X ϕ, ≥1, el á bol semán ico de
¬ϕes ce ado.
La demos ación es i ial a pa i de la e aluación de ∀
y del Teo ema 8. .
Teo ema 12: Pa a cada β∈1
1 al que ∃Z1,...,Zkβ∈
1
1y ca ezca a iables lib es, son equi alen es:
1. β(R1,...,Rk/Z1,...,Zk) es sa is acible, siendo Ri e-
la o de la misma a idad que Zi, pa a odo i≤k;
2. ∃Z1,...,Zkβes sa is acible;
3. si βes ∃X1,...,X ϕ, ≥1, el á bol semán ico de ϕ
es abie o.
En e ec o: (1) si y sólo si (2) po e aluación de ∃; (2) si
y sólo si (3) si enemos en cuen a el Teo ema 4; (3) si y
sólo si ϕes sa is acible (esencialmen e de p ime o den) si
y sólo si lo es la sen encia
ϕ(R1,...,Rk,S1,...,S /Z1,...,Zk,X1,...,X ),
donde Sjes ela o de la misma a idad que Xj, pa a odo
j≤ , si bien és a es sa is acible si y sólo si
13 Z1,...,Zkson las a iables lib es de β, pudiendo ocu i ela-
o es.
37
∃X1,...,X ϕ(R1,...,Rk/Z1,...,Zk),es sa is acible,
pe o ∃X1,...,X ϕ(R1,...,Rk/Z1,...,Zk) es p ecisamen-
e β(R1,...,Rk/Z1,...,Zk), luego (3) si y sólo si (1).
Respec o de las clases 1
1yΠ1
1hemos ob enido esul-
ados en pa e espe ados. Pe o el es udio de la clase IZ
se puede conside a más no edoso. Van Ben hen y Doe s
(1984) se habían ocupado de las p ime as, aunque no de
es a úl ima; el lenguaje o mal de p ime o den que u ili-
zan es un lenguaje con iden idad. En cualquie caso, cab ía
conside a el mé odo de los á boles al e na i o a aquel que
ecu e a depu adas nociones de eo ía abs ac a de mode-
los ( eo ía de il os: ul ap oduc o, ul apo encia, colapso,
e c.). Si bien nos hemos e e ido p incipalmen e a sen en-
cias en las cuales no ocu ían ela o es, sino sólo a iables
p edica i as ligadas, a pa i de los úl imos esul ados es
posible una ampliación de la aplicación del mé odo. Asi-
mismo, al ope a sob e sen encias en o ma p enexa con
cuan i icado es indi iduales p ecediendo a odos los cuan-
i icado es p edica i os, en el desa ollo de un á bol semán-
ico, se ob ienen sen encias de IZ, con las cuales se puede
con inua si enemos en cuen a lo es udiado más a iba.
Si la aplicabilidad del mé odo de ablas semán icas en
lógica de segundo o den no nos lle a a log os espec acula-
es, nos pe mi e, al menos, alcanza cie os esul ados desde
o a pe spec i a, lo que in i a a con inua la e lexión sob e
la na u aleza misma de la cuan i icación, cómo se pueden
plan ea ex ensiones de lógica elemen al, e c. En pa icula ,
si a pa i del mé odo de Be h es demos able la comple-
i ud de los sis emas de cálculo de p ime o den. ¿Qué se
puede deci ace ca de los sis emas de cálculo de segun-
do o den as las modi icaciones p opues as? La co ección
38
de es os sis emas es un esul ado conocido, ambién que
la comple i ud es imposible como consecuencia del eo e-
ma de incomple i ud de sis emas o males a i mé icos de
G¨
odel.14 No obs an e, adop ando la nue a semán ica p o-
pues a po Henkin,15 es demos able que los sis emas de
cálculo de segundo o den son comple os en sen ido gene al.
Conside emos un sis ema de cálculo ipo Hilbe (am-
pliado a segundo o den), que ep esen amos po (“α”
indica que la ó mula αes demos able en dicho cálcu-
lo). Adop ando la semán ica es ánda , la incomple i ud de
podemos enuncia la de la siguien e mane a: exis e una
sen encia γ∈L2 al que |=γpe o no es el caso que γ;
a pa i de la ó mula a i mé ica cons uida po G¨
odel es
de inible una al sen encia γ. No obs an e, cabe espe a una
cie a comple i ud, sin necesidad de cambia la semán ica
es ánda , siemp e que sea ela i a a una clase es ingida de
sen encias, que desde luego no con end á ó mulas como
la mencionada.
Sea la clase F∆⊆L2, al que e i ica
1. Si ϕ∈L2yϕ∈1
1∪Π1
1∪IZ, en onces ϕ∈F∆.
2. Si ψes la o ma p enexa de ϕyψ∈F∆, en onces
ϕ∈F∆.
Respec o de es a clase, y eniendo en cuen a los esul a-
dos an e io es, se pod á es ablece que pa a cada ϕ∈F∆,
si |=ϕ, en onces ϕ, y, dada co ección de ,
14 Manzano (1996) ha p esen ado una p ueba di ec a de incomple-
i ud, al ma gen del eo ema de G¨
odel; dicha p ueba es á basada en
cie as écnicas de eo ía de conjun os y en la capacidad exp esi a que
ca ac e iza la lógica de segundo o den.
15 En Henkin (1950). Esquemá icamen e, en sen ido gene al, en
las es uc u as in e p e a i as se ienen en cuen a el uni e so de dis-
cu so (no acío) y ambién uni e sos elacionales (pa a cada a idad),
los cuales poseen cie as ca ac e ís icas algeb aicas, como se desc ibe
en Manzano (1996), lo cual equi ale a que odas las elaciones son
de inibles (con el lenguaje o mal de que se a e).
39
pa a cada ϕ∈F∆,|=ϕsi y sólo si ϕ.
6. Ap´
endice
Conside amos aho a el lenguaje o mal L2=, ob enido a
pa i de L2con el ela o diádico =y conside ando que
si aybson a iables indi iduales o pa áme os, a=b∈
L2=. Pa a mayo acilidad, se esc ibi á a=ben luga
de ¬(a=b). Po lo que espec a a la semán ica de L2=,
si M=<D,>, pa a cualesquie a pa áme os ayb,
M|=a=bsi y sólo si (a)=(b).16
De inimos, pa a βy cada a iable p edica i a n-ádica
X, el conjun o de ó mulas ∆(β,X) po inducción sob e
el g ado de complejidad de β(pa a simpli ica , conside a-
emos que ¬y∨son las únicas conec i as que ocu en en
β). ∆(β,X) es el más pequeño conjun o que e i ica:
1. Si en βno ocu e X, en onces ∆(β,X)=∅.
2. Si βes Xb1...bn, en onces ∆(β,X)={δ, ¬δ},en
donde δes x1=b1∧...∧xn=bn. Po o a pa e,
se dice que δes posi i a,y¬δnega i a.
3. Si βes ¬γ, en onces ∆(β,X)=∆(γ,X).
4. Si βes γ∨η, en onces, ∆(β,X) es el mínimo conjun o
al que:
i. Si θ∈∆(γ,X)oθ∈∆(η,X)yθes posi i a,
en onces θ∈∆(β,X).
ii. Pa a oda i,j≥1, si θi∈∆(γ,X)oθj∈∆(η,X)
y ambas son posi i as, en onces θi∨θj∈∆(β,X).
iii.Pa a n>1, oda i≤n,siϑi∈∆(γ,X)oϑi∈
∆(η,X)yϑies nega i a, en onces ϑ1∧...∧ϑn∈
∆(β,X).
16 Fácilmen e se comp ueba que |=a=b↔∀X(Xa ↔Xb).
40
5. Si βes Qγ, donde Qes un p e ijo cuan i icacional
cuyos su ijos son Z1,...,Zm, las m≥1 a iables p e-
dica i as dis in as de Xque ocu en en γ, en onces
∆(Qγ,X)=∆(β(R1,...,Rm/Z1,...,Zm),X),
siendo Riun ela o de la misma a idad que Zi, pa a
oda i≤m.
Los á boles más a iba de inidos se pueden modi ica
añadiendo:
1. Si en una ama ocu e una sen encia de la o ma b=
b, en donde bes un pa áme o cualquie a, en onces
se p oduce el mismo e ec o que si se a a a de un
pa de con adicción; es deci , la ama es ce ada.
2. Si en una ama ocu en ó mulas de la o ma β(aj/x)
yai=aj, siendo és os unos pa áme os ales que
i≤j, en onces se achan odas las ó mulas β(aj/x)
y se sus i uyen po β(ai/x) ( ambién se pueden acha
las mencionadas ó mulas de iden idad).
Dada una ó mula de la clase IZ, que end á, po an o,
la o ma Q1Q2β, en donde βes esencialmen e de p ime
o den, y eniendo en cuen a la modi icación de las eglas de
los á boles espec o de ó mulas de iden idad, se de inen
las siguien es nue as eglas especí icas pa a el p e ijo Q2
(pa a la cons ucción de á boles an o de Be h, como ∃-
modi icados, aunque ya especí icos de segundo o den). Sea
un pun o del á bol en que la ó mula a ma ca iene la
o ma Q2βyβno con iene a iables indi iduales; pa a
mayo acilidad conside emos que |Q2|=1 y, po an o,
únicamen e ocu e un cuan i icado p edica i o, en onces
1. Si Q2βes ∃Xβ,X a iable p edica i a de a idad
n≥1, en onces se ab en sub amas cada una con
41

β(ρi(b1,...,bn/x1,...,xn)/Xb1,...,bn),
pa a oda ρi∈∆(β,X), ma cándose la ó mula inicial
con dichas ρicomo subíndices.
2. Si Q2βes ∀Xβ,X a iable p edica i a de a idad
n≥1, en onces se añaden a la ama las ó mulas
β(ρi(b1,...,bn/x1,...,xn)/Xb1,...,bn),
pa a oda ρi∈∆(β,X), ma cándose la ó mula inicial
con dichas ρicomo subíndices.
Demos ación del Lema: [Inducción sob e el g ado de
complejidad de Qγ.] Comencemos conside ando el caso
en que Q=∅:
1. γes Xb1...bn, pa a n≥1. En al caso, pa a cada
L2-es uc u a M
•M|=(b1=b1∧...∧bn=bn)∨(b1=b1∨...∨bn=
bn), asimismo M|=∃Xγ(ambas son álidas en el
co espondien e dominio);
•Mno sa is ace (b1=b1∧...∧bn=bn)∧(b1=
b1∨... ∨bn=bn), pe o Mno sa is ace ∀Xγ
ampoco.
2. γes ¬η; po hipó esis, M|=∃Xη⇐⇒ 17 M|=
η(δ1/X)∨...∨η(δk/X), pa a δi∈∆(ηX), i≤k
yk≥1; asimismo, M|=∀Xη⇐⇒ M|=η(δ1X)∧
...∧η(δkX), pa a δi∈∆(ηX), i≤kyk≥1; además
∆(γ,X)=∆(η,X). En onces, M|=∃X¬η⇐⇒
M|=¬∀Xη⇐⇒ no-(M|=∀Xη)⇐⇒ no-(M|=
η(δ1/X)∧...∧η(δk/X)) ⇐⇒ M|=¬η(δ1/X)∨...∨
17 Ab e ia u a que indica la equi alencia en e las p oposiciones
ano adas a sus ex emos. Es deci , A⇐⇒ B, ep esen a “si A, en onces
B, y si B, en onces A”.
42
¬η(δk/X). Recíp ocamen e, M|=∀X¬η⇐⇒ M|=
¬∃Xη⇐⇒ no-(M|=∃Xη)⇐⇒ no-(M|=η(δ1/X)∨
...∨η(δk/X)) ⇐⇒ M|=¬η(δ1/X)∧...∧¬η(δk/X).
3. γes η∨θ. Es ablecemos, según la de inición dada más
a iba, ∆(γ,X)=∆
∗, es el más pequeño conjun o al
que:
i) si δ∈∆(η,X)óδ∈∆(θ, X)yδes posi i a,
en onces δ∈∆∗;
ii) pa a odo i,j,siδi∈∆(η,X), δj∈∆(θ,X)y
ambas son posi i as, δi∨δj∈∆∗;
iii) pa a odo i,j,siδi∈∆(η,X), δj∈∆(θ,X)y
ambas son nega i as, δi∧δj∈∆∗.
Se nos p esen an dos casos:
(a) M|=∀X(η∨θ), en onces pa a oda asignación sde
alo es a las a iables se e i ica que M,s|=η∨θ;18
en onces, pa a cada δk∈∆(η/X), δm∈∆(θ/X),
M|=η(δk/X)óM|=θ(δm/X). Si δ∈∆∗po
i), M|=η(δ/X)óM|=θ(δ/X); si δ∈∆∗es
δk∨δm, de inida po ii), M|=η(δk∨δm/X)óM|=
θ(δk∨δm/X); si δ∈∆∗es δk∧δmde inida según iii),
M|=η(δk∧δm/X)óM|=θ(δk∧δm/X). Es deci ,
pa a cada δ∈∆∗,M|=η(δ/X)∨θ(δ/X), luego
M|=(η∨θ)(δ/X); si |∆∗|= ,M|=(η∨θ)(δ1/X)∧
...∧(η∨θ)(δ /X). Recíp ocamen e, si |∆∗|= , pa a
δi∈∆∗,i≤ ,M|=(η∨θ)(δ1/X)∧...∧(η∨
θ)(δ /X), en onces M|=(η(δ1/X)∨θ(δ1/X))∧...∧
(η(δ /X)∨θ(δ /X)), de donde, pa a oda asignación s,
M,s|=η∨θ, y, po e aluación de ∀,M|=∀X(η∨θ).
18 En el caso básico, M,s|=Xb1,...,bnpa a oda asignación ssi
y sólo si M|=(b1=b1∧...)∧(b1=b1∧...) (ninguna es sa is echa
po es a es uc u a). Po inducción, se es ablece que M,s|=γ, pa a
oda asignación s, si y sólo si M|=γ(δ1/X)∧...∧γ(δ X) pa a oda
δi∈∆(γ,X),|∆(γ,X)|= .
43
(b)M|=∃X(η∨θ), en onces pa a alguna asignación s,
M,s|=η∨θ; de mane a análoga al caso p eceden e,
hay alguna δ∈∆∗ al que M|=(η∨θ)(δ/X), es
deci , M|=η(δ/X)∨θ(δ/X). Teniendo en cuen a
la cons ucción de ∆∗, se alcanza que M|=(η∨
θ)(δ1/X)∨...∨(η∨θ)(δ /X). Recíp ocamen e, pa a
δi∈∆∗,i≤ ,siM|=(η∨θ)(δ1/X)∨...∨(η∨
θ)(δ /X), en onces M|=(η(δ1/X)∨θ(δ1/X))∨...∨
(η(δ /X)∨θ(δ /X)), de donde, pa a alguna asigna-
ción s, se e i ica M,s|=η∨θ, y, po e aluación de
∃,M|=∃X(η∨θ).
Conside emos aho a que |Q|=m≥1, siendo
Z1,...,Zmlas a iables (p edica i as) su ijo de los mcuan-
i icado es que in eg an Q. Hab emos de ene en cuen a
la cláusula 5 que de ine ∆(Qγ,X)=∆(γ(R1,...,Rm/
Z1,...,Zm),X); llamamos γa la ó mula γ(R1,...,Rm/
Z1,...,Zm). En onces:
1. M|=∃XQγ; en onces pa a alguna asignación s,
M,s|=Qγ; pa a cada δi∈∆(γ,X), i≤ , asig-
nación s(que di ie e de sa lo sumo con espec o
de los alo es de R1,...,Rm), M,s|=γ(δ1/X)∨
...∨γ(δ /X).19 Fácilmen e (i e ando el caso de dis-
yunción is o an e io men e) se alcanza que M,s|=
Qγ(δ1/X)∨...∨Qγ(δ /X) (asimismo, ecíp oca-
men e).
2. M|=∀XQγ; en onces pa a oda asignación s,
M,s|=Qγ; pa a cada δi∈∆(γ,X), i≤ , asig-
nación s(que di ie e de sa lo sumo con espec o
de los alo es de R1,...,Rm), M,s|=γ(δ1/X)∧
19 En es e apa ado, como en el siguien e, cab ía dis ingui a ios
casos: Q=∀Z1∀Z2,oQ=∀Z1∃Z2,oQ=∃Z1∀Z2,oQ=∃Z1∃Z2
(con lo que m=2); supues o pa a Q∗, es udia el de Q=Q∗∀Zmo
Q=Q∗∃Zm, eniendo siemp e en cuen a el modo de e aluación de
los cuan i icado es (cuyo de alle omi imos pa a ab e ia ).
44
...∧γ(δ /X). Fácilmen e ( eniendo en cuen a el ca-
so de disyunción ambién is o an es) se alcanza que
M,s|=Qγ(δ1/X)∧...∧Qγ(δ /X) (asimismo, e-
cíp ocamen e). .
BIBLIOGRAFÍA
an Ben hem, J. y K. Doe s, 1984, “Highe -O de Logic”,
Handbook o Philosophical Logic, Gabbay y Gen hne
(comps.), Kluwe Adademic Publishe s, Do d ech ,
ol. I, pp. 275–330.
Be h, E.W., 1955, “Seman ic En ailmen and Fo mal De-
i abili y”, en J. Hin ikka (1969), The Philosophy o
Ma hema ics, Ox o d Uni e si y P ess Lond es. [T a-
ducido en Cuade nos Teo ema, no. 18, “En añamien o
semán ico y de i abilidad o mal”, Valencia, 1978.]
Boolos, G., 1984, “T ees and Fini e Sa is ac ibili y”, No e
Dame Jou nal o Fo mal Logic, ol. 25, pp. 110–115.
Díaz, E., 1993, “ ´
A boles semán icos y modelos mínimos”,
Mad id, Ac as del I Cong eso de la Sociedad de Lógi-
ca, Me odología y Filoso ía de la Ciencia en España,
pp. 40–43.
——, 1987, “Conjun os enume ables ep esen a i os de
conjun os no enume ables”, Colloquium 1985–1986, Ba-
dajoz, ol. 15, pp. 51–66.
Henkin, L., 1950, “Comple eness in The Theo y o Types”,
en Hin ikka (1969), pp. 53–63.
——, 1949, “The Comple eness o The Fi s -O de Func-
ional Calculus”, en Hin ikka (1969), pp. 42–52.
Hilbe , D. y W. Acke man, 1962, Elemen os de lógica
eó ica. [T ad. V. Sánchez de Zabala, 6aedición), Tec-
nos, Mad id.
Manzano, M., 1996, Ex ensions o Fi s O de Logic, Cam-
b idge Uni e si y P ess, Camb idge.
45