[Raúl Aparicio Bustillo]

Cuando yo aplico un axioma o teorema en una demostración, ¿se puede repetir el proceso un número infinito de veces?

¿Qué conjunto o clase de números se utilizarían para indexar dichos pasos infinitos?

 Por otra parte, yo había oído que en lógica de primer orden todo lo que se puede deducir se puede hacer en un número finito de pasos.
Esto choca un poco con por ejemplo el conjunto omega+1, que con los ordinales de Von Neumann se obtiene en omega+1 pasos, ¿no? ¿O hay alguna manera finita de llegar hasta él?
Saludos

[Raúl Aparicio Bustillo]

Cuando yo aplico un axioma o teorema en una demostración, ¿se puede repetir el proceso un número infinito de veces?

¿Qué conjunto o clase de números se utilizarían para indexar dichos pasos infinitos?

 Por otra parte, yo había oído que en lógica de primer orden todo lo que se puede deducir se puede hacer en un número finito de pasos.
Esto choca un poco con por ejemplo el conjunto omega+1, que con los ordinales de Von Neumann se obtiene en omega+1 pasos, ¿no? ¿O hay alguna manera finita de llegar hasta él?

Los indexación de cada paso en las demostraciones deben ser un buen orden (porque todo razonamiento empieza con un axioma o teorema y acaba en una conclusión), así que hay que elegir una ordenación isomorfa a los números ordinales

[Óscar Matzerath]

Hola,

Pues en lógica de primer orden las demostraciones son objetos finitos, así que vienen indexadas por naturales.

El hecho de que en teoría de conjuntos haya conjuntos infinitos no debe causar confusión, pues un conjunto infinito y una demostración de que tal conjunto infinito existe son cosas muy distintas, y la demostración, siempre que se use lógica de primer orden, es finita. Por ejemplo, para el conjunto \( \omega + 1 \) que dices, una demostración de su existencia en ZFC viene a ser una cosa así (la versión formalizada y con todos los detalles de lo siguiente):

Por el axioma del infinito, existe un conjunto inductivo A. Por el axioma de partes, existe el conjunto de partes de ese conjunto inductivo, P(A). Por el axioma de separación aplicado a P(A), existe S, el conjunto de todos los subconjuntos inductivos de A. Por el axioma de separación aplicado a A, existe el conjunto \( \omega = \cap S = \{ x \in A : \forall y (y \in S \rightarrow x \in y) \} \). Esto demuestra la existencia de \( \omega \), el menor conjunto inductivo (se puede comprobar que esta definición de \( \omega \) como menor conjunto inductivo coincide con el conjunto de los números naturales, que es un ordinal y es el menor ordinal infinito, etc, pero no hace falta hacer todo eso para demostrar que existe). Ahora, por el axioma del par aplicado a \( \omega \), existe \( \{ \omega \} \) y otra aplicación del axioma del par nos da la existencia de \( \{ \omega , \{ \omega \} \} \). Finalmente, por el axioma de la unión aplicado a este último conjunto, tenemos que existe \( \bigcup \{ \omega , \{ \omega \} \} = \omega \cup \{ \omega \} = \omega + 1 \).

Como ves, la demostración de la existencia de \( \omega + 1 \) es finita, y de hecho, si te fijas, ni siquiera nos ha hecho falta hacer referencia a los elementos de \( \omega + 1 \) para demostrar que tal conjunto existe. Precisamente debido a que las demostraciones son objetos finitos, el axioma de infinitud es indispensable en una teoría de conjuntos si queremos poder demostrar que existe algún conjunto infinito. Con los demás axiomas, sólo podemos demostrar que existen conjuntos finitos, precisamente (en ZFC - infinitud) partiendo del conjunto vacío y construyendo explícitamente los conjuntos finitos a partir de los axiomas del par, unión y conjunto de partes. En cambio, para probar que existen conjuntos infinitos, no podemos construirlos explícitamente elemento a elemento, sino que hay que dar demostraciones "no constructivas" de ellos, como la de arriba, donde la existencia de \( \omega \) se deduce a partir de la existencia de un conjunto inductivo A, cuya existencia a su vez hay que postularla como axioma.

En sistemas de lógica infinitarios, donde pueden haber demostraciones de longitud infinita, se suele usar como indexación ordinales, aunque en principio nada impide que haya sistemas de demostración con demostraciones indexadas por otro tipo de números (si bien yo no conozco ningún caso, aunque tampoco estoy demasiado puesto en ese tipo de lógicas "exóticas").

Saludos

[Raúl Aparicio Bustillo]

Muy buena explicación, de las que nos tienes acostumbrado, la verdad clara y transparente, y "bonita"

Entonces, ¿mi argumento-restricción  de que los pasos de una demostración indexados deben constituir un buen orden es quizá una restricción demasiado fuerte, y quizás haya demostraciones no finitisitas que se indexen por ejemplo, por los naturales  un modelo no estandar  de N (con el modelo estandar es obvio que la demostración entra dentro de las demos finitistas), o cualquier otra indexación (cardinales finitos y transfinitos, o algún otro tipo de indexación infinita que yo no conozco, y que por alguna de tus ultimas respuestas parece ser que lo hay , incluso ordenes parciales, etc...

Lo que no termino de ver claro ( ya sé que no trabajas mucho con NFU), es la construcción ( de manera finitista, claro, de manera no finitista es trivial, con el llamemosle "axioma del siguiente" de que cada conunto inductivo x tiene su siguiente {x}Ux y se puede llegar a omega ,omega+1,etc... aplicando dicho axioma de manera infinita) de los ordinales de manera finitista (en NFU no hay axioma de partes), aunque imagino que aún de otro modo, se podrá hacer

 

Una última cuestión, entonces, cuando admites demostraciones con infinitos pasos,¿ ya estás saliendote a lógicas que no son de primer orden?

[Óscar Matzerath]

Hola,

Entonces, ¿mi argumento-restricción  de que los pasos de una demostración indexados deben constituir un buen orden es quizá una restricción demasiado fuerte, y quizás haya demostraciones no finitisitas que se indexen por ejemplo, por los naturales  un modelo no estandar  de N (con el modelo estandar es obvio que la demostración entra dentro de las demos finitistas), o cualquier otra indexación (cardinales finitos y transfinitos, o algún otro tipo de indexación infinita que yo no conozco, y que por alguna de tus ultimas respuestas parece ser que lo hay , incluso ordenes parciales, etc...

Tu argumento parece bastante razonable para una generalización de cálculos tipo Hilbert (una sucesión de fórmulas donde cada fórmula es un axioma o una premisa o se deduce de los anteriores mediante reglas de inferencia), y desde luego si tuviera que definir yo un cálculo de este tipo que permitiera demostraciones infinitas, lo haría con ordinales. Pero esto no quita para que pueda haber cálculos en los que se pueda seguir otra indexación. De hecho, por ejemplo, tienes los tableaux (que son un tipo de cálculo muy común) que tienen forma de árbol, de modo que si quieres numerar las fórmulas que aparecen (nodos) tiene más sentido usar un orden parcial que un orden lineal (como son los ordinales).

Lo que no termino de ver claro ( ya sé que no trabajas mucho con NFU), es la construcción ( de manera finitista, claro, de manera no finitista es trivial, con el llamemosle "axioma del siguiente" de que cada conunto inductivo x tiene su siguiente {x}Ux y se puede llegar a omega ,omega+1,etc... aplicando dicho axioma de manera infinita) de los ordinales de manera finitista (en NFU no hay axioma de partes), aunque imagino que aún de otro modo, se podrá hacer

Bueno, un ordinal se define como un conjunto transitivo y bien ordenado por \( \in \), así que realmente construir no se construye nada. Lo que se hace es demostrar que conjuntos como \( \emptyset, \omega \) son ordinales, y que dado un ordinal x, entonces el siguiente \( x \cup \{x\} \) también es un ordinal. No sé los detalles de todas estas demostraciones en NFU, pero en principio no tiene por qué ser mucho más complicado que en ZFC.

 

Una última cuestión, entonces, cuando admites demostraciones con infinitos pasos,¿ ya estás saliendote a lógicas que no son de primer orden?

Tienes toda la razón, debería haber dicho "lógica clásica de primer orden", es la costumbre. Y de hecho ni siquiera eso, ya que igual que hay muchos tipos distintos de cálculos deductivos para la lógica clásica de primer orden (tipo Hilbert, tipo Gentzen, deducción natural, tableaux, ...) es concebible que haya algíun cálculo deductivo infinitario que tenga como teoremas exactamente los de la lógica clásica de primer orden.

Saludos

[Raúl Aparicio Bustillo]

¡Hola!

En un post anterior tuyo no recuerdo ya fue hace tiempo, creí entender que la lógica de primer orden admitía infinitos pasos en una demostración, pero que en la realidad,  toda deducción con procesos repetidos hasta lo transfinito, admitiía tambien, una demostración finitista, y que por ello la lógica de primer orden no usaba inducción transfinita.

Pero ahora creo que interpreté mal aquello, lo que me lleva al planteamiento general de primero, que la lógica de primer orden (entendido el término "logica de primer orden" simplemente como cualquier sistema deductivo en el que no aparecen variables de función ni variables de predicado) tiene (por lo que he creido entender ahora) más de un calculo deductivo  válido (lo que llamas tipo Hilbert, tipo Gentzen...,etc)


Todo esto me lleva ya al planteamiento más general de

¿Qué calculos deductivos son aceptables (por "cálculo deductivo aceptable" entiendo que cualquier teorema deducido partiendo de un teorema previo   o de un  axioma de la teoría [axioma lógico  del calculo correspondiente o axioma propio de la teoría axiomática tratada] mediante la aplicación de las reglas de inferencia correspondientes a dicho cálculo , es una consecuencia lógica [entendida en el sentido habitual ,es decir, en el sentido de  que cualquier semántica que hace verdadera el axioma o teorema del que partimos como premisa, tambien hace verdadera la conclusión]

Entonces imagino que habrá un procedimiento general ( o quizás no haya un procedimiento general, quizás  en cada caso la demostración de que un cálculo deductivo  determinado es aceptable requiera un procedimiento distinto, pero que en cualquier caso, tiene que haber una demostración de que dicho calculo deductivo es aceptable en el sentido especificado arriba)

Una duda relacionada pero está es una "pregunta rápida". Los cálculos tipo Hilbert ¿son los que se basan en una demostración de un número finito de pasos con los axiomas y reglas de inferencia de la logica de primer orden?

¿Y los tipo Gentzen son los que permiten procedimientos no finitistas como la inducción transfinita

[Óscar Matzerath]

Hola,

Lo has entendido bien ahora. La lógica de primer orden admite muchos cálculos deductivos distintos. En principio, dada una lógica, un cálculo válido para ella debería ser un cálculo correcto y completo, es decir, que en el cálculo puedas obtener como teoremas exactamente los mismos que en la lógica. Aparte de esto, el único requisito que se debe imponer a un cálculo es que sea sintáctico, sin hacer referencia explícita a la semántica de la lógica. Normalmente las demostraciones en los cálculos deductivos son objetos finitos, pero también hay generalizaciones infinitarias.

En efecto, para cada lógica distinta (y cada cálculo distinto) hay que dar una prueba distinta de que un cálculo dado es correcto y completo para dicha lógica. En general, no hay un procedimiento general que sirva para todas las lógicas, pero normalmente la parte de corrección es fácil (simplemente comprobar que los axiomas son lógicamente válidos en tu lógica y que las reglas preservan la verdad), mientras que la parte de completitud es difícil. Para lógicas de tipo proposicional hay toda una teoría bien desarrollada que da un método más o menos general para probar esto, y se aplica a una clase muy amplia de lógicas (por ejemplo, a la lógica clásica), que es el método de las álgebras de Lindenbaum-Tarski. Para lógicas de primer orden hay técnicas parecidas, pero no hay una teoría tan general detrás y hay que ir con más cuidado.

Sobre la pregunta rápida: no. Los cálculos tipo Hilbert son los cálculos clásicos tipo axiomas + reglas de inferencia donde una demostración es una sucesión donde cada fórmula es un axioma, una premisa o se obtiene de anteriores con reglas de inferencia (típicamente, por ejemplo en lógica clásica, sólo modus ponens, o si es en primer orden, modus ponens e introducción del cuantificador). Luego hay otros tipos de cálculo, como la deducción natural donde puedes usar hipótesis y vas introduciendo o quitando conectivas lógicas usando reglas del tipo: si tienes \( \varphi \wedge \psi \) puedes obtener \( \varphi \) (eliminación de \( \wedge \)), o si tienes \( \varphi  \) puedes obtener \( \varphi \vee \psi \) (introducción de \( \vee \)). La diferencia es que en los cálculos de tipo Hilbert toda la importancia la tienen los axiomas, mientras que en deducción natural no hay axiomas y son básicamente reglas. Además la diferencia crucial es que en deducción natural puedes asumir cualquier fórmula como hipótesis mientras al final descartes la hipótesis (usando reglas). Por ejemplo, puedes tomar la fórmula \( \varphi \) como hipótesis, a partir de ahí usando reglas llegar a \( \psi \) y finalmente usar la regla de introducción de la implicación para descartar la hipótesis y obtener una demostración (a partir de nada) de \( \varphi \rightarrow \psi \). Como ves, el estilo de demostraciones en un cálculo tipo Hilbert y en uno deducción natural es bastante distinto.
Los cálculos tipo Gentzen son una formalización de la deducción natural. Aquí nuevamente la importancia la tienen las reglas, pero ahora ya no se trabaja con fórmulas sino con un objeto llamado secuente, que es algo del tipo \( \varphi_1,...,\varphi_n \triangleright \psi_1,...,\psi_n \) (la interpretación intuitiva es que ese secuente representa \( \varphi_1 \wedge ... \wedge \varphi_n \models \psi_1 \vee ... \vee \psi_n \)). Ahora las reglas hacen referencia a secuentes y se trabaja con estos. Este tipo de cálculo tiene muchas ventajas (más de las que parece a primera vista) y son la estrella de la llamada teoría de la demostración, que obtiene resultados de lógica estudiando solamente la estructura de las demostraciones formales. Un ejemplo típico de este campo es la prueba de consistencia de la aritmética de Gentzen usando inducción hasta \( \epsilon_0 \). En ese campo, se usa casi exclusivamente cálculos tipo Gentzen.

Saludos

 

[Raúl Aparicio Bustillo]

Dices:"un cálculo válido para ella debería ser un cálculo correcto y completo, es decir, que en el cálculo puedas obtener como teoremas exactamente los mismos que en la lógica

¿Qué diferencia hay entre una lógica y un cálculo deductivo?

Y, por último, la logica de primer orden solo admite conjuntos y urelementos como variables, no permitiendo cuantizar sobre relaciones (predicados) y funciones. Pero de ahí, ¿cómo se llega a la conclusión de que toda demostración se pueda hacer en un número finito de pasos?

En realidad yo antes pensaba que la inducción transfinita obligaba a aplicar el axioma que dice que si P(x)==>P(x+1) entonces para todo x P(x), implicaba infinitos pasos la demostración.Cuando en realidad hay infinitas aplicaciones P(1)==>P(2), P(2)==>P(3),etc...pero son infinitas aplicaciones, una para demostrar P(1). otra para demostrar P(2),etc... no una aplicación infinitas veces (para cualquier número natural P(n) implica n aplicaciones del axioma, pero n es un numero natural estandar.

 Lo que si es verdad es que para aplicar inducción transfinita, partimos de un conjunto infinito de premisas P(n), entonces en lógica de primer orden, ¿se puede partir de un conjunto infinito de premisas, requeridas cuando vamos a demostrar P para un ordinal limite?

[Óscar Matzerath]

Hola,

Dices:"un cálculo válido para ella debería ser un cálculo correcto y completo, es decir, que en el cálculo puedas obtener como teoremas exactamente los mismos que en la lógica

¿Qué diferencia hay entre una lógica y un cálculo deductivo?

Una lógica pueden ser muchas cosas. En el sentido más general, una lógica L es un subconjunto de P(Fm)xFm, donde Fm es el conjunto de fórmulas (en algún lenguaje) que cumple unas ciertas propiedades. La idea es que una lógica L queda completamente determinada dando todos los pares \( (\Gamma, \varphi) \) tales que \( Gamma \vdash_L \varphi \) (esta notación simplemente significa que \( (\Gamma, \varphi) \in L \)), donde \( \Gamma \) es un conjunto de fórmulas y \( \varphi \) una fórmula.

En cambio, un cálculo deductivo da una noción de demostración formal. Partes de unos axiomas y/o unas reglas y puedes ir obteniendo teoremas. Un cálculo deductivo siempre define una lógica L': \( \Gamma \vdash_{L'} \varphi \) si y sólo si existe una demostración formal en el cálculo de \( \varphi \) usando premisas en \( \Gamma \). Pero esto es solamente una manera posible de definir una lógica. También puedes definir lógicas semánticamente (por ejemplo la clásica de primer orden usando estructuras y la noción de satisfacibilidad de una fórmula en una estructura) y de otras maneras. Por supuesto, si defines una lógica a partir de un cálculo, automáticamente ese cálculo es completo y correcto respecto a la lógica. El problema es, dada una lógica L no definida por un cálculo (normalmente definida de alguna forma semántica) encontrar un cálculo deductivo correcto y completo para esa lógica. Esa es la parte difícil.

Y, por último, la logica de primer orden solo admite conjuntos como variables, no permitiendo cuantizar sobre relaciones (predicados) y funciones. Pero de ahí, ¿cómo se llega a la conclusión de que toda demostración se pueda hacer en un número finito de pasos?

Es que no se llega a esa conclusión. Eso es cierto en la lógica clásica de primer orden, pero hay lógicas de primer orden (y proposicionales) no clásicas para las que no existe ningún cálculo correcto y completo con demostraciones finitas. Un ejemplo muy popular es la lógica infinito-valuada de Lukasiewicz. Pero aun así, se suelen usar y estudiar cálculos deductivos para estas lógicas, que aunque no son completos, sí cumplen la llamada completitud débil: si \( \models \varphi \) entonces \( \vdash \varphi \) (aunque no es cierto que si \( \Gamma \models \varphi \) entonces \( \Gamma \vdash \varphi \) para cualquier \( \Gamma \)).

Saludos

[Raúl Aparicio Bustillo]

Hola

Bueno, en cualquier caso, a excepción de ZFC que no le cojo "el gusto", por eso tanto empeño en NFU (dado que parece ser la otra teoría que como ZFC es lo suficientemente potente para fundamentar las matemáticas [además, tiene su propia "Biblia" , el libro de Randall Holmes, que poquito a poquito lo voy pillando]

En cualquier caso,  doy por hecho que NFU está, al igual que ZFC, en un lenguaje de primer orden, y yendo más allá, doy por hecho que ambas teorías estan basadas en el cálculo deductivo de la lógica clásica de primer orden, dónde si tomamos las conectivas (no, implica, si y solo si, etc.....) con su significado intuitivo del lenguaje natural ,es trivial construyendo tablas de verdad e interpretando los cuantificadores con su significado intuitivo, que se  verifican los axiomas lógicos y reglas de inferencia de dicho cálculo

Entonces, cualquier demostración en dichas teorías se debería de limitar a un número finito de pasos, pero ¿qué pasa con la inducción transfinita? Tanto el libro de Holmes sobre NFU como el de Ivorra que trata NBG y ZFC, usan dicho método de inducción transfinita, así que imagino que este método es válido en lógica clásica de primer orden, pero yo , en la inducción transfinita, como digo no veo la finitud por nínguna parte (hay infinitos pasos si queremos alcanzar un ordinal transfinito)

Ahora me he dado cuenta que la cosa es todavía menos finitista peor: me he dado cuenta de que en el caso de un ordinal limite, para comprobar P(A)  (A ordinal límite), necesitamos probar que P es un enunciado que si lo verifica todo B<A, tambien lo verifica A, es decir, que aparte de infinitos pasos en la demo ,, en el caso del ordinal límite, se parte de infinitas premisas , pues usamos que P(A) es verdadero si lo es P(B) para todo B<A. En los ordinales que son sucesor de otro ordinal basta con probar P(B-1) como premisa, pero si es un ordinal límite y no hay numéro inmediatamente anterior (como ocurre con omega y con todos los ordinales límite) realmente hemos de coger infinitas premisas

Pero lo de las infinitas premisas quizá si lo admita (no lo sé) el calculo deductivo de la lógica clásica de primer orden, pero por lo que me cuentas los infinitos pasos en la demo no se puede usar en la lógica clásica de primer orden


Resumiendo: ¿Cómo se consigue que la inducción transfinita se pueda aplicar a lógica clásica de primer orden?