Interpreting infinite languages in graphs (for Vaught's conjecture)

117 Views Asked by At

Vaught's conjecture for first order theories (VC) in its original form states that every complete first order theory of a countable language has either at most countably many isomorphism classes of countable models or else continuum many.

Let $L:=\langle E \rangle$ be a first order language with the binary relation symbol $E$. In the book "The Descriptive Set Theory of Polish Group Actions" by H. Becker and A. Kechris theorem 6.1.3 claims that VC holds if and only if VC holds for $L$-theories of graphs.

The main idea behind this result is that every countable model of a countable language can be interpreted in a graph (seen as a $L$ structure) as demonstrated for example in section 5.5 of Wilfrid Hodges' book "Model Theory".

Let $S$ be an arbitrary countable relational language and $T_1$ a satisfiable $S$-theory. There is a $L$-formula $\phi_D(v_1)$ and a $L$-theory $T_2$ such that for every $L$-model $\mathcal{M}$ of $T_2$ we have $\mathcal{M}\models\exists v_1\phi_D(v_1)$. Furthermore, for each $k<\omega$ and each $k$-ary relation symbol $R$ of $S$ there is a $L$-formula $\psi_R(v_1,\dots ,v_k)$ such that for every model $\mathcal{M}$ of $T_2$ we can define a $S$ model $I(\mathcal{M})$ of $T_1$ in the following way:

1.) The universe of $I(\mathcal{M})$ is $\{a\in M\mid \mathcal{M}\models\phi_D(a)\}$.

2.) A $k$-ary relation symbol $R$ of $S$ is interpreted as $$ \{(a_1,\dots ,a_k)\in I(\mathcal{M})^k\mid \mathcal{M}\models\psi_R(a_1,\dots, a_k)\} $$ If $\mathcal{A}$ is a $S$-model of $T_1$ then we can define a model $\mathcal{M}$ of $T_2$ such that $I(\mathcal{M})\cong\mathcal{A}$.
In case $S$ is finite, VC for $S$-theories reduces to VC for $L$-theories because we can easily choose $T_2$ such that for all models $\mathcal{M}, \mathcal{M'}$ of $T_2$, we have $$\mathcal{M}\cong\mathcal{M'}\Leftrightarrow I(\mathcal{M})\cong I(\mathcal{M'}).$$

My problem is that I cannot define $T_2$ in such a way if the language $S$ is infinite. It can happen that $T_1$ has only countably many isomorphism classes while $T_2$ has continuum many. So my question is how can VC for $S$-theories be reduced to VC for $L$-theories if $S$ is infinite?

A possible approach I have been thinking about is to interpret $T_1$ in some other finite language $L_2$ thereby getting a theory $T_3$ which has the same number of isomorphism classes as $T_1$. Can someone help me with that? Thanks!

1

There are 1 best solutions below

0
On BEST ANSWER

By the way, the main idea to solve this problem, for those who are interested -apparently not too many- can be found here:

http://home.mathematik.uni-freiburg.de/ziegler/preprints/INTERPR.pdf