Logica

Carlos Ivorra Castillo

´
LOGICA
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
1.1 Introducci´
on a los lenguajes formales .
1.2 Definici´
on de lenguaje formal . . . . .
1.3Expresiones, t´erminos y f´
ormulas . . .
1.4 Variables libres y ligadas . . . . . . . .
1.5 Sustituci´
on de variables . . . . . . . .
1.6 Consideraciones finales . . . . . . . . .

orden
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .

Cap´ıtulo II: Sistemas deductivos formales
2.1 El c´
alculo deductivo de primer orden . .
2.2 Reglas derivadas de inferencia . . . . . .
2.3 T´ecnicas de deducci´
on .. . . . . . . . .
2.4 Teor´ıas axiom´
aticas . . . . . . . . . . . .
2.5 Descriptores . . . . . . . . . . . . . . . .
2.6 Forma prenexa . . . . . . . . . . . . . .
2.7 Consideraciones finales . . . . . . . . . .

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.17
17
23
26
30
32
35

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

39
40
45
53
60
66
70
71

Cap´ıtulo III: Modelos
73
3.1 Conceptos b´
asicos . . . . . . . . . . . . . . . . . . . . . . . . . . 73
3.2 Verdad y validez l´
ogica . . . . . . . . . . . . . . . . . . . . . . . . 813.3 Consistencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
Cap´ıtulo IV: La completitud sem´
antica
4.1 Completitud sint´
actica . . . . . . . . . . .
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´ıa de la recursi´
on
119
5.1 Funciones recursivas . . . . . . . . . . . . . . . . . . . . . . . . . 120
5.2 Relaciones recursivas . . . . . . . . . . . . . . . . . . . . . . . . . 124
5.3 Conjuntos recursivos . . . . . . . . . . . . . . . . . . . . . . . . . 127
v

´INDICE GENERAL

vi
5.4
5.5
5.6
5.7
5.8

N´
umeros de G¨
odel . . ..
Funciones parciales . . . .
M´
aquinas de Turing . . .
La tesis de Church-Turing
Consideraciones finales . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

128
137
139
145
150

Cap´ıtulo VI: Teor´ıasaritm´
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
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´
anticas . . . . . . . . .

2

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
..
.

.
.
.
.
.
.
.

175
175
180
184
186
188
190
192

La l´
ogica de la 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
8.1 La teor´ıa de conjuntos de von Neumann-Bernays-G¨
odel
8.2 La teor´ıa de conjuntos de Zermelo-Fraenkel . . . . . . .
8.3 Los axiomas restantes de NBG y ZF . . . . . . . . . . .
8.4...