Los mtodas de la lgica

Agrupamos los mtodos de la lgica en tres grandesrbricas:

- Mtodos sintcticos.- Mtodos semnticos.- Mtodas algortmicos.

Entre los primeros estudiaremos el mtodo axio-tico y los sistemas de deduccin natural. Dentro delsegundo apartado consideraremos el mtodo de lastablas semnticas y la utilizacin de interpretaconesy modi3los para pruebas de independencia, y engeneral la importancia deeisiva y la fecundidad delenfoque semntico para la demostracin de los prin-cipales metateoremas. Bajo la tercer clase de mtodosnos referiremos a los mtodos de decisin y los pro-blemas conectados con la decibilidad.

1. METODOS SINTAGTICflS

La sintaxis es aquella parte de la semitica o cienciageneral de los signos que se ocupa de las relacionesde los signos entre s, prescindiendo de lo que desig-nan y significan. Las otras dos partes, la semnticay la pragmtica, se ocupan respectivamente de lasrelaciones de los signos con los objetos a que serefieren y de las relaciones de los signos con lossujetos que los usan. Esas tres dimensiones de lossignos estn sin duda alguna vinculadas entre s.cLa relacin pragmtica supone la semntica y iasintctica; la semntica supone la sintctica. Unapalabra sin sentido no puede servr para entenderse,y para que una palabra tenga sentido debe estar endetermnadas relaciones con las otras palabras. Encambio, la relacin sintctica no supone tas otrasdos y es posible estudiar la semntica sin atendera la pragmtica (1 ).

Aunque esta famosa divisin de la semibtica esgeneralmente aceptada, el acuerdo ya no es tanunnime cuando se trata de dividir a su vez en puray descriptiva cada una de las partes. Y en particularhay lgicos actuales que consideran deseabli3 unanueva definicin de algunos conceptos semiticosbsicos, puesto que, segn ellos, la distincinentre sintaxis y semntica no es en modo algunotan clara como puede parecer por las definicionesrespectivas. En la prctica, tal como se usan esostrminos, no slo son un tanto vagos, sino que, sinduda aiguna, se solapan en sus significaciones;solapamiento que est reconocido por Tarski (2).Sin emprender ahora anlisis pormenorizados alrespecto, nos limitaremos a emplear aqu los trminoscsintaxis ysemntica en un sentido amplio como

Por Maximiliano FARTOS MARTINEZ{')

marcos para encuadrar los diferentes mtodoslgicos.

1.1. EI mtodo axiomticoLa caracterstica fundamental de toda teara

axiomatizada es la divisin de todos los enunciadosdel campo del saber que en ella se trate en dosclases:

a) La de los axiomas o postulados aceptados enprincipio, en razn de su evidencia o porsimple convencibn razonable.

b) La de los teoremas, que son los enunciadosdeducimos a partir de los axiomas por inferen-cia lgica.

Puede decirse que la silogstica arisiotlica fueaxiomatizada por su fundador al conseguir are-ducir el resto de los modos silogsticos vlidos -aunos pocos de ellos tomados como primitivos. Sa-bemos tambin que los estoicos axiomatizaron laspropias reglas de su lgica. No obstante, la axioma-tizacin considerada como modlica durante siglosfue la contenida en los Elementos de Euclides: En lossiglos XVII y XVIEI no slo la filosofa natural sefijaba en ese modelo, sino que incluso la filosofaut talis pretendi presentar sus demostracionesmore ,qeomtrico. Recurdese la Etica de Espinoza.Vieta y Leibniz con su preocupacin por la formaliza-cin del lenguaje matemtico y lgico fomentaronsin duda el desarrollo del estilo axiomtico. Peroel hecho decisivo para e1 despliegue sistemtico quedespus haba de conocer dicho rntodo fue el des-cubrimiento de las geometras no euclidianas. En elpresente trabajo nos veremos forzados a referirnosvarias veces a este acontecimiento trascendental dela historia de la ciencia. Entonces los matemticosse vieron abocados a suplir cada vez ms la antiguaconfianza en la intuicin por el rigor lgico de lasdemostracones. Siguiendo esta nueva direccinse vio la necesidad de Ilepar a sustituir las teorfas

' Catedrtico de la Universidad Cornplutense.(1} BOCHENSKI, Los mtodos aciuales del pensa-

miento, Madrid, 1968, 74-75.(2} CUFiRY y FEYS.: Lgica combinatoria, Madrid,

1967, 60, 59, 61. Cfr. MpRRIS, Ch.: Fundamenros de lateoria de /os signos, Mxico, 1958. CARNAP: lntrpductionto semantics, Harvard University Press, 1961. LogischeSyntax der Spracfie, Viena, 1"934. TARSKI: aDer Wahr-heitsbegriff in den formalisierten Sprachen en StudiaPhi/osoph:, vol. 1, 1936, 261-405. La concepcibn semnticade /a verdad y los fundamentos de /a semSntica, BuenosAires, 1972.

35

deductivas concretas por teortas deductivas apuras,en las que no slo no se parte ya de unos axiomas opostuladas considerados como evidentes, sino queni siquiera los trminos primitivos del sistema quedanrestringidos a una determinada interpretacin. Siadems las reglas empleadas en la deduccin de losteoremas son expticitamente formuladas, sin permi^tir entrar en juego ninguna otra por mas intuitiva-mente evidente que parezca, entonces se habrr7efiminado los elementos ingenuos y se habt Ile-gado a la canstruccin de un sistema /ormal. AHilbert se debe en primer lug8r ael subrayar que laformalizacin estricta de una teora envueive la totalabstraccin del significado, dando por resuitado loque se denomina un sistema formal o tormalismo,y en segundo lugar se le debe su mtodo consistenteen hacer del sistema formal, considerado como untodo, el objeto de un estudio matemtico denominadomatemStrco o teorla de la demostracin (3). En unsistema de objetos ea el que se efecta esa abs-abstraccin total del significado los objetos delsistema son conocidos slo mediante las relacionesdel sisiema. Lo que se establece es la estructura delsistemat ' dejando sir. especificar qu sean esosobjetos en cuales quiera de sus respectos, con laexcepcin del que se refiere a saber cmo encajan.en dicha estructurau. Ulteriormente puede hallarseuna representacin (o modelo) del sistema abs-trac^o, esto es, un sstema de objetos que satisfacelas relaciones del sistema abstracto y tiene ademsun estatoo propio. Por otra parte, estos objetosdel modelo pueden ser elegidos tambin de algnotro sistema abstracto (o incluso del mismo sistemade que se trate bajo una reinterpretacin de sus rela-ciones (4). Asf pues, podemos afirmar que unsistema formaf es esencialmente un conjunto deteoremas obtenidos mediante reglas precisas y re-ferentes a objetos indeterminados (5).

Para obviar las ambigiiedades; redundancias y di-ficultades de todo tipo propias de 1os lenguajesnaturales, cuando se los pretende emplear con finescientficos, la construccin de sistemas formales vanormalmente precedida o acompaada de fa elabora-cin de lenguajes artificiales apropiados. f^o obs-tante incluso una lengua "naturai'` (corriente)pudiera, en principio, ser formalizada, mientras quecabe muy bien considerar un lenguaje artificial comono formalizado (6). Los sistemas formales, pues;son sistemas axiomticos, que constan de smboloscuya interpretacin no pertenece al sistema y queestn estructurados de la siguiente formac

7 ) Smbolos primitivos.2) Reglas de definicin.3) Sfmbolos derivados.4) Reglas de formacin de frmulas.5) Lista de axiomas:6) Reglas de inferencia.7) La serie de los teoremas.

Sienda los ingredientes caractersticos: 1, 4, 5 y 6.En e1 captulo V de Outhines of a formalist philo-

sophy ofmathematics ofrece H. Curry nueve ejemplosde sistemas #ormales, correspondientes a diversasteoras en la mayora de los casos y a distintasformalizaciones de una misma teora en los restantes.

EI primero de ellos lo recoge en la ya citada Lgicacombinatoria como ejemplo de sistema completa-mente formalizado y es el que insertamos a conti-nuacin:

a) Obs (objetos):(1) Un ob primitivoa o:(2) Una operacibn monaria, indicada por

el ndice^(3) Una regla de formacin de obs: Si x es

un ob, entonces x' tambin lo es:

b) Enunciados elementales:(1) Un predicado binario;(2) Una regla de formacin de enunciados

elementales: si x e y son obs, en-tonces x= y es un enunciado elementaL

c) Teoremas elementales:(1 j Un axioma: 0= 0.(2) Una regla de deduccin: Si x= y,

entonces x' = y'.Los teoremas elementales de este sis-tema son precisamente iosque se indicanen la siguiente lista:

0=00' = 0'0'' = 0,,

que son enunciados verdaderos del sistema. Pero,una vez definido este, podemos formar epiteoremas,es decir, enunciados sobre l. Por ejemplo:

Si y es un ob, entonces y= y:es un enunciado verdadero sobre et sistema, aunqueno es un teorema elemental (7).

Entre las diferentes axiomatizaciones de la lgicade enunciados una de las que goza de universalaceptacin es la presentada por Lukasievvicz en3 929, y que, siguiendo a Frege, toma como trminosprimitivos los correspondientes a la impficacibnmateria[ y a la negacin (8j.

Utilizando la notacin de Lukasiewicz el sistemaqueda estructurado de la siguiente forma^

1 ) Simbolos primitivosa) Constantes lgicas: C, N.b) Variables enunciativas: p, q, r, ...

2) Reglas de formacin de frmulasa) Cualquier variable enunciativa en una fr-

mula.b) Si x es una frmula; fVx es tambin una

frmula: 'c) Si' x e y son frmulas; Cxy es igualmente

una frmufa:

3) Axiomas (Lukasiewcz Ilama tesis tanto a losaxiomas como a los teoremas),

T, CCpqCCqrCpr72 CGNpppT3 CP^NPq

(3) KLEENE,; lntroduccin a/a metamatemtica, Ma-drid, 1974, 64.

(4) lbil, 34.(5) CURRY y FEYS.: o.c:, 32.(6) BOCHENSKI, o.c:, 92.(7) Cfr. CURRy y FEYS.; o:c 33-34. Sobre la idea de

formalizacin completa; vease pqs. 55-56.(8) Cfr. LUKASIEWICZ.:' Arist: Syllog. Oxford, 1957,

79-83: Cfr. GARRIDO,: Lgica Simblica, Madrd, 1974,297-300.

36

4) Reglas de inferenciaa) Regla de sustitucin: A partir de una tesis

aceptada del sistema pueden deducirsenuevas tesis, escribiendo en lugar de cual-quiera de sus variables, en todas y cada unade sus ocurrencias, una frmula cualquiera.

b) Supuesta una tesis del tipo Cxy, si hayotra tesis que consista en el antecedente x,entonces puede afirmarse como nueva latesis y, que consista en el consecuente se-parado de aquel condicional.

As pueden obtenerse todas las tesis verdaderasdel sistema. No obstarite, para abreviar a escriturade las frmulas y para hacer ms sencillas las demos-traciones se introducen:5) Como smbolo derivados: K, A, E de acuerdo

con las definiciones:K p q= N C p N qA p q= C N p qE p q= K C p q C q p

6) Como nueva regla de inferencia, la regla deintercambio, que permite reemplazar el definienspor el defniendum y viceversa.

Como ejemplo de derivacin de una nueva tesispresentamos ia que da Lukasiewicz, en el formatosinttico que l utiliza, para obtener a partir de lostres axiomas la ley de identidad Cpp. La deduccinrequiere dos aplicaciones de la regla de sustituciny otras dos de la regla de separacin:

T, q/CNpqXCT3-T4TQCCCNpqrCprT4 C/C r/p X C T^ - T5

5 PP

Este sistema de Lukasiewicz posee el encanto deser una especie de recopilacin histrica. En efecto,el primer axioma es la ley del silogismo hipottico,cuyo origen se remonta a Aristteles; el tercero es laIlamada ley de Duns Escoto ( aparece par primera vezen un comentario a Aristteles atribuido al doctorSubtlis); el segundo es la conocida ley de Clavius,jesuita del siglo XVI, que fue el primero en Ilamarla atencin sobre esta ley en un comentario sobreEuclides. Por lo que respecta a las reglas de inferencia,la regla de sustitucin equivaldra al dictum de omniaristotlico; la regla de separacin es el modusponens de los estoicos, y la regla de intercambio ces-como escribe el profesor Garrido- trasunto de lapropiedad tradiccional de las definiciones, segnlo cual todo lo que sea verdad del extremo definiente(definiens) ha de serlo igualmente del extremo de-finido (definiendurnJ :

Entre los sistemas axiomticos de lgica elementalcabe destacar dos formulados recientemente (en ladcada 1950-1960) que han tenido una extraor-dinaria acogida entre los ttatadistas. Nos referimosa los sistemas-de Church y de Kleene. Mientras queel del primero presenta un nmero muy reducido desmbolos lgicos primitivos y de axiomas, el delsegundo exhbe abundancia de ellos (9).

Pero sin lugar a dudas la ms bella construccin,aunque seguramente no tan verdadera, que se haelaborado por el mtodo axiomtico ha sido lateora axiomtica de conjuntos.

A finales del siglp diecinueve se produce la mslprofunda crisis de fundamentos en la matemtica.

Con la aritmetizcin del anlisis y posterior reduccinde los nmeros naturales a los conjuntos, todo eledificio de la matemtica pura se apoyaba por fin en elconcepto de conjunto. Pero en el interior mismo dela teoria aingenua de conjuntos aparecieron para-dojas lgicas (como la de Cantor, la de Burali Fortiy la d Russell), y a la antigua paradoja semnticadel mentiroso vinieron a sumarse otras nuevas (lade Richard, la de Grelling). Ante el reto de las para-dojas se haca necesario elaborar una teora noingenua que solventara Ea crisis del cantorismo. Enla primera dcada de nuestro siglo, o precisandoms, entre los aos 1906 y 1908 surgen independien-temente y casi a la vez tres lneas distintas de pensa-miento que suponen otras tantas propuestas de solu-cin a la crisis: la de Zermelo que propone cons#ruiruna teoria axiomtica de conjuntos, aadiendoaxiomas especficos tle la teoria a la lgica elementaltomada como nica base; la de Russell o lnea logi-cista que opta por desarrollar el programa logicista,tomando como base la lgica superior y la teora delos tipos; y la de Browwer con quien recobran nuevovigor ias tesis finitista y constructivista del intuicio-nismo, '

Entre los posteriores desarrollos de la lnea iniciada.por Brouwer cabe destacar la formalizacin de lalgica intuicionista realizada por Heyting y las recien-tes aportaciones de Kleene. EI programa logicistadesarrollado en los Principia Mathematica fia sidoremodelado despus de forma muy orginal en lossistemas de Quine.

Entre las mltiples presentaciones axiomticasde la teora de conjuntos que se han producido si-guiendo la direccin emprendida por Zermelo (lalnea comunmente conocida como axiomtica)cabe destacar dos orientaciones fundamentales: lade la teora axiomtica conocida como sistema deZermelo-Fraenkel (o simplemente con la sigla Z F)y la teora axiomtica conocida como sistema de VonNewmann-Bernays-Gr;del ( sistema N B G): Unade las diferencias que saltan a primera vista es quemientras en Z F se opera slo con conjuntos enN B G se admiten clases y conjuntos; o dicho conms precisin, se admiten clases normales (las clasesque son elemento de aiguna otra) que son los con-juntos, y tambn se cuenta con las clases ltimas(clases no normales) que no son conjuntos. Porsupuesto est probada la consistencia relativa deN B G respecto de Z F. ^Se trata entonces de dosteoras o ms bien de dos formulaciones-de la mismateora7 Los seguidores de Z F se inclinan por el se-gundo miembro de la alternativa: The main pointwhich will, in our opinion, emerge from this analysis,is that set theory with classes and set theory withsets only are not two separate theories; they are,essentially, different formulations of the same un-derlying theory (10).

(9) Cfr. CHURCH.: lntroduction to mathematical /ogic,vol. I, Princeton, 1965. KLEENE.: lntr a la Meram. ed. c.Ambos sistemas estn recogdos en el libro ctado deGarrido, pgs. 280-288.

(10) FRAENKEL, BAR-HILLEL, LEVY.: Foundations ofset theory, Amsterdam, 1973, 119. Este libro, del que jus-tamente dice el profesor Garrido en la recensin hecha paraTeorema que es casi nico en su g8nero contiene unaabundante bibliografa. En castellano pueden verse: en ladireccin del sistema Z F: SUPPES.; Teor/a axiomStica deconjuntos, Cali-Colombia, 1968; en la lnea del sistemaN B G: MOSTERIN.: Teoa axiomtica de conjuntos,Barcelona, 1971.

37

1.2. Mtodo de la deduccin natural

En realidad los sistemas de reglas de deduccibnnatural son algo asi como sistemas axiomticos sinaxiomas. En torlo caso se puede decir de ellos quetambin son sistemas formales. Sistemas formalesen los que las funciones de los axiomas estaransuplidas por determinadas reglas peculiares: las deintroduccin y eliminacin de premisas.

Gentzen consideraba que los clculos logsticos,ta1 como i los encontr presentados, no eran adecua-dos para servir a los matemticos o cientficos y quese alejaban demasiado de la manera natural de ra-xonar. Como escribe Feys en fa introduccin a latraduccin francesa del famoso artculo de Gentzen(11) Untersuchungen i;iber das logische Schtiessende 1934: xGentzen ha empleado un camino diferentedel de Hilbert; Ha valorado el empleo frecuente y na-tural, en matemticas, de razonamientos a partir deuna suposicin (razonamientos que proceden en finde cuentas al modo de las pruebas ex suppositionede los antiguos). Para formalizar estos razonamientosdeber introducir la asercin uesto es verdadero bajotal suposicin como elemento formalizado de sus sis-temas. En efecto, la forma ms natural de procedercuando nos enfrentamos a la tarea de deducir algode algo es qua desencadenemos secuencias del tipo:supongamos el antecedente... y supongamos tam-bin ^de momento..., entonces se seguir que...,pero si esto es as, ocurrir,.., etc.

AI igual que en los sistemas formales axiomticostambin en los sistemas de deduccin natural sepuede optar por una mayor o menor abundancia desimbolos primitivos y reglas bsicas de derivacin.

Es muy frecuente (y didcticamente muy reco-mendable) que, adems de la regla de introduccinde premsas, se empleen, si4luendo a Gentzen, comoraglas bsicas dos para cada smbolo de constantelgica empleada: una de introduccin y otra de eli-minacin. As para la lgica elemental sin identidades usual emplear las correspondientes pares de reglaspara la negacin, la coniuncin, la disyuncin, el con-diciona{, ei cuantificador universal y el cuantificadorexistencial,

Cuando en una lnea de una derivacin realizadade acuerdo con las reglas estabiecidas aparece unenunciado que dpende del conjunto vaco de pre-msas, dicho enunciado es un teorema. Es de capitalimportancia resaltar que para la lgica elemental sedispone de sistemas formales de deduccin naturalcuyo rendimiento es equivalente al de los correspon-dientes sistemas formales axiomticos.

Para entrever esa equivalencia entre el rendimientode ambas presentaciones de la lgica elementalvamos a comparar el sistema de reglas expuestoen el texto de Ei, Mates y ef sistema axiomtico deChurch al que aluddamos en pginas anteriores.

Las diferencias ms chocantes a primera vistaentre SN y SA es que en SN se introducen premisasen lugar de partr de unos axiomas fiios como en SA;y luego esas premisas se eliminan por 2), quedandolos teoremas sin depender de nada. Pues bien 1) y 2)quedan justificados respecto a SA por la demostra-cin del teorema de deduccin (que se utiliza en 5Aulteriormente como regla derivada).

3) Se corresponde con VII. 4) puede justificarseen SA, ya que en SA se prueba IX y la ley de impor-tacin, Ilegndose a(A -. B) ^-B) --^ -A y 4) esla regla obtenida a partir de este esquema. 5) se .corresponde con la regla obtenida a partir de V.

Sistema de deduccin Sistema axiomticonatural S N S A

1) Regla de introduccinde premisas

Axiomas

2) Regla de Condiciona-nalizacin

I)II)

A-+(B-+A)(A-,(g-.C))-Y3) Modus Ponens- ( ( A - g ) - +4)

5)Modus TollensEspecificacibn uni-versai II)

^(A-,C))( -A --: -B) --. ( g -. A)

6) Generalizacin uni-versal IV) (A -Y Pa) -^

7) Cuantificacibnexis-tencial V)

-^ (A -a (x)Px)(x) Px -+ Pa

8) intercambio defi-cional Simbolos definidos

VP) Adems de las defi-niciones que se con-templan igualmenteen $) de SN, seincluye:( 3x) Px = df -- (x) - Px

Reglasde inferencia

VII) Modus ponensVI II ) Generalizacin

TeoremasIX) (A ^ g) --.

--^ ( - B -^ -A)

6) est directamente relaconado con 4V y VIII.7) y 8) estn comprendidos en Vl.

Decamos ms arriba que una vez constituido unsistema formal podamos considerarlo como untodo y hacerlo objeto de estudio metaterico, Aqu,por ejemplo, hemos comparado dos sistemas forma-les con miras a establecer la equivalencia de surendimiento.

Entre las propiedades principales de los sistemasformales en los que se centran los estudios metate-ricos figuran: la consistencia, la completud, la deci-bilidad, la independencia, la categoricidad. Mientrasque esta ltima es una propiedad netamente semn-tica, las otras cuatro pueden ser consideradas sintc-tica o semnticamente, si bien la independencia delos axiomas es demostrada en la mayora de loscasos semnticamente. Veamos como define Currylas otras tres:A system is consistent if not every elementary

proposition is a theorem; it is complete if everyelementary proposition is either a theorem or implissevery elementary proposition; it is resolvable if thereexist a definite algotithm wich, given an elementaryproposition, wll determine definitely vvether or notit is a theorem (12).

EI clculo proposicional es consistente, completoy decible. A Post se deben pruebas de carcter sin-tctico de la consistencia y completud de dichoclculo.

(11 ) Cfr. GENTZEN, Recherches sur la deductionlogique, PUF, Paris, 1955.

(12) CURRY: Outli Frm. Phi. of Math., Amsterdam,1970, 51-52.

38

2. METODUS SEMANTICOS

Aunque no se ha conseguido un criterio formal dediferenciacin entre sintass y semntica puedehablarse de un acuerdo unnime en cuanto alcarcter semntico de los conceptos de consecuen-cia y validez universal, en correspondencia con losconceptos sintcticos de derivabilidad y de teorema.

En cuanto a las propiedades de los sitemas formalesenfocados desde los puntos de vista sintctico ysemntico Hao Wang ha escrito:

Acerca de cada uno de los sistemas formalespodemos plantear diferentes problemas. Estos pro-blemas se distribuyen de ordinario en dos familas:probiemas sintcticos, que se refieren al sistemaconsiderado como un formalismo puro o como unamquina que maneja expresones simbticas, inde-pendientemente de sus significaciones, y problemassemnticos que se refieren a la interpretacin delsistema. Las nociones y problemas ms importantespueden dividirse del siguiente modo:

1. De naturaleza sintctica 2. De naturaleza semntica

1.1. Formlismo 2.1. Modelo o interpre-1.2. Teorema tacin1.3. Mtodo de decisin 2.2. Verdad o validez

para la demostrabi-lidad

2.3. Mtodo de decisinpara la verdad y

1.4. Consistencia criterio de id.1.5: Consistencia rela- 2.4. Realizabilidad

tiva 2.5. Modelo relativo1.6. Completud 2.6. Categoricidad (13).

^En e! punto 2.6. de esta tabla se debera hablar

ms bien de completud o saturacin semntica,dejando aparte. la categoricidad como propiedadnetamente semntica; ya que si bien puede darse porbueno que todo conjunto de axiomas que es cate-grico es tambin semnticamente completo; cabe,en cambio, que un conjunto de axiomas sea completoen sentido semntico, o en sentido sintctico, y nosea categrico (14).

Un sistema axiomtico es categrico si todos susmodelos son isomrficos. AI lado de esta definicinde la categoricidad absoluta (o simplemente cate-foricidad) cabe dar otra referida a la categoricidadrelativa: Un sistema se dice cate^rico respecto auna cierta clase de objetas CI pertenecientes a l,si todos los modelos de este sistema, en los cualesesta clase CI recibe la misma interpretacin, sonisomorfos (15).

Veamos ahora algunas definiciones de las otraspropiedades de los sistemas en sentido sintcticoy en sentido semntico:

Consistencia sintcticaUn sistema es consistente si no toda frmula del

sistema es derivable en L 0 tambin (en el caso deque el sistema incluya el operador de negacin) si noes posible derivar en l una frmula y su negacin.

Consistencia semnticaUn sistema es consistente si no toda frmula del

sistema es una consecuencia lgica. 0 sencillamente,un sistema es consistente si es realizable.

Prescindiremos ahora de la c^-- consistencia y dela consistencia relativa.

Completud sintcticaDe un sistema se dice que ex completo en sentido

fuerte si toda frmula perteneciente al sistema esderivable o refutable. Un sistema es completo ensentido dbil si, aadindole una frmula no derivabtedel sistema se torna en consistente.

Completud semnticaUn sistema es absolutamente compfeto o saturado

si, y slo si, toda frmula vlida del sistema esderivable.

Se dice que un sistema es completo en relacina un campo de interpretacin, si toda frmuta delsistema, vlida en relacin a ese campo, es-derivable,y recprocamente.

Decibilidad sintcticaUn sistema es decidible si se puede dar un proce-

dimiento efe tivo que permita detrminar, paratoda frmula del sistema, si es o no es derivable.

Decibilidad semnticaSe dice que un sistema es decidible si se puede

dar un procedimiento etectivo que permita detarmi-nar, para toda frmula del sistema, si es o no esvlida.

lndependenca sinicticaDado un sistema formal se dice de uno de sus

axiomas que es independiente si no es derivable delconjunto de los axiomas restantes.lndependencia semntica

Anlogamente se dice que un axioma es inde-pendiente si no es una consecuencia lgica de losotros axiomas del sistema. Un axoma es indepen-diente en este sentido si, y solamente si, hay unmodelo que satisface a( conjunto de axiomas res-tantes; y en el que resulta ser falso el axioma encuestin.

2.1. Teora de modelos y pruebas semnticasEn la segunda mitad del siglo XIX Beltrami y

Klein consiguieron encontrar modelos euclidianospara la geometra hiperbfica (no euclidiana), conlo que quedaba demostrda la consistencia relativade esta nueva geometra y ia independencia delaxioma de las paralelas.

Este descubrimiento paradigmtico es recogidounnimemente hoy por todos los tratadistas de lamoderna teora de modelos como el ms lustreprecedente histrico de la nueva disciplina. Otrohito igualmente memorable, el conocido teoremade L6wenheim-Skolem, pertenece ya a nuestrosiglo.

EI primero que empEe la expresin teora demodeloss> fue Tarski, en 1954. En l hay que ver

(13) HAO WANG.: Quelques notions daxiomatique,Rev. phil. Louvain, 51, 1953, pg. 411. Recogido por V.MUIVOZ en Lecciones de lgica, I, Salamanca, 1972,pgs. 178-179.

(i4) Cfr: FRAENKEL, BAR-HILLEL, o.c., 297-298.(15) LADRIERE; Limitaciones internas de los forma-

lismos, Madrid, 1969, 71. Tendremos en cuenta esta obraigualmente para las definiciones que siguen.

39

al principal promotor de la actual semntica pura,si bien ya en las obras de Bolzano y Frege se encon-traban importantes consideraciones semnticas ypor mbs que en los tratados medievales de lgica,e ir>c{uso en los estoicos y en el mismo Aristteles,puedan encontrarse pasajes muy sugestivos alrespecto. EI punto de arranque de los actuafes desa-rrollos de ta semntica se puede fijar en el articulode Tarski EI concepto de verdad en los lenguajesformalizados^ escrito en 1931 y cuya versin alemanapara la revista Studia Philosofica ya hemos citado.En l se recupera la doctrina de la verdad contenidaen e! famoso pasaje de la metafsica de Aristteles:decir de io que es que no es y de lo que no es queas, es falso; mientras que decir de lo que es que es,o de lo que no es que no es, es verdadero. Ahorabien, Tarski hace resaltar el carcter metalingiisticodel predicado averdadero, y como el lenguajecorriente por su universalismos, lejos de permitirla distincibn ntida entre lenguaje objeto y metalen-guaje, ^es fuente de las llamadas antinomias sem3n-ticas, como la de el cretense o la de tas palabrasheterolgicas, resulta como consecuencia que,para establecer una definicin correcta de la expre-sin aenunciado verdadero, es necesario acudira los lenguajes formalizados, con lo que esa nocindeja de ser absoluta y queda relativizada al {enguajeformalizado concreto al que pertenezca el enunciadode cuya verdad se trate.

En Undecidable Theories astablece Tarski la si-guiente definicibn de modelo: A possible realizationin which all valid sentences of a theory T are satisfedis called a madef of 7^ (16).

En esta definicin aparecen conectadas las nocio-nes de reafizaein, uvalidez, satisfaccin ymodelo.

Vamos a ocuparmos ahora de establecer breve-mente la conexin entre interpretacin, satisfaccin,verdad, modelo, verdad lgica o validez universal,y consecuencia lgica.

Dado un lenguaje L una interpretacin J de Lconsta de:

1) 1) Un dominio no vaco (o universo deldiscurso) D.

2) Una asignacin o atribucin que asocie:a) Con cada constante individual de L un

individuo o elemento de D.b) Con cada letra predicativa n-dica de L

una relacin n-dica entre miembros de D.c) Con cada letra enunciativa de L uno de

los dos valores de verdad V o f.d) Las constantes lgicas conservan en la

interpretacin su significacin usual.

Hemos supuesto que L es un lenguaje de lgicade primer orden sin identidad.

Dada una frmula A del lenguaje L, un dominio Dy una interpretacin J, se dice que J satisface a A,si dicha frmula al ser as interpretada se convierteen un enunciado verdadero.

He aqu una definicin recursiva (o inductiva)de la satisfaccin:

1. La frmula A es atmica1.1. A es una letra enunciativa. Entonces

J sat. A Sii J asigna el valor V a A.1.2. A es una predicacin. Entonces J sat.

A Sii los objetos que J asigna a lasconstantes individuales de A (tomndo-

tos en el orden en que sus correspon-dientes constantes ocurren en A) guar-dan entre s la relacin n-dica que Jasigna al predicado n-dico de A.

2. La frmu/a A es mo%cular2.1. Su signo lgico principal es un conec-

tivo.2.1.1. A=-B, entonces J sat. A 5ii no

es el caso que J sat. B.2.1.2. A= BvC, entonces J sat. A Sii J

sat. B o J sat. C.2.1.3. Anlogamente se procedera en

el caso de que A fuera una con-juncin, una implicacin o unadoble implicacin. Dadas las re-glas de intercambio definicionalbasta con los dos subcasos ana-lizados. -

2.2. Su signo lgico principal es un cuanti-ficador2.2.1. A=(x)B, entonces J sat. A Sii

B x/a es verdadero bajo todavariante de a en J, siendo B x/ael resultado de reemplazar todaslas ocurrencias libres de la va-riable x por ocurrencias de laconstante a, que se supone es laprimer constante individual queno ocurre en B{partiendo de quelas constantes individuales estnenumeradas por el siguiente or-den: a, b, ... t, a^, b,, ... t,,az, b2, ...).

2.2.2. Anlogamente si A tiene comosmbolo principaf el cuantificadorexistencial, exigindole solamen-te en este caso que B x/a seaverdadero, cuando menos, bajouna variante de a en J. La reglade intercambio definicional decuantificadores nos permite porotra parte reducir los dos casosa uno slo (17).

Por otra parte, de una interpretacin que no cum-pla las anteriores clusulas se dice que no satisfacea la fbrmula en cuestin, o que sta es falsa bajo esasupuesta interpretacin.

Si una interpretacin J satisface la frmula A sinque quepa ejemplo alguno en contra, se dice que Jes un modelo de A. (Anlogamente tratndose decualquier conjunto G de frmulas).

Una frmula A(o en general un conjunto G defrmulas) es verdadero o vlido bajo la interpretacinJ en el dominio o universo D si, y slo si, dichainterpretacin es un modelo suyo.

Un modelo M para ei lenguaje L puede represen-tarse por el par < D, J>, dbnde D y J son respec-tivamente el universo y la interpretacin elegidos.Suele escribirse M=< D, J>.

Dados dos modelos M=< D, J> y M', J' >

(16) TARSKI, MOSTOWSKI, ROBINSON: UndecidableTheories, Amsterdam, 1973, 11.

(17) Cfr. QUINE: filosoiia de la lgica, Madrid, 1973,77-81. MATES: Lgica ^riatemtica elemental, Madrid, 1971,77-79, GARRIDO: o.c. 226-228.

40

para un conjunto G de frmulas del lenguaje L, sedice que M y M' son isomrficos si slo si :

1) Para cada letra enunciativa P que ocurra en G,se cumple J(p) = J'(p), es decir, lo que Jasocia con p es idntico a lo que J' asociacon p.

2) Hay una aplicacin biyectiva f entre D yD' tal que:2.1. Para cada elemento x del dominio D

y ei elemento x' correspondiente deldominio D' se cumple: f(x) = x'.

2.2. Para cada relacirr n-dica R de M y lacorrespondiente relacin R' de M' secumple:

R(x, ... x) Sii R'(f(x,) ... f(x)para todas las x, ... x de D(18).

Se dice que una frmula A es universalmentevlida o lgicamente verdadera si A es verdadera ovlida bajo toda interpretacin.

Una frmula A es una consecuencia lgica de unconjunto de frmulas G, si no hay ninguna interpre-tacin bajo la cual todas las frmulas de G sonverdaderas y A es falsa: 0 como dira Tarski, elenunciado A se sigue lgicamente del conjunto deenunciados G si y slo si todo modelo del conjunto Ges tambin un modelo de A:

La distincin entre las dos clases de relacindeductiva, la deducibilidad formal y 1a consecuenciasemntica, no es triviaL En principio no est garan-tizado que ambas hayan de coincidir. Posiblementeel resultado ms interesante de la investigacin desistemas de lgica elemental o de primer orden,es que en dicho orden la relacin de deductibilidady la relacin de consecuencia son coextensivas oequivalentes. Este resultado se debe a Gdel ( 1930).Pero en teoras de orden superior no es ese el caso.En tales teoras el control lgico inherente a larelacin de deducibilidad deja de ser operante, y espreciso atenerse tan slo al criterio de consecuencialgica (19).

Para calibrar la fecundidad del mtodo semnticobastar con mencionar algunos de los resultadosmetalgicos ms decisivos: Se han conseguidodiferentes pruebas semnticas de la consistencia ycompletud del clculo proposicional, as como laconsistencia de la lgica de primer orden. Sobresaleespecialmente el teorema ya aludido sobre la com-pletud semntica de esa parte de la lgica. Unademostracin implcita estaba contenida en lasinvestigaciones de Herbrand ( 1930). La primerademostracin explcita fue la ya mencionada deGdel ( 1930). Una nueva prueba ms sencilla fueconseguida por Henklin en 1949 (20). Un pasoesencial en esta prueba consiste en la exhibicinde un modelo enumerable construido sobre la basede una autointerpretacin del propio sistema. En1953 HASENJAGER presenta una simplificacinde la prueba de Henkin. Otra demostracin esconseguida por SCHUTE en 1956. Pruebas cons-tructivas se deben a Hintikka, Beth y Smullyam.Hay asimismo una demostracin de Rasiowa ySikorski ( 1951) que utiliza lgebra y topologa (21).

EI teorema de L6wenheim ( 1915) generalizadopor Skolem ( 1920) puede obtenerse como corolariode la prueba de Henkin y nos garantiza que si unconjunto de frmulas es simultneamnte satisfacibleen un dominio no vaco, entonces es simultnea-mente satisfacible en un dominio infinito enumerable.

EI famoso teorema de incompletitud presentadopor Gdel en 1931 tiene como punto crucial laexhibicin de una expresin indecidible que esautorreferente pero cuya ucircufaridad no es para-djica, pues, gracias a la estrategia d la aritmeti2a-cin, la aritmetizacin de la matematica del clculoaritmtico permite reflejar las reflexiones sobre elclcuEo en el clculo mismo; se trata de un sumergi-miento de la metaaritmtica en la aritmtica misma,mediante el rodeo de la aritmetizacin del clculo PMque se supone coherente (ms an co - coherente)y suficientemente amplio para que la aritmticarecursiva sea formalizable en l (22). Ya hemosmencionado el carcter semntico de las pruebasusuales de independencia.

Es de destacar la reciente prueba de independenciade la hiptesis del continuo que nos ha conducidoen teora de conjuntos a una situacin similar a laproducida en geometra con la demostracin de laindependencia del quinto postulado de Euclides.

La prueba de independencia de la hiptesis delcontinuo se obtiene uniendo los resultados conse-guidos por Gbdel (1939) y Cohen (T963).

Gdel demostr ta consistencia relativa del axiomade eleccin AE y la hiptesis generalizada del con-tinuo HGC respecto de la teora axiomtica deconjuntos ZF. Para Ilevar a cabo la demostracinemple la nocin de conjunto constructible.G^del Ilama constructibles los-conjuntos que puedenser obtenidos corno resultado de una secuenciatransfinita de de#iniciones predicativas. Llamando La la ccclase de los conjuntos constructivos y V a laclase universaf, la dernostracin discurre por lossiguientes pasos:

1) Los axiomas de ZF se cumplen en L, es decir,los conjuntos constructibles son un modelopara ZF.

2) Axioma de constructibilidad: L= V. EI uni-verso de ZF y el de los-conjuntos constructiblesson equivalentes, es decir, todos los conjuntosson constructibles:

3) L= V es expresable en ZF y se cumple en L(en este punto entra en juego la nocin derelacin absoluta).

4) EI axioma de constructibilidad L= V implicael axioma de eleccin AE y la hiptesis delcontinuo HGC.

En conclusin: La consistencia de ZF implica laconsistencia de 2F + AE + HGC.

(18) Cfr. MATES: a.c., 229. GHANG, C.C. y KEISILER,H. J.: Model theory, Amsterdam, 1973, 20-21. Estos autorescaracterizan a fa teora de modelos mediante la siguienteecuacin: lgebra universal + lgica = a teor(a de modelos.Cfr. tambin: BELt_, J.L. y SLOMSON, A.B.: Models anu/traproducts: an introduction, Amsterdam, 1974. Sobrela interpretabilidad de unas teorias en otras vase la obrade TARSKI, MOSTOWSKI, ROBINSON, antes citadapg. 20 y siguientes.

(19) GARRibO: o,c. 231-232.(20) Cfr. HENKIN, L.: The comp/eteness of the first-

order funcionaf calculus, Journal of Simholic Log^ic, vol. 14(1949), 159-166. Recogido en HINTIKKA, J. (ed.):: Thephilosophy of mathematics. Oxford university press, 1969.

(21) Cfr. BEtL y SLONSON.: o.c., 62-65 y 71.(22) Cfr. CHURCH, A,: lntroduction to mathematical

Logic, Princeton, 1956, 236-245.(22) Cfr. GODEL, K.: On formally undecidable propo-

sition of principia mathematica and related systems, withintroduction by R. B. BRAITH-wAITTE, London, 1962.

41

Cohen por su parte probb que: La consistenciade ZF implica la consistencia de ZF +- AE +-- HGC es decir, demostr la consistencia relativade la negacin del axioma de eleccin y la negacinde la hiptesis del continuo respecto de los restan-tes axiomas de la teora de conjuntos. Hay interpre-taciones en las que no se cumplen AE y/o HC y enlas que en cambio siguen valiendo los axiomasde ZF.

Empleando las originales ideas de forcing yconjunto genrico logra construir en primer lugarun modelo N tal que en l se cumplen ZF y tambinHGC y AE, pero que contiene un conjunto a noconstructible y, que; por lo tanto, no satisface V= L.De ah se sigue, de momento, que aunque V= Limplique HGC y AE, en cambio HGC y AE no im-plican V= L. Por una extensin ulterior del mtodose alcanza el resultado completo (23).

2.2. EI mtodo de las tablas semnticas

Entre los mtodos semnticos merece una especialmencin el denominado mtodo de las tablas semn-ticas, Sabemos por la definicin de consecuencialgica que no cabe en una deduccin correcta que,siendo verdaderas las premisas, sea falsa la con-clusin. Supongamos un conjunto de premisas Py urta supuesta conclusin c. Para comprobar si cse sigue de P podemos ensayar la bsqueda de unainterpretacin que satisfaga a P y a-c, en la seguri-dad de que si esto ocurre, entonces queda invalidadala supuesta inferencia. Ahora bien, en el caso de quela bsqueda dea contraejernplo o contramodelo nosIleve a una contradiccin, entonces queda garantiza-do que la conclusin c se sigue de las premisas P.

Realmente Aristteles ya hizo uso del mtodo delos contraejemplos para invalidar algunos modosincorrectos del silogismo. Este procedimiento vienea ser una especie de versin semntica de la reduc-cin al absurdo. No obstante el hallazgo del contra-ejemplo era algo que dependa prcticamente delazar, hasta que fas recientes investigaciones deE. W. Beth y J. Hintikka condujeron a la consecucinde un mtodo que permite la bsqueda sistemticade la interpretacin invalidadora del argumento (24).

EI procedimiento consiste en la aplicacin siste-mtica de un conjunto de reglas de eliminacin desmbolos de constantes lgicas de acuerdo con unadistribucin tabular o arborescente que puede con-ducir a una de las tres situaciones siguientes:

a) Clausura completa, esto es, que en toda tra-yectoria continua descendente aparezca unafrmula atmica afirmada en una de suslneas y negada en otra. En este caso la bs-queda sstemtica del contraejemplo ha con-ducido a contradicin, quedando refrendadala validez di31 argumento que se pretendainvalidar.

b) Que el procedimiento termine sin que sehaya producido la clausura completa. Eneste caso el argumento sometido al procesoqueda invalidado.

c) Que el procedimiento no tenga fin, es decirque la tabla se revele como in/inita.

La situacin c) puede presentarse y de hechose presenta en los argumentos sometidos al controlde este mtodo intervienen frmulas con letraspredicativas poliadidicas. Pero para los argumentos

en los que slo intervienen frmulas del clculoproposicional y/o del clculo cuantificacional mo-ndico las tablas en cuestin desembocan siempreen una de las dos primeras situaciones descritas.Esto es, el mtodo de las tablas semnticas propor-ciona un algoritmo de decisibn para la vslidez de lasfrmulas pertenecientes a ssa parte de la lgica.

3. EL METODO ALGORITMICO

Acabamos de decir que el mtodo de las tablassemnticas permite decidir la validez de cualquierfrmula o argumento en los que no intervenganletras predicativas polidicas. Sabemos tambin quetoda frmula vlida de ese mbito de la lgica puedeser obtenida como teorema, tanto por el mtodoaxiomtico como por ef mtodo de la deduccinnatural, yque se cumple la recproca: si una frmulase obtiene como teorema es vlida. No obstantehay una diferencia importante entre estos dos mto-dos y aquel otro. Tanto en el mtodo axiomticocomo en el mtodo de la deduccin natural, porms que se conozcan estrategas ocasionalmentemuy tiles, se requiere a menudo una cierta dosis deinventiva de quien lo practica para la derivacinde los teoremas, no siendo infrecuentes los tpicosfenmenos de invisin o de reestructuracingestltica y hasta diferentes estilos de demostra-cin. EI mtodo de las tablas semnticas, es, encambio, mecnico. En l las demostraciones serealizan a travs de pasos ordenados siguiendo unarutina establecida. Los procedimientos de estetipo son algortmicos. Algunos procedimientos algo-rtmicos en el campo de las matemticas se conocandesde la antiguedad, Recurdese el algoritmo deEuclides para la descomposicin de un nmero ensus factores primos. EI ideal algortmico ha sidouna constante en el desarrollo de la lgica formaly hasta la dcada de los aos 30 de nuestro siglono se haba conseguido demostrar los limites deestos mtodos.

Desde hace tiempo se ensayaron y consiguieronvarios mtodos para resolver silogismos. EI mtodode diagramas y diferentes tipos de mquinas lgicasconstituyeron verdaderos mtodos de decisin paraese campo y hay que verlos como autnticos prece-dentes de los mtodos ms potentes de que hoydisponemos (25).

Un mtodo de decisin para las frmulas y argu-mentos del clculo proposicional es el constituidopor el conocido mtodo de las tablas de verdad.Otro puede obtenerse fcilmente a partir de lateora de las formas normales.

(23) Cfr. COHEN, P. J.: Set theory and the continuumhypotesis W. A. Benjamin, Massachusetts, 1966 especial-mente, pgs. 85-99 y 120-127. Cfr. KRIVINE, J. L.: Theorieaxiomatique des ensembles, Paris 1969, especialmentepginas 100-118. Cfr. SMULIYAN, R. M.: The continuumhypotesis en The mathematical sciences, a collectionof essays, Cambridge, Massachusetts, and London, England,1969, 252-260. Para el tratamiento de estas pruebas deindependencia con modelos de valores booleanos Cfr.ROSSER, J. B.: Simplied lndependence Proofs, Academicpress New York and London, 1969.

(24) Cfr. GARRIDO, ac., 259. Cfr. BETH.: Semanticentailment and formal derivability recogido en NINTIKKA(ed.) o.c., 9-41. Cfr. tambin la obra conjunta de BETHy PIAG ET, Relaciones entre la lgica formal y e/ pensamientoreal, Madrid, 1968, 33.

(25) Cfr. GADNER, M.: Mquinas lgicas y diagramas,Mxico, 1973.

42

En cuanto a los mtodos de decisin para laparte montica de la lgica de predicados cabedestacar los resultados de Lwenheim (1915),Behmann (1922); Von Wrigh (1949) y Quine(1950) (26).

En esta ocasin nos limitaremos a consignaraqu el siguiente teorema: Si una frmula del cl-culo cuantificacional mondico es vlida en undominio de 2" individuos, donde n es el nmero deletras predicativas distintas, entonces es vlida entodo dominio no vaco.

Con motivo de este teorema hace Ghurch lassiguientes observaciones sobre la relacin en elmarco de la lgica de primr orden entre The decisionproblem i.e. the decision problem for provabiltyy the decision problem for validity

By Gbdel's completeness theorem it istrue inone sense that a solution of a special case of thedecisibn porblem for validity is also a solution, inthe same special case, of the decision problem.But in another sense -which ve have not attemptedto make precise- this is not true, as may be seenfrom the fact that proof of" 466 (el teoremaexpuesto) provides no effective method of findinga proof of a wff A which passes the test of containingnone but singulary functional variables and beingvalid in a domain of 2" individuals (27).

Hasta aqu hemos visto que para el clculo deproposiciones y para el clculo cuantificacionalmondico no slo se poda hallar una solucintotal al problema de la decibilidad, sino que ademsse cuenta de hecho con varios mtodos concretosde decisin. EI caso no es el mismo cuando sobrepa-samos la lgica mondica, esto es; cuando nos en-frentamos con el problema de la decibilidad de todoel clculo de predicados de primer orden. No setrata solamente de que no se disponga an de unasolucibn completa de ese problema, sino que existenrazones que excluyen el que podamos Ilegar nuncaa encontrarnos en posesin de una tai solucin.A. Church ha demostrado el primero (1936) laimposibilidad de descubrir un proceso general desolventar la decibilidad.

Antes de describir a grandes rasgos la marchade la argumentacin de Church veamos como precisaAckermann el alcance de sus consecuencias:

No ha de malentendernos este resultado, porlo dems en el sentido de que podran presentarseexpresiones determinadas acerca de las cuale$ seprobase que no es factible decidir si son universal-mente vfidas o no: de hechn no es posible talprueba. Por si se puede probar que no cabe decirnada acerca de la validez universai o no de una ex-presin, existe tambin una demostracin de que talexpresin no es deductible en el sistema de axiomas,o sea que -debido a la completitud de este sistemade axiomas, se tendra una demostracin de que laexpresin no era universalmente vlida, contralo que se haba supuesto. Ms la imposibilidadde un proceso general para solventar la decibili-dad quiere decir lo siguiente: se ha encontradoprocesos de esta ndole para clases especialesde expresiones, y hemos de suponer que se encon-trarn procesos anlogos para an otras clases deexpresiones; ahora bien todos estos procesos callanacerca de expresiones cualesquiera. Con esto seaclara tambin al mismo tiempo porqu los esfuerzospara ampliar e campo de las expresiones cuyavalidez universal puede decidirse en uno u otro

sentido, tropiezan cada vez con mayores dificul-tades (27).

Insertamos a continuacin un resumen panor-mico de !os casos especiales para los que se hasolucionado positivamente el problema de ta deci-bilidad de la lgica de predicados de primer or-den (28).

EI problema de la decisin ha podido ser resueltopara todo esquema bien formado que:

1) Slo contenga letras funcionales mondicas.2) Pueda ser reduciclo a una forma normal pre-

nexuada cuyo prefijo no contenga:a) Ningn cuantificador existencial.b) Ningn cuantificador universal.c) Ningn cuantificador existencial delante

de un cuantificador universal.d) Ms que un cuantificador existencial.e) Ms que dos cuantificadores existencia-

les que no se hallen separados entre spor ningn cuantificador universal.

3) Pueda ser reducido a una forma normalprenexuada en la que:a) La matriz ( esto es, la expresin que sigue

al prefijo) sea una disyuncin de compo-nentes elementales y sus correspondien-tes negaciones o quepa reducirla a dichaforma.

b) EI prefijo sea de la forma ( 3x, )... ( 3xm)(y^ )... jy") y todo componente elementalde la matriz que contenga alguna delas variables x,, ..., x, o bien al menosuna de las variables y,, ..., y".

c) EI prefijo concluya con (z, )... (z") ytodo componente elemental de la matrizque contenga alguna de las variables queintervienen en el prefijo contenga almenos una de las variables z,, ... z,,.

d) EI prefijo sea de la forma ( 3x) (y) ( 3z^ )...... ( 3z"), donde n` 4, y la matriz seade la forma G(x,y) ^ H(z ,.., z), conla letra funcionat didica i; como nicaletra funcional en la versin compietao desarrollada de H(z,, ..., z").

EI teorema sobre la i.mposibilidad de hallar unprocedimiento decisorio para el clculo de predica-dos de primer orden puede esquematizarse de lasiguiente manera. Desde la indecibilidad de la teoriaelemental de nmeros ( presentida ya desde el teore-ma de incompletitud de Gridel) se arguye a la inde-cibilidad del clculo de predicados de primer orden.

Llamando P a la aritmtica de Peano, P a laaritmtica de Skolem y Q al sistema de R. M. Ro-binson, A. Tarski y A. Mostowski, se cumpie:

(26) Cfr. ACKERMANN, W.: Solvab/e cases of thedecision prob/em, Amsterdam, 1954. CHURCH.: o.c:,246-280. Para los mtodos que emplea Quine para la de-cisin del clcuto cuantificacional mondico Cfr. nUINE.:El sentido de la nueva lgica, Buenos Aires, 1971, 94-96 yLos mtodos de fa lgica, Barcelona, 1962, 145-172 y262-266, Cfr. VON WRIGHT.: Logical studies, Londres,1957, 22-43. Una adaptacin del mtodo de Von WRIGHTpuede verse en HUGHEUES y LONDEY: The e%ments offormal Logic, London, 1966, 182-197.

(27) CHURCH.: o.c., 254. -(27) HIBERT y ACKERMANN, Elementos de lgica

terica, 4.a ed. Madrid, 1962, 138-139.(28) EI texto que ofrecemos est en la pg. 675 de E/

desarrollo de la lgica de W. y M. Kneale, Madrid, 1972.

43

Q C P C P. Aunque Q es considerablemente menospotente que P^, en cambio consta de un nmerofinito de axiomas y a la vez es igualmente adecuadopara la definicin de las funciones recursivas. Ahorabien Q es indecidible porque adinite en su interiorla definicin de la funcin diagonal. Ms an, esesencialmente indecidible, puesto que todas susextensiones consistentes (como, por ejemplo, Py P) lo son.

Llamando A a los axiomas especiales de Q elprobPema de saber si cabe probar, por ejemplo,F dentro del sistema Q queda reducido al de sabersi cabe probar A--^ F dentro de ta Ibgica de primerorden, Si esta lgica, lammosle L, fuese decidible,habrfa de serlo tambin el sistema Q. Pero como yasabemos que Q no lo es, se sigue por una sencillaaplicacin del mddus tol%ns que L tampoco puedeserlo (29),

La notacin de la teora elemental de nmeroses la del clculo de predicados de primer orden conidentidad, complementada con las notaciones 'x + y'y'x y' para la suma y el producto respectivamente.Las variables individuales x, y, z, etc:, son las deltipo ordinario, pero construidas como referentesexclusivamente a los nmeros naturales (30).

Varios problemas seculares, como el famoso deFermatan resistentes a los ms variados ensayos desolucin y que son formulables en la notacin dela teoria elemental de nmeros, hacen que no sor-prenda demasiado la indecibilidad de esta teora.Por otro lado, conviene resaltar que para estateora las relaciones entre completitud y decibilidadson muy distintas a las que median entre ambaspropiedades cuando se barajan en el marco de lalgica de predicados de primer orden. De la teoraelemental de nmeros sabemos por el teorema deGiidel que es incompieta. Pero, adems, si fueracompleta podra hallarse para ella un procedimientodecisorio. As que puede de nuevo arguirse suincompletitud a partir de su indecibilidad: En cambiode la lgica de predicados de primer orden sabemospor el otro teorema de Gdel que es completa, perode su completitud no puede inferirse su decibilidad.Esta situacin tan dispar se debe al hecho de queun procedimiento demostrativo completo para lavalidez no acarrea consigo un procedimiento refuta-torio completo de la validez, por que los esquemasno vlidos no tienen siempre negaciones vlidas.En cambio, un procedimiento completo de demos-tracin de la verdad acarrea necesariamente unprocedimiento completo refutatorio (si ef sistemaincluye la negacin) y, por tanto, un procedimientodecisorio (31).

Para demostrar la imposibilidad de un procedi-miento decisorio general para la teora elemental denmeros se siryi Church de su famosa tesis de queKToda funcin efectivamente calculable es recursivageneral. Aunque esta tesis es ms bien una con-jetura dado el carcter vago e intuitivo de la nocinde ufuncin efectivamente calculable es coincidentecon muchas otras formas de abordar esta temticadebidas a Gdel, Turing, Post y Kleene.

En particular: la tesis de Turing de que todafuncin que sea naturalmente considerada comocomputable, es computable en el sentido por lespecificado, esto es, computable por una mquinade Turing, es equivalente a la tesis de Church (32).

No es este el momento de abordar los problemasfilosficos conectados con estas cuestiones, y enparticular el de las relaciones entre inteligenciahumana e inteligencia artificial (33).

En la introduccin al ensayo citado de Turingescribe Garrido: uLa tesis de la identidad de lamente con las mquinas no est an definitivamentedemostrada y continua siendo materia de conjeturas.Pero los adversarios de esta tesis han de ponerahora ms cuidado que antes al elaborar sus argu-mentos. Por lo que toda en concreto a la indecibili-dad de la lgica de predicados, Garrido termina sulibro Lgica Simblica relacionando ese resultadocon la existencia de tablas semnticas infinitas ytraduciendo un pasaje de Beth en el que ste exponesu parecer de que la mente humana est equipadacon operaciones adicionales que van ms all delpoder de una supuesta mquina de buscar contra-ejemplos (34).

Terminaremos este apartado resaltando el hechode que, segn ha demostrado Tarski, el lgebra ele-mental de los nmeros reales admite un procesodecisorio; y acompaando este resultado notablecon ef siguiente comentario de Quine: La notacinde este lgebra elemental es precisamente la mismadescrita antes para la teora elemental de nmeros,con adicin y multiplicacin (ambas), y con lasola diferencia de que las variables se contruyenahora como referentes a nmeros reales en general,y no slo a nmeros naturales. A pesar de la com-plejidad aparentemente mayor de su tema, el igebraelemental es completable y decidible mecnica-mente, mientras que la teora elemental de nmerosno lo es (35).

(29) Cfr. TARSKI, MOSTOWSKI, ROBINSON.: o.c.,46 y ss. Cfr. W. y M. KNEALE.: o.c., 682-685. Los dos tra-bajos de CHURCH An insolvable problem of elementarynumber theory y cA note on the Entscheidungs problem,aparecidos en 1936 respecfivamente en las revistasAmerjcan Journal oi Mathematics y Journal of Symboliclogic, estn reimpresos en DAVIS.: The undecidab/e,Nueva York, 1965.

(30) Cfr. QUINE.: Los mtodos de la lgica, ed. c. 326.(31 ) lbid. 328 Cfr. tambin pp. 260-261. Cfr. tambin

LORENZEN, Matematica, Madrid, 1971, 157.(32) KLENE, o:c., 340. Toda esta problemtica es

minuciosamente tratada en esta obra ejemplar. Cfr. tambinLADRIERE, Limitaciones internas de los formalismos,ed. c. Cfc H. ROGERS.: Theory of recursiva functions andeffective computability, New York, 1967:

(33) Cfc TURING.: ^Puede pensar una mquinalValencia, 1974. Cfr. A. NEWELL, y H. A. SIMON.: Simula-cin del pensamiento humano, Teorema IV/3, 1974,335-377. Cfr. SMART.: Ent. Ci. y fils, 230-247; Cfr. entreotras obras: VON NEUMANN. The computer and the brain,Yale l^niversity Press, 1974. STARKE, P. H. Abstractautomata, Amsterdam. 1972. FRANK NORMAN.: MarkovProcesses and tearning Models, Now York, 1972.

(34) Cfr. el ensayo de Beth recogido en HINTIKKA (ed.)ed. c., 34.

(35) OUINE, o.c., 330. Sobre el mtodo de eliminacinde cuantificadores que utiliza Tarski en sus demostracionesde decibilidad de teoras Cfr. KREISEL y KRIVINE: Elementsde /ogique matematique, Paris, 1967, 47-50. Cfr: tambinLORENZEN, o.c. 183 y ss.

44