viernes 22 de octubre

Este viernes 29 de octubre los espero "temprano" (ojalá estemos
comenzando tipo 9:15 a.m.)

OBSERVACIÓN: NO es cierto que son equivalentes el hecho de que una fórmula φ implica lógicamente a ψ al hecho de que φ implica tautológicamente ψ. El mismo ejemplo de su compañero sirve de contraejemplo, puesto que de ∀z∀w Pzw se deduce Pyx y por el teorema de la validez se tiene que ∀z∀w Pzw implica lógicamente Pyx; pero vistas como fórmulas primas ∀z∀w Pzw y Pyx son diferentes por lo que no son tautológicamente equivalentes.

El viernes se trabajaron algunos de los ejercicios de las páginas 130-131 del libro de Enderton (en esto empleamos la mayor parte de la clase dado que comenzó un poco tarde!!!), y aunque no se alcanzó a hacer un esquema completo de la prueba del teorema de completitud, vimos una prueba de la dirección trivial (si Γ tiene un modelo entonces es consistente) y alzanzamos a definir la noción de teoría de Henkin. Una teoría es de Henkin ssi dada cualquier fórmula φ, existe un símbolo de constante c en el mismo lenguaje de la teoría donde dicha teoría es capaz de deducir ∃xφ→φ(x/c) (intuitivamente, la teoría es capaz de "codificar" la existencia de testigos, en el mismo lenguaje, de todas las fórmulas existenciales).

Al tomar una teoría Γ consistente, la idea es extenderla a una teoría consistente Γ_H que sea de Henkin en un lenguaje enriquecido con nuevos símbolos de constante (como se menciona en el blog en una entrada anterior) que van a ser los testigos mencionados anteriormente.

wiki

La red ofrece recursos que pueden ser interesantes (y sobre todo, volverse interesantes con la participación de la gente). Uno de estos es (por si no lo conoce) el proyecto wikipedia. Se trata de una enciclopedia armada por todos los usuarios que sientan que pueden escribir sobre algo. Además, cualquier usuario puede corregir lo que hayan puesto como definición los usuarios anteriores. Y mejor aún, si uno pone una definición, puede dejar "enlaces abiertos" para que alguien llene definiciones que uno cree que hacen falta.

Pero lo mejor es que mire y juzgue por su cuenta.

Mire por ejemplo la entrada de lógica aquí.
Observe que está en los siguientes idiomas:
Afrikaans, Български, Català, Česky, Dansk, Deutsch, Eesti, Español, Esperanto, Français, 한국어, Bahasa Indonesia, Italiano, Latina, Latviešu, Magyar, Bahasa Melayu, Nederlands, 日本語, Polski, Português, Simple English, Slovenčina, Bahasa Sunda, Suomi, Svenska, Türkçe, 中文(简体)

¡pero que las entradas son distintas en todos los idiomas!

Observe la entrada de Lógica Matemática y note que aunque tiene cosas interesantes, está bastante incompleta.

Usted mismo podría en principio empezar a completar cosas. Pero obviamente hay que hacerlo con responsabilidad.

otro post de hoy: completitud

Aunque no alcanzamos a entrar realmente en materia, sí enunciamos Completitud hoy, en sus dos versiones estándar:

Γ deduce φ ssi todo modelo de Γ es modelo de φ.

Γ es consistente ssi Γ tiene algún modelo.

Este, junto con Compacidad en Cálculo de Predicados, es el teorema central de este curso.

Para el miércoles, usted debe mostrar por qué son equivalentes los dos enuciados anteriores.

Aún no he dejado en fotocopiadora el trozo del libro de Goldstern y Judah, en el cual leeremos la demostración. Lo dejaré el martes.

"Leeremos" quiere decir que ustedes expondrán en tablero trozos de la demostración.

La prueba que seguimos es la de Henkin, de los años 50. Henkin arma un modelo para Γ consistente

1. Enriqueciendo el lenguaje, de manera tal que las fórmulas existenciales que son teoremas de Γ tienen todas un término cerrado que las satisface (un "testigo").
2. Armando el modelo con los términos cerrados... o más exactamente con las clases de equivalencia dada por τ ~ σ ssi Γ deduce τ=σ.
   

hoy: extraer cuantificadores, esp. existencial, ...

Hoy empezamos la parte más "dura" de todo el sistema deductivo en Cálculo de Predicados:

1. Extracción de cuantificadores
2. Especificación del existencial
3. Agregar constantes

Las extracciones de cuantificadores que vimos

(α → ∀ x β) equiv ∀ x (α → β)
(∃ x β → α) equiv ∀ x (β → α)

(¡siempre y cuando x no ocurra libre en α!) son muy útiles a la hora de buscar la forma normal prenexa de una fórmula. Hay varias otras - mire los ejercicios 15, 16 y 17 de la página 131. Vale la pena que arme una ficha con algunas de estas extracciones, pues las va a necesitar. ¡También debe saber demostrarlas!

La especificación del existencial que demostramos hoy es muy usada en matemática al hacer demostraciones. Nos tomó tiempo demostrarla con cuidado, con el teorema previo y el lema, pero creo que valía la pena hacer al menos ese trozo con mucho detalle. Usted debe poder reconstruir pasos de la demostración de hoy.

Por último, aunque no lo vamos a discutir con mucho detalle, usted debe poder hacer los cambios de variable cuando sean necesarios (ver página 126, y ejercicio 11 en página 130).

del parcial

Puede bajar las respuestas del parcial haciendo clic aquí. El viernes seguimos con el capítulo de deducciones, y dejaré la lectura de Goldstern-Judah para la demostración del Teorema de Completitud (el enunciado está en la parte de abajo abajo en este blog).

horas de atención para el parcial

Para el parcial del miércoles 13, las horas de atención serán el lunes 11, de 16 a 18. Ojo: el martes tengo clase y reuniones, y no podré atenderlos - si tiene preguntas de horas de atención, debe usar el horario de este lunes.

divertimento

Dado que tienen bastante tiempo extra con este cierre, pueden hacer lo siguiente (lo pueden ver como un simple divertimento, o como práctica para el parcial).

A. Decida si cada una de las siguientes sentencias es un teorema lógico o no. Si sí lo es, escriba una deducción (puede usar, naturalmente, los metateoremas). Si no lo es, encuentre un modelo en el cual falle.

1. ∀x ∀y P(x,y) → ∀z P(z,z)
2. ∀x P(fx,x) → ∃y ∀x P(y,x)
3. ∀x ∀y (P(x,y) → ∃z (P(x,z) ∧ P(z,y))) → ∃x ∃y (x≠y)

B. Recuerde que una teoría Γ (es decir, un conjunto de sentencias) es "completa" si es consistente y dada cualquier sentencia φ, se tiene que o bien φ es un Γ-teorema o bien ¬φ es un Γ-teorema.

1. (vuelta a la Universidad Nacional) Demuestre que dado un modelo A, Th(A) := {φ | φ vale en A} (la "teoría de A") es una teoría completa.
2. (subida a Patios) Demuestre que la teoría de grupos, la teoría de anillos, la teoría de campos no son completas.
3. (etapa Bogotá-Tunja) Muestre por qué la teoría cuyos modelos son los conjuntos infinitos, en el lenguaje de la pura igualdad, sí es completa.
4. (etapa Bogotá-Calarcá) Intente explicar por qué la teoría de órdenes lineales densos sin extremos es completa.

C. Algo de definibles y automorfismos:

1. Demuestre que R (los reales) no es definible (sin parámetros) en (C,+, . , 0,1).
2. ¿Cuáles automorfismos tiene la estructura (N,+, . , < , 0,1)?
3. (otro premio de montaña) Recuerde el grafo aleatorio contable visto en clase. ¿Cuáles son sus automorfismos? Si uno define el grafo aleatorio sobre los naturales, es definible ahí el conjunto de los pares?
   

parcial aplazado

Por el desalojo, naturalmente nos toca aplazar el parcial para el próximo miércoles (13 de octubre). Esté alerta a este blog, pues iré poniendo información y preguntas de aquí a esa fecha. Puede hacer preguntas vía el blog, o escribiendo directamente a mi correo electrónico. Recuerde que toda comunicación debe ir con su nombre.

parcial del miércoles

Los temas:

1. Compacidad del Cálculo Proposicional
2. Completitud del Cálculo Proposicional
3. Conjuntos efectivamente enumerables, decidibles, recursivos, recursivamente enumerables.
4. Modelos y teorías
5. Teorías importantes vistas en clase
   
6. La conexión entre definibles y automorfismos
7. Sintaxis del Cálculo de Predicados, hasta los seis metateoremas vistos hoy en clase (debe conocerlos, al fin y al cabo no son tantos todavía :).
8. Inconsistencia y las consecuencias de esta - Teorías completas
   

Esa es la lista (por cierto, bastante extensa) de temas. El nivel requerido para que le pueda ir bien en el examen corresponde a ser capaz de resolver todos los problemas asignados.

El examen será de una hora de duración.

El martes por la tarde (de 2 a 4) estaré en mi oficina - puede usar ese tiempo para dudas o preguntas del parcial.