MATEMATICAS

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 delenguaje formal . . . . .
1.3 Expresiones, 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 deinferencia . . . . . .
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
59
66
69
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
4.1Completitud 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´
aquinasde Turing . . .
La tesis de Church-Turing
Consideraciones finales . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
..
.
.

.
.
.
.
.

.
.
.
.
.

128
137
139
145
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
7.1 Elprimer 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

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
....