Countable Structures, Ehrenfeucht Strategies, and Wadge Reductions
Linton, Tom
J. Symbolic Logic, Tome 56 (1991) no. 1, p. 1325-1348 / Harvested from Project Euclid
For countable structures $\mathfrak{U}$ and $\mathfrak{B}$, let $\mathfrak{U}\overset{\alpha}{\rightarrow}\mathfrak{B}$ abbreviate the statement that every $\Sigma^0_\alpha (\mathbf{L}_{\omega_1,\omega})$ sentence true in $\mathfrak{U}$ also holds in $\mathfrak{B}$. One can define a back and forth game between the structures $\mathfrak{U}$ and $\mathfrak{B}$ that determines whether $\mathfrak{U}\overset{\alpha}{\rightarrow}\mathfrak{B}$. We verify that if $\theta$ is an $\mathbf{L}_{\omega,\omega}$ sentence that is not equivalent to any $\mathbf{L}_{\omega,\omega} \Sigma^0_n$ sentence, then there are countably infinite models $\mathfrak{U}$ and $\mathfrak{B}$ such that $\mathfrak{U} \vDash \theta, \mathfrak{B} \vDash \neg \theta$, and $\mathfrak{U}\overset{n}{\rightarrow}\mathfrak{B}$. For countable languages $\mathscr{L}$ there is a natural way to view $\mathscr{L}$ structures with universe $\omega$ as a topological space, $X_\mathscr{L}$. Let $\lbrack\mathfrak{U}\rbrack = \{\mathfrak{B} \in X_\mathscr{L}\mid\mathfrak{B} \cong \mathfrak{U}\}$ denote the isomorphism class of $\mathfrak{U}$. Let $\mathfrak{U}$ and $\mathfrak{B}$ be countably infinite nonisomorphic $\mathscr{L}$ structures, and let $C \subseteq \omega^\omega$ be any $\Pi^0_\alpha$ subset. Our main result states that if $\mathfrak{U}\overset{\alpha}{\rightarrow}\mathfrak{B}$, then there is a continuous function $f: \omega^\omega \rightarrow X_\mathscr{L}$ with the property that $x \in C \Rightarrow f(x) \in \lbrack\mathfrak{U}\rbrack$ and $x \notin C \Rightarrow f(x) \in \lbrack\mathfrak{B}\rbrack$. In fact, for $\alpha \leq 3$, the continuous function $f$ can be defined from the $\overset{\alpha}{\rightarrow}$ relation.
Publié le : 1991-12-14
Classification: 
@article{1183743818,
     author = {Linton, Tom},
     title = {Countable Structures, Ehrenfeucht Strategies, and Wadge Reductions},
     journal = {J. Symbolic Logic},
     volume = {56},
     number = {1},
     year = {1991},
     pages = { 1325-1348},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183743818}
}
Linton, Tom. Countable Structures, Ehrenfeucht Strategies, and Wadge Reductions. J. Symbolic Logic, Tome 56 (1991) no. 1, pp.  1325-1348. http://gdmltest.u-ga.fr/item/1183743818/