Is there a finite set of sentences, $\Gamma$ which is satisfiable?

Question

Prove/ Disprove:

• There's a finite satisfiable set of sentences above $\Sigma$ a monadic-language, $\Gamma$ such that $\Gamma $ is satisfiable only for structures with size larger than $5$.
• There's a finite satisfiable set of sentences above $\Sigma$ a monadic-language, $\Gamma$ such that $\Gamma $ is satisfiable only for structures with size less than $5$.

• First I'm not sure but I think the size of a structure is the cardinality of the domain (a.k.a Universe) - $|D^M|$.
• Since it's a monadic logic I don't think we can use/ express the equality relation. Otherwise, the task was trivial.
• We also learned in class that for a monadic sentence with $k$ predicates there's a structure with the size $2^k$ which the sentence holds.

So I'm trying to connect the dots but couldn't yield something useful.
I'd be glad for help

Thanks

Answer 1

If you have some domain on which a set of formalae $\Gamma$ is valid, then you double the domain always, by just cloning the structure again. So I don't think there can be a finite upper bound.

And to get at least 5, posit the existence of 5 elements that all satisfy some unique, but mutually incompatible, combination of predicates $P_1(x), P_2(x), P_3(x)$.

Answer 2

Let the signature $\Sigma$ comprise just the monadic predicate symbols $A_1(x), \ldots A_k(x)$. If $T$ is any theory over $\Sigma$, $\mathbf{M}$ is a model of $T$ and $c \in M$, define a new model $\mathbf{M'}$ with $M' = M \cup \{d\}$ where $d \not\in M$ and with $A_i(d)$ defined to be equivalent to $A_i(c)$. Now prove that if $\phi$ is a sentence over $\Sigma$, then $\mathbf{M} \models \phi$ iff $\mathbf{M'} \models \phi$. (You prove this by an induction over formulas and you need to be careful about how you set up the induction. Please comment if you need more help with this.) So if a theory over $\Sigma$ has a model of size $n$, then it also has a model of size $n + 1$ and the first statement is false.

For the second statement, consider:

$$ \begin{array}{lcr} \phi \equiv \exists x_1, x_2, x_3, x_4, x_5&\cdot & \lnot A_1(x_1) \land \lnot A_2(x_1) \land A_3(x_1)\\ &\land& \lnot A_1(x_2) \land A_2(x_2) \land \lnot A_3(x_2) \\ &\land& \lnot A_1(x_3) \land A_2(x_3) \land A_3(x_3) \\ &\land& A_1(x_4) \land \lnot A_2(x_4) \land \lnot A_3(x_4) \\ &\land& A_1(x_5) \land \lnot A_2(x_5) \land A_3(x_5) \\ \end{array} $$

$\phi$ has models, but in any model of $\phi$ the witnesses to the $x_i$ must all be different so every model has at least $5$ elements. So the second statement is true.