Monadic signature with constant > Consider a signature $\Sigma = \\{ P^1, R^1, c\\}$. Where $P^1, R^1$ are unary predicates, and $c$ is a constant. > > Let A be a formula in FOL over $\Sigma$. Prove/Disprove: > > If A is satisfiable then A is satisfiable in a structure M s.t. $|D^M| <= 4$ This is a "non-pure" monadic signature, as it contains a constant. However, I remember that constants can be "treated" as unary predicates whose definition is a singleton. Therefore according to the small model property, if satisfiable, then A should be satisfiable in a structure M s.t. $|D^M|<=8$. So the above statement should be false. I was not able to find a formal way to disprove this, hopefully someone can help.

Hint: the statement is true. so try to prove it. To do this, consider $A' \equiv \exists z(A[z/c])$, i.e., $A'$ is what you get from $A$ if you replace all instances of $c$ in $A$ by the fresh variable $z$ and existentially quantify the result over $z$. $A'$ is a sentence over the purely monadic signature $(P^1, R^1)$ and hence is satisfiable iff it is satisfiable in a model with at most 4 elements. Any model $M$ of $A'$ can be expanded to a model of $A$ by interpreting $c$ as the witness for $z$ that makes $A'$ hold in $M$. (Expanding a model, i.e., adding interpretations for new symbols within its universe, does not make its universe bigger.)