MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Hi all,

can someone please tell me whether the question whether a FO formula F has a model of size k (where k is a finite number) is decidable?

Thanks in advance! TL

share|cite|improve this question
Sure. Just check all the possible interpretations for all the formula's function and relation symbols over the domain $\{1,2,\dots,k\}$. – Andreas Blass Nov 19 '12 at 11:32
Thanks so much :). – user29224 Nov 19 '12 at 11:37
Note that in Andreas's answer (and the question, too), $k$ can be replaced by $k$ or fewer elements without changing the character of decidability. Gerhard "Ask Me About System Design" Paseman, 2012.11.19 – Gerhard Paseman Nov 19 '12 at 15:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.