0
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ But the satisfiability problem for dyadic logic is unsolvable... $\endgroup$ – Mauro ALLEGRANZA Jun 22 '15 at 10:13
  • $\begingroup$ 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! $\endgroup$ – Noah Schweber Sep 8 '15 at 11:59
0
$\begingroup$

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.

Similarly there is a formula in a language with just one unary function that can only be satisfied by infinite models. Again, we can find such a formula by looking at the properties of the successor function on the naturals.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.