Fix some countable language $\Sigma$, and some reasonable way of interpreting reals as $\Sigma$-structures with domain $\omega$. Let $T$ be a complete $\Sigma$-theory with continuum-many isomorphism types of countable models (EDIT) which is not a counterexample to Vaught's conjecture. Then of course there is a perfect set $P$ of reals, whose elements code pairwise nonisomorphic models of $T$.

However, it occurred to me recently that I see no reason why we should be able to get all the models of $T$ so represented. Specifically:

Need there be a perfect set $P$ of reals, such that every countable model of $T$ has exactly one real in $P$ which codes a copy of it?

I assume the answer is no - I imagine that models of sufficiently low Scott rank might be hard to incorporate into any such $P$ - but I don't see how to prove this.

If the answer is indeed no, what are the $T$s for which the answer is yes?

  • $\begingroup$ Do you expect all the models to be rigid (have trivial automorphism group)? Unless you have an infinite language, I would expect several reals to encode different but otherwise isomorphic models. Gerhard "Maybe Permutation Structures Help Here?" Paseman, 2017.03.25. $\endgroup$ Commented Mar 26, 2017 at 5:18
  • $\begingroup$ @GerhardPaseman No, of course in general they won't be rigid and each model will be (in all probability) represented continuum-many times. So? $\endgroup$ Commented Mar 26, 2017 at 5:28
  • $\begingroup$ I guess I am confused. Did you want P to be a set that captures one of every model, or one of every isomorphism type? I am seeing ambiguity in the post. Also, there is an exercise in Chapter I of Algebras Lattices and Varieties which suggests (but does not assert) to me a yes answer. Gerhard "Burris And Kwatinetz, I Think" Paseman, 2017.03.25. $\endgroup$ Commented Mar 26, 2017 at 5:36
  • $\begingroup$ @GerhardPaseman One of every isomorphism type. Sorry, by "copy" I meant "isomorphic copy of", so "representative of isomorphism type of." (What's the exercise?) $\endgroup$ Commented Mar 26, 2017 at 5:38
  • $\begingroup$ Let A be a countable (infinite or finite) universal algebra of countable (i. or f.) type. Show each of four associated structures is either at most countably infinite or else has size precisely that of the continuum: automorphism group, sub algebra lattice, endomorphism monoid, and congruence lattice of A. It's on page 35 of my copy, but I don't know if there is an online copy. Gerhard "Copy Not Meaning Isomorphism Type" Paseman, 2017.03.25. $\endgroup$ Commented Mar 26, 2017 at 5:47

1 Answer 1


The property you are asking for is a very strong condition on $T$. Let met try to rephrase the question more carefully:

The set of countable $\Sigma$-structures with universe $\omega$ is naturally a Polish space $\mbox{Mod}(\Sigma)$ which has no isolated points (if it has isolated points, then necessarily $\Sigma$ would consist of a finite set of constant symbols, contradicting the existence of $T$ with continuum many countable models). I assume that the ``reasonable way of coding reals as $\Sigma$-structures" is some Borel bijection $f: \mathbb{R} \to \mbox{Mod}(\Sigma)$; for your question, choosing such a Borel bijection is the same thing as fixing a new completely metrizable topology on $\mbox{Mod}(\Sigma)$ (which induces the same Borel structure on $\mbox{Mod}(\Sigma)$ as the original topology).

Now $\mbox{Mod}(T)$ is a Borel subset of $\mbox{Mod}(\Sigma)$; we are supposing that $\mbox{Mod}(T)/\cong$ has size continuum. It doesn't automatically follow, that there is a perfect subset $P$ of $\mbox{Mod}(T)$ of pairwise nonisomorphic models (if $2^{\aleph_0} = \aleph_1$, then this is Vaught's conjecture).

In any case, we are asking for a perfect set $P$ of $\mbox{Mod}(T)$ of pairwise nonisomorphic models, such that every element of $\mbox{Mod}(T)$ is isomorphic to exactly one element of $P$. In the terminology of invariant descriptive set theory, this is asking for a perfect transversal of $(\mbox{Mod}(T), \cong)$. In general, even the existence of a Borel transversal of $(\mbox{Mod}(T), \cong)$ is quite strong:

Note that first of all, if $(\mbox{Mod}(T), \cong)$ has a Borel transversal $S$ then $\cong$ is Borel, since $M \not \cong N$ iff $\exists M', N' \in S$ with $M \cong M', N \cong N'$ and $M' \not= N'$. Hence by Theorem 6.4.4 from Su Gao's textbook on Invariant Descriptive Set Theory, if $(\mbox{Mod}(T), \cong)$ has a Borel transversal, then $(\mbox{Mod}(T), \cong)$ is smooth, that is $(\mbox{Mod}(T), \cong) \leq_B (\mathbb{R}, =)$.

In terms of Borel complexity theory this is saying, that if $(\mbox{Mod}(T), \cong)$ has a Borel transversal, then it is at the bottom of the complexity hierarchy. For instance, any non-small theory is not smooth.

  • $\begingroup$ Whoops, I forgot to include the condition that $T$ isn't a counterexample to VC! Otherwise of course you're right. The rest of your answer polishes off my question - thanks! (Also, by "reals" I was being sloppy - I was thinking of $\omega^\omega$ - but that doesn't make a difference.) $\endgroup$ Commented Mar 26, 2017 at 18:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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