Este número especial contiene artículos que representan tres direcciones: teoría descriptiva de conjuntos (DTM), algoritmos de complejidad polinomial exacta (EPA) y aplicaciones de lógica matemática y teoría de algoritmos (Appl). Diremos unas palabras sobre cada una de las direcciones.

De acuerdo con la descripción clásica de Nicolas Luzin, DTM considera propiedades simples de conjuntos simples de números reales R. Los conjuntos “simples” son conjuntos de Borel (la familia más pequeña que contiene conjuntos abiertos y cerrados en Rn y cerrados con respecto a las operaciones de unión contable e intersección contable) y conjuntos proyectivos (la familia más pequeña que contiene conjuntos de Borel y cerrados con respecto a las operaciones de proyección de Rn a Rm, m <n, y el complemento a todo el espacio).

La cuestión de qué es una propiedad «simple» es más complicada, pero no es importante, ya que de hecho estudiamos una pequeña lista de propiedades individuales, incluida la mensurabilidad de Lebesgue, la propiedad de Baire y la definibilidad individual de un conjunto, función, o real.

También te interesará La Matemática del Futuro

Lo último significa que hay una fórmula que se aplica a un número real dado y no a otros. Esto depende de la clase de fórmulas permitidas. Esta clase natural consta de fórmulas de la forma ∀x1 ∃y1 ∀x2 ∃y2. . . ∀xn ∃yn ψ (x1, y1,…, Xn, yn, x), donde las variables x1, y1,. . . , xn, yn, x ejecutar a través de todo R, y la parte elemental ψ (x1, y1,…, xn, yn, x) es cualquier fórmula aritmética (que contiene cualquier cuantificador sobre los números naturales, así como las igualdades y desigualdades que conectan las superposiciones de operaciones a partir del semiring de números naturales).

Hasta la fecha, el desarrollo de DTM lleva a una conclusión cultural general no trivial: cada número real es definible (usando ordinales contables) o aleatorio; en el último caso, no posee propiedades no triviales. Esto implica que existen enunciados absolutamente indecidibles; así como sorprendentes conexiones entre aparentemente muy diferentes absolutamente indecidibles.

Por ejemplo, la mensurabilidad implica la propiedad de Baire para una amplia clase de conjuntos. Los tres primeros artículos pertenecen a esta dirección. En particular, resuelven el conocido problema (1948) de A. Tarski sobre la definibilidad de la noción de definibilidad en sí, y prueban la afirmación (1975) de H. Friedman.

Obtener libro
Descargar/Download PDF