examen final - FECHA, SALÓN Y HORA

AVISO IMPORTANTE (II)

El examen final será oficialmente el 2 de diciembre, a las 11 am, en el salón 313 del edificio 405 (el "nuevo" de matemáticas).

Habrá horas de oficina para preguntas de preparación el martes 30, de 2:30 a 4:00 pm.

examen final - FECHA

AVISO IMPORTANTE

El examen final fue oficialmente programado para el lunes 29 de noviembre. Ojo: ese día más de ocho estudiantes tienen otro examen justo a la misma hora. Por lo tanto, cambiamos oficialmente la fecha de nuestro examen al jueves 2 de diciembre, de 11 a 13. Todos los estudiantes que estaban en clase hoy dijeron que esa nueva fecha es posible.

fin de semestre

Nos quedan dos clases este semestre. Mañana miércoles planeo ver los temas que enumero más adelante, y el viernes básicamente haré sesión de repaso, preguntas y ejercicios (importantísimo estar ahí, pues algunas de las cosas que se discutan aparecerán seguro en el examen final).

Los temas de mañana:

1. Forma normal prenexa (en deuda antigua) - estratificación de las fórmulas - definibilidad refinada
2. Esquema (muy esquelético) del teorema de Gödel

El semestre entrante no ofrecemos teoría de modelos (se ofrece cada dos semestres). Pero si le llamaron la atención algunos de los últimos temas, tengan en mente la posibilidad de tomar teoría de modelos después. Conviene que la tomen después, o al tiempo con, teoría de Galois (que en la carrera se ve en el curso Teoría de Cuerpos). Si está muy entusiasmado con la teoría de modelos, y no quiere esperar hasta el otro semestre, puede intentar tomarla en los Andes (con Xavier Caicedo) el próximo semestre - pero hable conmigo primero.

Clase extra mañana lunes

Mañana lunes a las 14:30 tendremos clase extra. Planeo hacer dos cosas:

1. Una brevísima introducción a ordinales infinitos, con algunos ejemplos. Vale la pena que lean dos cosas:
   
   
   
   • El capítulo 4 de Jech-Hrbacek,
   
   
   • La entrada en wikipedia sobre ordinales (no está nada mal escrita).
   
   
   
   


2. Terminar el tema de modelos no estándar de la aritmética.

página web

Finalmente empecé a actualizar mi página web. Aquí está la nueva versión.

hoy - para el viernes

Hoy básicamente vimos dos cosas: modelos no estándar de la aritmética y el criterio de Vaught. De modelos no estándar vimos

1. Existencia (en detalle, con compacidad)
2. Calculamos el tipo de orden de los modelos no estándar contables (que resulta siempre ser ω+(ω^*+ω)×η, donde ω^* es el tipo de orden de los enteros negativos y η el tipo de orden de los racionales).
3. Aún no hemos visto cómo puede haber más de un modelo no estándar (módulo isomorfismo).

Del criterio de Vaught, vimos un esquema de la demostración, y un primer corolario (la teoría T_odse (orden denso sin extremos) es completa). Más adelante, veremos otras aplicaciones, algunas muy sorprendentes.

de categoricidad

Una teoría Γ es categórica si tiene exactamente un modelo módulo isomorfismo. Por los teoremas vistos la semana pasada, realmente casi no hay teorías categóricas: apenas una teoría Γ tiene UN modelo infinito, tiene modelos infinitos de cardinales arbitrarios. De modo que esa definición solo funciona en teorías de modelos finitos (revise - ¡debe poder explicar! - que la teoría de un modelo finito siempre es categórica).

De modo que suavizamos la definición - dado un cardinal infinito κ una teoría Γ es κ-categórica si tiene exactamente un modelo de cardinalidad κ módulo isomorfismo.

Preguntas:

1. La teoría de un conjunto infinito es κ-categórica en todo cardinal infinito κ. Explique por qué.
   
2. La teoría de grupos NO es categórica en ningún cardinal infinito. De nuevo explique por qué.
3. La teoría de orden lineal denso sin extremos es ω-categórica. Use la idea de Cantor del "vaivén". Pueden presentar esto en clase para bonus el miércoles.
   

Veremos que las teorías sin modelos finitos que son κ-categóricas para algún cardinal infinito κ son completas. Este es el "criterio de Vaught".

Reposición de clase

Recuerde que el 22 de enero (lunes), a las 2:30 pm, tendremos reposición de clase.

Hoy les dejé varias preguntas, variantes de la demostración hecha en tablero del modelo elementalmente equivalente a (Z,P), pero con dos elementos "a distancia infinita" el uno del otro.

Las preguntas eran (en orden aproximado)

1. Demuestre que en el lenguaje L= < > (llamado usualmente el lenguaje de la "igualdad pura", no hay sentencia σ_fin que capture el ser finito.
   
2. Demuestre que en el lenguaje L= < R > , con R símbolo de relación binario, no existe ninguna sentencia σ_bo que capture el ser buen orden.
   
3. Encuentre un modelo elementalmente equivalente a (N,+,.,0,1) pero con elementos "infinitos".
   
4. Encuentre un modelo elementalmente equivalente a (R,+,., < ,0,1) pero con elementos "infinitesimales".
   

En todos los casos anteriores, un uso de compacidad es la clave. Iniciaremos la clase del miércoles próximo con la presentación de uno o dos de esos problemas... o con quiz. Prepárese.

También veremos tema nuevo en axiomatizabilidad. Y problemas de la siguiente tanda.

de vuelta al blog

Para mañana (viernes 12): hay sesión de problemas (quiz correspondiente a parte de su 20% de participación en clase)... me interesan todos los problemas asignados de la sección 2.5 (páginas 145 y 146) y todos los que puedan hacer de la sección 2.6 (pp. 162 a 164).

En particular, el ejercicio 5 de la p. 146 me interesa: es ver que el teorema de los cuatro colores finito implica la versión infinita (usando compacidad). El 6 también quiero que lo presenten mañana en tablero. Dos de los problemas 7, 8 y 9 también. En todos hay que usar el teorema de compacidad adecuadamente.

Hasta ahora, en clase solo iniciamos un uso del teorema de compacidad: para demostrar Löwenheim-Skolem ascendente, recuerde que agregamos κ constantes nuevas al lenguaje (así, L' = L ∪ {c_i : i < κ })

T' = T ∪ {c_i ≠ c_j : i < j < κ }

T' es finitamente consistente (¿por qué? tome un subconjunto finito de T', y use que T tiene modelos infinitos - escriba con cuidado las interpretaciones), luego por compacidad es consistente. Pero si (M,c_i^M)_{i < κ}
es modelo de T', entonces, las interpretaciones de las c_i (para i < κ) deben ser todas distintas... luego M|L es un modelo de T de cardinalidad por lo menos κ.

Por otro lado, ya teníamos una versión (débil) de Löwenheim-Skolem descendente: todo modelo de una teoría T en lenguaje contable, con modelos infinitos, debe tener un modelo contable: ¡el modelo de Henkin que construimos en clase resulta contable!

En algunos casos, ustedes mismos descubrieron esto: por ejemplo, si la teoría T es

Th(R,+, . ,0,1),

al armar el modelo de Henkin para T obtienen un modelo contable, y no los reales. Este modelo contable resulta (isomorfo a) los algebraicos reales.

el viernes

Hola a todos.

El viernes es la próxima clase (regreso a Bogotá el miércoles por la noche). Discutiremos algunos aspectos relacionados con completitud, compacidad, y modelos no estándar de la aritmética. Como siempre, debe estar preparado para la clase.

Después del interludio con el libro de Judah y Goldstern, regresamos a nuestro libro-texto usual.

Andrés

No hay clase el miércoles 3 de noviembre

Este miércoles no hay clase. Esta se reanudará el próximo viernes 5 de noviembre.

Viernes 29 de octubre

Un breve esquema de la prueba del teorema de completitud
es el siguiente:

Primero, dada Γ una teoría consistente, se demuestra la existencia
de un conjunto de símbolos de constante {c_i | i<ω}
que no están en L(Γ) y de una teoría Γ_H⊃Γ
en ese lenguaje extendido, que es de Henkin.

Luego, se completa dicha teoría (es decir, se toma Γ_H⊂Γ^*
en el mismo lenguaje extendido, que es completa)

Definiendo la relación τ∼σ ssi Γ^* deduce
que τ=σ (donde τ y σ son L(Γ^*)-términos),
se toma la L(Γ^*)-estructura A cuyo universo es (L(Γ^*)-términos)/∼,
la interpretación de cada símbolo de constante c es [c], donde
siendo F símbolo de función de aridad n se toma F^A([τ₁],...,[τ_n])=[F(τ₁,...,τ_n)]
y para cada símbolo de relación R de aridad m se define R^A([τ₁],...,[τ_m])
ssi Γ^*deduce R(τ₁,...,τ_m)
(hay que verificar que están bien definidos!!!)

La clave está en ver que A es un modelo de Γ^* (y por tanto
de Γ, luego la restricción de A al lenguaje L(Γ) es un modelo
de Γ).

Adicionalmente vimos una prueba del teorema de compacidad:
Γ es consistente ssi cada subconjunto de Γ es consistente. Aquí
se usa fuertemente el hecho de que una deducción es una sucesión
finita de fórmulas. Combinando este hecho con el teorema
de completitud tenemos lo siguiente: Γ es tiene un modelo
ssi cada subconjunto de Γ tiene un modelo.

Este hecho es uno de los teoremas mas útiles que se tiene en lógica
matemática. Una sencilla aplicación del teorema de compacidad es
la prueba de la existencia de modelos no estandar de la aritmética. La
idea es añadir al lenguaje de la aritmética un nuevo símbolo
de constante c y aplicar el teorema de compacidad (versión semántica)
a la teoría Th(ℕ)∪{sⁿ0<c | n<ω}.