Lógica de segundo orden

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 . ^{[ a ]} ​​La lógica de segundo orden, a su vez, es extendida por la lógica de orden superior y la teoría de tipos .

La lógica de primer orden cuantifica solo variables que abarcan individuos (elementos del dominio del discurso ); la lógica de segundo orden, además, cuantifica sobre relaciones . Por ejemplo, la oración de segundo orden${\displaystyle \forall P\,\forall x(Px\lor \neg Px)}$dice que para cada fórmula P y cada individuo x , o Px es verdadero o no( Px ) es verdadero (esta es la ley del tercero excluido ). La lógica de segundo orden también incluye la cuantificación sobre conjuntos , funciones y otras variables (ver sección a continuación ). Tanto la lógica de primer orden como la de segundo orden utilizan la idea de un dominio de discurso (a menudo llamado simplemente "dominio" o "universo"). El dominio es un conjunto sobre el cual se pueden cuantificar elementos individuales.

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

$${\displaystyle \exists x\,\mathrm {Cubo} (x)}$$

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

$${\displaystyle \existe \mathrm {P} \,\mathrm {P} (b)}$$

No es una oración de lógica de primer orden, pero sí es una oración legítima de lógica de segundo orden. Aquí, P es una variable predicativa y semánticamente es un conjunto de individuos. ^{[ 1 ]}

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

$${\displaystyle \exists \mathrm {P} \,\forall x\,(\mathrm {P} x\leftrightarrow (\mathrm {Cube} (x)\vee \mathrm {Tet} (x))).}$$

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

$${\displaystyle \forall \mathrm {P} \,(\forall x\,(\mathrm {P} x\leftrightarrow (\mathrm {Cube} (x)\vee \mathrm {Tet} (x)))\rightarrow \lnot \exists x\,(\mathrm {P} x\wedge \mathrm {Dodec} (x))).}$$

La cuantificación de segundo orden es especialmente útil porque permite expresar propiedades de alcanzabilidad . Por ejemplo, si Parent( x , y ) denota que x es padre de y , entonces la lógica de primer orden no puede expresar la propiedad de que x es antepasado de y . En lógica de segundo orden podemos expresar esto diciendo que todo conjunto de personas que contiene a y y que está cerrado bajo la relación Parent contiene a x :

$${\displaystyle \forall \mathrm {P} \,((\mathrm {P} y\wedge \forall a\,\forall b\,((\mathrm {P} b\wedge \mathrm {Parent} (a,b))\rightarrow \mathrm {P} a))\rightarrow \mathrm {P} x).}$$

Es notable que, si bien tenemos variables para los predicados en lógica de segundo orden, no tenemos variables para las propiedades de los predicados. No podemos decir, por ejemplo, que existe una propiedad Shape( P ) que sea verdadera para los predicados P Cube, Tet y Dodec. Esto requeriría lógica de tercer orden . ^{[ 2 ]}

La sintaxis de la lógica de segundo orden prescribe 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 tipos nuevos (a veces llamados tipos de variables). Estos son:

• Un tipo 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 escrita S ( t ), o St para ahorrar paréntesis) es una fórmula atómica . Los conjuntos de individuos también pueden considerarse como relaciones unarias en el dominio.
• Para cada número natural k existe una especie de variable que abarca todas las relaciones k -arias entre los individuos. Si R es una variable de relación k -aria 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 existe una especie de variable que abarca todas las funciones que toman k elementos del dominio y devuelven un único elemento del dominio. Si f es una variable de función k -aria 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, existen muchos tipos de cuantificadores, dos para cada tipo de variable. Una oración en lógica de segundo orden, al igual que 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.  63)

La lógica de segundo orden débil (LSO) es una restricción de la lógica de segundo orden que solo permite la cuantificación sobre conjuntos finitos. Es decir, solo permite la cuantificación sobre relaciones unarias con un número finito de elementos positivos.

La lógica monádica de segundo orden (MSO) es una restricción de la lógica de segundo orden en la que solo se permite la cuantificación sobre relaciones unarias (es decir, conjuntos). Es más fuerte que la WSO. Por lo tanto, la cuantificación sobre funciones, debido a la equivalencia con las relaciones descritas anteriormente, tampoco está permitida. La lógica de segundo orden sin estas restricciones a veces se denomina lógica de segundo orden completa para distinguirla 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 grafos . La teoría MSO del árbol binario infinito completo ( S2S ) es decidible . Por el contrario, la lógica de segundo orden completa sobre cualquier conjunto infinito (o la lógica MSO sobre, por ejemplo,${\displaystyle \mathbb {N} }$,+)) puede interpretar la verdadera aritmética de segundo orden y, por lo tanto, es indecidible.

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 específico. Sin embargo, estos símbolos están restringidos, ya que todos los términos que forman deben ser términos de primer orden (que pueden sustituir a una variable de primer orden) o términos de segundo orden (que pueden sustituir a una variable de segundo orden del tipo apropiado).

Se dice que una fórmula en lógica de segundo orden es de primer orden (y a veces se denota como tal).${\displaystyle \Sigma _{0}^{1}}$o${\displaystyle \Pi _{0}^{1}}$) si sus cuantificadores (que pueden ser universales o existenciales) abarcan solo variables de primer orden, aunque puede tener variables libres de segundo orden. A${\displaystyle \Sigma _{1}^{1}}$La fórmula (existencial de segundo orden) es aquella que además tiene algunos cuantificadores existenciales sobre variables de segundo orden, es decir${\displaystyle \exists R_{0}\ldots \exists R_{m}\phi }$, dónde${\displaystyle \phi }$es una fórmula de primer orden. El fragmento de lógica de segundo orden que consiste únicamente en fórmulas existenciales de segundo orden se llama lógica existencial de segundo orden y se abrevia como ESO, como${\displaystyle \Sigma _{1}^{1}}$, o incluso como ∃SO. El fragmento de${\displaystyle \Pi _{1}^{1}}$La fórmula se define de forma dual, y se denomina lógica universal de segundo orden. Se definen fragmentos más expresivos para cualquier k > 0 mediante recursión mutua:${\displaystyle \Sigma _{k+1}^{1}}$tiene la forma${\displaystyle \exists R_{0}\ldots \exists R_{m}\phi }$, dónde${\displaystyle \phi }$es un${\displaystyle \Pi _{k}^{1}}$fórmula y similares,${\displaystyle \Pi _{k+1}^{1}}$tiene la forma${\displaystyle \forall R_{0}\ldots \forall R_{m}\phi }$, dónde${\displaystyle \phi }$es un${\displaystyle \Sigma _{k}^{1}}$fórmula. (Véase jerarquía analítica para la construcción análoga de la aritmética de segundo orden ).

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 posee una única semántica estándar, existen dos semánticas diferentes que se utilizan comúnmente para la lógica de segundo orden: la semántica estándar y la 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 los cuantificadores sobre las variables de segundo orden difieren entre los dos tipos de semántica. ^{[ 3 ]}

En la semántica estándar, también llamada semántica completa, los cuantificadores abarcan todos los conjuntos o funciones del tipo apropiado. Un modelo con esta condición se denomina modelo completo, y estos son iguales a los modelos en los que el rango de los cuantificadores de segundo orden es el conjunto potencia de la parte de primer orden del modelo. ^{[ 3 ]} Por lo tanto, una vez establecido el dominio de las variables de primer orden, el significado de los cuantificadores restantes queda fijo. Es esta semántica la que confiere a la lógica de segundo orden su poder expresivo, y se asumirá en el resto de este artículo.

Leon Henkin (1950) definió un tipo alternativo de semántica para teorías de segundo orden y de orden superior, en la 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 abarcados. La semántica de Henkin es un tipo de semántica de primer orden multisortada, donde existe una clase de modelos de los axiomas, en lugar de que la semántica esté fijada únicamente 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 interpretación de los dominios de orden superior, que puede ser un subconjunto propio 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 son válidos para la lógica de primer orden, se extienden a la lógica de segundo orden con la semántica de Henkin. Dado que los teoremas de Löwenheim-Skolem también se cumplen para la semántica de Henkin, el teorema de Lindström implica que los modelos de Henkin son simplemente modelos de primer orden disfrazados . ^{[ 4 ]}

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 del teorema de incompletitud de Gödel : los axiomas de Henkin no pueden complementarse más para asegurar 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 argumentó que la distinción entre la semántica de Henkin y la semántica completa para la lógica de segundo orden es análoga a la distinción entre la demostrabilidad en ZFC y la verdad en V , en el sentido de que la primera obedece propiedades de la teoría de modelos como el teorema de Löwenheim-Skolem y la compacidad, y la segunda tiene fenómenos de categoricidad. ^{[ 3 ]} Por ejemplo, "no podemos preguntar significativamente si la${\displaystyle V}$según se define en${\displaystyle \mathrm {ZFC} }$es el real${\displaystyle V}$. Pero si reformulamos${\displaystyle \mathrm {ZFC} }$adentro${\displaystyle \mathrm {ZFC} }$, entonces podemos notar que la reformulada${\displaystyle \mathrm {ZFC} }$... tiene modelos contables y, por lo tanto, no puede ser categórico."

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 , se puede afirmar en lógica de primer orden la existencia de un inverso aditivo de cada número real escribiendo:${\displaystyle \forall x\exists y(x+y=0)}$pero se necesita lógica de segundo orden para afirmar la propiedad de cota superior mínima para conjuntos de números reales, que establece que todo conjunto acotado y no vacío de números reales tiene un supremo . Si el dominio es el conjunto de todos los números reales, la siguiente proposición de segundo orden (dividida en dos líneas) expresa la propiedad de cota superior mínima: $${\displaystyle {\begin{aligned}\forall A{\biggl (}&{\bigl (}\exists w(w\in A)\wedge \exists z\forall u(u\in A\rightarrow u\leq z){\bigr )}\rightarrow \\&\exists x{\Bigl (}\forall u(u\in A\rightarrow u\leq x)\wedge \forall y\forall u{\bigl (}(u\in A\rightarrow u\leq y)\rightarrow x\leq y{\bigr )}{\Bigr )}{\biggr )}\\\end{aligned}}}$$ Aquí, la parte de la primera línea involucra${\displaystyle w}$representa la suposición de que${\displaystyle A}$no está vacío (tiene un elemento,${\displaystyle w}$). El resto de la primera línea representa la suposición de que${\displaystyle A}$está acotado desde arriba (existe un número${\displaystyle z}$que sea mayor o igual que todos los elementos${\displaystyle u}$de${\displaystyle A}$La segunda línea expresa la existencia de un límite superior mínimo.${\displaystyle x}$Afirma que${\displaystyle x}$es un límite superior (es mayor o igual que cualquier elemento)${\displaystyle u}$en${\displaystyle A}$) y que, si algún número${\displaystyle y}$es también un límite superior, entonces${\displaystyle x\leq y}$Cualquier cuerpo ordenado que satisfaga esta propiedad es isomorfo al cuerpo de los números reales. Por otro lado, el conjunto de sentencias de primer orden válidas en los reales tiene modelos arbitrariamente grandes debido al teorema de compacidad. Por lo tanto, la propiedad de cota superior mínima no puede expresarse mediante ningún conjunto de sentencias en lógica de primer orden. (De hecho, todo cuerpo real cerrado satisface las mismas sentencias de primer orden en la signatura${\displaystyle \langle +,\cdot ,\leq \rangle }$como las cifras reales.)

En lógica de segundo orden, es posible escribir enunciados formales que indiquen que el dominio es finito o que tiene cardinalidad numerable . Para afirmar que el dominio es finito, se utiliza el enunciado que establece que toda función sobreyectiva del dominio sobre sí mismo es inyectiva . Para afirmar que el dominio tiene cardinalidad numerable, se utiliza el enunciado que establece que existe una biyección entre cada par de subconjuntos infinitos del dominio. Del teorema de compacidad y del teorema de Löwenheim-Skolem ascendente se deduce que no es posible caracterizar la finitud ni la numerabilidad, respectivamente, en lógica de primer orden.

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

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 utilizar varios sistemas deductivos para la lógica de segundo orden, aunque ninguno es completo para la semántica estándar (véase más adelante). Cada uno de estos sistemas es sólido , lo que significa que cualquier enunciado que puedan probar es lógicamente válido en la semántica apropiada.

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

Los sistemas deductivos considerados por Shapiro (2000) 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. ^{[ c ]}

Podría intentarse reducir la teoría de segundo orden de los números reales, con su semántica completa de segundo orden, a la teoría de primer orden de la siguiente manera. Primero, se amplía el dominio del conjunto de todos los números reales a un dominio de dos tipos, donde el segundo tipo contiene todos los conjuntos de números reales. Se añade un nuevo predicado binario al lenguaje: la relación de pertenencia. Entonces, las oraciones que eran de segundo orden se convierten en de primer orden, y los cuantificadores que antes eran de segundo orden ahora abarcan el segundo tipo. Esta reducción puede intentarse en una teoría de un solo tipo añadiendo predicados unarios que indiquen si un elemento es un número o un conjunto, y considerando que el dominio es la unión del conjunto de los números reales y el conjunto potencia de los números reales.

Pero observe que se afirmó que el dominio incluía todos los conjuntos de números reales. Ese requisito no puede reducirse a una proposición de primer orden, ni siquiera a una teoría de primer orden , como lo demuestra el teorema de Löwenheim-Skolem . Dicho teorema implica que existe un subconjunto infinito numerable de los números reales, cuyos miembros llamaremos números internos , y una colección infinita numerable de conjuntos de números internos, cuyos miembros llamaremos "conjuntos internos", tales que el dominio formado por los números internos y los conjuntos internos satisface exactamente las mismas proposiciones de primer orden que satisfacen el dominio de los números reales y los conjuntos de números reales. En particular, satisface una especie de axioma de cota superior mínima que dice, en efecto:

La numerabilidad del conjunto de todos los números internos (junto con el hecho de que estos forman un conjunto densamente ordenado) implica que dicho conjunto no satisface el axioma de cota superior mínima completa. La numerabilidad 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 el teorema de Cantor implica que el conjunto de todos los subconjuntos de un conjunto infinito numerable es un conjunto infinito no numerable). Esta construcción está estrechamente relacionada con la paradoja de Skolem .

Así, la teoría de primer orden de los números reales y de los conjuntos de números reales posee numerosos modelos, algunos de los cuales son numerables. Sin embargo, la teoría de segundo orden de los números reales solo posee un modelo. Esto se deduce del teorema clásico que establece que existe un único cuerpo ordenado completo arquimediano , junto con el hecho de que todos los axiomas de un cuerpo ordenado completo arquimediano pueden expresarse en lógica de segundo orden. Esto demuestra 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 posee un único modelo, mientras que la teoría de primer orden correspondiente posee numerosos modelos.

Existen ejemplos más extremos que demuestran 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 carece de modelo si dicha hipótesis no se cumple. ^{[ 5 ]} Esta teoría consiste en una teoría finita que caracteriza los números reales como un cuerpo ordenado arquimediano completo, además de un axioma que establece que el dominio es de cardinalidad incontable de primer orden. Este ejemplo ilustra que la cuestión de si una sentencia en lógica de segundo orden es consistente es extremadamente sutil.

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

Es un corolario del teorema de incompletitud de Gödel que no existe ningún sistema deductivo (es decir, ninguna noción de demostrabilidad ) para fórmulas de segundo orden que satisfaga simultáneamente estos tres atributos deseados: ^{[ d ]}

• ( Solidez ) Toda oración de segundo orden demostrable es universalmente válida, es decir, verdadera en todos los dominios bajo la semántica estándar.
• ( Completitud ) Toda fórmula de segundo orden universalmente válida, bajo la semántica estándar, es demostrable.
• ( Eficacia ) Existe un algoritmo de verificación de pruebas que puede decidir correctamente si una secuencia dada 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 la prueba completa . En este sentido, la lógica de segundo orden con semántica estándar difiere de la lógica de primer orden; Quine señaló la falta de un sistema de prueba completo como una razón para considerar que la lógica de segundo orden no es lógica propiamente dicha. ^{[ 6 ]}

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 que el sistema deductivo con principios de comprensión y elección es sólido, completo y efectivo para la semántica de Henkin utilizando 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, sí se cumplen para modelos de Henkin. ^{[ 7 ]}

La lógica de predicados fue introducida en la comunidad matemática por C.S. Peirce , quien acuñó el término lógica de segundo orden y cuya notación es la 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 la obra de Frege , quien publicó su trabajo varios años antes que Peirce, pero cuya obra permaneció menos conocida hasta que Bertrand Russell y Alfred North Whitehead la popularizaron. Frege utilizó diferentes variables para distinguir la cuantificación sobre objetos de la cuantificación sobre propiedades y conjuntos; pero no se consideraba a sí mismo practicando dos tipos de lógica distintos. Tras el descubrimiento de la paradoja de Russell, se comprendió que su sistema presentaba algún problema. Finalmente, los lógicos descubrieron que restringir la lógica de Frege de diversas maneras —a lo que ahora se denomina lógica de primer orden— eliminaba este problema: los conjuntos y las propiedades no pueden cuantificarse únicamente con la lógica de primer orden. La jerarquía estándar de órdenes de lógica data de esta época.

Se descubrió 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 cierta completitud , pero nada tan grave como la paradoja de Russell), y así se hizo (véase la teoría de conjuntos de Zermelo-Fraenkel ), ya que los conjuntos son fundamentales para las matemáticas . La aritmética , la mereología y diversas teorías lógicas poderosas podían formularse axiomáticamente sin recurrir a ningún aparato lógico más allá de 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 un declive general en el trabajo sobre lógica de segundo orden (o de orden superior).

Este rechazo fue defendido activamente por algunos lógicos, en particular por WV Quine . Quine sostenía que en oraciones del lenguaje predicativo como Fx, la “ x ” debe considerarse una variable o nombre que denota un objeto y, por lo tanto, puede cuantificarse, como en “Para todas las cosas, es cierto que …”, pero la “ F ” debe considerarse 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 podamos cuantificar algo así. (Esta postura es bastante coherente con los argumentos de Frege sobre la distinción entre concepto y objeto ). Así pues, usar un predicado como variable implica 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 ha experimentado una cierta recuperación, impulsada por la interpretación de Boolos 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 señala además la supuesta no ordenabilidad de oraciones como «Algunos críticos se admiran solo entre sí» y «Algunos de los hombres de Fianchetto entraron en el almacén sin la compañía de nadie más», las cuales, según él, solo pueden expresarse mediante la cuantificación de segundo orden en su totalidad. Sin embargo, la cuantificación generalizada y la cuantificación parcialmente ordenada (o ramificada) también pueden ser suficientes para expresar cierta clase de oraciones supuestamente no ordenables, y estas no recurren a la cuantificación de segundo orden.

El poder expresivo de diversas 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 puede representarse mediante una estructura finita con dominio D = {1,..., n }, predicados unarios P _​​a para cada a ∈ A , satisfechos por aquellos índices i tales que w _i = a , y predicados adicionales que sirven para identificar unívocamente qué índice es cuál (típicamente, se toma el grafo de la función sucesora en D o la relación de orden <, posiblemente con otros predicados aritméticos). A la inversa, las tablas de Cayley de cualquier estructura finita (sobre una signatura 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 lenguajes regulares ) es el conjunto de lenguajes definibles por fórmulas monádicas de segundo orden ( teorema de Büchi-Elgot-Trakhtenbrot , 1960).
• NP es el conjunto de lenguajes definibles por fórmulas existenciales de segundo orden ( teorema de Fagin , 1974).
• co-NP es el conjunto de lenguajes definibles mediante fórmulas universales de segundo orden.
• PH es el conjunto de lenguajes definibles mediante fórmulas de segundo orden.
• PSPACE es el conjunto de lenguajes definibles mediante fórmulas de segundo orden con un operador de cierre transitivo añadido.
• EXPTIME es el conjunto de lenguajes definibles mediante fórmulas de segundo orden con un operador de punto fijo mínimo añadido .

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

• Lógica de primer orden
• Lógica de orden superior
• Número de Löwenheim
• Lenguaje Omega
• Lógica proposicional de segundo orden
• lógica monádica de segundo orden

• Andrews, Peter (2002). Introducción a la lógica matemática y la teoría de tipos: Hacia la verdad a través de la demostración (2.ª  ed.). Kluwer Academic Publishers.
• Boolos, George (1984). "Ser es ser un valor de una variable (o ser algunos valores de algunas variables)". Journal of Philosophy . 81 (8): 430– 50. doi : 10.2307/2026308 . JSTOR 2026308 . Reimpreso en Boolos, Logic, Logic and Logic , 1998.
• Grädel, Erich; Kolaitis, Phokion G.; Libkin, Leonid ; Maarten, Marx; Spencer, Joel ; Vardi, Moshe Y .; Venema, Yde; Weinstein, Scott (2007). Teoría de modelos finitos y sus aplicaciones . Textos en Ciencias de la Computación Teórica. Una serie de EATCS. ​​Berlín: Springer-Verlag . ISBN 978-3-540-00428-8. Zbl 1133.03001 . 
• Putnam, Hilary (1982). "Peirce el lógico" . Historia Mathematica . 9 (3): 290– 301. doi : 10.1016/0315-0860(82)90123-9 .. Reimpreso en Putnam, Hilary (1990), Realismo con rostro humano , Harvard University Press , pp.  252 – 260 .
• Rossberg, M. (2004). "Lógica de primer orden, lógica de segundo orden y completitud" (PDF) . En V. Hendricks; et  al. (eds.). Lógica de primer orden revisitada . Berlín: Logos-Verlag.