Question Regrading Proof Of Ryll-Nardzewski Theorem of Model Theory.

Question

I have the a problem understanding the proof given by Tent and Ziegler. It states that a countable theory $T$ is $\aleph_0$ categorical if and only if for every $n \in \mathbb{N}$ there is a finte number of formulas, up to equivalence, relative to $T$. Nevertheless I have a problem understanding what does it precisely mean by "finte number of formulas, up to equivalence, relative to $T$". Does this means that for each $n \in \mathbb{N}$ there is a set $\{\varphi_i\}_{i < \omega}$ such that for every $L$-formula $\varphi$ with $n$ free variables, there is a $j < \omega$ such that $T \models \forall \bar{x}(\varphi(\bar{x} \leftrightarrow \varphi_j(\bar{x}))$ and for all $i \neq j$ $T \models \forall \bar{x}(\varphi_i(\bar{x} \leftrightarrow \varphi_j(\bar{x}))$. Or does it simply mean that there is a set $\{\varphi_i\}_{i < \omega}$ such that $i \neq j$ $T \models \forall \bar{x}(\varphi_i(\bar{x} \leftrightarrow \varphi_j(\bar{x}))$. I would be very grateful if someone could completely clarify this matter. Thanks.

Answer 1

It means that for each $n$, there is a finite set of formulas $\{\varphi_1, \ldots, \varphi_m\}$ such that for any formula $\varphi,$ there is an $i\in\{1,\ldots, m\}$ such that $$ T\vdash \forall x_1\ldots \forall x_n (\varphi(x_1,\ldots, x_n)\leftrightarrow \varphi_i(x_1,\ldots, x_n))$$

(In all cases 'formula' means formula in the language $L$, i.e. without parameters, with free variables amongst $x_1,\ldots, x_n$. Note that $m$ may depend on $n$, so e.g. there does not need to be a uniform bound over all $n$ for the number of inequivalent formulas in $n$ variables, it just needs to be finite for each $n$.)

---

Another way to look at it is that for each $n$, there are only finitely many sets of tuples $(a_1,\ldots, a_n)$ definable without parameters in any model of $T.$ For a concrete example, for a model $(\mathcal M,<)$ of the countably categorical theory of dense linear orderings without endpoints, the only definable sets of elements are $\emptyset$ and $M$ and the only definable sets of ordered pairs are $\{(x,y): x>y\},$ $\{(x,y): y < x\},$ $\{(x,y): x\ge y\},$ $\{(x,y): y \le x\},$ $\{(x,y): x=y\},$ $\{(x,y): x\ne y\}$, $\emptyset,$ and $M^2$. (And so on for larger $n$... the only manner in which DLOWE can distinguish tuples $(a_1,\ldots, a_n)$ is in the finitely many possibilities for how $a_1,\ldots, a_n$ are ordered.)

On the other hand, if we consider the theory of discrete linear orders without endpoints (i.e. $Th(\mathbb Z,<)$), which is not countably categorical, again the only definable sets of elements are $M$ and $\emptyset,$ but for $n=2,$ we can consider the set of pairs $(x,y)$ that are distance $1$ apart, the set of pairs that are distance $2$ apart, and so on for each natural-number distance, so we have an infinite number of definable sets of ordered pairs.