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 típico 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:
Que esta fórmula no tiene equivalente de primer orden se puede ver al convertirla en una fórmula en el lenguaje de la aritmética. Sustituyamos la fórmula por Axy . El resultado indica que existe un conjunto X con estas propiedades:
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 0, 1, 2, ... como elementos. En caso contrario, el modelo se denomina no estándar . Por lo tanto, la fórmula dada anteriormente es verdadera solo en modelos no estándar, porque, en el modelo estándar, el conjunto X debe contener todos los números disponibles 0, 1, 2, ... . Además, existe un conjunto X que satisface la fórmula en cada modelo no estándar.
Supongamos 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.
