-----------------------------------------PER LINDSTRÖM (1936-2009)------------------
---------------------DAVID HILBERT (1862-1943), ALFRED TARSKI (1901-1983)-----------
Un clásico e interesante resultado sobre la Lógica de Primer Orden es el PRIMER TEOREMA DE LINDSTRÖM (1969): "No existe una lógica con mayor capacidad expresiva que la Lógica de Primer Orden que satisfaga simultáneamente Compacidad y Löwenheim-Skolem". Este teorema proporciona una caracterización de la Lógica de primer orden en el contexto de la Lógica Abstracta. Una demostración del mismo puede encontrarse en el texto MATHEMATICAL LOGIC de los autores Ebbbinghaus, Flum y Thomas. Springer-Verlag. 1984. Existe una versión digital de dicho texto en la biblioteca digital de este blog (y se puede bajar). VER, POR FAVOR, DICHA DEMOSTRACIÓN EN TAL TEXTO, así se hará mucho más digerible lo que a continuación se comenta (muy resumidamente) en esta entrada.
Otra demostración puede encontrarse en el texto MODEL THEORY de Chang y Keisler,North-Holland, 1992. Existe también una versión digital de tal libro en la biblioteca digital de este blog (y se puede bajar). Y otra demostración puede encontrarse en el artículo de Xavier Caicedo titulado "CUANTIFICADORES GENERALIZADOS Y EL TEOREMA DE LINDSTRÖM", Acta Científica Venezolana 37: 243-250, 1986. (También en la tesis de licenciatura-en el área de Lógica Matemática- de Franklin Galindo (1997-UCV), titulada "Una Demostración del Teorema de Lindström", puede encontrarse una demostración detallada de dicho teorema realizada usando ideas de las referencias que se han colocado anteriormente de Ebbbinghaus, Flum, Thomas y Caicedo. El tutor de dicha tesis de licenciatura fue el Prof. Dr. Carlos Di Prisco.).
Vale la pena resaltar que tales demostraciones utilizan varias técnicas hermosas y sofisticadas de la Teoría de Modelos (Álgebra universal + Lógica = Teoría de Modelos), por ejemplo el Teorema de Fraissé el cual proporciona una caracterización de la relación de equivalencia elemental entre estructuras en términos de isomorfismos parciales (con la propiedad de "back-and-forth") entre estructuras, y también el concepto de "Lógica abstracta".
Considerando las referencias anteriores, una prueba del Teorema de Lindström se puede realizar, a grandes rasgos, en tres partes ((1), (2) y (3)):
(1) Se demuestra el Teorema de Lindström en una primera versión, caso "compacidad numerable" (compacidad restringida a conjuntos numerables de sentencias) sin "eliminación" (una lógica tiene la propiedad de "eliminación" si se pueden eliminar símbolos funcionales y constantes), es decir, en esta parte, se demuestra que, PARA EL CASO DE LENGUAJES RELACIONALES FINITOS: NO EXISTE UNA EXTENSIÓN DE LA LÓGICA DE PRIMER ORDEN, CON MAYOR PODER EXPRESIVO, QUE SATISFAGA SIMULTÁNEAMENTE TEOREMAS ANÁLOGOS A LOS DE COMPACIDAD NUMERABLE Y LÖWENHEIM-SKOLEM. En esta demostración las extensiones consideradas tienen dos propiedades que satisface la lógica de primer orden: (a) Son cerradas bajo conjunciones y negaciones y (b) satisfacen "relativización". Es importante resaltar que esta primera demostración (de esta primera versión del Teorema de Lindström) se hace por reducción al absurdo y que para formularlo y encontrar la contradicción se usan a su vez TRES IDEAS que utilizan técnicas sofisticadas de la teoría de modelos como por ejemplo las dos anteriormente mencionadas ("Teorema de Fraissé" y "la noción de Lógica abstracta"). La parte más medular de la demostración del Teorema de Lindström es esta parte (1).
(2) Se extiende (1) demostrándose que para lenguajes relacionales cualesquiera no existe una extensión de la lógica de primer orden, con mayor poder expresivo, que satisfaga simultáneamente teoremas análogos a los de compacidad y Löwenheim-Skolem. Es decir, se demuestra una versión más cercana del Teorema de Lindström que la versión (1). Esta demostración se hace considerando algunos resultados probados por los autores Flum, Thomas y Ebbinghaus en la demostración que los mismos realizan del Teorema de Lindström (en el libro citado anteriormente que se llama "Mathematical Logic").
(3) Se extiende (2) demostrándose que para lenguajes cualesquiera no existe una extensión de la lógica de primer orden, con mayor poder expresivo, que satisfaga simultáneamente teoremas análogos a los de compacidad y Löwenheim-Skolem, es decir, en esta parte (3) se demuestra la versión final del Teorema de Lindström. Esta prueba se realiza adicionándole a las extensiones consideradas en (2) la propiedad de "eliminación", una propiedad mencionada anteriormente en la parte (1).
Ahora bien, como es conocido, ejemplos de lógicas más expresivas que la de primer orden son las de omega-orden (segundo orden,etc), pero las más relevantes para el Primer Teorema de Lindström son las lógicas intermedias entre primer y segundo orden con fórmulas de longitud infinita (de cualquier cardinalidad alef_alfa) o con cuantificadores generalizados (de cualquier cardinalidad alef_alfa) las cuales se propusieron hacia los años 50 del siglo pasado (aproximadamente 1950-60 por Mostowski, Karp, etc). Creo que es posible conectar de varias maneras el Primer Teorema de Lindström con el poderoso Método Metamatemático de David Hilbert-Alfred Tarski (entre otros). (1) Una de las maneras de conectarlo, tal vez la más inmediata, es que tal teorema es un resultado metamatemático pues cada una de las teorías lógicas que se considera en el mismo se define como una teoría matemática como es usual hacerlo en la Lógica Matemática, no es casual que tal teorema se encuentre (también) formulado y demostrado en el libro "Model theory" de Chang y Keisler. (2) Otra manera de conectarlo, también inmediata, es que dichas lógicas (las más expresivas) NO SON AXIOMATIZABLES, es decir, ellas son incompletas ya que Compacidad y Löwenheim-Skolem son un corolario de Completitud, entonces al no satisfacer Compacidad o Löwenheim-Skolem no satisfacen completitud (Nota: Dichas lógicas sí satisfacen la propiedad de Corrección). ¿Y cuántas lógicas más expresivas-del tipo descrito-existen? Infinitas, al menos dos por cada cardinal alef_alfa (una con fórmulas de longitud infinita y otra con cuantificadores generalizados), es decir la colección de todas esas lógicas es una clase propia que no puede ser un conjunto. (3) Creo que otra posible relación del Primer Teorema de Lindström con el Método Metamatemático de Hilbert-Tarski (entre otros) surge de la respuesta a la pregunta: ¿ Cómo se ha consolidado (en la comunidad de los lógicos matemáticos del mundo contemporáneo) la lógica de primer orden como la lógica base para las matemáticas, a pesar de sus limitaciones expresivas las cuales son consecuencia de sus importantes propiedades de Compacidad y Löwenheim-Skolem?. Dicha pregunta se puede intentar responder en buena medida con el artículo del Profesor Gregory Moore: " UN HOGAR DIVIDIDO DENTRO DE SI MISMO: EL SURGIMIENTO DE LA LÓGICA DE PRIMER ORDEN COMO LA LÓGICA BASE PARA LAS MATEMÁTICAS". Dicho artículo, en su versión titulada "THE EMERGENCE OF FIRST-ORDER LOGIC", está en el texto HISTORY AND PHILOSOPHY OF MODERN MATHEMATICS de Aspray y Kitcher. Este texto se puede encontrar en el buscador de mano derecha (de este blog) y en la biblioteca digital (de este blog, y se puede bajar). En mi opinión la respuesta del Profesor Gregory Moore a dicha pregunta considera cinco hechos fundamentales (entre otros): (a) El Teorema de completitud de Gödel de la lógica de Primer Orden (1930), (b) Los Teoremas de Compacidad y Löwenheim-Skolem de la Lógica de Primer Orden, (c) Los Teoremas de incompletitud de Gödel de 1931 ("La Matemática no es axiomatizable"), (d) La simplicidad de la Lógica de primer orden, (e) Que la Teoría de conjuntos se puede desarrollar en primer orden (axiomatizar y demostrar sus teoremas conocidos), y que además todo teorema matemático conocido (de cualquier área de la matemática) se puede re-expresar y demostrar en tal teoría de conjuntos. Sin embargo, cuando uno quiere entender los detalles argumentativos de tal respuesta surgen algunas preguntas relacionadas con hechos probados de la lógica matemática después de 1940 (el profesor Gregory Moore afirma que la lógica de primer orden se consolidó como la lógica base de la matemática en la década 1930-1940, y uno quiere saber por qué continúa consololidada en la actualidad, como de hecho lo está). [por ejemplo el surgimiento de nuevos sistemas lógicos "omega-completos", como la lógica con cuantificadores generalizados "L_Q", y el surgimiento de nuevas técnicas de construcción de modelos en primer orden, después de 1940, e intentando responder alguna de dichas preguntas me ha surgido a mí la necesidad de recurrir al Primer Teorema de Lindström y a la Teoría de modelos en primer orden (dentro y fuera de la Teoría de conjuntos axiomatizada) para justificar completamente la respuesta del Profesor Moore en la actualidad (2019). Por ejemplo, una pregunta es la siguiente: Dada una determinada axiomatización de la Teoría de conjuntos con una lógica L ¿qué tipo de problemas abiertos pueden aparecer en dicha teoría de conjuntos axiomatizada: (i) Solamente problemas matemáticos, o, (ii) problemas lógicos (si la lógica usada es incompleta) y problemas matemáticos? al respecto de (i) y (ii): ¿qué tipo de problemas desea encontrar e intentar resolver un matemático estándar (es decir, un matemático no interesado en problemas de fundamentos) ?. Y una segunda pregunta es la siguiente: ¿Cuál es el papel de la Lógica de primer orden en la matemática contemporánea y en metamatemática contemporánea?, por ejemplo en la construcción de modelos en la teoría de conjuntos y en la teoría de modelos: técnicas de construcción de modelos como compacidad y Löwenhein-Skolem- Tarski hacia abajo y hacia arriba [modelos no estándar, es decir, modelos que son al mismo tiempo "no isomorfos" y "elementalmente equivalentes" al modelo estándar, y donde se podría aplicar el "Principio de Transferencia" como método para conocer nuevas verdades en el modelo estándar], los constructibles de Gödel L (1940), Constructibilidad relativizada L(A), Forcing (1963), Forcing iterado, Modelos HOD(A), Modelos H(k), Modelos simétricos, Ultraproductos (1950), Modelos Fraenkel-Mostowski, etc. Es conocido que dichos modelos permiten probar teoremas metamatemáticos y también teoremas matemáticos. ES CONOCIDO QUE DICHO PAPEL (EL DE LA LÓGICA DE PRIMER ORDEN EN LA MATEMÁTICA CONTEMPORÁNEA Y EN LA METAMATEMÁTICA CONTEMPORÁNEA) ES MUY FRUCTÍFERO. ES DECIR, LA LÓGICA DE PRIMER ORDEN HA DEMOSTRADO SER ("EN EL QUEHACER MATEMÁTICO COTIDIANO") UN INSTRUMENTO (UN MÉTODO) DE INVESTIGACIÓN MATEMÁTICA EXTRAORDINARIAMENTE FRUCTÍFERO (MUY RICO EN NUEVOS RESULTADOS MATEMÁTICOS PRESENTES Y FUTUROS ("INAGOTABLE")). Es importante destacar acá que la matemática y la metamatemática contemporánea también usa otras lógicas distintas a la lógica de primer orden o fragmentos de otras lógicas para sus investigaciones (por ejemplo en la investigación de grandes cardinales), pero (hasta ahora) no en la misma proporción (o privilegio) que usa a la lógica de primer orden.] El Profesor Gregory Moore no menciona al Primer Teorema de Lindström en su artículo, lo que hace pensar que tal vez para su respuesta en el artículo no sea necesario dicho teorema, yo comparto su punto de vista (por varias razones) pero creo que como analizo otras posibilidades (preguntas, el momento actual, la matemática actual, la metamátematica actual, etc) me surge a mí la necesidad de recurrir a dicho teorema y a la teoría de modelos en primer orden (la cual ha demostrado ser muy fructífica). El lector del artículo del Profesor Moore y de este pequeño comentario se creará su propia opinión al respecto.
Otra demostración puede encontrarse en el texto MODEL THEORY de Chang y Keisler,North-Holland, 1992. Existe también una versión digital de tal libro en la biblioteca digital de este blog (y se puede bajar). Y otra demostración puede encontrarse en el artículo de Xavier Caicedo titulado "CUANTIFICADORES GENERALIZADOS Y EL TEOREMA DE LINDSTRÖM", Acta Científica Venezolana 37: 243-250, 1986. (También en la tesis de licenciatura-en el área de Lógica Matemática- de Franklin Galindo (1997-UCV), titulada "Una Demostración del Teorema de Lindström", puede encontrarse una demostración detallada de dicho teorema realizada usando ideas de las referencias que se han colocado anteriormente de Ebbbinghaus, Flum, Thomas y Caicedo. El tutor de dicha tesis de licenciatura fue el Prof. Dr. Carlos Di Prisco.).
Vale la pena resaltar que tales demostraciones utilizan varias técnicas hermosas y sofisticadas de la Teoría de Modelos (Álgebra universal + Lógica = Teoría de Modelos), por ejemplo el Teorema de Fraissé el cual proporciona una caracterización de la relación de equivalencia elemental entre estructuras en términos de isomorfismos parciales (con la propiedad de "back-and-forth") entre estructuras, y también el concepto de "Lógica abstracta".
(1) Se demuestra el Teorema de Lindström en una primera versión, caso "compacidad numerable" (compacidad restringida a conjuntos numerables de sentencias) sin "eliminación" (una lógica tiene la propiedad de "eliminación" si se pueden eliminar símbolos funcionales y constantes), es decir, en esta parte, se demuestra que, PARA EL CASO DE LENGUAJES RELACIONALES FINITOS: NO EXISTE UNA EXTENSIÓN DE LA LÓGICA DE PRIMER ORDEN, CON MAYOR PODER EXPRESIVO, QUE SATISFAGA SIMULTÁNEAMENTE TEOREMAS ANÁLOGOS A LOS DE COMPACIDAD NUMERABLE Y LÖWENHEIM-SKOLEM. En esta demostración las extensiones consideradas tienen dos propiedades que satisface la lógica de primer orden: (a) Son cerradas bajo conjunciones y negaciones y (b) satisfacen "relativización". Es importante resaltar que esta primera demostración (de esta primera versión del Teorema de Lindström) se hace por reducción al absurdo y que para formularlo y encontrar la contradicción se usan a su vez TRES IDEAS que utilizan técnicas sofisticadas de la teoría de modelos como por ejemplo las dos anteriormente mencionadas ("Teorema de Fraissé" y "la noción de Lógica abstracta"). La parte más medular de la demostración del Teorema de Lindström es esta parte (1).
(2) Se extiende (1) demostrándose que para lenguajes relacionales cualesquiera no existe una extensión de la lógica de primer orden, con mayor poder expresivo, que satisfaga simultáneamente teoremas análogos a los de compacidad y Löwenheim-Skolem. Es decir, se demuestra una versión más cercana del Teorema de Lindström que la versión (1). Esta demostración se hace considerando algunos resultados probados por los autores Flum, Thomas y Ebbinghaus en la demostración que los mismos realizan del Teorema de Lindström (en el libro citado anteriormente que se llama "Mathematical Logic").
(3) Se extiende (2) demostrándose que para lenguajes cualesquiera no existe una extensión de la lógica de primer orden, con mayor poder expresivo, que satisfaga simultáneamente teoremas análogos a los de compacidad y Löwenheim-Skolem, es decir, en esta parte (3) se demuestra la versión final del Teorema de Lindström. Esta prueba se realiza adicionándole a las extensiones consideradas en (2) la propiedad de "eliminación", una propiedad mencionada anteriormente en la parte (1).
Ahora bien, como es conocido, ejemplos de lógicas más expresivas que la de primer orden son las de omega-orden (segundo orden,etc), pero las más relevantes para el Primer Teorema de Lindström son las lógicas intermedias entre primer y segundo orden con fórmulas de longitud infinita (de cualquier cardinalidad alef_alfa) o con cuantificadores generalizados (de cualquier cardinalidad alef_alfa) las cuales se propusieron hacia los años 50 del siglo pasado (aproximadamente 1950-60 por Mostowski, Karp, etc). Creo que es posible conectar de varias maneras el Primer Teorema de Lindström con el poderoso Método Metamatemático de David Hilbert-Alfred Tarski (entre otros). (1) Una de las maneras de conectarlo, tal vez la más inmediata, es que tal teorema es un resultado metamatemático pues cada una de las teorías lógicas que se considera en el mismo se define como una teoría matemática como es usual hacerlo en la Lógica Matemática, no es casual que tal teorema se encuentre (también) formulado y demostrado en el libro "Model theory" de Chang y Keisler. (2) Otra manera de conectarlo, también inmediata, es que dichas lógicas (las más expresivas) NO SON AXIOMATIZABLES, es decir, ellas son incompletas ya que Compacidad y Löwenheim-Skolem son un corolario de Completitud, entonces al no satisfacer Compacidad o Löwenheim-Skolem no satisfacen completitud (Nota: Dichas lógicas sí satisfacen la propiedad de Corrección). ¿Y cuántas lógicas más expresivas-del tipo descrito-existen? Infinitas, al menos dos por cada cardinal alef_alfa (una con fórmulas de longitud infinita y otra con cuantificadores generalizados), es decir la colección de todas esas lógicas es una clase propia que no puede ser un conjunto. (3) Creo que otra posible relación del Primer Teorema de Lindström con el Método Metamatemático de Hilbert-Tarski (entre otros) surge de la respuesta a la pregunta: ¿ Cómo se ha consolidado (en la comunidad de los lógicos matemáticos del mundo contemporáneo) la lógica de primer orden como la lógica base para las matemáticas, a pesar de sus limitaciones expresivas las cuales son consecuencia de sus importantes propiedades de Compacidad y Löwenheim-Skolem?. Dicha pregunta se puede intentar responder en buena medida con el artículo del Profesor Gregory Moore: " UN HOGAR DIVIDIDO DENTRO DE SI MISMO: EL SURGIMIENTO DE LA LÓGICA DE PRIMER ORDEN COMO LA LÓGICA BASE PARA LAS MATEMÁTICAS". Dicho artículo, en su versión titulada "THE EMERGENCE OF FIRST-ORDER LOGIC", está en el texto HISTORY AND PHILOSOPHY OF MODERN MATHEMATICS de Aspray y Kitcher. Este texto se puede encontrar en el buscador de mano derecha (de este blog) y en la biblioteca digital (de este blog, y se puede bajar). En mi opinión la respuesta del Profesor Gregory Moore a dicha pregunta considera cinco hechos fundamentales (entre otros): (a) El Teorema de completitud de Gödel de la lógica de Primer Orden (1930), (b) Los Teoremas de Compacidad y Löwenheim-Skolem de la Lógica de Primer Orden, (c) Los Teoremas de incompletitud de Gödel de 1931 ("La Matemática no es axiomatizable"), (d) La simplicidad de la Lógica de primer orden, (e) Que la Teoría de conjuntos se puede desarrollar en primer orden (axiomatizar y demostrar sus teoremas conocidos), y que además todo teorema matemático conocido (de cualquier área de la matemática) se puede re-expresar y demostrar en tal teoría de conjuntos. Sin embargo, cuando uno quiere entender los detalles argumentativos de tal respuesta surgen algunas preguntas relacionadas con hechos probados de la lógica matemática después de 1940 (el profesor Gregory Moore afirma que la lógica de primer orden se consolidó como la lógica base de la matemática en la década 1930-1940, y uno quiere saber por qué continúa consololidada en la actualidad, como de hecho lo está). [por ejemplo el surgimiento de nuevos sistemas lógicos "omega-completos", como la lógica con cuantificadores generalizados "L_Q", y el surgimiento de nuevas técnicas de construcción de modelos en primer orden, después de 1940, e intentando responder alguna de dichas preguntas me ha surgido a mí la necesidad de recurrir al Primer Teorema de Lindström y a la Teoría de modelos en primer orden (dentro y fuera de la Teoría de conjuntos axiomatizada) para justificar completamente la respuesta del Profesor Moore en la actualidad (2019). Por ejemplo, una pregunta es la siguiente: Dada una determinada axiomatización de la Teoría de conjuntos con una lógica L ¿qué tipo de problemas abiertos pueden aparecer en dicha teoría de conjuntos axiomatizada: (i) Solamente problemas matemáticos, o, (ii) problemas lógicos (si la lógica usada es incompleta) y problemas matemáticos? al respecto de (i) y (ii): ¿qué tipo de problemas desea encontrar e intentar resolver un matemático estándar (es decir, un matemático no interesado en problemas de fundamentos) ?. Y una segunda pregunta es la siguiente: ¿Cuál es el papel de la Lógica de primer orden en la matemática contemporánea y en metamatemática contemporánea?, por ejemplo en la construcción de modelos en la teoría de conjuntos y en la teoría de modelos: técnicas de construcción de modelos como compacidad y Löwenhein-Skolem- Tarski hacia abajo y hacia arriba [modelos no estándar, es decir, modelos que son al mismo tiempo "no isomorfos" y "elementalmente equivalentes" al modelo estándar, y donde se podría aplicar el "Principio de Transferencia" como método para conocer nuevas verdades en el modelo estándar], los constructibles de Gödel L (1940), Constructibilidad relativizada L(A), Forcing (1963), Forcing iterado, Modelos HOD(A), Modelos H(k), Modelos simétricos, Ultraproductos (1950), Modelos Fraenkel-Mostowski, etc. Es conocido que dichos modelos permiten probar teoremas metamatemáticos y también teoremas matemáticos. ES CONOCIDO QUE DICHO PAPEL (EL DE LA LÓGICA DE PRIMER ORDEN EN LA MATEMÁTICA CONTEMPORÁNEA Y EN LA METAMATEMÁTICA CONTEMPORÁNEA) ES MUY FRUCTÍFERO. ES DECIR, LA LÓGICA DE PRIMER ORDEN HA DEMOSTRADO SER ("EN EL QUEHACER MATEMÁTICO COTIDIANO") UN INSTRUMENTO (UN MÉTODO) DE INVESTIGACIÓN MATEMÁTICA EXTRAORDINARIAMENTE FRUCTÍFERO (MUY RICO EN NUEVOS RESULTADOS MATEMÁTICOS PRESENTES Y FUTUROS ("INAGOTABLE")). Es importante destacar acá que la matemática y la metamatemática contemporánea también usa otras lógicas distintas a la lógica de primer orden o fragmentos de otras lógicas para sus investigaciones (por ejemplo en la investigación de grandes cardinales), pero (hasta ahora) no en la misma proporción (o privilegio) que usa a la lógica de primer orden.] El Profesor Gregory Moore no menciona al Primer Teorema de Lindström en su artículo, lo que hace pensar que tal vez para su respuesta en el artículo no sea necesario dicho teorema, yo comparto su punto de vista (por varias razones) pero creo que como analizo otras posibilidades (preguntas, el momento actual, la matemática actual, la metamátematica actual, etc) me surge a mí la necesidad de recurrir a dicho teorema y a la teoría de modelos en primer orden (la cual ha demostrado ser muy fructífica). El lector del artículo del Profesor Moore y de este pequeño comentario se creará su propia opinión al respecto.
Nota biográfica sobre Per Lindström: A continuación se agrega el enlace de un homenaje hecho a Per Lindström en la revista THEORIA, 2010, 76, 100-107. En dicho escrito se exponen sus principales contribuciones académicas, los autores son Jouko Väänänen y Dag Westersáhl: http://www.math.helsinki.fi/logic/opetus/lt/Pelle.pdf. Esta es una imagen de la primera página del PDF:
No hay comentarios:
Publicar un comentario
Nota: solo los miembros de este blog pueden publicar comentarios.