Next:
Notación y conceptos básicos
Computabilidad y lógica
Diego Vaggione
14 de abril de 2026
1
Notación y conceptos básicos
1.1
Conjuntos
1.2
Producto Cartesiano
1.3
Alfabetos
1.3.1
Ocurrencias
1.4
Numerales
1.5
Matemática orientada a objetos
1.6
Escarabajo y Mariposa
1.7
El concepto de función
1.7.1
Igualdad de funciones
1.7.2
Función identidad
1.7.3
Composición de funciones
1.7.4
Regla Pertenecer a la Imagen
1.7.5
Funciones inyectivas, suryectivas y biyectivas
1.7.6
El núcleo de una función
1.7.7
Función característica de un subconjunto
1.7.8
Restricción de una función
1.7.9
Funciones de la forma
\([f_{1},...,f_{n}]\)
1.7.10
Unión de funciones con dominios disjuntos
1.8
Principio de Inducción
1.8.1
Variaciones del Principio de Inducción
1.8.2
Inducción Completa
1.8.3
El caso en que la sucesión de enunciados es finita
1.8.4
El principio de inducción usado en la ficción de una prueba
1.9
Relaciones binarias
1.9.1
Propiedades notables de relaciones binarias
1.9.2
Ordenes parciales
1.9.3
Relaciones de equivalencia
1.10
Operaciones
\(n\)
-arias sobre un conjunto
1.11
Relaciones
\(n\)
-arias sobre un conjunto
1.12
Funciones y conjuntos
\(\Sigma\)
-mixtos
1.12.1
Definición de función
\(\Sigma\)
-mixta
1.12.2
El tipo de una función mixta
1.12.3
Funciones con imagen contenida en
\(\omega^{n}\times\Sigma^{\ast m}\)
1.12.4
Predicados
\(\Sigma\)
-mixtos
1.12.5
Familias
\(\Sigma\)
-indexadas de funciones
1.12.6
Definición de conjunto
\(\Sigma\)
-mixto
1.12.7
El tipo de un conjunto mixto
1.12.8
Conjuntos rectangulares
1.12.9
Notación lambda
2
Dos codificaciones importantes
2.1
Ordenes naturales sobre
\(\Sigma^{\ast}\)
2.1.1
Notación decimal sin
\(0\)
2.1.2
El caso general
2.2
Codificación de infinituplas de números
3
Procedimientos efectivos
3.1
Funciones
\(\Sigma\)
-efectivamente computables
3.2
Conjuntos
\(\Sigma\)
-efectivamente computables
3.3
Conjuntos
\(\Sigma\)
-efectivamente enumerables
3.4
Algunos constructores que preservan la computabilidad efectiva
3.4.1
Operaciones logicas entre predicados
3.4.2
Composición
3.4.3
Lema de división por casos para funciones
\(\Sigma\)
-efectivamente computables
3.5
Independencia del alfabeto
4
Tres modelos matemáticos de la computabilidad efectiva
4.1
El paradigma de Turing
4.1.1
Descripción informal de las máquinas de Turing
4.1.2
Definición matemática de máquina de Turing
4.1.3
Funciones
\(\Sigma\)
-Turing computables
4.1.4
Conjuntos
\(\Sigma\)
-Turing enumerables
4.1.5
Conjuntos
\(\Sigma\)
-Turing computables
4.2
El paradigma de Godel: Funciones
\(\Sigma\)
-recursivas
4.2.1
Composición
4.2.2
Recursión primitiva
4.2.3
Funciones
\(\Sigma\)
-recursivas primitivas
4.2.4
Minimización y funciones
\(\Sigma\)
-recursivas
4.2.5
Conjuntos
\(\Sigma\)
-recursivamente enumerables
4.2.6
Conjuntos
\(\Sigma\)
-recursivos
4.2.7
Algunos resultados básicos
4.2.8
Recursión primitiva sobre valores anteriores
4.2.9
Independencia del alfabeto
4.2.10
Funciones recursivas clásicas
4.3
El paradigma imperativo de Neumann: El lenguaje
\(\mathcal{S}^{\Sigma}\)
4.3.1
Sintaxis de
\(\mathcal{S}^{\Sigma}\)
4.3.2
Semántica de
\(\mathcal{S}^{\Sigma}\)
4.3.3
Funciones
\(\Sigma\)
-computables
4.3.4
Macros
4.3.5
Conjuntos
\(\Sigma\)
-enumerables
4.3.6
Conjuntos
\(\Sigma\)
-computables
4.4
Batallas entre paradigmas
4.4.1
Neumann vence a Godel
4.4.2
Godel vence a Neumann
4.4.3
Godel vence a Turing
4.4.4
Turing vence a Neumann
4.5
Conclusiones: La tesis de Church
4.6
Resultados básicos presentados en paradigma recursivo
4.6.1
Lema de división por casos para funciones
\(\Sigma\)
-recursivas
4.6.2
Conjuntos
\(\Sigma\)
-recursivos y
\(\Sigma\)
-recursivamente enumerables
4.6.3
El halting problem y los conjuntos
\(A\)
y
\(N\)
5
Estructuras algebraicas ordenadas
5.1
Conjuntos parcialmente ordenados
5.1.1
Ordenes totales sobre un conjunto
5.1.2
Conjuntos parcialmente ordenados o posets
5.1.3
Conjuntos totalmente ordenados
5.1.4
Diagrama de Hasse de un poset
5.1.5
Elementos maximales, máximos, minimales y mínimos
5.1.6
Supremos
5.1.7
Ínfimos
5.1.8
Homomorfismos de posets
5.2
Reticulados par
5.3
Reticulados terna
Reflexión Informática
El orden asociado a un reticulado terna
Convenciones notacionales
5.3.1
Subreticulados terna
5.3.2
Homomorfismos de reticulados terna
5.3.3
Congruencias de reticulados terna
5.4
Reticulados acotados
Reflexión Informática
El orden asociado a un reticulado acotado
5.4.1
Subreticulados acotados
5.4.2
Homomorfismos de reticulados acotados
5.4.3
Congruencias de reticulados acotados
5.5
Reticulados complementados
Reflexión Informática
El orden asociado a un reticulado complementado
5.5.1
Subreticulados complementados
5.5.2
Homomorfismos de reticulados complementados
5.5.3
Congruencias de reticulados complementados
5.6
Álgebras de Boole
5.7
Teoremas del filtro primo y de Rasiowa Sikorski
5.8
Reticulados cuaterna y su lenguaje elemental
5.8.1
Términos elementales de reticulados cuaterna
5.8.2
fórmulas elementales de reticulados cuaterna
5.8.3
Pruebas elementales de reticulados cuaterna
6
Estructuras y su lenguaje elemental
6.1
Posets
6.2
Reticulados complementados
6.3
Grafos
6.4
Grafos bicoloreados
6.5
Median algebras
6.6
Pruebas elementales
6.6.1
Pruebas elementales de posets
6.6.2
Pruebas elementales de reticulados terna
6.6.3
Pruebas elementales de reticulados acotados
6.6.4
Pruebas elementales de reticulados complementados
6.6.5
Pruebas elementales de grafos
6.6.6
Pruebas elementales de median algebras
6.6.7
Pruebas elementales de grafos bicoloreados
6.7
Limitaciones del poder expresivo de las fórmulas elementales
6.8
Extendiendo el concepto de verdad
7
Lógica matemática
7.1
Tipos
7.1.1
Notación práctica
7.2
Estructuras de tipo
\(\tau\)
Conteo de estructuras
7.2.1
Independencia entre sintaxis y semántica
7.3
Un poco de arrogancia
7.4
Términos y fórmulas elementales de tipo
\(\tau\)
7.4.1
Términos elementales de tipo
\(\tau\)
7.4.2
Fórmulas elementales de tipo
\(\tau\)
7.4.3
Variables libres, acotadas y alcance de un cuantificador
7.5
Valores de términos y fórmulas elementales para una estructura dada
7.6
Teorías elementales y pruebas elementales
7.6.1
Pruebas elementales en una teoría elemental
\((\Sigma,\tau)\)
7.7
Programa de Lógica Matemática
7.8
Modelo matemático de las fórmulas elementales
7.8.1
Variables
7.8.2
Términos
7.8.3
Fórmulas
7.8.4
Modelo matemático de las fórmulas elementales de tipo
\(\tau\)
7.9
Modelo matemático del valor de verdad de una fórmula
7.9.1
El valor de un término en una estructura
7.9.2
La relación
\(\models\)
7.9.3
Sentencias universalmente válidas
7.9.4
Equivalencia de fórmulas
7.9.5
El valor de verdad es “efectivamente computable” en el caso finito
7.9.6
Hemos creado un monstruo?
7.10
Un poco de semántica
7.10.1
Homomorfismos
7.10.2
Álgebras
7.11
Notación declaratoria
7.11.1
Notación declaratoria para términos
7.11.2
Notación declaratoria para fórmulas
7.12
Dos Teoremas de Reemplazo
7.12.1
Teorema de Reemplazo para Términos
7.12.2
Teorema de Reemplazo para Fórmulas
7.13
Teorías de Primer Orden
7.13.1
Definición del Concepto de Prueba Formal
La Regla Generalización
La Regla de Elección
7.13.2
El Concepto de Teorema
7.13.3
Simulación de Mecánicas de Prueba (Azuquita para Escarabajo)
7.13.4
Redundancia de Axiomas y Reglas
7.13.5
Propiedades Básicas de Pruebas y Teoremas
7.13.6
Consistencia
7.13.7
El Teorema de Corrección
7.13.8
El Álgebra de Lindenbaum
7.13.9
Teorema de Completitud
7.13.10
Interpretación Semántica del Álgebra de Lindenbaum
7.13.11
Teorías Completas
7.13.12
La Aritmética de Peano
7.14
Lógica Ecuacional
7.14.1
Pruebas Ecuacionales
7.14.2
Teorema de Corrección Ecuacional
7.14.3
Teorema de Completitud Ecuacional
7.15
Teorema de Incompletitud
7.15.1
Análisis de Recursividad del Lenguaje de Primer Orden
7.15.2
Funciones Representables
7.15.3
Prueba del Teorema de Incompletitud