MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Is the question whether a FO formula F has a model of size k (k is a finite number) decidable?

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

-
 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 at 11:32 Thanks so much :). – TL Nov 19 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 at 15:32