Informatica

Carlos Ivorra Castillo
L´OGICA Y TEOR´IA DE
CONJUNTOS

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

´Indice General
1 L´ogica de primer orden 1
Introducci´on a la l´ogica matem´atica 3
Cap´ıtulo I: Lenguajes formales de primer orden 17
1.1 Introducci´on a los lenguajes formales . . . . . . . . . . . . . . . . 17
1.2 Definici´on delenguaje formal . . . . . . . . . . . . . . . . . . . . 23
1.3 Expresiones, t´erminos y f´ormulas . . . . . . . . . . . . . . . . . . 26
1.4 Variables libres y ligadas . . . . . . . . . . . . . . . . . . . . . . . 30
1.5 Sustituci´on de variables . . . . . . . . . . . . . . . . . . . . . . . 32
1.6 Consideraciones finales . . . . . . . . . . . . . . . . . . . . . . . . 35
Cap´ıtulo II:Sistemas deductivos formales 39
2.1 El c´alculo deductivo de primer orden . . . . . . . . . . . . . . . . 40
2.2 Reglas derivadas de inferencia . . . . . . . . . . . . . . . . . . . . 45
2.3 T´ecnicas de deducci´on . . . . . . . . . . . . . . . . . . . . . . . . 53
2.4 Teor´ıas axiom´aticas . . . . . . . . . . . . . . . . . . . . . . . . . . 60
2.5 Descriptores . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . 66
2.6 Forma prenexa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
2.7 Consideraciones finales . . . . . . . . . . . . . . . . . . . . . . . . 71
Cap´ıtulo III: Modelos 73
3.1 Conceptos b´asicos . . . . . . . . . . . . . . . . . . . . . . . . . . 73
3.2 Verdad y validez l´ogica . . . . . . . . . . . . . . . . . . . . . . . . 81
3.3 Consistencia . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . 89
Cap´ıtulo IV: La completitud sem´antica 95
4.1 Completitud sint´actica . . . . . . . . . . . . . . . . . . . . . . . . 96
4.2 La prueba del teorema de completitud . . . . . . . . . . . . . . . 100
4.3 Consecuencias del teorema de completitud . . . . . . . . . . . . . 106
4.4 Consideraciones finales . . . . . . . . . . . . . . . . . . . . .. . . 116
Cap´ıtulo V: Teor´ıa de la recursi´on 119
5.1 Funciones recursivas . . . . . . . . . . . . . . . . . . . . . . . . . 120
5.2 Relaciones recursivas . . . . . . . . . . . . . . . . . . . . . . . . . 124
5.3 Conjuntos recursivos . . . . . . . . . . . . . . . . . . . . . . . . . 127
v
vi ´INDICE GENERAL
5.4 N´umeros de G¨odel . . . . . . . . . . . . . . . . . . . . . . . . . . 1285.5 Funciones parciales . . . . . . . . . . . . . . . . . . . . . . . . . . 137
5.6 M´aquinas de Turing . . . . . . . . . . . . . . . . . . . . . . . . . 139
5.7 La tesis de Church-Turing . . . . . . . . . . . . . . . . . . . . . . 145
5.8 Consideraciones finales . . . . . . . . . . . . . . . . . . . . . . . . 150
Cap´ıtulo VI: Teor´ıas aritm´eticas 153
6.1 Definici´on y propiedades b´asicas .. . . . . . . . . . . . . . . . . 153
6.2 Algunos teoremas en teor´ıas aritm´eticas . . . . . . . . . . . . . . 156
6.3 Expresabilidad y representabilidad . . . . . . . . . . . . . . . . . 163
Cap´ıtulo VII: Incompletitud 175
7.1 El primer teorema de incompletitud . . . . . . . . . . . . . . . . 175
7.2 El segundo teorema de incompletitud . . . . . . . . . . . . . . . . 180
7.3 El teorema deRosser . . . . . . . . . . . . . . . . . . . . . . . . . 184
7.4 El teorema de Tarski . . . . . . . . . . . . . . . . . . . . . . . . . 186
7.5 Otros resultados afines . . . . . . . . . . . . . . . . . . . . . . . . 188
7.6 El teorema de Church . . . . . . . . . . . . . . . . . . . . . . . . 190
7.7 Ecuaciones diof´anticas . . . . . . . . . . . . . . . . . . . . . . . . 192
2 La l´ogica dela teor´ıa de conjuntos 213
Introducci´on a la teor´ıa axiom´atica de conjuntos 215
Cap´ıtulo VIII: Los axiomas de la teor´ıa de conjuntos 223
8.1 La teor´ıa de conjuntos de von Neumann-Bernays-G¨odel . . . . . 223
8.2 La teor´ıa de conjuntos de Zermelo-Fraenkel . . . . . . . . . . . . 236
8.3 Los axiomas restantes de NBG y ZF . . . . . . . . . . . . . . . . 242
8.4 Los n´umeros naturales ....