11
$\begingroup$

If $T$ is a countable complete first-order theory with infinite models, the number of countable models it has, $I(T,\omega)$, must be an element of $N=\{1,3,4,5,6,7,\dots,\omega,\omega_1,2^\omega\}$ (although we don't know if $\omega_1$ can happen). For which pairs $n,m\in N$ does there exist a countable complete theory $T$ with $n$ countable models but $m$ countable models after adding finitely many constants to the theory? Countably many new constants? In particular can we have $m<n$? EDIT: By 'adding constants,' I mean adding constants whose type is completely specified, i.e. expanding by constants and then passing to a complete theory in the expanded language.

Let $n\rightarrow m$ denote the statement "There exists a complete countable theory $T$ and a finite tuple of constants $\overline{a}$ such that $I(T,\omega)=n$ and $I(T_\overline{a},\omega)=m$." And let $n\rightarrow_\omega m$ denote the statement "There exists a complete countable theory $T$ and a countable set of distinct constants $A$ such that $I(T,\omega)=n$ and $I(T_A,\omega)=m$." Some easy results and relevant observations:

  • If $n\rightarrow m$ (resp. $n\rightarrow_\omega m$) and $k \rightarrow \ell$ (resp. $k \rightarrow_\omega \ell$), then $nk \rightarrow m\ell$ (resp. $nk \rightarrow_\omega m\ell$). (Take the disjoint union of the relevant theories.)
  • $n \rightarrow n$ for every $n\in N-\{\omega_1\}$. (This is obvious for $n=1$. There are easy examples for $n=\omega,2^\omega$ and the standard examples for $n=3,4,5\dots$ all have constants which do not increase the number of countable models.)
  • $n^2+n\rightarrow (n+1)^2$ for any $1<n<\omega$. (DLO with $n-1$ colors and a countable set of constants of order type $\omega + \omega^\ast$. By itself this theory has $n^2 + 1$ countable models. Adding a constant in between $\omega$ and $\omega^\ast$ makes the theory have $(n+1)^2$ models.)
  • $1\not\rightarrow n$ and $n\not\rightarrow 1$ for any $n\in N - \{1\}$.
  • $1\rightarrow_\omega 2^\omega$ (For example: DLO.)
  • $1\rightarrow_\omega \omega$ (For example: A structureless set.)
  • $n\not\rightarrow_\omega 1$ for any $n\in N$.
  • $1 \rightarrow_\omega n$ for every $2<n<\omega$. (The standard examples of Ehrenfeucht theories are $\omega$-categorical theories with countably many constants added.)
  • If a theory is not small, then it will have $2^\omega$ countable models after adding any countable set of constants.
$\endgroup$
  • 1
    $\begingroup$ An observation: adding finitely many constants can raise the number of models only by at most $\omega$. In particular, $\omega\nrightarrow\omega_1\nrightarrow2^\omega$. $\endgroup$ – Emil Jeřábek supports Monica Jun 22 '18 at 9:46
  • $\begingroup$ That sounds very believable to me but I can't completely convince myself. Why is that true and what is an example of it happening? $\endgroup$ – James Hanson Jun 22 '18 at 19:07
  • 2
    $\begingroup$ This follows trivially from the fact that for any given countable model, there are only countably many ways how to expand it with the new constants. $\endgroup$ – Emil Jeřábek supports Monica Jun 22 '18 at 19:26
  • 1
    $\begingroup$ I don’t know, but I think it might be possible, if the models are sufficiently inhomogeneous. $\endgroup$ – Emil Jeřábek supports Monica Jun 22 '18 at 20:20
  • 3
    $\begingroup$ As @WillSawin points out in comments on my answer, it sounds like by "adding constants" you mean not just adding constant symbols to the language, but also adding assertions about them in the theory. Can you clarify exactly what you mean here — what assertions, if any, are you considering adding to the theory? $\endgroup$ – Peter LeFanu Lumsdaine Jun 23 '18 at 10:08
9
$\begingroup$

I believe that the number of models can indeed decrease. The following seems to be an example of $5 \to 3$:

Start with $T$ the model companion of the theory of "valued trees": the language has two sorts $M$ and $\Gamma$, $\Gamma$ is equipped with a linear order $\leq_{\Gamma}$ and is a model of DLO. The sort $M$ has a tree structure, say in the language $\{\leq ,\wedge \}$, so $\leq $ is a partial order such that the set of predecessors of any point is a chain and $\wedge$ maps two points to their infimum. There is also a valuation map $v:M \to \Gamma$ which is increasing and such that for any $a\in M$, the restriction of $v$ to $\{x\in M:x<a\}$ is an injection onto $\{\gamma\in \Gamma:\gamma<v(a)\}$. This theory is $\aleph_0$-categorical.

Add a countable set of constants $\{c_0,c_1,\ldots,\}$ interpreted such that $c_0<c_1<\cdots$. Call $T_1$ the resulting theory. Then $T_1$ has 5 countable models:

  • the prime model where the $c_i$'s are cofinal;
  • two models with no element above all the $c_i$'s (one with a minimal valuation larger that all $v(c_i)$ and one without);
  • two models with an element above all the $c_i$'s (same as the previous case).

If we now add another constant which is above all the $c_i$'s, then we have only 3 models (one where the constant is minimal above the $c_i$'s, one where it isn't, but there is such a minimal point, one where there is no such minimal point).

Edit: Example of $2^{\omega}\to_{\omega} 3$:

We modify a little bit the example above. Take the constants $c_i$ to name a subtree that has exactly $\aleph_0$ branches, all going all the way up in the tree. This has $2^{\aleph_0}$ many countable models, since we can independently add or not elements at the top of each branch. Now add $\aleph_0$ constants, one above each branch of the named tree and impose that they have the same valuation. If I am not mistaken, this has now only 3 countable models similarly as above.

$\endgroup$
  • $\begingroup$ Ah very nice. I probably should have said this in the question, but even though I am interested in the question in general, I am particularly interested in the case $2^\omega \rightarrow \leq \omega$ or $2^\omega \rightarrow_\omega \leq \omega$, do you have any opinion about those possibilities? $\endgroup$ – James Hanson Jun 24 '18 at 1:55
  • $\begingroup$ Also wait a second, if you have no element above all the $c_i$'s but a minimal valuation larger than all of them, doesn't that give you a maximal chain which is not in bijection with $\Gamma$? $\endgroup$ – James Hanson Jun 24 '18 at 2:15
  • $\begingroup$ Yes, you are right. I was sloppy in describing the structure. It is just the Fraisse limit of finite trees with a valuation map. I edited it, hopefully it's correct now. $\endgroup$ – Pierre Simon Jun 24 '18 at 3:17
  • $\begingroup$ It seems unlikely to me that $2^{\omega}\to_{(\omega)} \leq \omega$ is possible, but I do not see an argument. $\endgroup$ – Pierre Simon Jun 24 '18 at 3:58
  • 2
    $\begingroup$ In your modified example, couldn't each of the countably many branches either have a sup to their valuations or not, independently, regardless of the new bounds? This would seem still to give continuum many models. $\endgroup$ – Joel David Hamkins Jun 25 '18 at 1:04
3
$\begingroup$

See the paper Nonnessential extensions of complete theories(B. Omarov)

Translated from Algebra i Logika, Vol. 22, No. 5, pp. 542-550, September-October, 1983] Original article submitted June ii, 1982.

By adding constants (that may realize new types) Omarov write `A. D. Taimanov posed the following questions: "Is it possible to lower the number of countable models from continuum to countable , and from continuum to the finite number k ?" These questions are also answered affirmatively.

$\endgroup$
1
$\begingroup$

Edit: Emil Jeřábek confiems that this doesn’t answer the question; the OP is using “adding constants” to mean something different from what I would understand by it. However, I’m leaving this here for others who understand the question the same way I did.

The number of countable models cannot decrease.

Let $T$ be any theory, $T^+$ any expansion of $T$ by new constant symbols (and possibly new function symbols too). Taking reducts gives a map from models of $T^+$ to models of $T$. This map doesn’t change cardinality of models, respects isomorphism, and is surjective except possibly on the empty model. So on isomorphism classes of models of any nonzero cardinality $\kappa$, it induces a surjection, showing $I(T^+,\kappa) \geq I(T,\kappa)$.

(I am slightly worried I’m misunderstanding something in your terminology conventions, since this answer seems a bit too easy?)

$\endgroup$
  • 2
    $\begingroup$ If you look at some of the examples, like $n^2+n \to (n+1)^2$, it looks like constants are allowed to satisfy some relations, like "in between $\omega$ and $\omega^*$". But I don't know which relations are allowed. $\endgroup$ – Will Sawin Jun 23 '18 at 9:55
  • 3
    $\begingroup$ You are supposed to count the number of models of each completion of the expansion with constants. Otherwise the answer is trivial, indeed. $\endgroup$ – Emil Jeřábek supports Monica Jun 23 '18 at 10:10
  • $\begingroup$ @EmilJeřábek: Ah, thanks. Just to check where I’m misunderstanding the OP’s terminology, then: should “adding constants” be understood as “adding constants realising a specified complete type”, or is the completion of the theory implied by something else in what’s written? $\endgroup$ – Peter LeFanu Lumsdaine Jun 23 '18 at 10:36
  • 1
    $\begingroup$ Admittedly, it could be written more clearly, as the notation $T_{\bar a}$ is not defined. It is implicit in that $I(T,\kappa)$ is defined only for complete $T$ (and for incomplete $T$, it should presumably be defined as $\sup\{I(T',\kappa):T'\supseteq T\text{ complete}\}$). I guess a good way to think about it is that the operation of adding constants does not operate on theories, but on models: given a model $M$ and its expansion $(M,\bar a)$, what are the possible values of $I(\mathrm{Th}(M),\omega)$ vs. $I(\mathrm{Th}(M,\bar a),\omega)$. But I can’t speak for the OP. $\endgroup$ – Emil Jeřábek supports Monica Jun 23 '18 at 14:17
  • $\begingroup$ Yes sorry I mean completions of expansions by constants. Although, why does the definition of $I(T,\kappa)$ (number of models of $T$ of cardinality $\kappa$ up to isomorphism) not make sense for incomplete theories? $\endgroup$ – James Hanson Jun 23 '18 at 17:59

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.