En lógica formal , la no ordenabilidad es la incapacidad de un enunciado en lenguaje natural de ser capturado adecuadamente por una fórmula de lógica de primer orden . Específicamente, un enunciado es no ordenable si no existe una fórmula de lógica de primer orden que sea verdadera en un modelo si y solo si el enunciado se cumple en ese modelo. Los enunciados no ordenables a veces se presentan como evidencia de que la lógica de primer orden no es adecuada para capturar los matices del significado en lenguaje natural.
El término fue acuñado por George Boolos en su artículo "Ser es ser un valor de una variable (o ser algunos valores de algunas variables)". [1] Quine argumentó que tales oraciones requieren una simbolización de segundo orden , que puede interpretarse como una cuantificación plural sobre el mismo dominio que utilizan los cuantificadores de primer orden, sin postulación de "objetos de segundo orden" distintos ( propiedades , conjuntos, etc.).
Un ejemplo estándar es la oración de Geach - Kaplan : "Algunos críticos sólo se admiran entre sí". Si se entiende que Axy significa " x admira a y ", y el universo del discurso es el conjunto de todos los críticos, entonces una traducción razonable de la oración a la lógica de segundo orden es: En palabras, esto establece que existe una colección de críticos con las siguientes propiedades: La colección forma una subclase propia de todos los críticos; está habitada (y por lo tanto no está vacía) por un miembro que admira a un crítico que también es miembro; y es tal que si alguno de sus miembros admira a alguien, entonces este último es necesariamente también un miembro.
Que esta fórmula no tiene equivalente de primer orden se puede comprobar convirtiéndola en una fórmula en el lenguaje de la aritmética. Para ello, sustituimos la fórmula por Axy . Esto expresa que los dos términos son sucesores uno del otro, de alguna manera. La proposición resultante, afirma que existe un conjunto X con las tres propiedades siguientes:
Recordemos que un modelo de una teoría formal de la aritmética, como la aritmética de Peano de primer orden , se denomina estándar si solo contiene los números naturales familiares como elementos (es decir, 0, 1, 2, ... ). En caso contrario, el modelo se denomina no estándar . La fórmula anterior es verdadera solo en modelos no estándar: en el modelo estándar, X sería un subconjunto propio de todos los números que también tendría que contener todos los números disponibles ( 0, 1, 2, ... ), por lo que falla. Y, por otro lado, en cada modelo no estándar hay un subconjunto X que satisface la fórmula.
Supongamos ahora que existe una representación de primer orden de la fórmula anterior llamada E . Si se añadiera a los axiomas de Peano, significaría que no existen modelos no estándar de los axiomas ampliados. Sin embargo, el argumento habitual sobre la existencia de modelos no estándar seguiría siendo válido, lo que demostraría que, después de todo, existen modelos no estándar. Esto es una contradicción, por lo que podemos concluir que no existe tal fórmula E en la lógica de primer orden.
No existe una fórmula A en lógica de primer orden con igualdad que sea válida para todos y solo para los modelos con dominios finitos. En otras palabras, no existe una fórmula de primer orden que pueda expresar "solo hay un número finito de cosas".
Esto está implícito en el teorema de compacidad de la siguiente manera. [2] Supongamos que hay una fórmula A que es verdadera en todos y solo los modelos con dominios finitos. Podemos expresar, para cualquier entero positivo n , la oración "hay al menos n elementos en el dominio". Para un n dado , llamemos a la fórmula que expresa que hay al menos n elementos B n . Por ejemplo, la fórmula B 3 es: que expresa que hay al menos tres elementos distintos en el dominio. Consideremos el conjunto infinito de fórmulas Cada subconjunto finito de estas fórmulas tiene un modelo: dado un subconjunto, encuentre el n mayor para el cual la fórmula B n esté en el subconjunto. Entonces, un modelo con un dominio que contenga n elementos satisfará A (porque el dominio es finito) y todas las fórmulas B en el subconjunto. Aplicando el teorema de compacidad, todo el conjunto infinito también debe tener un modelo. Debido a lo que asumimos sobre A , el modelo debe ser finito. Sin embargo, este modelo no puede ser finito, porque si el modelo tiene sólo m elementos, no satisface la fórmula B m+1 . Esta contradicción muestra que no puede haber una fórmula A con la propiedad que supusimos.
