# Is first-order logic complete with respect to countable structures?

Question. Let $\Gamma$ denote a first-order signature, and consider a sentence $\tau$ and a set of sentences $\Sigma$ in the language generated by $\Gamma$. If every countable $\Gamma$-structure that satisfies $\Sigma$ also satisfies $\tau$, do we necessarily have that $\Sigma$ proves $\tau$?

In other words, is first-order logic complete with respect to countable structures?

• The signature must be countable, of course. – Zhen Lin Jun 3 '14 at 13:26

Almost.

First note that if $M$ is an infinite model of $\Sigma$ then there is some $M'$ which is countable and elementary equivalent to $M$. So if $\tau$ is true for all countable models of $\Sigma$ it is true for all infinite models of $\Sigma$.

But if $\Sigma$ has finite models not satisfying $\tau$, then of course it cannot prove $\tau$.

(Interestingly, if $\tau$ is true in every infinite model of $\Sigma$ then there is some $k$ such that every finite model of size $\geq k$ must satisfy $\tau$.)

That been said, if you consider finite as countable in this context, then the above answer immediately changes to "Yes" for the same reasons. Every model is finite, or elementarily equivalent to a countably infinite model.

• Nice, thanks. For the record, I use "countable" to mean $|X| \leq \aleph_0$ and "countably infinite" to mean $|X|= \aleph_0$. – goblin Jun 3 '14 at 12:22
• Since often we don't care about finite models, it's sometimes more fruitful to separate finite models from countably infinite models. – Asaf Karagila Jun 3 '14 at 12:24
• The "finite" issue is intertwined with equality, of course. If you allow structures to interpret equality as an arbitrary equivalence relation, then there is no need for finite structures, and the answer becomes "yes". – Carl Mummert Jun 3 '14 at 13:45
• Just to elaborate on the comment by Zhen Lin: This proof only works because of Downward Lowenheim Skolem (assuming there are no finite models). If you have a language of cardinality greater than $\aleph_{0}$, this statement is false. To see this, let $L=\{c_{i}:i\in{\aleph_{1}}\}$ and let $\Sigma=\{c_{i}\neq{c_{j}}:i\neq{j}\}$. Since there are no countable models, you can say for all countable models M of $\Sigma$, $M\models{c_{i}=c_{j}}$ for all $i,j$. But clearly $\Sigma$ does not prove this. – UserB1234 Jun 3 '14 at 19:42
• Thanks @Danul, that's a fine point that somehow slipped under the radar here. – Asaf Karagila Jun 3 '14 at 21:07