Logica UAS

  • Published on
    29-Jun-2015

  • View
    742

  • Download
    0

Embed Size (px)

Transcript

<p>Carlos Ivorra CastilloLOGICAYTEORIADECONJUNTOSNopuedesencontrarlaverdadconlal ogicasi nolahasencontradoyasinella.G.K.ChestertonIndiceGeneral1 L ogicadeprimerorden 1Introduccionalalogicamatematica 3CaptuloI:Lenguajesformalesdeprimerorden 171.1 Introducci on a los lenguajes formales. . . . . . . . . . . . . . . . 171.2 Denici on de lenguaje formal . . . . . . . . . . . . . . . . . . . . 231.3 Expresiones, terminos y f ormulas . . . . . . . . . . . . . . . . . . 261.4 Variables libres y ligadas . . . . . . . . . . . . . . . . . . . . . . . 301.5 Sustituci on de variables . . . . . . . . . . . . . . . . . . . . . . . 321.6 Consideraciones nales. . . . . . . . . . . . . . . . . . . . . . . . 35CaptuloII:Sistemasdeductivosformales 392.1 El c alculo deductivo de primer orden. . . . . . . . . . . . . . . . 402.2 Reglas derivadas de inferencia. . . . . . . . . . . . . . . . . . . . 452.3 Tecnicas de deduccion . . . . . . . . . . . . . . . . . . . . . . . . 532.4 Teoras axiomaticas . . . . . . . . . . . . . . . . . . . . . . . . . . 602.5 Descriptores. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 662.6 Forma prenexa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 702.7 Consideraciones nales. . . . . . . . . . . . . . . . . . . . . . . . 71CaptuloIII:Modelos 733.1 Conceptos b asicos . . . . . . . . . . . . . . . . . . . . . . . . . . 733.2 Verdad y validez l ogica . . . . . . . . . . . . . . . . . . . . . . . . 813.3 Consistencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89CaptuloIV:Lacompletitudsemantica 954.1 Completitud sint actica. . . . . . . . . . . . . . . . . . . . . . . . 964.2 La prueba del teorema de completitud . . . . . . . . . . . . . . . 1004.3 Consecuencias del teorema de completitud. . . . . . . . . . . . . 1064.4 Consideraciones nales. . . . . . . . . . . . . . . . . . . . . . . . 116CaptuloV:Teoradelarecursion 1195.1 Funciones recursivas . . . . . . . . . . . . . . . . . . . . . . . . . 1205.2 Relaciones recursivas . . . . . . . . . . . . . . . . . . . . . . . . . 1245.3 Conjuntos recursivos . . . . . . . . . . . . . . . . . . . . . . . . . 127vviINDICEGENERAL5.4 N umeros de Godel . . . . . . . . . . . . . . . . . . . . . . . . . . 1285.5 Funciones parciales . . . . . . . . . . . . . . . . . . . . . . . . . . 1375.6 M aquinas de Turing . . . . . . . . . . . . . . . . . . . . . . . . . 1395.7 La tesis de Church-Turing . . . . . . . . . . . . . . . . . . . . . . 1455.8 Consideraciones nales. . . . . . . . . . . . . . . . . . . . . . . . 150CaptuloVI:Teorasaritmeticas 1536.1 Denici on y propiedades b asicas . . . . . . . . . . . . . . . . . . 1536.2 Algunos teoremas en teoras aritmeticas . . . . . . . . . . . . . . 1566.3 Expresabilidad y representabilidad . . . . . . . . . . . . . . . . . 163CaptuloVII:Incompletitud 1757.1 El primer teorema de incompletitud . . . . . . . . . . . . . . . . 1757.2 El segundo teorema de incompletitud . . . . . . . . . . . . . . . . 1807.3 El teorema de Rosser . . . . . . . . . . . . . . . . . . . . . . . . . 1847.4 El teorema de Tarski . . . . . . . . . . . . . . . . . . . . . . . . . 1867.5 Otros resultados anes . . . . . . . . . . . . . . . . . . . . . . . . 1887.6 El teorema de Church . . . . . . . . . . . . . . . . . . . . . . . . 1907.7 Ecuaciones diof anticas . . . . . . . . . . . . . . . . . . . . . . . . 1922 Lal ogicadelateoradeconjuntos 213Introduccionalateoraaxiomaticadeconjuntos 215CaptuloVIII:Losaxiomasdelateoradeconjuntos 2238.1 La teora de conjuntos de von Neumann-Bernays-G odel . . . . . 2238.2 La teora de conjuntos de Zermelo-Fraenkel . . . . . . . . . . . . 2368.3 Los axiomas restantes de NBG y ZF . . . . . . . . . . . . . . . . 2428.4 Los n umeros naturales . . . . . . . . . . . . . . . . . . . . . . . . 2468.5 Eliminaci on de descriptores . . . . . . . . . . . . . . . . . . . . . 251CaptuloIX:Modelosdelateoradeconjuntos 2539.1 La consistencia de ZFCAI . . . . . . . . . . . . . . . . . . . . . 2539.2 Consis NBG implica Consis ZFC . . . . . . . . . . . . . . . . . . 2549.3 Consis ZFC implica Consis NBG . . . . . . . . . . . . . . . . . . 257CaptuloX:Laformalizaciondelalogicaenteoradeconjuntos 26510.1Lenguajes formales . . . . . . . . . . . . . . . . . . . . . . . . . . 26510.2Modelos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26910.3L ogica de segundo orden. . . . . . . . . . . . . . . . . . . . . . . 27010.4El lenguaje de la teora de conjuntos . . . . . . . . . . . . . . . . 27610.5Los teoremas de incompletitud . . . . . . . . . . . . . . . . . . . 27910.6Modelos que son clases propias . . . . . . . . . . . . . . . . . . . 284INDICEGENERAL vii3 Lateoradeconjuntos 289Introduccionalateoradeconjuntos 291CaptuloXI:N umerosordinales 30111.1La construccion de los ordinales . . . . . . . . . . . . . . . . . . . 30111.2Inducci on y recursi on transnita . . . . . . . . . . . . . . . . . . 30711.3Funciones normales . . . . . . . . . . . . . . . . . . . . . . . . . . 31311.4La aritmetica ordinal . . . . . . . . . . . . . . . . . . . . . . . . . 31411.5La forma normal de Cantor . . . . . . . . . . . . . . . . . . . . . 319CaptuloXII:Relacionesbienfundadas 32312.1Conceptos b asicos . . . . . . . . . . . . . . . . . . . . . . . . . . 32412.2Inducci on y recursi on transnita . . . . . . . . . . . . . . . . . . 32712.3Conjuntos regulares . . . . . . . . . . . . . . . . . . . . . . . . . 33312.4Atomos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337CaptuloXIII:N umeroscardinales 34113.1El axioma de eleccion . . . . . . . . . . . . . . . . . . . . . . . . 34113.2Cardinalidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34513.3La aritmetica cardinal . . . . . . . . . . . . . . . . . . . . . . . . 35313.4Sumas y productos innitos . . . . . . . . . . . . . . . . . . . . . 36113.5Conalidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366CaptuloXIV:Laexponenciacioncardinal 37314.1La exponenciaci on en ZFC . . . . . . . . . . . . . . . . . . . . . . 37314.2La hip otesis de los cardinales singulares . . . . . . . . . . . . . . 37914.3Cardinales fuertemente inaccesibles. . . . . . . . . . . . . . . . . 384CaptuloXV:Conjuntoscerradosnoacotados 39715.1Conjuntos cerrados no acotados. . . . . . . . . . . . . . . . . . . 39715.2Conjuntos estacionarios . . . . . . . . . . . . . . . . . . . . . . . 40115.3Un teorema de Silver. . . . . . . . . . . . . . . . . . . . . . . . . 40615.4Cardinales de Mahlo . . . . . . . . . . . . . . . . . . . . . . . . . 411ApendiceA:Conceptoselementalesdelateoradeconjuntos 415ApendiceB:Complementossobrearitmetica 421B.1 Hechos elementales . . . . . . . . . . . . . . . . . . . . . . . . . . 421B.2 Divisibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424B.3 Congruencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426B.4 Cuerpos cuadr aticos . . . . . . . . . . . . . . . . . . . . . . . . . 429Bibliografa 433IndicedeMaterias 435PrimeraparteL ogicadeprimerorden1Introducci onalal ogicamatematicaLa logica y su historia Tradicionalmente se ha dicho que la l ogica se ocupadel estudio del razonamiento. Esto hoy en da puede considerarse desbordadoporlaenormeextensi onydiversidadquehaalcanzadoestadisciplina, peropuede servirnos como primera aproximaci on a su contenido.Unmatematicocompetentedistinguesindicultadunademostraci onco-rrectadeunaincorrecta, omejordicho, unademostraci ondeotracosaqueaparenta serlo pero que no lo es. Sin embargo, no le pregunteis que es lo que en-tiende por demostraci on, pues a menos que ademas sepa logica no os sabraresponder, ni falta que le hace. El matem atico se las arregla para reconocer lavalidez de un argumento o sus defectos posibles de una forma improvisada pero,al menos en principio, de total abilidad. No necesita para su tarea contar conun concepto preciso de demostracion. Eso es en cambio lo que ocupa al l ogico:El matematico demuestra,el logico estudia lo que hace el matematico cuandodemuestra.Aqu sevuelveobligadalapreguntadehastaquepuntotieneestointeresy hasta que punto es una perdida de tiempo. Hemos dicho que el matematicose las arregla solo sin necesidad de que nadie le vigile los pasos, pero entonces,que hace ah el l ogico?Posiblemente la mejor forma de justicar el estudio dela l ogica sea dar una visi on, aunque breve, de las causas hist oricas que han dadoa la l ogica actual tal grado de prosperidad.En el sentido m as general de la palabra,el estudio de la l ogica se remontaal siglo IV a.C., cuando Arist oteles la puso a la cabeza de su sistema losococomomateriaindispensableparacualquierotraciencia. Lal ogicaaristotelicaera bastante rgida y estrecha de miras, pero con todo pervivi o casi inalterada,paralelamenteal restodesudoctrina, hastael sigloXVI. Apartirdeaqu,mientrassufsicafuesustituidaporlanuevafsicadeGalileoyNewton, lal ogica simplemente fue ignorada. Se mantuvo, pero en manos de l osofos y enparte de los matematicos con inclinaciones losocas, aunque sin jugar ning unpapel relevanteenel desarrollodelasciencias. Leibnizlediociertoimpulso,pero sin abandonar una postura conservadora. A principios del siglo XIX, lostrabajosdeBooleyalgunosotrosempezaronarelacionarlam asdirectamentecon la matematica, pero sin obtener nada que la hiciera especialmente relevante34(aunquelos trabajos deBoolecobraranimportanciam as tardepor motivosquiz a distintos de los que el mismo tena in mente).As pues, tenemos que, hasta mediados del siglo XIX, la l ogica era poco masqueunacuriosidadqueinteresabaaquienessentanalgunainquietudporlalosofa de la matematica o del pensamiento en general. La l ogica como hoy laentendemos surgio b asicamente con los trabajos de Frege y Peano. En principioestoseran, al igual quelosanteriores, nuevosensayossobreel razonamiento,si bienm ascomplejosyambiciosos. Loquelesdioimportanciafuequenoaparecieroncomoproductosdementesinquietas, sinocomoculminaciondelprocesodeformalizacionquelamatematicavenaexperimentandodesdelostiempos de Newton y Leibniz.En efecto, el calculo innitesimal que estos trazaron con tanta imaginaci onyquedespuesdesarrollaronCauchy, Gaussyotros, tuvoqueserprecisadoamedidaquesemanejabanconceptosmasgeneralesyabstractos. Dedekind,Riemann,Weierstrass,fueron sistematizando la matematica hasta el punto dedejarla construida esencialmente a partir de los n umeros naturales y de las pro-piedades elementales sobre los conjuntos. La obra de Frege y de Peano pretendaserel ultimoeslab ondeestacadena. Tratarondedarreglasprecisasquede-terminaran completamente la labor del matem atico, explicitando los puntos departida que haba que suponer as como los metodos usados para deducir nuevosresultados a partir de ellos.Si s olo fuera por esto, probablemente este trabajo habra acabado como unacuriosidad de presencia obligada en las primeras p aginas de cada libro introduc-torio a la matematica y que continuara interesando tan s olo a los matematicoscon inclinaciones los ocas. Pero sucedieron hechos que conrmaron la necesi-dad de la l ogica como herramienta matematica. A nales del siglo XIX, GeorgCantor cre o y desarroll o la parte m as general y mas abstracta de la matematicamoderna: la teora de conjuntos. No pas o mucho tiempo sin que el propio Can-tor, junto con otros muchos, descubriera descaradas contradicciones en la teora,es decir, se obtenan demostraciones de ciertos hechos y de sus contrarios, perode tal forma que burlaban el ojo crtico del matematico, tan de ar hasta enton-ces. Se obtenan pares de pruebas de forma que cada una por separado parecairreprochable pero que ambas juntas eran inadmisibles.El ejemplom as simpledeestos resultados fuedescubiertopor BertrandRussell al despojardecontenidomatem aticoaotrodebidoaCantor: Enlateora cantoriana se puede hablar de cualquier conjunto de objetos con tal de queseespeciquensuselementossinambig uedadalguna. EnparticularpodemosconsiderarelconjuntoRcuyoselementossonexactamenteaquellosconjuntosquenosonelementosdes mismos. Esfacil verquesi Resunelementodes mismo, entoncespordenici onnodeberaserlo, yviceversa. Endenitivaresultaque Rnopuedeni pertenecersecomoelementoni nohacerlo. Estocontradice a la l ogica mas elemental.El lector puede pensar que esto es una tontera y que basta no preocuparsede estas cosas para librarnos de tales problemas, sin embargo sucede que contra-dicciones similares surgen continuamente en la teora pero afectando a conjuntosno tan articiales y rebuscados como pueda parecer el conjuntoR, sino a otros5queaparecendeformanatural al trabajarenlamateria. Encualquiercasoestoshechosmostrabanqueel criterioqueconadamentehanvenidousandodesdesiemprelosmatematicosnoesinmuneaerroresdifcilespornodecirimposibles de detectar, al menos al enfrentarse a la teora de conjuntos.La primera muestra de la importancia de la l ogica fue un estrepitoso fracaso.Frege haba creado (tras mucho tiempo de cuidadosa reexi on) un sistema quepretendaregulartodoelrazonamientomatem atico, demaneraquecualquierresultado que un matem atico pudiera demostrar, debera poder demostrarse si-guiendo las reglas que con tanto detalle haba descrito. Russell observo que laparadoja antes citada poda probarse en el sistema de Frege y que, a consecuen-cia de esto, cualquier armaci on, fuera la que fuera, poda ser demostrada seg unestas reglas, que se volvan, por tanto, completamente in utiles.Este desastre, no obstante, mostraba que la laboriosa tarea de Frege no eraen modo alguno trivial, y urga encontrar una sustituta a su fallida teora. Con eltiempo surgieron varias opciones. La primera fueron los Principia Mathematicade Whitehead y Russell, de una terrible complejidad l ogica, a la que siguieronmuchas teoras bastante mas simples aunque quiz a menos naturales. Destacanentre ellas las teoras de conjuntos de Zermelo-Fraenkel (ZF) y de von Neumann-Bernays-Godel (NBG). Ambas constan de unos principios b asicos (axiomas) yunasreglasprecisasdedemostracionquepermitendeducirdeellostodoslosteoremas matematicos y hasta donde hoy se sabe ninguna contradicci on.De esta forma la logica ha probado ser indispensable a la hora de trabajaren teora de conjuntos, hasta el punto de que es inconcebible el estudio de estasin un buen conocimiento de aquella.El contenidode la logica matematica Enel apartadoanterior hemosmostradounadelasfuncionesprincipalesdelal ogicamatematica: servirdefundamento al razonamiento matem atico, evitando ambig uedades y contradic-ciones mediante la determinacion absolutamente precisa y rigurosa de lo que esun razonamiento matem atico v alido. Pero cuando la necesidad obliga al estudiode un determinado campo, el esfuerzo pronto es premiado con nuevos resultadosinesperados:Si uno tiene paciencia o un libro de geometra a mano, puede coger una reglayuncomp asydibujarunpent agonoregular. Siahorapruebasuerteconunhept agono no encontrar a ning un libro de ayuda y la paciencia servir a de muypoco. Puede probarse que es imposible construir un hept agono regular sin m asayudaqueunaregla(nograduada)yuncomp as, pero, parademostrarlonobasta con coger una regla y un comp...</p>