Sentencias finitamente válidas y otras cosas relacionadas

Question

Casi termino la sección 2.6 de la obra de Enderton Una introducción matemática a la lógica pero sigo sin entender algunas cosas.

( Las tres primeras preguntas están estrechamente relacionadas, así que espero que no sea un problema que haga varias preguntas en un mismo tema. )

(1) Finamente válido

Al principio de la subsección Modelos finitos dice

Algunas frases sólo tienen infinitos modelos, por ejemplo, la frase que dice que $<$ es un ordenamiento sin elemento mayor. La negación de tal frase es finitamente válido es decir, es verdadera en toda estructura finita.

• una sentencia $\sigma$ es finitamente válido si $\sigma$ es verdadera en toda estructura finita

Si una sentencia $\sigma$ sólo tiene infinitos modelos (pero no necesariamente $\sigma$ es verdadera en todo modelo infinito, es decir, puede haber alguna estructura infinita tal que la estructura no sea modelo de $\sigma$ ), entonces la negación de $\sigma$ es finitamente válida. ¿Estoy en lo cierto? Además, ¿hay aquí alguna prueba? (¿cómo puedo estar seguro de que no hay infinitos modelos de $\sigma$ )

A la inversa, dejemos que $\sigma$ sea una sentencia finitamente válida. Es evidente que la negación de $\sigma$ no puede ser verdadera en ninguna estructura finita (pero necesariamente $\sigma$ es verdadera en toda estructura infinita). ¿Estoy en lo cierto?

(2) La clase de toda estructura infinita no es $EC$ ( segunda parte del Corrolario 26B )

• una clase de estructuras $K$ está en $EC$ si existe alguna setencia $\sigma$ tal que $\text{Mod }\sigma = K$

Aquí está la prueba dada por Enderton:

Si la clase de toda estructura infinita es $\text{Mod }\tau$ entonces la clase de todas las estructuras finitas es $\text{Mod }\neg\tau$ . Pero esta clase ni siquiera es $EC_\Delta$ mucho menos $EC$ .

Acepto que lo que escribió, pero creo que para terminar la prueba hay que demostrar que $\text{Mod }\tau \in EC$ pero no veo cómo se deduce de eso $\text{Mod }\neg\tau$ no está en $EC$ . Creo que falta algo, pero no soy capaz de terminar la prueba por mí mismo.

(3) Corolario 26E

Supongamos que el lenguaje es finito y que $\Phi$ sea el conjunto de setencias verdaderas en toda estructura finita. Entonces su complemento, $\overline \Phi$ es efectivamente enumerable.

Prueba. Para una frase $\sigma$ , $$\sigma \in \overline \Phi \Leftrightarrow (\neg\sigma) \text{ has a finite model.}$$ [...]

En otras palabras, $\Phi$ es un conjunto de sentencias finitamente válidas. Por lo tanto, su complemento, $\overline \Phi$ es el conjunto de frases $\sigma$ tal que $\sigma$ no es cierto en alguna estructura finita. No implica que $\sigma$ sólo tiene infinitos modelos ( $\sigma$ puede ser verdadera en alguna estructura finita, pero no en todas las estructuras finitas). Por lo tanto, no podemos utilizar los hechos de (1). ¿Cómo puedo obtener la equivalencia?

Answer 1

1. No puedo entender lo que está pidiendo y diciendo. Si una frase sólo es verdadera en modelos infinitos, entonces es falsa en todo modelo finito, por lo que su negación es verdadera en todo modelo finito. Eso es todo.
2. Para cualquier frase $\sigma$ lo que sea $\operatorname{Mod}(\sigma)\in EC$ ... esta es la definición de $EC.$ Así que en particular $\operatorname{Mod}(\lnot \tau)\in EC.$ De esto no se deduce que $\operatorname{Mod}(\lnot \tau)\notin EC$ ... que se desprende de la primera parte del teorema donde se demuestra que la clase de estructuras finitas no está en EC. Esto produce una contradicción que demuestra que un $\tau$ con las propiedades asumidas no puede existir.
3. Esto es un corolario de un teorema inmediatamente anterior que muestra que el conjunto de todas las oraciones que tienen un modelo finito es efectivamente enumerable (como ha dicho, $\bar\Phi$ es simplemente el conjunto de todas las oraciones cuyas negaciones tienen un modelo finito). Esto, a su vez, se deduce de un par de párrafos más arriba, donde se demuestra que para cualquier $n$ es decidible si una frase tiene un modelo de tamaño $n.$ (Todo esto suponiendo un lenguaje finito).