3
$\begingroup$

Consider the language $\mathcal{L}$ of first-order logic equipped with a single binary relation symbol $R$. Let $\Gamma$ denote the theory expressing that $R$ is an equivalence relation such that there is exactly one equivalence class of size $n$ for each $n\in \mathbb{Z}_{>0}$.

Is it the case that $\Gamma$ is $\kappa$-categorical for every uncountable cardinal $\kappa$?

I've been unable to make progress in determining the answer. Any help would be appreciated!

$\endgroup$
3
$\begingroup$

This theory is complete, but not $\kappa$-categorical. The conditions don't say anything about the number of infinite equivalence classes, so you can construct two models, one with a single infinite equivalence class, the other with $\kappa$-many such classes. These are clearly not isomorphic, so the theory is not categorical.

In fact, for every infinite cardinal $\kappa$ and every model M of cardinality $\leq \kappa$ we can find an elementary extension $N_\kappa$ of $M$ with $\kappa$ infinite equivalence classes and with each infinite equivalence class having cardinality $\kappa$. This extension is unique up to isomorphism for each cardinal $\kappa$, so the theory is complete.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you. In your second paragraph, are you tacitly using a well-known theorem to conclude that the theory is complete, or does it follow from an elementary argument (which I'm not seeing)? $\endgroup$ – CuriousKid7 Feb 4 at 5:37
  • $\begingroup$ The latter. If you had a model in which $\varphi$ holds, and one in which $\neg \varphi$ holds, both of cardinality $\kappa$, then one of them would not admit $N_\kappa$ as an elementary extension. $\endgroup$ – Z. A. K. Feb 4 at 5:42
  • $\begingroup$ Got it. You've already answered my original question, but if you'd be willing to sketch how we construct $N_{\kappa}$, that would be great. $\endgroup$ – CuriousKid7 Feb 4 at 6:07
  • 1
    $\begingroup$ @Z.A.K. Just a small correction. It's not clear from the construction you give that the resulting model has the property that every equivalence class has cardinality $\kappa$. When you find a model by compactness, it might have new equivalence classes of size smaller than $\kappa$. But if you repeat your construction $\omega$-many times, building an elementary chain, you'll get what you want, since then each equivalence class had to be added at some point in the chain. $\endgroup$ – Alex Kruckman Feb 4 at 12:55
  • 1
    $\begingroup$ I mean that if $M$ is the union of an increasing chain of structures, for any equivalence class in $M$, if $m$ is a representative of that class, then $m$ is an element of some structure $M_i$ in the chain. Based on Z.A.K.'s construction, the equivalence class of $m$ is blown up to size $\kappa$ in $M_{i+1}$, so it has size $\kappa$ in $M$. $\endgroup$ – Alex Kruckman Feb 4 at 18:00

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.