Next:
Notación y conceptos básicos
Computabilidad y lógica
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
Matematica orientada a objetos
1.6
El concepto de funcion
1.6.1
Igualdad de funciones
1.6.2
Funcion identidad
1.6.3
Composicion de funciones
1.6.4
Regla Pertenecer a la Imagen
1.6.5
Funciones inyectivas, suryectivas y biyectivas
1.6.6
El nucleo de una funcion
1.6.7
Funcion caracteristica de un subconjunto
1.6.8
Restriccion de una funcion
1.6.9
Funciones de la forma
\([f_{1},...,f_{n}]\)
1.6.10
Union de funciones con dominios disjuntos
1.7
Relaciones binarias
1.7.1
Propiedades notables de relaciones binarias
1.7.2
Ordenes parciales
1.7.3
Relaciones de equivalencia
1.8
Operaciones
\(n\)
-arias sobre un conjunto
1.9
Relaciones
\(n\)
-arias sobre un conjunto
1.10
Funciones y conjuntos
\(\Sigma\)
-mixtos
1.10.1
Definicion de funcion
\(\Sigma\)
-mixta
1.10.2
El tipo de una funcion mixta
1.10.3
Funciones con imagen contenida en
\(\omega^{n}\times\Sigma^{\ast m}\)
1.10.4
Predicados
\(\Sigma\)
-mixtos
1.10.5
Familias
\(\Sigma\)
-indexadas de funciones
1.10.6
Definicion de conjunto
\(\Sigma\)
-mixto
1.10.7
El tipo de un conjunto mixto
1.10.8
Conjuntos rectangulares
1.10.9
Notacion lambda
2
Dos codificaciones importantes
2.1
Ordenes naturales sobre
\(\Sigma^{\ast}\)
2.1.1
Notacion decimal sin
\(0\)
2.1.2
El caso general
2.2
Codificacion de infinituplas de numeros
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 computabilidad efectiva
3.4.1
Composicion
3.4.2
Lema de division por casos para funciones
\(\Sigma\)
-efectivamente computables
3.5
Independencia del alfabeto
4
Tres modelos matematicos de la computabilidad efectiva
4.1
El paradigma de Turing
4.1.1
Descripcion informal de las maquinas de Turing
4.1.2
Definicion matematica de maquina 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
Composicion
4.2.2
Recursion primitiva
4.2.3
Funciones
\(\Sigma\)
-recursivas primitivas
4.2.4
Minimizacion y funciones
\(\Sigma\)
-recursivas
4.2.5
Conjuntos
\(\Sigma\)
-recursivamente enumerables
4.2.6
Conjuntos
\(\Sigma\)
-recursivos
4.2.7
Algunos resultados basicos
4.2.8
Recursion primitiva sobre valores anteriores
4.2.9
Independencia del alfabeto
4.3
El paradigma imperativo de Neumann: El lenguaje
\(\mathcal{S}^{\Sigma}\)
4.3.1
Sintaxis de
\(\mathcal{S}^{\Sigma}\)
4.3.2
Semantica 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 basicos presentados en paradigma recursivo
4.6.1
Lema de division 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
Diagramas de Hasse
5.1.2
Elementos maximales, maximos, minimales y minimos
5.1.3
Supremos
5.1.4
Infimos
5.1.5
Homomorfismos de posets
5.2
Reticulados par
5.3
Reticulados terna
Refleccion Informatica
El orden asociado a un reticulado terna
Convencion notacional
Convencion notacional
5.3.1
Subreticulados terna
5.3.2
Homomorfismos de reticulados terna
5.3.3
Congruencias de reticulados terna
5.4
Reticulados acotados
Reflexion Informatica
El orden asociado a un reticulado acotado
Convencion notacional
5.4.1
Subreticulados acotados
5.4.2
Homomorfismos de reticulados acotados
5.4.3
Congruencias de reticulados acotados
5.5
Reticulados complementados
Reflexion Informatica
El orden asociado a un reticulado complementado
Convencion notacional
5.5.1
Subreticulados complementados
5.5.2
Homomorfismos de reticulados complementados
5.5.3
Congruencias de reticulados complementados
5.6
Algebras de Boole
5.7
Teoremas del filtro primo y de Rasiowa Sikorski
5.8
Reticulados cuaterna y su lenguaje elemental
5.8.1
Terminos elementales de reticulados cuaterna
5.8.2
Formulas 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
Axiomas elementales de posets
Axiomas elementales de reticulados terna
Axiomas elementales de reticulados acotados
Axiomas elementales de reticulados complementados
Axiomas elementales de reticulados cuaterna
Axiomas elementales de grafos
Axiomas elementales de grafos bicoloreados
Axiomas elementales de median algebras
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 grafos
6.6.5
Pruebas elementales de median algebras
6.6.6
Pruebas elementales de grafos bicoloreados
6.6.7
Limitaciones del poder expresivo de las formulas elementales
6.6.8
Extendiendo el concepto de verdad
7
Logica matematica
7.1
Tipos
7.2
Estructuras de tipo
\(\tau\)
Conteo de estructuras
7.2.1
Independencia entre sintaxis y semantica
7.3
Un poco de arrogancia
7.4
Formulas elementales de tipo
\(\tau\)
Terminos elementales puros de tipo
\(\tau\)
Formulas elementales puras de tipo
\(\tau\)
7.4.1
Variables libres, acotadas y alcance de un cuantificador
7.4.2
Valores de terminos y formulas para una estructura dada
7.5
Teorias elementales y pruebas elementales
7.5.1
Pruebas elementales en una teoria elemental
\((\Sigma,\tau)\)
7.6
Programa de Logica Matematica
7.7
Modelo matematico de las formulas elementales
7.7.1
Variables
7.7.2
Terminos
7.7.3
Formulas
7.7.4
Modelo matematico de las formulas elementales de tipo
\(\tau\)
7.8
Modelo matematico del valor de verdad de una formula
7.8.1
El valor de un termino en una estructura
7.8.2
La relacion
\(\models\)
7.8.3
Equivalencia de formulas
7.9
Un poco de semantica
7.9.1
Homomorfismos
7.9.2
Algebras
7.10
Notacion declaratoria
7.10.1
Notacion declaratoria para terminos
7.10.2
Notacion declaratoria para formulas
7.11
Dos teoremas de reemplazo
7.11.1
Teorema de reemplazo para terminos
7.11.2
Teorema de reemplazo para formulas
7.12
Teorias de primer orden
7.12.1
Definicion del concepto de prueba formal
7.12.2
El concepto de teorema
7.12.3
Azuquita para escarabajo
7.12.4
Redundancia de axiomas y reglas
7.12.5
Propiedades basicas de pruebas y teoremas
7.12.6
Consistencia
7.12.7
El Teorema de Correccion
7.12.8
El algebra de Lindenbaum
7.12.9
Teorema de Completitud
7.12.10
Interpretacion semantica del algebra de Lindenbaum
7.12.11
Teorias completas
7.12.12
La aritmetica de Peano
7.13
Logica ecuacional
7.13.1
Pruebas ecuacionales
7.13.2
Correccion ecuacional
7.13.3
Completitud ecuacional
7.14
Teorema de incompletitud
7.14.1
Analisis de recursividad del lenguaje de primer orden
7.14.2
Funciones representables
7.14.3
Prueba del teorema de incompletitud