Lógica de segundo orden

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Forma de lógica que permite la cuantificación sobre los predicados

En lógica y matemáticas, la lógica de segundo orden es una extensión de la lógica de primer orden, que a su vez es una extensión de la lógica proposicional. La lógica de segundo orden se amplía a su vez con la lógica de orden superior y la teoría de tipos.

La lógica de primer orden cuantifica sólo variables que abarcan a individuos (elementos del dominio del discurso); la lógica de segundo orden, además, también cuantifica sobre las relaciones. Por ejemplo, la segunda oración ${displaystyle forall P,forall x(Pxlor neg Px)}$ dice que por cada fórmula P, y cada individuo x, o Px es verdad o noPx) es cierto (esta es la ley del centro excluido). La lógica de segundo orden también incluye la cuantificación sobre conjuntos, funciones y otras variables (ver sección abajo). Tanto la lógica de primer orden como la segunda orden utilizan la idea de un dominio del discurso (a menudo llamado simplemente el "dominio" o el "universo"). El dominio es un conjunto sobre el cual los elementos individuales pueden ser cuantificados.

Ejemplos

La lógica de primer orden puede cuantificar sobre individuos, pero no sobre propiedades. Es decir, podemos tomar una oración atómica como Cube(b) y obtener una oración cuantificada reemplazando el nombre con una variable y adjuntando un cuantificador:

\exists x Cube(x)

Sin embargo, no podemos hacer lo mismo con el predicado. Es decir, la siguiente expresión

\existsP P(b)

no es una oración de lógica de primer orden, pero es una oración legítima de lógica de segundo orden. Aquí, P es una variable predicada y es semánticamente un conjunto de individuos.

Como resultado, la lógica de segundo orden tiene mayor poder expresivo que la lógica de primer orden. Por ejemplo, no hay forma en la lógica de primer orden de identificar el conjunto de todos los cubos y tetraedros. Pero la existencia de este conjunto se puede afirmar en lógica de segundo orden como

\existsP x (Px \leftrightarrow (C) x) Tet(x)).

Entonces podemos afirmar las propiedades de este conjunto. Por ejemplo, lo siguiente dice que el conjunto de todos los cubos y tetraedros no contiene ningún dodecaedro:

Отели (principal) x (Px \leftrightarrow (C) x) Tet(x) \to \neg \neg x (Px \land Dodec x)).

La cuantificación de segundo orden es especialmente útil porque permite expresar las propiedades de accesibilidad. Por ejemplo, si Parent(x, y) denota que x es un padre de y, entonces primero- la lógica de orden no puede expresar la propiedad de que x es un ancestro de y. En lógica de segundo orden podemos expresar esto diciendo que cada conjunto de personas que contiene y y cerrado bajo la relación principal contiene x:

(P) Sí. \land a О b (P b \land Parent(a, b)) \to P a) \to P x).

Es notable que mientras tenemos variables para predicados en lógica de segundo orden, no tenemos variables para propiedades de predicados. No podemos decir, por ejemplo, que haya una propiedad Shape(P) que sea verdadera para los predicados P Cube, Tet y Dodec. Esto requeriría una lógica de tercer orden.

Sintaxis y fragmentos

La sintaxis de la lógica de segundo orden indica qué expresiones son fórmulas bien formadas. Además de la sintaxis de la lógica de primer orden, la lógica de segundo orden incluye muchos nuevos tipos (a veces llamados tipos) de variables. Estos son:

Una especie de variables que abarcan conjuntos de individuos. Si S es una variable de este tipo y t es un término de primer orden entonces la expresión t ▪ S (también escrito S()t), o St para salvar paréntesis) es una fórmula atómica. Los conjuntos de individuos también pueden ser considerados como relaciones inadvertidas en el dominio.
Para cada número natural k hay una especie de variables que oscilan sobre todos k- relaciones con los individuos. Si R es tal k- relación variable y t₁,...t_k son términos de primer orden entonces la expresión R()t₁,...t_k) es una fórmula atómica.
Para cada número natural k hay una especie de variables que abarcan todas las funciones que toman k elementos del dominio y devolver un único elemento del dominio. Si f es tal k- función variable y t₁,...t_k son términos de primer orden entonces la expresión f()t₁,...t_k) es un término de primer orden.

Cada una de las variables recién definidas puede cuantificarse universal y/o existencialmente para construir fórmulas. Por lo tanto, hay muchos tipos de cuantificadores, dos para cada tipo de variable. Una oración en lógica de segundo orden, como en lógica de primer orden, es una fórmula bien formada sin variables libres (de ningún tipo).

Es posible prescindir de la introducción de variables de función en la definición anterior (y algunos autores lo hacen) porque una variable de función n-aria puede representarse mediante una variable de relación de aridad n+1 y una fórmula apropiada para la unicidad del "resultado" en el argumento n+1 de la relación. (Shapiro 2000, pág. 63)

Monadic segunda orden lógica (MSO) es una restricción de la lógica de segundo orden en la que sólo se permite la cuantificación sobre las relaciones no comunes (es decir, conjuntos). Así pues, tampoco se permite la cuantificación de las funciones, debido a la equivalencia a las relaciones descritas anteriormente. La lógica de segundo orden sin estas restricciones a veces se llama lógica de segundo orden para distinguirlo de la versión monádica. La lógica monádica de segundo orden se utiliza particularmente en el contexto del teorema de Courcelle, un metateorema algorítmico en la teoría de gráficos. La teoría MSO del árbol binario infinito completo (S2S) es decidable. Por el contrario, la lógica de segundo orden completo sobre cualquier conjunto infinito (o la lógica MSO sobre por ejemplo ( $mathbb {N}$ ,+)) puede interpretar la verdadera aritmética de segundo orden.

Al igual que en la lógica de primer orden, la lógica de segundo orden puede incluir símbolos no lógicos en un lenguaje de segundo orden en particular. Estos están restringidos, sin embargo, en que todos los términos que forman deben ser términos de primer orden (que pueden ser sustituidos por una variable de primer orden) o términos de segundo orden (que pueden ser sustituidos por una variable de segundo orden de un tipo apropiado).

Una fórmula en la lógica de segundo orden se dice que es de primer orden (y a veces denotado) $Sigma _{0}^{1}$ o $Pi _{0}^{1}$ ) si sus cuantificadores (que pueden ser universales o existenciales) varían sólo sobre variables de primer orden, aunque puede tener variables libres de segundo orden. A $Sigma _{1}^{1}$ (actual segunda orden) fórmula es otra que tiene algunos cuantificadores existenciales sobre variables de segundo orden, es decir. $exists R_{0}ldots exists R_{m}phi$ , donde $phi$ es una fórmula de primer orden. El fragmento de la lógica de segundo orden consiste sólo en fórmulas existenciales de segundo orden se llama lógica existencial de segundo orden y abreviado como ESO, como $Sigma _{1}^{1}$ , o incluso como ∃SO. El fragmento de $Pi _{1}^{1}$ fórmulas se definen dualmente, se llama lógica universal de segundo orden. Se definen fragmentos más expresivos para cualquier k ■ 0 por recidiva mutua: $Sigma _{k+1}^{1}$ tiene la forma $exists R_{0}ldots exists R_{m}phi$ , donde $phi$ es un $Pi _{k}^{1}$ fórmula, y similar, $Pi _{k+1}^{1}$ tiene la forma $forall R_{0}ldots forall R_{m}phi$ , donde $phi$ es un $Sigma _{k}^{1}$ fórmula. (Ver jerarquía analítica para la construcción analógica de aritmética de segundo orden.)

Semántica

La semántica de la lógica de segundo orden establece el significado de cada oración. A diferencia de la lógica de primer orden, que tiene solo una semántica estándar, hay dos semánticas diferentes que se usan comúnmente para la lógica de segundo orden: semántica estándar y semántica de Henkin. En cada una de estas semánticas, las interpretaciones de los cuantificadores de primer orden y los conectores lógicos son las mismas que en la lógica de primer orden. Solo los rangos de cuantificadores sobre variables de segundo orden difieren en los dos tipos de semántica (Väänänen 2001).

En la semántica estándar, también llamada semántica completa, los cuantificadores cubren todos los conjuntos o funciones del tipo apropiado. Así, una vez establecido el dominio de las variables de primer orden, se fija el significado de los cuantificadores restantes. Son estas semánticas las que dan a la lógica de segundo orden su poder expresivo, y se asumirán en el resto de este artículo.

Leon Henkin (1950) definió un tipo alternativo de semántica para las teorías de segundo orden y de orden superior, en el que el significado de los dominios de orden superior está parcialmente determinado por una axiomatización explícita, basada en la teoría de tipos, de las propiedades de los conjuntos o funciones recorridas. La semántica de Henkin es un tipo de semántica de primer orden de orden múltiple, donde hay una clase de modelos de los axiomas, en lugar de que la semántica se fije solo al modelo estándar como en la semántica estándar. Un modelo en la semántica de Henkin proporcionará un conjunto de conjuntos o un conjunto de funciones como la interpretación de dominios de orden superior, que pueden ser un subconjunto adecuado de todos los conjuntos o funciones de ese tipo. Para su axiomatización, Henkin demostró que el teorema de completitud y el teorema de compacidad de Gödel, que se cumplen para la lógica de primer orden, se trasladan a la lógica de segundo orden con la semántica de Henkin. Dado que también los teoremas de Skolem-Löwenheim se cumplen para la semántica de Henkin, el teorema de Lindström importa que los modelos de Henkin son solo modelos de primer orden encubiertos.

Para teorías como la aritmética de segundo orden, la existencia de interpretaciones no estándar de dominios de orden superior no es solo una deficiencia de la axiomatización particular derivada de la teoría de tipos que usó Henkin, sino una consecuencia necesaria de Gödel& Teorema de incompletitud de #39: los axiomas de Henkin no se pueden complementar más para garantizar que la interpretación estándar sea el único modelo posible. La semántica de Henkin se usa comúnmente en el estudio de la aritmética de segundo orden.

Jouko Väänänen (2001) argumentó que la elección entre los modelos de Henkin y los modelos completos para la lógica de segundo orden es análoga a la elección entre ZFC y V como base para la teoría de conjuntos: " Al igual que con la lógica de segundo orden, realmente no podemos elegir si axiomatizamos las matemáticas usando V o ZFC. El resultado es el mismo en ambos casos, ya que ZFC es el mejor intento hasta ahora de usar V como una axiomatización de las matemáticas."

Poder expresivo

La lógica de segundo orden es más expresiva que la lógica de primer orden. Por ejemplo, si el dominio es el conjunto de todos los números reales, uno puede afirmar en lógica de primer orden la existencia de un inverso aditivo de cada número real escribiendo ∀x ∃y (x + y = 0) pero se necesita una lógica de segundo orden para afirmar la propiedad del límite superior mínimo para conjuntos de números reales, que establece que cada límite, el conjunto no vacío de números reales tiene un supremo. Si el dominio es el conjunto de todos los números reales, la siguiente oración de segundo orden (dividida en dos líneas) expresa la propiedad del límite superior mínimo:

(VAN) (\exists) w) w ANTE A) \land (\exists) z) u) u \neg u \leq z)]

:\to (\exists) x) Sí. [(Primero) w) w \neg w \leq x) \land [u) u \neg u \leq Sí.) \to x \leq Sí.))

Esta fórmula es una formalización directa de "todos no vacía, atado set A tiene un límite inferior." Se puede demostrar que cualquier campo ordenado que satisfaga esta propiedad es isomorfo al campo número real. Por otro lado, el conjunto de oraciones de primera orden válidas en los reales tiene modelos arbitrariamente grandes debido al teorema de compactidad. Así, la propiedad menos alta no puede ser expresada por ningún conjunto de oraciones en la lógica de primera orden. (De hecho, cada campo cerrado real satisface las mismas oraciones de primer orden en la firma $langle +,cdotleq rangle$ como los números reales.)

En la lógica de segundo orden, es posible escribir oraciones formales que digan "el dominio es finito" o "el dominio es de cardinalidad contable." Para decir que el dominio es finito, usa la oración que dice que toda función sobreyectiva desde el dominio hasta sí misma es inyectiva. Para decir que el dominio tiene cardinalidad contable, usa la oración que dice que hay una biyección entre cada dos subconjuntos infinitos del dominio. Del teorema de la compacidad y del teorema ascendente de Löwenheim-Skolem se deduce que no es posible caracterizar la finitud o la contabilidad, respectivamente, en lógica de primer orden.

Ciertos fragmentos de la lógica de segundo orden como ESO también son más expresivos que la lógica de primer orden, aunque son estrictamente menos expresivos que la lógica de segundo orden completa. ESO también disfruta de la equivalencia de traducción con algunas extensiones de la lógica de primer orden que permiten la ordenación no lineal de las dependencias de los cuantificadores, como la lógica de primer orden extendida con los cuantificadores de Henkin, la lógica favorable a la independencia de Hintikka y Sandu, y la lógica de Väänänen' s lógica de dependencia.

Sistemas deductivos

Un sistema deductivo para una lógica es un conjunto de reglas de inferencia y axiomas lógicos que determinan qué secuencias de fórmulas constituyen pruebas válidas. Se pueden usar varios sistemas deductivos para la lógica de segundo orden, aunque ninguno puede ser completo para la semántica estándar (ver más abajo). Cada uno de estos sistemas es sólido, lo que significa que cualquier oración que puedan usarse para probar es lógicamente válida en la semántica apropiada.

El sistema deductivo más débil que se puede usar consiste en un sistema deductivo estándar para lógica de primer orden (como la deducción natural) aumentado con reglas de sustitución para términos de segundo orden. Este sistema deductivo se usa comúnmente en el estudio de la aritmética de segundo orden.

Los sistemas deductivos considerados por Shapiro (1991) y Henkin (1950) añaden al esquema deductivo de primer orden aumentado tanto axiomas de comprensión como axiomas de elección. Estos axiomas son válidos para la semántica estándar de segundo orden. Son válidos para la semántica de Henkin restringida a los modelos de Henkin que satisfacen los axiomas de comprensión y elección.

No reducibilidad a lógica de primer orden

Se podría intentar reducir la teoría de segundo orden de los números reales, con semántica completa de segundo orden, a la teoría de primer orden de la siguiente manera. Primero, expanda el dominio del conjunto de todos los números reales a un dominio de dos ordenaciones, con la segunda ordenación que contiene todos los conjuntos de números reales. Agrega un nuevo predicado binario al lenguaje: la relación de membresía. Luego, las oraciones que eran de segundo orden se convierten en de primer orden, y los cuantificadores de segundo orden anteriormente se ubican en el segundo orden. Esta reducción se puede intentar en una teoría de orden único agregando predicados unitarios que indican si un elemento es un número o un conjunto, y tomando el dominio como la unión del conjunto de números reales y el conjunto de potencia de los números reales.

Pero observe que se afirmó que el dominio incluye todos los conjuntos de números reales. Ese requisito no puede reducirse a una oración de primer orden, como muestra el teorema de Löwenheim-Skolem. Ese teorema implica que hay un subconjunto contablemente infinito de los números reales, cuyos miembros llamaremos números internos, y alguna colección contablemente infinita de conjuntos de números internos, cuyos miembros llamaremos " conjuntos internos", tales que el dominio que consta de números internos y conjuntos internos satisface exactamente las mismas oraciones de primer orden que satisface el dominio de los números reales y los conjuntos de números reales. En particular, satisface una especie de axioma de límite superior mínimo que dice, en efecto:

Todo extranjero interna que tiene un interna el límite superior tiene un mínimo interna superior.

La contabilidad del conjunto de todos los números internos (junto con el hecho de que forman un conjunto densamente ordenado) implica que ese conjunto no satisface el axioma completo del límite superior mínimo. La contabilidad del conjunto de todos los conjuntos internos implica que no es el conjunto de todos los subconjuntos del conjunto de todos los números internos (ya que Cantor&# El teorema de 39 implica que el conjunto de todos los subconjuntos de un conjunto infinito contable es un conjunto infinito incontable). Esta construcción está estrechamente relacionada con la paradoja de Skolem.

Por lo tanto, la teoría de primer orden de números reales y conjuntos de números reales tiene muchos modelos, algunos de los cuales son contables. Sin embargo, la teoría de segundo orden de los números reales tiene un solo modelo. Esto se deriva del teorema clásico de que solo hay un campo ordenado completo de Arquímedes, junto con el hecho de que todos los axiomas de un campo ordenado completo de Arquímedes son expresables en lógica de segundo orden. Esto muestra que la teoría de segundo orden de los números reales no puede reducirse a una teoría de primer orden, en el sentido de que la teoría de segundo orden de los números reales tiene un solo modelo pero la correspondiente teoría de primer orden tiene muchos modelos.

Hay ejemplos más extremos que muestran que la lógica de segundo orden con semántica estándar es más expresiva que la lógica de primer orden. Existe una teoría finita de segundo orden cuyo único modelo son los números reales si se cumple la hipótesis del continuo y que no tiene modelo si no se cumple la hipótesis del continuo (cf. Shapiro 2000, p. 105). Esta teoría consiste en una teoría finita que caracteriza a los números reales como un campo completo ordenado de Arquímedes más un axioma que dice que el dominio es de primera cardinalidad incontable. Este ejemplo ilustra que la cuestión de si una oración en lógica de segundo orden es consistente es extremadamente sutil.

Las limitaciones adicionales de la lógica de segundo orden se describen en la siguiente sección.

Did you mean:

Metallurgical results

Es un corolario del teorema de incompletitud de Gödel que no existe un sistema deductivo (es decir, ninguna noción de probabilidad) para fórmulas de segundo orden que satisfagan simultáneamente estos tres atributos deseados:

(Suena) Cada frase provable de segundo orden es universalmente válida, es decir, verdadera en todos los dominios bajo semántica estándar.
(Completa) Cada fórmula universalmente válida de segundo orden, bajo semántica estándar, es provable.
(Efectividad) Hay un algoritmo de verificación de pruebas que puede decidir correctamente si una secuencia determinada de símbolos es una prueba o no.

Este corolario se expresa a veces diciendo que la lógica de segundo orden no admite una teoría de prueba completa. A este respecto, la lógica de segundo orden con semántica estándar difiere de la lógica de primer orden; Quine (1970, pp. 90-91) señaló la falta de un sistema de prueba completo como una razón para pensar que la lógica de segundo orden no es lógica propiamente dicha.

Como se mencionó anteriormente, Henkin demostró que el sistema deductivo estándar para la lógica de primer orden es sólido, completo y efectivo para la lógica de segundo orden con la semántica de Henkin, y el sistema deductivo con principios de comprensión y elección es sólido, completo y efectivo para la semántica de Henkin usando solo modelos que satisfacen estos principios.

El teorema de compacidad y el teorema de Löwenheim-Skolem no se cumplen para modelos completos de lógica de segundo orden. Sin embargo, se mantienen para los modelos Henkin.

Historial y valor en disputa

La lógica de predicados fue introducida a la comunidad matemática por C. S. Peirce, quien acuñó el término lógica de segundo orden y cuya notación es más similar a la forma moderna (Putnam 1982). Sin embargo, hoy en día, la mayoría de los estudiantes de lógica están más familiarizados con los trabajos de Frege, quien publicó su trabajo varios años antes que Peirce, pero cuyos trabajos fueron menos conocidos hasta que Bertrand Russell y Alfred North Whitehead los hicieron famosos. Frege usó diferentes variables para distinguir la cuantificación sobre objetos de la cuantificación sobre propiedades y conjuntos; pero él no se veía a sí mismo haciendo dos tipos diferentes de lógica. Después del descubrimiento de la paradoja de Russell, se dio cuenta de que algo andaba mal con su sistema. Eventualmente, los lógicos descubrieron que restringir la lógica de Frege de varias maneras, a lo que ahora se llama lógica de primer orden, eliminó este problema: los conjuntos y las propiedades no se pueden cuantificar solo en la lógica de primer orden. La jerarquía ahora estándar de órdenes de lógica data de esta época.

Se encontró que la teoría de conjuntos podía formularse como un sistema axiomatizado dentro del aparato de la lógica de primer orden (a costa de varios tipos de completitud, pero nada tan malo como la paradoja de Russell), y esto fue hecho (ver Teoría de conjuntos de Zermelo-Fraenkel), ya que los conjuntos son vitales para las matemáticas. La aritmética, la mereología y una variedad de otras teorías lógicas poderosas podrían formularse axiomáticamente sin apelar a ningún aparato más lógico que la cuantificación de primer orden, y esto, junto con la adhesión de Gödel y Skolem a la lógica de primer orden, condujo a una disminución general del trabajo en lógica de segundo orden (o superior).

Este rechazo fue promovido activamente por algunos lógicos, sobre todo W. V. Quine. Quine avanzó la opinión de que en oraciones de lenguaje predicado como Fx el "x" debe pensarse como una variable o nombre que denota un objeto y, por lo tanto, puede cuantificarse, como en "Para todas las cosas, es el caso que..." pero la "F" debe considerarse como una abreviatura de una oración incompleta, no el nombre de un objeto (ni siquiera de un objeto abstracto como una propiedad). Por ejemplo, podría significar "... es un perro." Pero no tiene sentido pensar que podemos cuantificar sobre algo como esto. (Tal posición es bastante consistente con los propios argumentos de Frege sobre la distinción concepto-objeto). Entonces, usar un predicado como variable es hacer que ocupe el lugar de un nombre, que solo deberían ocupar las variables individuales. Este razonamiento ha sido rechazado por George Boolos.

En los últimos años, la lógica de segundo orden se ha recuperado, impulsada por Boolos' interpretación de la cuantificación de segundo orden como cuantificación plural sobre el mismo dominio de objetos que la cuantificación de primer orden (Boolos 1984). Boolos, además, señala la supuesta no ordenación de oraciones como 'Algunos críticos solo se admiran unos a otros'. y 'Algunos de los hombres de Fianchetto entraron en el almacén sin nadie más', lo que, según él, solo puede expresarse con toda la fuerza de la cuantificación de segundo orden. Sin embargo, la cuantificación generalizada y la cuantificación parcialmente ordenada (o bifurcada) también pueden ser suficientes para expresar una cierta clase de oraciones supuestamente no ordenables en primer lugar y estas no apelan a la cuantificación de segundo orden.

Relación con la complejidad computacional

Did you mean:

El poder expresivo de varias formas de lógica de segundo orden en estructuras finitas está íntimamente ligado a la teoría de la complejidad computacional. El campo de la complejidad descriptiva estudia qué clases de complejidad computacional pueden caracterizarse por el poder de la lógica necesaria para expresar lenguajes (conjuntos de cadenas finitas) en ellas. Una cadena w = w₁···w_n en un alfabeto finito A se puede representar mediante una estructura finita con dominio D = {1,...,n}, predicados unarios P_a para cada a ∈ A, satisfecho por esos índices i tales que w_i = a, y predicados adicionales que sirven para identificar de forma única qué índice es cuál (típicamente, uno toma el gráfico de la función sucesora en D o la relación de orden <, posiblemente con otros predicados aritméticos). Por el contrario, las tablas de Cayley de cualquier estructura finita (sobre una firma finita) pueden codificarse mediante una cadena finita.

Esta identificación conduce a las siguientes caracterizaciones de variantes de lógica de segundo orden sobre estructuras finitas:

REG (los idiomas regulares) es el conjunto de idiomas definibles por fórmulas monádicas de segundo orden (Teorema Büchi-Elgot-Trakhtenbrot, 1960)
NP es el conjunto de idiomas definibles por fórmulas existenciales de segundo orden (Teorema de Fagin, 1974).
co-NP es el conjunto de idiomas definibles por fórmulas universales de segundo orden.
El PH es el conjunto de idiomas definibles por fórmulas de segundo orden.
PSPACE es el conjunto de idiomas definibles por fórmulas de segundo orden con un operador de cierre transitivo añadido.
EXPTIME es el conjunto de idiomas definibles por fórmulas de segundo orden con un operador de punto menos fijo añadido.

Las relaciones entre estas clases impactan directamente en la expresividad relativa de las lógicas sobre estructuras finitas; por ejemplo, si PH = PSPACE, agregar un operador de cierre transitivo a la lógica de segundo orden no lo haría más expresivo en estructuras finitas.

Contenido relacionado

Más resultados...