Firma monádica con constante

Question

Considere una firma $\Sigma = \{ P^1, R^1, c\}$ . Donde $P^1, R^1$ son predicados unarios, y $c$ es una constante.

Sea A una fórmula en FOL sobre $\Sigma$ . Demostrar/Desmentir:

Si A es satisfactorio, entonces A es satisfactorio en una estructura M s.t. $|D^M| <= 4$

Esta es una firma monádica "no pura", ya que contiene una constante. Sin embargo, recuerdo que las constantes pueden ser "tratadas" como predicados unarios cuya definición es un singleton. Por lo tanto, de acuerdo con la propiedad del modelo pequeño, si es satisfacible, entonces A debería ser satisfacible en una estructura M s.t. $|D^M|<=8$ . Por lo tanto, la afirmación anterior debe ser falsa.

No he podido encontrar una manera formal de refutar esto, espero que alguien pueda ayudar.

Answer 1

Pista: la afirmación es cierta, así que intenta demostrarla. Para ello, considere $A' \equiv \exists z(A[z/c])$ es decir, $A'$ es lo que se obtiene de $A$ si sustituye todas las instancias de $c$ en $A$ por la variable fresca $z$ y cuantificar existencialmente el resultado sobre $z$ . $A'$ es una sentencia sobre la firma puramente monádica $(P^1, R^1)$ y, por tanto, es satisfacible si lo es en un modelo con un máximo de 4 elementos. Cualquier modelo $M$ de $A'$ puede ampliarse a un modelo de $A$ interpretando $c$ como testigo de $z$ que hace que $A'$ mantener en $M$ . (Ampliar un modelo, es decir, añadir interpretaciones para nuevos símbolos dentro de su universo, no hace que su universo sea mayor).