Logica y teoria de conjuntos

Carlos Ivorra Castillo

´ LOGICA Y TEOR´ DE IA CONJUNTOS

No puedes encontrar la verdad con la l´gica si no o la has encontrado ya sin ella. G.K. Chesterton

´ Indice General
1 L´gica de primer orden o 1
3 orden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 17 23 26 30 32 35 39 40 45 53 59 66 69 71 Introducci´n a la l´gica matem´tica o o a Cap´ ıtulo I: Lenguajes formales de primer 1.1 Introducci´n a los lenguajes formales . o 1.2 Definici´n delenguaje formal . . . . . o 1.3 Expresiones, t´rminos y f´rmulas . . . e o 1.4 Variables libres y ligadas . . . . . . . . 1.5 Sustituci´n de variables . . . . . . . . o 1.6 Consideraciones finales . . . . . . . . .

Cap´ ıtulo II: Sistemas deductivos formales 2.1 El c´lculo deductivo de primer orden . . a 2.2 Reglas derivadas de inferencia . . . . . . 2.3 T´cnicas de deducci´n . . . . . . . . . . e o2.4 Teor´ axiom´ticas . . . . . . . . . . . . ıas a 2.5 Descriptores . . . . . . . . . . . . . . . . 2.6 Forma prenexa . . . . . . . . . . . . . . 2.7 Consideraciones finales . . . . . . . . . .

ıtulo III: Modelos 73 Cap´ 3.1 Conceptos b´sicos . . . . . . . . . . . . . . . . . . . . . . . . . . 73 a 3.2 Verdad y validez l´gica . . . . . . . . . . . . . . . . . . . . . . . . 81 o 3.3 Consistencia. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 ıtulo IV: La completitud sem´ntica a Cap´ a 4.1 Completitud sint´ctica . . . . . . . . . . . 4.2 La prueba del teorema de completitud . . 4.3 Consecuencias del teorema de completitud 4.4 Consideraciones finales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 . 96 .100 . 106 . 116

Cap´ ıtulo V: Teor´ de la recursi´n ıa o 119 5.1 Funciones recursivas . . . . . . . . . . . . . . . . . . . . . . . . . 120 5.2 Relaciones recursivas . . . . . . . . . . . . . . . . . . . . . . . . . 124 5.3 Conjuntos recursivos . . . . . . . . . . . . . . . . . . . . . . . . . 127 v

vi 5.4 5.5 5.6 5.7 5.8 N´meros de G¨del . . . . u o Funciones parciales . . . . M´quinas deTuring . . . a La tesis de Church-Turing Consideraciones finales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

´ INDICE GENERAL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 137 139 145 150

Cap´ ıtulo VI: Teor´ aritm´ticas ıas e 153 6.1 Definici´n ypropiedades b´sicas . . . . . . . . . . . . . . . . . . 153 o a 6.2 Algunos teoremas en teor´ aritm´ticas . . . . . . . . . . . . . . 156 ıas e 6.3 Expresabilidad y representabilidad . . . . . . . . . . . . . . . . . 163 Cap´ ıtulo VII: Incompletitud 7.1 El primer teorema de incompletitud 7.2 El segundo teorema de incompletitud 7.3 El teorema de Rosser . . . . . . . . . 7.4 El teorema de Tarski . . . . . .. . . 7.5 Otros resultados afines . . . . . . . . 7.6 El teorema de Church . . . . . . . . 7.7 Ecuaciones diof´nticas . . . . . . . . a 175 175 180 184 186 188 190 192

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . .. . .

. . . . . . .

. . . . . . .

2

La l´gica de la teor´ de conjuntos o ıa

213
215 223 223 236 242 246 251

Introducci´n a la teor´ axiom´tica de conjuntos o ıa a Cap´ ıtulo VIII: Los axiomas de la teor´ de conjuntos ıa 8.1 La teor´ de conjuntos de von Neumann-Bernays-G¨del ıa o 8.2 La teor´ de conjuntos de Zermelo-Fraenkel . . . . . . . ıa 8.3 Los axiomas restantes de NBG y...