# Countable structures, Ehrenfeucht strategies, and wadge reductions

Journal of Symbolic Logic 56 (4):1325-1348 (1991)

 Abstract For countable structures U and B, let $\mathfrak{U}\overset{\alpha}{\rightarrow}\mathfrak{B}$ abbreviate the statement that every Σ0 α (Lω1,ω) sentence true in U also holds in B. One can define a back and forth game between the structures U and B that determines whether $\mathfrak{U}\overset{\alpha}{\rightarrow}\mathfrak{B}$ . We verify that if θ is an Lω,ω sentence that is not equivalent to any Lω,ω Σ0 n sentence, then there are countably infinite models U and B such that $\mathfrak{U} \vDash \theta, \mathfrak{B} \vDash \neg \theta$ , and $\mathfrak{U}\overset{n}{\rightarrow}\mathfrak{B}$ . For countable languages L there is a natural way to view L structures with universe ω as a topological space, XL. Let [U] = {B ∈ XL∣B ≅ U} denote the isomorphism class of U. Let U and B be countably infinite nonisomorphic L structures, and let $C \subseteq \omega^\omega$ be any Π0 α subset. Our main result states that if $\mathfrak{U}\overset{\alpha}{\rightarrow}\mathfrak{B}$ , then there is a continuous function f: ωω → XL 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 α ≤ 3, the continuous function f can be defined from the $\overset{\alpha}{\rightarrow}$ relation Keywords No keywords specified (fix it) Categories Logic and Philosophy of Logic (categorize this paper) DOI 10.2307/2275478 Options Mark as duplicate Export citation Request removal from index

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 53,742

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)

## References found in this work BETA

Model Theory.Michael Makkai, C. C. Chang & H. J. Keisler - 1991 - Journal of Symbolic Logic 56 (3):1096.
Descriptive Set Theory.Yiannis Nicholas Moschovakis - 1982 - Studia Logica 41 (4):429-430.

## Citations of this work BETA

No citations found.

## Similar books and articles

Les Automorphismes d'Un Ensemble Fortement Minimal.Daniel Lascar - 1992 - Journal of Symbolic Logic 57 (1):238-251.
Limit Ultrapowers and Abstract Logics.Paolo Lipparini - 1987 - Journal of Symbolic Logic 52 (2):437-454.
On Some Small Cardinals for Boolean Algebras.Ralph Mckenzie & J. Donald Monk - 2004 - Journal of Symbolic Logic 69 (3):674-682.
On Scott and Karp Trees of Uncountable Models.Tapani Hyttinen & Jouko Väänänen - 1990 - Journal of Symbolic Logic 55 (3):897-908.