¿Están los números naturales implícitos en la construcción de la lógica de primer orden? Si es así, ¿por qué es esto aceptable?

Question

Recientemente he estado leyendo sobre la lógica de primer orden y la teoría de conjuntos. He visto axiomas estándar de la teoría de conjuntos (digamos ZFC) construidos formalmente en lógica de primer orden, donde la lógica de primer orden se utiliza como lenguaje de objetos y el inglés como metalenguaje.

Me gustaría construir una lógica de primer orden y luego construir una teoría axiomática de conjuntos en ese lenguaje. Al construir la lógica de primer orden en inglés, se suele incluir un número contablemente infinito de variables. Sin embargo, me parece que se necesita una definición de contablemente infinito para poder definir estas variables. Una colección contablemente infinita (todavía no queremos llamarla conjunto) es una colección que puede ponerse en correspondencia 1-1 con la colección de números naturales. Me parece problemático que uno parece estar utilizando implícitamente una noción de números naturales para definir la cosa que luego define los números naturales (por ejemplo, a través de la construcción de Von Neumann). ¿Es esta una preocupación legítima que tengo o hay una definición alternativa de "colección contablemente infinita" que debería utilizar? Si no es así, ¿podría alguien explicarme por qué no?

Creo que una posible solución es simplemente asumir los axiomas de la teoría de conjuntos que desee utilizando oraciones inglesas claras y precisas, definir los números naturales a partir de ahí, y luego definir la lógica de primer orden como una taquigrafía conveniente para el inglés claro y preciso que estoy utilizando. Me parece que la lógica de primer orden no es más que una abreviatura de oraciones inglesas claras y precisas. Cuál es el estatus ontológico exacto del inglés y si está o no justificado que lo usemos así son cuestiones filosóficas irresolubles, que estoy dispuesto a reconocer, y luego ignorar porque no están realmente en el ámbito de las matemáticas.

¿Parece ésta una solución viable y es correcta mi percepción de la lógica de primer orden como abreviatura del inglés claro y preciso (u otro lenguaje natural)?

Muchas gracias de antemano por la ayuda y la información.

Answer 1

Creo que aquí hay dos cuestiones (muy interesantes). Permítanme tratar de abordarlas.

En primer lugar, la pregunta del título: ¿se presuponen los números naturales en la lógica de primer orden?

Yo diría que la respuesta es definitivamente sí . Tenemos que suponer algo para poder arrancar; a cierto nivel, yo al menos doy por sentados los números naturales.

(Hay que tener en cuenta que hay mucho margen de maniobra en lo que se refiere a significa : Conozco gente que realmente encuentra inconcebible que la AP pueda ser inconsistente, y conozco gente que encuentra muy plausible, si no probable, que la AP sea inconsistente - todos ellos gente muy inteligente. Pero creo que tenemos que presuponer $\mathbb{N}$ al menos en la medida en que, por ejemplo, la aritmética de Presburgo https://en.wikipedia.org/wiki/Presburger_arithmetic es coherente).

Hay que tener en cuenta que esto no es circular, siempre y cuando seamos honestos sobre el hecho de que realmente estamos dando por sentado algunas cosas. Esto no debería ser demasiado extraño: si realmente das por nada por sentado, no se puede hacer mucho https://en.wikipedia.org/wiki/What_the_Tortoise_Said_to_Achilles . En cuanto a los fundamentos, nótese que todavía nos resultará valioso definir los números naturales dentro de nuestros fundamentos; pero esto será una expresión "interna" de algo que damos por sentado "externamente". Así, por ejemplo, a veces querremos distinguir entre "los números naturales" (tal como se definen en ZFC) y "los números naturales" (que suponemos al principio que "tenemos" de alguna manera).

Segunda pregunta: ¿Está bien ver la lógica de primer orden como una especie de "proxy" del lenguaje natural claro y preciso?

Mi respuesta es un rotundo ¡Más o menos! :P

Por un lado, me preocupa intrínsecamente el lenguaje natural. No confío en mi propio juicio sobre lo que es "claro" y "preciso". Por ejemplo, ¿es "Esta afirmación es falsa" clara y precisa? ¿Y la Hipótesis del Continuo?

Para mí, una de las cosas que hace la lógica de primer orden es precisar una clase de expresiones que garantizado son claros y precisos. Tal vez haya más (aunque yo diría que no los hay, en cierto sentido; véase el teorema de Lindstrom https://en.wikipedia.org/wiki/Lindstr%C3%B6m%27s_theorem ), pero al menos cualquier cosa que pueda expresar en lógica de primer orden es clara y precisa. Hay una serie de propiedades de FOL que me hacen sentirme cómodo diciendo esto; puedo entrar en más detalles si eso es útil.

Así que para mí, FOL realmente es un sustituto del pensamiento matemático claro y preciso. Sin embargo, hay una gran advertencia: el contexto es importante. Consideremos la afirmación " $G$ es la torsión" (aquí $G$ es un grupo). En el lenguaje de la teoría de conjuntos con un parámetro para $G$ es de primer orden; pero en el lenguaje de los grupos, no hay ninguna frase de primer orden $\varphi$ tal que [ $G\models\varphi$ si $G$ es de torsión] para todos los grupos $G$ ¡! Esto es una consecuencia de la Teorema de la compacidad para FOL.

Así que hay que tener cuidado al afirmar que algo es de primer orden, si se trabaja en un dominio que es "demasiado pequeño" (en cierto sentido, la teoría de conjuntos es "suficientemente grande", y un grupo individual no lo es). Pero siempre que se tenga cuidado sobre si lo que se está diciendo es realmente expresable en FOL, creo que esto es lo que todo el mundo hace hasta cierto punto, o de cierta manera.

Al menos, es lo que yo hago.

Answer 2

Hay tres conceptos interrelacionados:

• Los números naturales
• Cadenas finitas de símbolos
• Fórmulas - cadenas particulares de símbolos utilizados en la lógica formal.

Si entendemos uno de estos tres, podemos usarlo para entender los tres.

Por ejemplo, si sabemos lo que son las cadenas de símbolos, podemos modelar los números naturales utilizando la notación unaria y cualquier símbolo concreto que sirva de contador.

Del mismo modo, el método de prueba por inducción (utilizado para demostrar afirmaciones universales sobre los números naturales) tiene su reflejo en el principio de inducción estructural (utilizado para demostrar afirmaciones universales sobre cadenas finitas de símbolos, o sobre fórmulas).

A la inversa, si sabemos qué son los números naturales, podemos modelar cadenas de símbolos codificándolas como números naturales (por ejemplo, con la codificación de potencias primarias).

Esto da un argumento muy específico sobre la forma en que la lógica formal presupone un concepto de números naturales. Incluso si intentamos tratar la lógica formal de forma totalmente sintáctica, en cuanto sepamos cómo manejar cadenas finitas de símbolos, podremos reconstruir los números naturales a partir de ellas.

La idea subyacente a los tres conceptos relacionados es una noción que, a falta de una palabra mejor, podría describirse como "finitud discreta". Sin embargo, no se basa en la noción de "conjunto": si entendemos lo que son los números naturales individuales, esto nos permite entender las cadenas individuales, y viceversa, incluso sin referencia a la teoría de conjuntos. Pero, si entendemos los conjuntos de números naturales, entonces también entendemos los conjuntos de cadenas, y viceversa.

Si se leen los tratamientos más clásicos de la lógica formal, se verá que sí consideraron la cuestión de si sería necesario algo como la teoría de conjuntos para desarrollar la lógica formal - no lo es. Estos textos suelen proceder de una manera más "finitista", utilizando una definición inductiva de las fórmulas y un principio de inducción estructural que nos permite demostrar teoremas sobre las fórmulas sin ninguna referencia a la teoría de conjuntos. Este método sigue siendo bien conocido por los lógicos matemáticos contemporáneos, pero los textos actuales suelen estar escritos de forma que lo ocultan. Sin embargo, el enfoque teórico de conjuntos no es el único.

Answer 3

Para la pregunta del título, yo diría que la respuesta es no (más o menos). Para definir el lenguaje de la lógica de primer orden, basta con hablar de listas finitas de signos extraídos de un alfabeto finito. Por ejemplo, el alfabeto podría comprender los 36 signos $a,b,c,\ldots,x, y, z,0,1, \ldots, 9$ junto con un signo que llamaré "espacio". Ciertamente, no es necesario definir la noción "contablemente infinita" para garantizar un suministro contablemente infinito de símbolos variables: basta con garantizarlo cuando se define cómo las secuencias de signos codifican las construcciones del lenguaje: por ejemplo, diciendo que una variable comprende una letra seguida de un dígito distinto de cero seguido de una secuencia de dígitos terminada por un espacio.

Pero dicho esto, para razonar sobre la sintaxis, necesitarás razonar por inducción, y la línea divisoria entre el razonamiento sobre secuencias de signos y el razonamiento sobre números naturales se vuelve muy fina.

(Ver https://en.wikipedia.org/wiki/Formal_system#Logical_system para obtener más información sobre este tipo de cosas. Por buenas razones, los textos de lógica suelen pasar por alto los detalles, ya que lo único que realmente importa es que las fórmulas del lenguaje pueden representarse como objetos finitos).