0
$\begingroup$

For a theory $\Sigma$, if it has a finite model $M$ of order $\kappa$ which is $\kappa$-categorical, then $\Sigma$ is complete.

It was mentioned in a class, but I wasn't able to find a proof, neither here nor in Enderton.
Would be thankful for a reference or some guidance.

Edit: This has turned out to be a false claim, the correct claim is for $\kappa$-categorical with an infinite $\kappa$, with no finite models. See the answer by @Noah Schweber.

$\endgroup$
  • $\begingroup$ Shouldn't it be "infinite" ? $\endgroup$ – Max Jul 7 '18 at 16:17
  • 7
    $\begingroup$ This seems very garbled, and isn't true as written. I suspect that the actual claim is: "If $\Sigma$ is a theory with no finite models which is $\kappa$-categorical for some infinite $\kappa$, then $\Sigma$ is complete" (which is true). $\endgroup$ – Noah Schweber Jul 7 '18 at 16:22
  • 3
    $\begingroup$ What does it mean for a model to be $\kappa$-categorical? $\endgroup$ – bof Jul 7 '18 at 16:34
  • 2
    $\begingroup$ What does it mean for a theorem to have a model? $\endgroup$ – Andrés E. Caicedo Jul 7 '18 at 17:49
  • 1
    $\begingroup$ @Berci I know what it means for a theory to be $\kappa$-categorical. I'm wondering what the OP means by saying that the finite model $M$ is $\kappa$-categorical. $\endgroup$ – bof Jul 7 '18 at 22:03
2
$\begingroup$

As written this is not true. E.g. consider the theory $T$ of groups, and let $\kappa=7$; there is a unique group up to isomorphism of order $7$, but $T$ is certainly not complete.

What is true is the following (until the second part of this answer, $\kappa$ is finite; the statement below is true for infinite $\kappa$ too, but vacuous in that case since by the compactness theorem no theory will satisfy the hypothesis if $\kappa$ is infinite):

Suppose $T$ is a theory with exactly one model of cardinality $\kappa$ (up to isomorphism), and no models of cardinality $\not=\kappa$. Then $T$ is complete.

The proof of this is straightforward. Suppose there were some sentence $\varphi$ such that $T\not\vdash\varphi$ and $T\not\vdash\neg\varphi$. Then both $S_1=T\cup\{\varphi\}$ and $S_2=T\cup\{\neg\varphi\}$ are consistent. By the completeness theorem, there are models $\mathcal{M}_1$ of $S_1$ and $\mathcal{M}_2$ of $S_2$. But then:

  • We can't have $\mathcal{M}_1\cong\mathcal{M}_2$, since they disagree about $\varphi$.

  • We have $\mathcal{M}_1,\mathcal{M}_2\models T$, since $S_1, S_2\supseteq T$.

  • But then $\mathcal{M}_1$ and $\mathcal{M}_2$ are nonisomorphic models of $T$ of cardinality $\kappa$ (since $T$ has no models of cardinality $\not=\kappa$), contradicting the $\kappa$-categoricity of $T$.


Incidentally, a similar argument shows:

Let $\lambda$ be an infinite cardinal. Suppose $T$ is a theory with no finite models and exactly one model up to isomorphism of cardinality $\lambda$ (that is, $T$ is $\lambda$-categorical). Then $T$ is complete.

This is actually a bit trickier, since we don't have the assumption that every model of $T$ has cardinality $\lambda$, merely that $T$ has no finite models. We have to use the Lowenheim-Skolem theorem (together with the fact that $T$ has no finite models) to show that if there are two non-elementarily-equivalent models of $T$, then there are two non-elementarily-equivalent models of $T$ of cardinality $\lambda$, and since non-elementary-equivalence implies non-isomorphism this would contradict the $\lambda$-categoricity of $T$.

$\endgroup$
  • $\begingroup$ I assume the first part of your answer is only relevant for a finite $\kappa$ (though of course as written the theorem stays true for infinite $\kappa$) $\endgroup$ – Max Jul 15 '18 at 20:07
  • $\begingroup$ @Max Yes, it's only relevant for finite $\kappa$ but true as written for all $\kappa$. Incidentally, it's vacuous for infinite $\kappa$: by the compactness theorem, any theory with an infinite model has models of unboundedly large infinite cardinalities - so the hypothesis can't be satisfied. (And this is further refined by the Lowenheim-Skolem theorems, which together show that if a theory $T$ has an infinite model of cardinality at least that of $T$, then it has models in every infinite cardinality $\ge\vert T\vert$.) $\endgroup$ – Noah Schweber Jul 15 '18 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.