Fórmula del espectro de cuadrados perfectos.

Question

He estado trabajando con ejercicios de "A first Course in Logic" de S. Hedman. En el ejercicio 2.3 (d) se pide encontrar una oración de primer orden $\varphi$ teniendo el conjunto de cuadrados perfectos como un espectro finito. Pero no estoy seguro de si mi comprensión de los conceptos de modelo y espectro es correcta o no.

Mi solución es:

$\varphi = (\exists x)((x^2 = b) \wedge (\forall y)(y\leq b))$ es decir, hay $x$ tal que $x^2 = b$ y para todos $y$ , $y$ es menor o igual que una constante $b$ . Por lo tanto, cualquier conjunto de números enteros positivos, con el elemento máximo que es un cuadrado perfecto, modela esta frase. Por ejemplo, $\{1\}, \{1,2,3,4\}, \{1,\ldots, 9\}$ y así sucesivamente.

¿Podría alguien confirmar mi solución (estoy en el camino correcto)? ¿O me falta algo?

Answer 1

Puede hacerlo con la firma que tiene una relación unaria $A(x)$ y una función binaria $f(x,y)$ . La sentencia dirá, esencialmente, que $f$ es una biyección entre $A \times A$ y $M$ .

Es mucho más difícil hacer este tipo de cosas con la firma de la aritmética. Habría que incluir en $\phi$ varios axiomas sobre las operaciones de suma y multiplicación, la relación de orden y cómo se relacionan. En comparación, la sentencia obtenida en el párrafo anterior es relativamente sencilla.

Recuerda que, para los problemas del espectro, puedes elegir la firma que quieras. Elegir la firma adecuada puede simplificar mucho el problema.

Answer 2

Esquema: Utilizamos un lenguaje bastante rico basado en el cálculo de predicados con igualdad, Hay dos símbolos de predicado unario, $P$ , donde $P(x)$ debe pensarse como si dijera que $x$ es un punto, y $E$ , donde $E(x)$ debe pensarse como si dijera que $x$ es una arista (dirigida). Entonces hay un símbolo de predicado ternario $S$ , donde $S(x,y,z)$ debe interpretarse en el sentido de que $z$ es el borde que va desde $x$ a $y$ . Ahora describimos los axiomas en un lenguaje informal que no debería ser difícil, si se desea, convertir en lenguaje formal.

$1.$ Todo es un punto o una arista, y nada puede ser a la vez un punto y una arista.

$2.$ $S(x,y,z)$ implica que $x$ y $y$ son puntos y $z$ es un borde.

$3.$ Nunca podremos tener $S(x,x,z)$ .

$4.$ Para cualquier $z$ hay un único $x$ y $y$ tal que $S(x,y,z)$ .

$5.$ Para cualquier $x$ y $y$ con $x\ne y$ hay un único $z$ tal que $S(x,y,z)$ .

Dejemos que $\varphi$ sea la conjunción del conjunto de axiomas descritos anteriormente.

Ahora dejemos que $M$ sea un modelo finito de este conjunto de axiomas, y sea $q$ sea la cardinalidad del conjunto de elementos de (el conjunto subyacente de) $M$ que satisfacen (la interpretación de) el símbolo de predicado $P$ . Entonces el número de elementos de $M$ que satisfagan $E$ es $q(q-1)$ Así que $M$ tiene cardinalidad $q+q(q-1)=q^2$ . Y está claro que para todo entero positivo $q$ existe un modelo de cardinalidad $q^2$ .