= Finite model theory
<Finite model theory> studies <first-order structures> restricted to finite domains, and asks which properties can be expressed in specified <formal languages>. The restriction changes the available tools: ordinary first-order <compactness> does not hold when only finite models are admitted.
For example, the sentences saying there are at least $n$ distinct elements, one for every positive <integer> $n$, have a finite model for each finite subset but no common finite model. This is a direct failure of finite compactness. Logical games, locality, and bounded-variable fragments then compare the expressive power of formulas on finite databases and <graphs>, linking definability with <computational complexity theory>.
Back to article page
