finalmente, la sintaxis

Ayer empezamos en serio la sintaxis, con dos construcciones, discusión de los seis axiomas (o mejor, los seis esquemas axiomáticos) lógicos, que el libro llama Λ.

Alcanzamos a usar (levemente) los dos primeros metateoremas: el Teorema de la Deducción (TD) y el de la Generalización Universal (G∀).

Para mañana, recuerde que debe traer la demostración de estos dos metateoremas. ¡Puede haber quiz o preguntas!

Para pensar: demuestre que ∃x(x=x) es un teorema lógico. Puede usar todos los metateoremas que aún no hemos visto. ¿Qué implica esto? Habrá bonus para quien explique bien esto mañana.

El miércoles es nuestro segundo parcial. Cubre hasta todo lo que alcancemos a ver mañana. Lleve preguntas.

el miércoles

El miércoles por la mañana terminaremos el tema de automorfismos. Hay acumulación de problemas; el miércoles preguntaré, pero recuerde que los que no alcancen a ser discutidos aún los debe resolver (o sea que es mejor preguntar el miércoles). Por otro lado, alguno de ustedes deberá demostrar que si D es definible sobre X en una L-estructura A, entonces todo automorfismo f de A que deje fijo puntualmente a X (es decir, f|X = id_X) debe dejar fijo a D como conjunto.

Por otro lado, también deben traer resueltos los problemas 18, 19 y 20 de la página 102.

Finalmente, empezaremos la sección 2.5 (deducción en cálculo de predicados). Prepare la definición de Γ-deducción en Cálculo de Predicados (p. 111) al igual que los axiomas lógicos (p. 112).

clase más tarde

Mañana viernes la clase empezará hacia las 10 am - resulta que soy asesor del jurado de un examen por videoconferencia a un candidato a ser profesor. Ese examen fue cuadrado a las 9 am de mañana - dado que es un asunto en el que está involucrado un lugar internacional, y que el área de ese profesor es cercana a la mía, debo estar ahí. Pero puedo llegar más tarde, hacia las 10 de la mañana. Haré clase a esa hora.

Andrés.

definibles - pp.99--104

La tanda de ejercicios de páginas 99 a 104 es realmente importante. No sé cuántos alcancemos a resolver en clase (eso depende de ustedes) pero usted ciertamente debe intentar hacer el máximo posible. También debe leer (para el miércoles) las definiciones faltantes, de homomofismo entre modelos, al igual que iso- y auto- morfismos.

1. Son definibles los pares en (N,+,⋅,0,1)?
2. Son definibles los pares en (N,+,0,1)?
3. Son definibles los pares en (N,0,1)?
4. ¿Cuáles subconjuntos de A son definibles con parámetros en la estructura A = (A) del lenguaje sin símbolos de relación ni de función ni de constante? Esta es una pregunta bonus. El primero que la resuelva bien en tablero el miércoles tiene un bonus en nota de participación en clase.
   

Un subconjunto D⊂A es definible con parámetros en A si existe una fórmula φ(x,y₁,y₂,...,y_m) y existen elementos a₁, a₂,... ,a_m ∈ A tales que

b ∈ D si y solo si A satisface φ[b,a₁,a₂,...,a_m].

sobre The Music of the Primes

Vuelvo a recomendar el libro de Du Sautoy. Además, quiero que lean el artículo de aperitivo que escribe el mismo Du Sautoy sobre su libro. Vale la pena.

Una imagen tomada de ese mismo lugar, con los armónicos de Riemann:

Maths holy grail could bring disaster for internet

En este artículo del Guardian (Maths holy grail could bring disaster for internet) entrevistan a Du Sautoy sobre las dos supuestas soluciones a dos de los siete problemas del millón de dólares (Conjetura de Poincaré e Hipótesis de Riemann).

Aparentemente, la solución a la hipótesis de Riemann no es muy clara. Ya veremos.

Aunque el artículo es de periódico de circulación general, vale la pena leerlo, pues los del Guardian son cuidadosos, y escogieron a Du Sautoy (el autor de The Music of the Primes, investigador en teoría de números y profesor en Oxford) para algunas de las opiniones.

y no olvide...

el problema 7 de la tanda discutida ayer viernes ... el miércoles debe traerlo resuelto

algunos libros

Esta semana tocamos un poco el tema de enumerabilidad efectiva y decidibilidad, con sus variantes "A es recursivo" y "A es semidecidible".

Si el tema le llama la atención, puede consultar (ya por fuera del contexto de este curso) los libros siguientes:

1. Hopcroft & Ullman es un clásico con varias ediciones. La biblioteca tiene alguna edición en español. La edición más reciente tiene como co-autor a Motwani también.
2. Lewis & Papadimitriou es otro texto de pregrado importante.
3. Algunas de las explicaciones que da Poizat en su extraño Les Petits Cailloux (e.g. las pequeñas piedras, es decir los calculi de los romanos) son bien interesantes. Sin embargo, en ese libro, Poizat mezcla muchos niveles distintos (aparece trabajo completamente novedoso, y también aparece presentación básica).
4. A nivel local, vale la pena leer un libro del profesor Rodrigo De Castro, llamado Teoría de la Computación - Lenguajes, Autómatas, Gramáticas. Publicado por la Facultad de Ciencias (no le encontré enlace, pero debería estar en esta lista).

Aunque distinto, hay un proyecto aparentemente aún no terminado, de Christos Papadimitriou y Apostolos Doxiadis, llamado LogiComix. Se trata de una historia de la lógica matemática en formato de comics, escrita por un profesor de Berkeley (Papadimitriou, muy famoso en Teoría de la Computación), y Doxiadis, conocido por su novela El Tío Petros y la Conjetura de Goldbach (que puede conseguir en cualquier librería). Sin embargo, aún no está listo LogiComix. Aquí hay una descripción del proyecto.