Logica2

Carlos Ivorra Castillo

´
´
LOGICA
MATEMATICA

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

´Indice General
Introducci´
on a la l´
ogica matem´
atica

ix

1

1

L´
ogica de primer orden

Cap´ıtulo I: Lenguajes y modelos
1.1 Estructuras . . . . . . . . . . . .
1.2 Lenguajes formales y modelos . .
1.3 Expresiones, t´erminos y f´
ormulas
1.4Variables libres y ligadas . . . . .
1.5 Sustituci´
on . . . . . . . . . . . .
1.6 F´
ormulas verdaderas y falsas . .
1.7 Consideraciones finales . . . . . .

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
..
.
.
.
.
.
.

.
.
.
.
.
.
.

3
4
7
15
24
27
35
37

Cap´ıtulo II: El c´
alculo deductivo
2.1 Reglas de inferencia sem´
anticas
2.2 Sistemas deductivos formales .
2.3 Reglas derivadas de inferencia .
2.4 Algunos teoremas l´
ogicos . . .
2.5 Consideraciones finales . . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
..
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

39
39
45
57
69
74

Cap´ıtulo III: Teor´ıas axiom´
aticas
3.1 Consistencia y completitud .
3.2 La teor´ıa b´
asica de conjuntos
3.3 La teor´ıa de Zermelo . . . . .
3.4 Interpretaciones de teor´ıas . .
3.5 Descriptores . . . . . . . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
..
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

75
. 75
. 80
. 97
. 101
. 107

Cap´ıtulo IV: La completitud sem´
antica
4.1 Conjuntos maximalmente consistentes . .
4.2 La prueba del teorema de completitud . .
4.3 Consecuencias del teorema de completitud
4.4 Consideraciones finales . . . . . . . . . . .

.
.
.
.

.
.
.
.

.
..
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.
.

v

113
114
119
125
135

´INDICE GENERAL

vi

2

Teor´ıas aritm´
eticas

Cap´ıtulo V: La aritm´
etica de Peano
5.1 La aritm´etica de Robinson . . . . . .
5.2 La aritm´etica con inducci´
on abierta .
5.3 La jerarqu´ıa de Kleene . . . . . . . .
5.4 Relaciones y funciones aritm´eticas .
5.5Conjuntos en IΣ1 . . . . . . . . . . .

139
.
.
.
.
.

.
.
.
.
.

Cap´ıtulo VI: La teor´ıa de Kripke-Platek
6.1 La jerarqu´ıa de L´evy . . . . . . . . . . .
6.2 La teor´ıa KP . . . . . . . . . . . . . . .
6.3 KP como teor´ıa aritm´etica . . . . . . . .
6.4 Conceptos conjuntistas b´
asicos . . . . .
6.5 Recolecci´
on, especificaci´
on y reemplazo .
6.6 Conjuntos finitos, cardinales . . . . . . .
6.7Sucesiones . . . . . . . . . . . . . . . . .
6.8 Sumas finitas . . . . . . . . . . . . . . .
6.9 IΣ1 como teor´ıa de conjuntos . . . . . .
6.10 La formalizaci´
on de la aritm´etica . . . .
Cap´ıtulo VII: La teor´ıa de la recursi´
on
7.1 Funciones y relaciones recursivas . . . .
7.2 Caracterizaci´
on aritm´etica . . . . . . . .
7.3 Funciones recursivas parciales . . . . . .
7.4 M´
aquinas de Turing . .. . . . . . . . .
7.5 La tesis de Church-Turing . . . . . . . .
7.6 Codificaci´
on de las funciones recursivas .
7.7 Relaciones diof´
anticas . . . . . . . . . .

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
..
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.

141
141
149...