This paper addresses the structures (M, ω) and (ω, SSy(M)), where M is a nonstandard model of PA and ω is the standard cut. It is known that (ω, SSy(M)) is interpretable in (M, ω). Our main technical result is that there is an reverse interpretation of (M, ω) in (ω, SSy(M)) which is ‘local’ in the sense of Visser [11]. We also relate the model theory of (M, ω) to the study of transplendent models of PA [2].

This yields a number of model theoretic results concerning the ω-models (M, ω) and their standard systems SSy(M, ω), including the following.

• $\left( {M,\omega } \right) \prec \left( {K,\omega } \right)$ if and only if $M \prec K$ and $\left( {\omega ,{\rm{SSy}}\left( M \right)} \right) \prec \left( {\omega ,{\rm{SSy}}\left( K \right)} \right)$.

• $\left( {\omega ,{\rm{SSy}}\left( M \right)} \right) \prec \left( {\omega ,{\cal P}\left( \omega \right)} \right)$ if and only if $\left( {M,\omega } \right) \prec \left( {{M^{\rm{*}}},\omega } \right)$ for some ω-saturated M*.

• $M{ \prec _{\rm{e}}}K$ implies SSy(M, ω) = SSy(K, ω), but cofinal extensions do not necessarily preserve standard system in this sense.

• SSy(M, ω)=SSy(M) if and only if (ω, SSy(M)) satisfies the full comprehension scheme.

• If SSy(M, ω) is uniformly defined by a single formula (analogous to a β function), then (ω, SSy(M, ω)) satisfies the full comprehension scheme; and there are models M for which SSy(M, ω) is not uniformly defined in this sense.

Assume ZF + AD + V = L(ℝ) and let κ < Θ be an uncountable cardinal. We show that κ is Jónsson, and that if cof (κ) = ω then κ is Rowbottom. We also establish some other partition properties.

Péter Gács showed (Gács 1974) that for every n there exists a bit string x of length n whose plain complexity C(x) has almost maximal conditional complexity relative to x, i.e., $C\left( {C\left( x \right)|x} \right) \ge {\rm{log}}n - {\rm{log}}^{\left( 2 \right)} n - O\left( 1 \right)$ (Here ${\rm{log}}^{\left( 2 \right)} i = {\rm{loglog}}i$.) Following Elena Kalinina (Kalinina 2011), we provide a simple game-based proof of this result; modifying her argument, we get a better (and tight) bound ${\rm{log}}n - O\left( 1 \right)$ We also show the same bound for prefix-free complexity.

Robert Solovay showed (Solovay 1975) that infinitely many strings x have maximal plain complexity but not maximal prefix complexity (among the strings of the same length): for some c there exist infinitely many x such that $|x| - C\left( x \right) \le c$ and $|x| + K\left( {|x|} \right) - K\left( x \right) \ge {\rm{log}}^{\left( 2 \right)} |x| - c{\rm{log}}^{\left( 3 \right)} |x|$ In fact, the results of Solovay and Gács are closely related. Using the result above, we provide a short proof for Solovay’s result. We also generalize it by showing that for some c and for all n there are strings x of length n with $n - C\left( x \right) \le c$ and $n + K\left( n \right) - K\left( x \right) \ge K\left( {K\left( n \right)|n} \right) - 3K\left( {K\left( {K\left( n \right)|n} \right)|n} \right) - c.$ We also prove a close upper bound $K\left( {K\left( n \right)|n} \right) + O\left( 1 \right)$

Finally, we provide a direct game proof for Joseph Miller’s generalization (Miller 2006) of the same Solovay’s theorem: if a co-enumerable set (a set with c.e. complement) contains for every length a string of this length, then it contains infinitely many strings x such that$|x| + K\left( {|x|} \right) - K\left( x \right) \ge {\rm{log}}^{\left( 2 \right)} |x| - O\left( {{\rm{log}}^{\left( 3 \right)} |x|} \right).$

We prove two results about generically stable types p in arbitrary theories. The first, on existence of strong germs, generalizes results from [2] on stably dominated types. The second is an equivalence of forking and dividing, assuming generic stability of p(m) for all m. We use the latter result to answer in full generality a question posed by Hasson and Onshuus: If P(x) ε S(B) is stable and does not fork over A then prestrictionA is stable. (They had solved some special cases.)

We study the relative complexity of equivalence relations and preorders from computability theory and complexity theory. Given binary relations R, S, a componentwise reducibility is defined by

R ≤ S ⇔ ∃f ∀x, y [x R y ↔ f (x) S f (y)].

Here, f is taken from a suitable class of effective functions. For us the relations will be on natural numbers, and f must be computable. We show that there is a ${\rm{\Pi }}_1^0$-complete equivalence relation, but no ${\rm{\Pi }}_k^0$-complete for k ≥ 2. We show that ${\rm{\Sigma }}_k^0$ preorders arising naturally in the above-mentioned areas are ${\rm{\Sigma }}_k^0$-complete. This includes polynomial time m-reducibility on exponential time sets, which is ${\rm{\Sigma }}_2^0$, almost inclusion on r.e. sets, which is ${\rm{\Sigma }}_3^0$, and Turing reducibility on r.e. sets, which is ${\rm{\Sigma }}_4^0$.

We show that no nontrivial principal ideal of the enumeration degrees is linearly ordered: in fact, below every nonzero enumeration degree one can embed every countable partial order. The result can be relativized above any total degree: if a,b are enumeration degrees, with a total, and a < b, then in the degree interval (a,b), one can embed every countable partial order.

Assume G is a group definable in a model M of a stable theory T. We prove that the semigroup SG (M) of complete G-types over M is an inverse limit of some semigroups type-definable in Meq. We prove that the maximal subgroups of SG (M) are inverse limits of some definable quotients of subgroups of G. We consider the powers of types in the semigroup SG (M) and prove that in a way every type in SG (M) is profinitely many steps away from a type in a subgroup of SG (M).

We characterize the ω-stable theories all of whose countable models admit decidable presentations. In particular, we show that for a countable ω-stable T, every countable model of T admits a decidable presentation if and only if all n-types in T are recursive and T has only countably many countable models. We further characterize the decidable models of ω-stable theories with countably many countable models as those which realize only recursive types.

Define a second order tree to be a map between trees (with fixed codomain). We show that many properties of ordinary trees have analogs for second order trees. In particular, we show that there is a notion of “definition by recursion on a well-founded second order tree” which generalizes “definition by transfinite recursion”. We then use this new notion of definition by recursion to prove an analog of Lusin’s Separation theorem for closure spaces of global sections of a second order tree.

An inaccessible cardinal is strongly compact if, and only if, it satisfies thestrong tree property. We prove that if there is a model of ZFC with infinitelymany supercompact cardinals, then there is a model of ZFC where ${\aleph _{\omega + 1}}$ has the strong tree property. Moreover, we prove that everysuccessor of a singular limit of strongly compact cardinals has the strong treeproperty.

Following the topic of the book Canonical Ramsey Theory on Polish Spaces by V. Kanovei, M. Sabok, and J. Zapletal we study Borel equivalences on Laver trees. We prove that equivalence relations Borel reducible to an equivalence relation on 2ω given by some FσP-ideal on ω can be canonized to the full equivalence relation or to the identity relation.

This has several consequences, e.g., Silver type dichotomy for the Laver ideal and equivalences Borel reducible to equivalence relations given by FσP-ideals.

We study the expressive power of independence-friendly quantifier prefixes composed of universal $\left( {\forall x/X} \right)$, existential $\left( {\exists x/X} \right)$, and majority quantifiers $\left( {Mx/X} \right)$. We provide four quantifier prefixes that can express NP hard properties and show that all quantifier prefixes capable of expressing NP-hard properties embed at least one of these four quantifier prefixes. As for the quantifier prefixes that do not embed any of these four quantifier prefixes, we show that they are equivalent to a first-order quantifier prefix composed of $\forall x$, $\exists x$, and Mx. In unison, our results imply a dichotomy result: every independence-friendly quantifier prefix is either decidable in LOGSPACE or NP hard.

We consider the arithmetic complexity of index sets of uniformly computably enumerable families learnable under different learning criteria. We determine the exact complexity of these sets for the standard notions of finite learning, learning in the limit, behaviorally correct learning and anomalous learning in the limit. In proving the ${\rm{\Sigma }}_5^0$-completeness result for behaviorally correct learning we prove a result of independent interest; if a uniformly computably enumerable family is not learnable, then for any computable learner there is a ${\rm{\Delta }}_2^0$ enumeration witnessing failure.

It is well known that saturation of ideals is closely related to the “antichain-catching” phenomenon from Foreman–Magidor–Shelah [10]. We consider several antichain-catching properties that are weaker than saturation, and prove:

1. (1) If ${\cal I}$ is a normal ideal on $\omega _2 $ which satisfies stationary antichain catching, then there is an inner model with a Woodin cardinal;

2. (2) For any $n \in \omega $, it is consistent relative to large cardinals that there is a normal ideal ${\cal I}$ on $\omega _n $ which satisfies projective antichain catching, yet ${\cal I}$ is not saturated (or even strong). This provides a negative answer to Open Question number 13 from Foreman’s chapter in the Handbook of Set Theory ([7]).

Hirsch and Hodkinson proved, for $3 \le m < \omega $ and any $k < \omega $, that the class $SNr_m {\bf{CA}}_{m + k + 1} $ is strictly contained in $SNr_m {\bf{CA}}_{m + k} $ and if $k \ge 1$ then the former class cannot be defined by any finite set offirst-order formulas, within the latter class. We generalize this result to thefollowing algebras of m-ary relations for which the neat reductoperator $_m $ is meaningful: polyadic algebras with or without equality andsubstitution algebras. We also generalize this result to allow the case wherem is an infinite ordinal, using quasipolyadic algebras inplace of polyadic algebras (with or without equality).

In recent years, much work in descriptive set theory has been focused on the Borel complexity of naturally occurring classification problems, in particular, the study of countable Borel equivalence relations and their structure under the quasi-order of Borel reducibility. Following the approach of Louveau and Rosendal for the study of analytic equivalence relations, we study countable Borel quasi-orders.

In this paper we are concerned with universal countable Borel quasi-orders, i.e., countable Borel quasi-orders above all other countable Borel quasi-orders with regard to Borel reducibility. We first establish that there is a universal countable Borel quasi-order, and then establish that several countable Borel quasi-orders are universal. An important example is an embeddability relation on descriptive set theoretic trees.

Our main result states that embeddability of finitely generated groups is a universal countable Borel quasi-order, answering a question of Louveau and Rosendal. This immediately implies that biembeddability of finitely generated groups is a universal countable Borel equivalence relation. The same techniques are also used to show that embeddability of countable groups is a universal analytic quasi-order.

Finally, we show that, up to Borel bireducibility, there are ${2^{{\aleph _0}}}$ distinct countable Borel quasi-orders, which symmetrize to a universal countable Borel equivalence relation.

Criteria are obtained for a filter ${\cal F}$ of subsets of a set I to be an intersection of finitely many ultrafilters, respectively, finitely many κ-complete ultrafilters for a given uncountable cardinal $\kappa .$ From these, general results are deduced concerning homomorphisms on infinite direct product groups, which yield quick proofs of some results in the literature: the Łoś–Eda theorem (characterizing homomorphisms from a not-necessarily-countable direct product of modules to a slender module), and some results of Nahlus and the author on homomorphisms on infinite direct products of not-necessarily-associative k-algebras. The same tools allow other results of Nahlus and the author to be nontrivially strengthened, and yield an analog to one of their results, with nonabelian groups taking the place of k-algebras.

We briefly examine the question of how the common technique used in applying the general results of this note to k-algebras on the one hand, and to nonabelian groups on the other, might be extended to more general varieties of algebras in the sense of universal algebra.

In a final section, the Erdős–Kaplansky theorem on dimensions of vector spaces ${D^I}$$(D$ a division ring) is extended to reduced products ${D^I}/{\cal F},$ and an application is noted.

The main result of this paper is a combinatorial characterization of Magidor-generic sequences. Using this characterization, I show that the critical sequences of certain iterations are Magidor-generic over the target model. I then employ these results in order to analyze which other Magidor sequences exist in a Magidor extension. One result in this direction is that if we temporarily identify Magidor sequences with their ranges, then Magidor sequences are maximal, in the sense that they contain any other Magidor sequence that is present in their forcing extension, even if the other sequence is generic for a different Magidor forcing. A stronger result holds if both sequences come from the same forcing: I show that a Magidor sequence is almost unique in its forcing extension, in the sense that any other sequence generic for the same forcing which is present in the same forcing extension coincides with the original sequence at all but finitely many coordinates, and at all limit coordinates. Further, I ask the question: If d ε V[c], where c and d are Magidor-generic over V, then which Magidor forcing can d be generic for? It turns out that it must essentially be a collapsed version of the Magidor forcing for which c was generic. I treat several related questions as well. Finally, I introduce a special case of Magidor forcing which I call minimal Magidor forcing. This approach simplifies the forcing, and I prove that it doesn’t restrict the class of possible Magidor sequences. That is, if c is generic for a Magidor forcing over V, then it is generic for a minimal Magidor forcing over V.