# Logic - “Small model property” for a signature with only binary predicates

The "Small Model Property" lemma says that if a monadic formula $\phi$ (i.e. over a monadic signature - contains only constants and (monadic) unary predicates) with $k$ unary predicates is satisfiable, then it is satisfiable in a structure with at most $2^k$ elements.

Also - the satisfiability problem for monadic signature is decided (follows from the lemma above).

So, is it true that if a signature contains only constans and binary predicates, then any satisfiable formula $\phi$ over this signature with $k$ binary predicates is satisfiable in a structure with at most $4^k$ elements? - It came to my mind because the $2^k$ "comes from" going all over the possible definitions of the predicate - it is unary so only $2$ options available. In the other case - there are $4$ options so it may be also true (and therefore to any signature with $n$-nary predicates would correspond $n^k$).

Thanks

• But the satisfiability problem for dyadic logic is unsolvable... – Mauro ALLEGRANZA Jun 22 '15 at 10:13
• I disagree with the votes to close - I think this is a very reasonable question for someone to ask who's seeing model theory for the first time. It's not immediately obvious just how much complexity suddenly shows up as soon as you have binary relations! – Noah Schweber Sep 8 '15 at 11:59

It is relatively easy to construct a language that has no constants and only one binary predicate $<$ and a single formula in that language that captures what you know about $<$ on $\mathbb{N}$, namely that it is a total strict ordering with no largest. You should try this yourself. You can then show that any model must be infinite.