# Deciding whether a theory $T$ is $\aleph_0$-categorical?

I'm trying to solve the following exercise from my lecture notes:

1. For $$n ≥ 1$$, let $$L_n$$ be the language with $$n$$ unary predicate symbols $$P_1, . . . , P_n$$. Show there exists a theory $$T_n$$ asserting that each $$P_i$$ is infinite, the $$P_i$$ are disjoint ($$¬(∃x)(P_1(x)\wedge P_2(x))$$, etc.) and there are infinitely many elements not in any $$P_i$$, $$i ≤ n$$.
1. Show $$T_n$$ is $$ℵ_0$$-categorical. Conclude that $$T_n$$ is complete.
1. How many models of cardinality $$ℵ_1$$ (up to isomorphism) does $$T_2$$ have?
1. Let $$T = \bigcup_n T_n$$. Show that $$T$$ is a complete theory.
1. Is $$T$$ $$\aleph_0$$-categorical? If not how many countable models does $$T$$ have?

I've done everything apart from number 5.

It's easy to show that each $$T_n$$ is $$ℵ_0$$-categorical as in part 2, because if you have a countably infinite model, and each of the $$P_i$$ are infinite then they must also be countably infinite and you can take bijections between them. Moreover, if we take any countably infinite model to have domain $$A$$, then since $$A\backslash(P_1\cup ...\cup P_n)$$ is infinite this will also be countably infinite, and so you can take a bijection between these parts of any two countably infinite model. It's easy to check that the function defined on the domain of a whole model as the union of these bijections (which is well defined since the $$P_i$$ are disjoint) will be an isomorphism between any two countably infinite models, hence $$T_n$$ is $$ℵ_0$$-categorical.

I'm not sure if I can do the same in part 5 - each of the $$P_i$$ will still be countably infinite and so I could do the same thing for them, taking bijections between their interpretations under any two models. But I'm not sure if in this case the subset of the domain of a model not in any $$P_i$$ will still have to be infinite - there are infinitely many not in any finite selection of the $$P_i$$ because $$T$$ contains all the $$T_n$$, but I'm not convinced that means there will be infinitely many not in any of the $$P_i$$.

I'd really appreciate any advice you could offer - if the the subset of the domain of a model not in any $$P_i$$ will still have to be infinite, an explanation of why would be really helpful. If this might not be infinite, then I can see that presumably in this case there would be $$\aleph_0$$ countable models (up to isomorphism) as you could take a bijection between this subset of any possible size and use it to get an isomorphism as above, but I'm not sure how to show it might not be infinite - I can't think of an obvious counterexample.

Your intuition is absolutely correct; we can make the set $$M=\bigcup_{0 into an $$L$$-structure by realizing each $$P_i$$ as $$\{i\}\times\mathbb{Z}$$. This is a model of $$T$$; each $$P_i$$ is infinite, the $$P_i$$ are pairwise disjoint, and for any $$n\in\omega$$ there are infinitely many elements not in $$\bigcup_{0.
On the other hand, we can realize $$\{\star\}\cup M$$ as an $$L$$-superstructure of $$M$$ by asserting $$\star\notin P_i$$ for any $$0, and this will again be a model of $$T$$ for the same reasons as $$M$$. However, these two structures cannot be isomorphic, as one has an element not in any $$P_i$$ and the other does not. In fact there is no $$L$$-embedding at all from $$\{\star\}\cup M$$ to $$M$$, as there is nowhere to map $$\star$$ to.
In this way, there are indeed $$\aleph_0$$ countable models of $$T$$ up to isomorphism, with one unique model for any possible countable size of the complement of $$\bigcup_{0.