We introduce a reducibility preordering between classes of countable structures, each class containing only structures of a given similarity type (which is allowed to vary from class to class). Though we sometimes work in a slightly larger context, we are principally concerned with the case where each class is an invariant Borel class (i.e. the class of all models, with underlying set $= \omega$, of an $L_{\omega_1\omega}$ sentence; from this point of view, the reducibility can be thought of as a (...) (rather weak) sort of $L_{\omega_1\omega}$-interpretability notion). We prove a number of general results about this notion, but our main thrust is to situate various mathematically natural classes with respect to the preordering, most notably classes of algebraic structures such as groups and fields. (shrink)

We present two different types of models where, for certain singular cardinals λ of uncountable cofinality, λ → (λ,ω + 1) 2 , although λ is not a strong limit cardinal. We announce, here, and will present in a subsequent paper, [7], that, for example, consistently, $\aleph_{\omega_1} \nrightarrow (\aleph_{\omega_1}, \omega + 1)^2$ and consistently, 2 $^{\aleph_0} \nrightarrow (2^{\aleph_0},\omega + 1)^2$.

A fairly quotable special, but still representative, case of our main result is that for 2 ≤ n ≤ ω, there is a natural number m (n) such that, the following holds. Assume GCH: If $\lambda are regular, there is a cofinality preserving forcing extension in which 2 λ = μ and, for all $\sigma such that η +m(n)-1) ≤ μ, ((η +m(n)-1) ) σ ) → ((κ) σ ) η (1)n . This generalizes results of [3], Section 1, and (...) the forcing is a "many cardinals" version of the forcing there. (shrink)

Assuming 0 ♯ does not exist, we present a combinatorial approach to Jensen's method of coding by a real. The forcing uses combinatorial consequences of fine structure (including the Covering Lemma, in various guises), but makes no direct appeal to fine structure itself.

We lay the combinatorial foundations for [5] by setting up and proving the essential properties of the coding apparatus for singular cardinals. We also prove another result concerning the coding apparatus for inaccessible cardinals.