Finitely many countable models implies decidability

213 Views Asked by At

Suppose $T$ is decidably axiomatizable first order theory and has no finite model. We shall focus on countable models. If $T$ has just one countable model (up to isomorphism), which means $T$ is $\aleph_0$-categorical, which implies it's complete so it's decidable. Now suppose $\mathrm{Mod}_{\aleph_0}(T)$ is finite up to isomorphism, this weaker condition also implies decidability.

Proceed by induction on number of countable models $m$. If $m=1$, it's proved. Suppose $T$ is incomplete, then there is some sentence $\varphi$ such that $T\cup\varphi$ and $T\cup\lnot\varphi$ are both consistent, they must have strictly fewer countable models, so by induction hypothesis, they're decidable, but how does this fact imply the decidability of $T$?

1

There are 1 best solutions below

0
On BEST ANSWER

If $T\cup\{\phi\} \vdash \psi$ and $T\cup\{\neg\phi\}\vdash \psi$ then $T\vdash \psi$, and if either $T\cup\{\phi\}\not\vdash\psi$ or $T\cup\{\neg\phi\}\not\vdash\psi$, then $T\not\vdash\psi$.