El teorema de completitud de Godel puede enunciarse como "Toda teoría de primer orden consistente con un lenguaje bien ordenable tiene un modelo". (de Wikipedia)
¿Cuál sería un ejemplo de un lenguaje que no es bien ordenable?
Respuesta
¿Demasiados anuncios?
Thilo-Alexander Ginkel
Puntos
2984
Si se asume la elección, entonces cada El lenguaje puede estar bien ordenado por el teorema del buen orden.
Incluso sin elección, cualquier lenguaje finito (es decir, un conjunto de cadenas finitas) puede estar bien ordenado, siempre que podamos ordenar bien su alfabeto.
Si tenemos un alfabeto arbitrario bien ordenado $\Sigma$ entonces podemos ordenar bien $\Sigma^*$ (el conjunto de todas las cadenas finitas sobre $\Sigma$ ) de la siguiente manera: Primero se ordenan todas las cadenas del lenguaje por longitud creciente; luego se ordenan las cadenas de la misma longitud (inversa) lexicográficamente, por el ordenamiento en $\Sigma$ . Dado que todos los lenguajes finitarios sobre $\Sigma$ son subconjuntos de $\Sigma^*$ También estos pueden estar bien ordenados de la misma manera.
Ciertamente, cualquier lenguaje contable puede estar bien ordenado, ya que por definición podemos poner tal lenguaje en biyección con los números naturales, que están bien ordenados.
Así que asumiendo el fracaso de la elección, un lenguaje finito no ordenable por el pozo necesitaría tener un alfabeto incontable y no ordenable por el pozo.
