Autor Tema: ¿Cómo probar que la clase de estructuras bien ordenadas no es caracterizable?

0 Usuarios y 1 Visitante están viendo este tema.

27 Noviembre, 2012, 11:23 am
Leído 2889 veces

matllibo

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 4
  • Karma: +0/-0
  • Sexo: Masculino
Quiero probar que la clase K de estructuras bien ordenadas no es caracterizable en primer orden, es decir, no es una clase elemental, o también, no existe un conjunto de enunciados finito "T" tal que Mod(T) = K, ¿cómo se hace?

Gracias por su ayuda!


27 Noviembre, 2012, 12:46 pm
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Considera un lenguaje formal L y un conjunto de fórmulas F, finito o infinito, que sean verdaderas sobre todo conjunto bien ordenado. En principio el lenguaje L constaría únicamente de un relator binario \( \leq \) que representara la relación de orden, pero no hay problema en añadir más signos, si quieres, como una constante para el mínimo elemento, o un signo de función que represente el sucesor de un elemento si existe, etc. En cualquier caso, el relator \( \leq \) tiene que estar, y doy por hecho que el lenguaje posee un igualador, por lo que podemos considerar igualmente un relator \( < \) (añadiéndolo con una definición, si es preciso).

Ahora añade a L un conjunto infinito de constantes \( \{c_n\} \) y añade a F los infinitos axiomas \( c_{i+1}<c_i \) para todo \( i \). Llama F' al conjunto ampliado de axiomas. Entonces, todo subconjunto finito de axiomas de F' tiene un modelo, a saber, el conjunto de los números naturales con el orden usual y en el que las constantes \( c_i \) que aparecen en el subconjunto finito elegido (que serán un número finito) se interpreten como números naturales \( n_i \) tales que \( i>j\rightarrow n_i<n_j \).

Por el teorema de compacidad, F' tiene un modelo (que será también un modelo de F), en el cual, los objetos denotados por las constantes \( c_i \) forman un subconjunto del universo que no tiene mínimo elemento, luego el modelo no es un conjunto bien ordenado.